problem-8.clj

;;; Project Euler #8
;;; http://projecteuler.net/problem=8
;;; http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%208

(use 'clojure.test)

(def input
  (str
    "73167176531330624919225119674426574742355349194934"
    "96983520312774506326239578318016984801869478851843"
    "85861560789112949495459501737958331952853208805511"
    "12540698747158523863050715693290963295227443043557"
    "66896648950445244523161731856403098711121722383113"
    "62229893423380308135336276614282806444486645238749"
    "30358907296290491560440772390713810515859307960866"
    "70172427121883998797908792274921901699720888093776"
    "65727333001053367881220235421809751254540594752243"
    "52584907711670556013604839586446706324415722155397"
    "53697817977846174064955149290862569321978468622482"
    "83972241375657056057490261407972968652414535100474"
    "82166370484403199890008895243450658541227588666881"
    "16427171479924442928230863465674813919123162824586"
    "17866458359124566529476545682848912883142607690042"
    "24219022671055626321111109370544217506941658960408"
    "07198403850962455444362981230987879927244284909188"
    "84580156166097919133875499200524063689912560717606"
    "05886116467109405077541002256983155200055935729725"
    "71636269561882670428252483600823257530420752963450"))

(defn char->int
  [c]
  (Integer/parseInt (str c)))

(defn string->int-seq
  [s]
  (map char->int s))

(defn problem-8
  ([] (problem-8 input))
  ([s] (->>
         (string->int-seq s)
         (partition 5 1)
         (map #(apply * %))
         (reduce max 0))))

(is (= (char->int \0) 0))
(is (= (char->int \9) 9))

(is (= (string->int-seq "1") [1]))
(is (= (string->int-seq "12345") [1 2 3 4 5]))

(is (= (problem-8 "123789") 3024))
(is (= (problem-8) 40824))

解説

文字列を数値のシーケンスに変換し、5つずつに分割し、それぞれの積を求め、より大きいものを選び出す。素直な解法を選択したつもり。

string->int-seq

文字列から数値のシーケンスって関数ありそうだけど、見つけられなかった。(map int s)とかやるとintがcharのコード値を返してしまう。

partition

partitionを知っていれば楽になる、と思う。partitionの動作はこんな感じ。

(is (= (partition 3 1 [1 2 3 4 5]) '((1 2 3) (2 3 4) (3 4 5))))

(reduce max 0)

(reduce max 0)が(reduce max) でないのは... ( デジャヴ )

• reduceの引数が2つのとき、動作が分かりづらい(私見)。
• 負の数の入力はできないので、積は最低でも0。
• 5文字未満などの場合に例外を投げずに0を返せる。(仕様としての良し悪しの判断はお任せします)

maxは引数1つでも動作するので、5文字未満が渡されない前提なら(reduce max)で良いです。

以上。

partitionエレガントですね。私はこんな風にハードコーディングしてしまっていたので、きれいな解が大変参考になります。

(map * s (drop 1 s) (drop 2 s) (drop 3 s) (drop 4 s))

あと、最初partitionの名前だけ見て、filterとremoveを両方やってくれる関数だと早とちりしました。

👍

partition 使わない解答を考えるほうが難しい．

👍 これ以上ない模範解答と思います.

• map, reduce の使い方 (clojure に限らない)
• partition の使い方
• ->> の使い方
• defn における引数の数によるオーバーロード

など, 頻出要素が, まさに「そうやって使うためのもの」として綺麗に使われいて, お手本になります.

さらに, char->int や string->int-seq など汎用部分を分かりやすく分離し, 簡潔で十分と思われるテストを書いているところもお手本にしたいです.
私は, 全部ぐちゃぐちゃっと一個の関数の中にいれてしまうことが多いので, 反省.

char->int 相当の処理は良く出てきますが, #(- (int %) (int \0)) という, ASCII に依存した C コードみたいなの書いてました. こちらも反省.

partition使わないやりかたっていうことで、つっこみどころ満載ではありますが、僕が最初に解いたときの回答ルーチンです。

(loop [tgt-num-list (rest target-num-list)
       result-list (list (reduce * (take 5 target-num-list))
                         (take 5 target-num-list))]
  (if (> 5 (count tgt-num-list))
    result-list
    (let [next-5 (take 5 tgt-num-list)
          product-of-5 (reduce * next-5)]
      (if (< product-of-5 (first result-list))
        (recur (next tgt-num-list) result-list)
        (recur (next tgt-num-list) (list product-of-5 next-5))))))

文字列をリストにして、nextlで減らしながら、時々に5つ取って計算してます。

char->int 相当の処理は良く出てきますが, #(- (int %) (int \0)) という, ASCII に依存した C コードみたいなの書いてました. こちらも反省.

真面目にやるなら #(Character/digit (char %) 10) なんでしょうけど，私は面倒臭がりなのと貧乏性なのとで，残念なことに，いつも #(- (int %) 48) です．

#(Character/digit (char %) 10)

Character/digit 探してた動作のメソッドですね。良い方法が浮かばなかったので、char->int は適当にやっちゃいました。

#(Character/digit (char %) 10) は #(Character/digit ^char % 10) のほうがよかったかもしれません．ついさっきまで ^char を type hinting に使えることに気づいていませんでした．

Clojure は文字列も(文字の)シーケンスとして扱えるのがよいですね。
文字列を分配束縛できることを知った時は、軽い衝撃を受けた覚えがあります。(シーケンスなので当然の動作なのですが)

---

char->int 相当の処理は、僕も @bouzuya さんと同じ方法で行なっていましたが、
@tnoda さんの提示した、#(Character/digit (char %) 10), #(Character/digit ^char % 10) というコードの方が良いと思うので、次からはそちらを使おうと思います。
やはり、Clojure を有効に使うには Java API の知識が必要になりますね……。

やはり、Clojure を有効に使うには Java API の知識が必要になりますね……。

そうですね．といっても，Project Euler を解くだけであれば，Clojure の基本型にもなっている Long, Double, Character と String. それに Math といった java.lang のごくごく一部の知識があれば十分です．

今，Java API の知識が必要になるもの = clojure.jar で提供されていないものを思いつきで列挙してみます．

• Mutable なデータ型
• プリミティブ型のラッパクラス
  • (java.lang (Long Double Character))
• 文字列操作
  • java.lang.String
• 数学関数
  • java.lang.Math
• 実行環境へのアクセス
  • java.lang.System
• 低レベルの I/O
  • java.io

などなど結構ありますね．

最初に戻って，「有効」というのがどの程度なのかにもよるのですが，

• 速く・効率のよいプログラムを書く
• コード量を減らす

という目的であれば，Java interop は必須かと思います．Java interop が無い Clojure は，言語仕様だけを見ていると末尾呼出最適化も継続も無い劣化 Scheme のように思えてしまいます．しかし，Clojure は Java を書けたり Java の豊富なライブラリを使えたりすので，プロダクションコードを書こうとする分にはその欠点を自覚することはありません．むしろ，Java interop があるおかげで，実績のあるライブラリを使うことでバグが減ったり，コーディングに使う時間を減らせる分十分に設計を検討できたり，と非 JVM 言語にはない恩恵を受けられます．Scheme や CL から来た人や理論派の人が Clojure を触ると何か物足りないと思い，Java で実践的に開発しているプログラマが Clojure を触ると何かいいなと思うのも，このあたりに理由があると考えています．