§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]