Project Euler Problem 16 solution in Clojure

pe-16.clj

;;;; Project Euler Problem 16 solution
;;;; http://projecteuler.net/problem=16

(use 'clojure.test)
(import 'java.math.BigInteger)

;; Character/digit usage from: https://gist.github.com/4276901
(def solve
  (comp (partial apply +)
        (partial map #(Character/digit ^char % 10))
        str
        #(. (BigInteger. "2") pow %)
        ;; no reflection warnings at this method call. really?
        ;; cf. #(. % pow %2) => reflection warning "call to pow can't be resolved."
        ))

(is (= 26 (solve 15)))
(is (= 1366 (solve 1000)))

解答過程での疑問とか調査とか 参考になります.
疑問に思われているあたり, 私も明るくないのでどなたかの追加情報を待ちたいと思います.

累乗 Problem 5 で少し話題に上がった math.numeric-tower の expt でも良いかもしれません.
私は @plaster さんとまったく同じ方法ですが, 一応定義を外に出して
(defn expt [n m] (apply * (repeat m n)))
としてこれを使っていました.

本体 ポイントフリーいいですね. 👍
ポイント有り (ポイントフリーの反意語って何だろう?) で書くと

(defn solve [n]
  (->> n
    (#(apply * (repeat % 2N)))           ; 2 のべき乗を求めて
    str                                  ; 10進の文字列に変換し
    (map #(Character/digit ^char % 10))  ; 各文字を数値に変換して
    (apply +)))                          ; 和を求める

ということで素直な解法と思います.

別解です。
僕としては、これが普通の解きかたではないかと思っています。

1桁ずつの値を取るのに、10で割った余りを使います。そして、再帰の rest のところで、quot を使うイメージです。

(require '[clojure.math.numeric-tower :as math])

(loop [num (math/expt 2 1000)
       result 0]
  (if (< num 1)
    result
    (recur (quot num 10)
           (+ result (rem num 10)))))

普段あまりClojureの深いところのことを考えていなくて、まして、リフレクションとか考えてないので、解説参考になります。特に、print関連はgood。

@plaster 詳細なレポートありがとうございます．*print-readably* 知りませんでした．また，isDynamic も初めて見ました．(and (var? #'foo) (.isDynamic #'foo)) で変数かどうか調べられそうですね．まだまだ知らないことが多いので勉強になります．#mitori_clj は毎日が発見です．

ところで，問題の解答について私も @plaster の解き方で書いていたのですが，@kohyama の遅延シーケンスを使ったフィボナッチ数列 を見てから lazy-seq で書くのにはまってしまい，次のような解答を書きました．

(ns tnoda.projecteuler.problem-16
  (:use [clojure.test :only [is]]))

(defn- digits*
  [x]
  (if (pos? x)
    (lazy-seq
      (cons (rem x 10) (digits* (quot x 10))))))

(def ^:private digits (comp reverse digits*))

(defn- solver*
  [n]
  (->> (.pow (BigInteger. "2") n)
       digits
       (apply +)))

(def solver (partial solver* 1000))

(is (= 26 (solver* 15)))

digits* の lazy-seq は無くてもこのケースでは問題ないのですが，lazy-seq が無ければ，大きな桁数のときにスタックオーバーフローするのでつけてみました．読み易さ的には @plaster の解答のほうが上なので，あくまでもネタ解答の域を出ませんが，練習として書いてみました．考え方は @ypsilon-takai の

1桁ずつの値を取るのに、10で割った余りを使います。そして、再帰の rest のところで、quot を使うイメージです。

と同じです．

余談ですが，私は @plaster の Java のメソッドを使うスタイルが好きです．具体的には #(. (BigInteger. "2") pow %) のところです．Java 臭がすると Clojure っぽく見えないかもしれませんが，既存の Java の知識を活用できるというのは嬉しいものです．

@ypsilon-takai さん
「文字列化すれば文字のシーケンスが手に入るので...」という方法でなく, 数値のまま処理するとすれば, 御解答は模範的ですね.
言われてみればその方が普通のような気がします.

@tnoda さん
同じく lazy-seq 版, いいですね.
個人的に遅延評価と再帰で書くのは好きです.

目的は和なので reverse しなくても良いのですが, ヘルパー関数 digits として外に出したので, 少し汎用的に上の桁から順に返すようにしたのだと推測します.
digits* の「下の桁から一桁ずつの数値のシーケンスを返す関数」という仕様を, 名前や doc-string やコメントで, 伝える工夫をして reverse はしないというのもありかもしれません.

局所性の高い名前は defn- や def ^:private を使って, 名前空間の外に export されないようにする, というのは良い習慣ですね.
見習いたいです.

@ypsilon-takai さんの指摘どおり、この問題なら数値のまま解くのが自然ですね。文字列化するにも内部的にはmodとquotしてるでしょうから、実行効率もよさそうな気がします。

@tnoda さんの lazy-seq わかりやすくて素敵です。
別のところで話題になっていた気がしますが、再帰のどこに lazy-seq を入れるか悩みどころです。
ほとんど好みの問題のような気もするのですが、(cons (rem x 10) (lazy-seq (digits* (quot x 10)))) のように書きたくなります。

• 全体をlazy-seq にすると、先頭の要素すら、とり出されるまで計算されない
  ** 一方で、先頭の要素を取り出すだけで再帰呼び出しが1段進んで、 (pos? x) は評価される
  VS
• 再帰呼び出しだけを lazy-seq にすると、先頭の要素を取り出しただけでは他の計算は何も起きない
  ** ただし、先頭の要素の (rem x 10) は即座に評価される

徹底するならいっそ、if の外にまで lazy-seq を出してもいいのかも? しれません。

真面目にトレードオフを考える必要がある場面があるとしたらどういうときなのか、もうちょっと考えてみます。

あと、 pos? みたいな基本的な関数をちゃんと使えるようにしたいですね。覚えます。