簡単な硬貨問題 from IT速報

Project Eulerをブログ用に解いていると、

1. 答えを出す 2.高速化 3.コードの美化

の順番でかなり書き直しが必要なので、ただ単に解き散らかすのに比べてべらぼうに時間がかかる。

息抜きにIT速報を見ていたら、タイムリーなことに硬貨関連の問題が出ていた。

blog.livedoor.jp

ある金額に対して額の大きい硬貨をできるだけ多く使った場合、各硬貨の使用数はいくつになるかという問い。Project Eulerに比べるとべらぼうに簡単だが、ちょっと解いてみたい。

Pythonだと本当に簡単だが、Clojureで解くとなるとパッと思いつくのは再帰を使う方法とreduceを使う方法である。

とりあえずどちらのアルゴリズムにも共通の硬貨のタイプと、戻り値を出力するための関数を定義しておく。やはり関数型言語だし、計算ロジックと副作用は分割しておきたい。手続き型でもなるべくそうすべきだけど。

(def coins [500 100 50 10 5 1])

(defn print-coins [coin-count]
  (dorun
    (map #(println 
            (str %1 "円玉：" %2 "枚"))
         coins coin-count)))

完全に副作用目的のmapなので、dorunは忘れずに・・・　引数が一つだけだったらforを使っていたところだが、リスト二つから1個ずつ要素を受け取って出力するのにはmapの方が綺麗に書ける。

まずは再帰：

(defn get-coins-recursive
  ([n] (get-coins-recursive n coins))
  ([n coins]
   (if (not-empty coins)
     (let [coin (first coins)]
       (cons (quot n coin)
         (get-coins-recursive (rem n coin) (rest coins)))))))

硬貨のリストの大きさがStack Overflowを引き起こすには程遠いレベルで定まっているのでtail recursionはなし。素直に再帰的に書くとこんな感じだろう。

loop/recurだとコードがゴツくなるのでできれば避けたい。lazy-seqは使っても良かったけど。

reduceだとこんな感じ：

(defn get-coins-reduce [n]
  (letfn [(f [[counts r] coin]
             [(conj counts (quot r coin)) (rem r coin)])]
    (first
      (reduce f [[] n] coins))))

reduceに使う関数の第一引数が[商のvector、余のint]で第二引数が次に余を割るためのコインの値。戻り値も[商のvector、余のint]。

個人的にはこっちの方が好き。できればfにちゃんと名前をつけて、letfnじゃなくて独立した関数にしたい。インナー関数であるのが適当だとは思うんだけど、letfnだとやっぱり読みにくい気がする。

ちなみにここで悪魔の囁き：

「商のリストと余の両方をreduceで回そうとするからロジックが複雑になるんだよ。

商のリストは作成せずにreduce用の関数内副作用で表示してしまえ」

それがこのコード。

(defn f2 [n coin]
  (println (str coin "円玉：" (quot n coin) "枚"))
  (rem n coin))

(defn get-and-print-coins [n]
  (reduce f2 n coins) nil)

確かにずっと簡単だが、その後の仕様変更やら再利用やらにはよろしくない。

続く