Problem

How to design 3 kinds of postage stamps so that they can cover from 1 to 15 unit with up to 3 postage stamps per letter?

Solution

The answer is not obvious to me, so I resorted to brute-force. The generation of all combinations is the most interesting part, especially the contrast between list comprehension and list monad.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import Data.List
import Control.Monad

solution :: [Int]
solution = head $ do
x <- [1..15]
y <- [1..x-1]
z <- [1..y-1]
guard $ [1..15] == normalized [x, y, z]
return [x, y, z]

where
normalized list =
take 15 . sort . nub $ candidates
where
candidates = all_combination list
-- candidates = all_combination' list

all_combination :: [Int] -> [Int]
all_combination list =
concat $
[ []
, [e1 | e1 <- list]
, [e1 + e2 | e1 <- list, e2 <- list]
, [e1 + e2 + e3 | e1 <- list, e2 <- list, e3 <- list]
]

all_combination' :: [Int] -> [Int]
all_combination' list = do
i <- [1..3]
loop i 0
where
loop 0 acc = return acc
loop n acc = do
x <- list
loop (n-1) $ x+acc

main = do
print solution
-- [5,4,1]