Haskell/Clojureで数学パズル：コインの両替

いやあ「プログラマ脳を鍛える数学パズル」楽しいですわ。 まだ5問しかやっていないけど、Clojure/Haskell両方で解いているので、一粒で二度美味しい。 しかも、解説は違う視点の解法を示してくれるので、３度も４度も美味しい感じだ。

5問目は、お金の両替問題で、これシンプルだけど奥が深い。 1000円を10円、50円、100円、500円に両替する。同じコインは何枚使ってもいいが、最大コイン数は15枚。 この時の両替パターン数を求める。

名著SICPにも内容が少し違う両替問題が出ていて、再帰の威力を見せつけられたな。

さて、この問題、まず最初にぱっと思いつく方法は、ベタに組み合わせと条件判定。

Haskellの回答例は、

change_coin :: Int -> Int -> Int
change_coin money max_coins = 
    sum [1 | m10 <- [0..max_coins],
             m50 <- [0..max_coins],
             m100 <- [0..max_coins],
             m500 <- [0..max_coins],
             m10 + m50 + m100 + m500 <= max_coins,
             money == (10*m10 + 50*m50 + 100*m100 + 500*m500)]

main :: IO ()
main = do print $ change_coin 1000 15 

リスト内包表記、便利で簡潔で美しいですわ。

似た簡潔さでClojureも書ける。for文を使う。

(defn change_coin [money max_coins]
  (reduce +
          (for [m10 (range 0 (inc max_coins))
                m50 (range 0 (inc max_coins))
                m100 (range 0 (inc max_coins))
                m500 (range 0 (inc max_coins))
                :when (and (<= (+ m10 m50 m100 m500) max_coins)
                           (= money (+ (* 10 m10)
                                       (* 50 m50)
                                       (* 100 m100)
                                       (* 500 m500))))
                ]
            1)))

(println (change_coin 1000 15))

少しだけ考えて、再帰を使って汎用的な関数を作ってみる。

Haskell版：

change_coin :: Int -> [Int] -> Int -> Int
change_coin 0 _ _ = 1
change_coin _ _ 0 = 0
change_coin _ [] _ = 0
change_coin money (x:xs) max_coins
    = sum [ change_coin (money - x * use) xs (max_coins - use)
            | use <- [0..max_coins]]

main :: IO ()
main = do print $ change_coin 1000 [10,50,100,500] 15

考え方としては、使うコインのリスト[10,50,100,500]を与えて、前からコインを取り出して、 (この場合だとまずは10円）

• コインを0枚使う → 1000-0 に対して残ったコインで両替する
• コインを1枚使う → 1000-10 に対して残ったコインで両替する
• ・・・
• コインを15枚使う → 1000-10*15 に対して残ったコインで両替する

というのを再帰でやる。（まあ15枚使ったら、もう終わりだけどね） 最後に残金が０なら、うまく換金できたので１を返し、 それ以外でコインのリストが空になったり、最大コイン数使ったら０を返す。

Clojureも同じように組める。

(defn change_coin_patterns [money coins max-coins]
  (cond (zero? money) 1
        (empty? coins) 0
        (zero? max-coins) 0
        :else (reduce + 
                      (for [uses (range 0 (inc max-coins))]
                        (change_coin_patterns (- money (* uses (first coins)))
                                              (rest coins)
                                              (- max-coins uses))))))

(println (change_coin_patterns 1000 [10 50 100 500] 15))

Haskellだとパターンマッチングを使った記述がビューティフル。