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)))

解説

2のべき乗の10進表現の各桁の和を求める問題なので、素直に

• べき乗を求めて
• 10進の文字列に変換し
• 各文字を数値に変換して
• 和を求める

関数にしました。

べき乗を求めるにあたって java.math.BigInteger#pow を使いました。

以下、問題の解き方そのものには関係ない脱線ですが、Clojure使う上で私にとって勉強になりそうな内容なので、つらつらと書いてみます。とりとめなくて申し訳ありませんが、お気づきの点にツッコミいただけると大変うれしいです。

java.math.BigIntegerのメソッドを呼ぶときの reflection warningについて

ソースコメントに書きましたが、java.math.BigInteger のメソッドを呼ぶところ #(. (BigInteger. "2") pow %) で reflection warning が出ません。どうやらClojureがどのクラスのメソッドを呼べばいいのかコンパイル時に決めてくれたみたいです。
実際、レシーバの型がわからない #(. % pow %2) は reflection warning が出ました。
さらに、@tnoda さんのコメント https://gist.github.com/4291907#comment-663360 でちょうどいただいたヒントのとおり
(fn [^java.math.BigInteger x y] (. x pow y)) と型ヒントを与えて、reflection warningを消すこともできました。

多倍長整数について

Clojureが普通に多倍長整数をサポートしているようなので

pe-16.core=> (type 10000000000000000000)
clojure.lang.BigInt

そのまま使うのがよさそうだったのですが、単に

#(apply * (repeat % 2))

とすると、java.lang.ArithmeticException: integer overflow
してしまいました。BigIntを明示する方法を探したところ

pe-16.core=> 10000000000000000000
10000000000000000000N

どうやら実はNをつけるだけだったとわかったため、

#(apply * (repeat % 2N))

これで無事答えを得ることができました。

(def solve
  (comp (partial apply +)
        (partial map #(Character/digit ^char % 10))
        str
        #(apply * (repeat % 2N))
        ))

str と print について

strでは、末尾のNが入りません。もちろん今回はこれでちょうどよかったのですが、replで、つまりprint すれば出てくるものは何だかそのまま読み戻せそうですし、それを文字列にできたりするといろいろ便利そうな感じがします。strはJavaの.toStringのようなので単純な比較はできないですが、Schemeでいうところのdisplayやwriteに近い存在とか、文字列ポートはどのようなものだろう、と気になったわけです。

「clojure print object」でぐぐったところ、 http://clojure.org/other_functions#Other%20Useful%20Functions%20and%20Macros-Printing に、printやその仲間（？）の関数の詳細がまとめて載っていました。
表にするとこんな感じです。

	Print without newline		Print with newline
	Print to *out*	Print to string	Print to *out*	Print to string
Machine readable	pr	pr-str	prn	prn-str
Human readable	print	print-str	println	println-str

• print 系はhuman readableで pr 系はmachine readable。それぞれSchemeでいうところのdisplay と write に相当する感じ。
  print-str や pr-str もある。
• 改行つきのバージョンがそれぞれある。
• 内部的には、出力先を *out* で、出力形式を*print-readably*で、それぞれコントロールしている。

ダイナミックスコープについて

引数として与えずに関数の挙動を一時的に変えるには、ダイナミックスコープの変数（もしくは、それに相当するもの）が使われます。*out* や *print-readably* はきっとそのようなものであるに違いないと考えたため、調べてみたところ、すぐにみつかりました。
「clojure dynamic scope」
でGoogle検索して1件目の http://stackoverflow.com/questions/1774417/scoping-rules-in-clojure に貼られていたリンク
http://clojure.org/vars に答えは載っていて、def で ^:dynamic を指定し、bindingマクロで束縛できるようです。

とりあえず簡単に試せそうな *print-readably* でやってみたところ、期待どおりになりました。

pe-16.core=> (pr-str "hoge")
"\"hoge\""
pe-16.core=> (binding [*print-readably* false] (pr-str "hoge"))
"hoge"

残った疑問 変数がダイナミックスコープかどうかを知るためのAPI

「ダイナミックスコープな変数であるかどうか」をプログラムから（というかreplから）知る方法がないか気になったので、調べ始めてみたのですが、思いのほか長くなってしまったので、この件を調べた経緯については https://gist.github.com/4363770 に書きます。
結論だけここに書いてしまうと、「clojure.lang.VarのメソッドisDynamicで分かりそうだ」ということになります。

pe-16.core=> (. #'*print-readably* isDynamic)
true

また、(def ^:dynamic ...) で定義した場合は meta にも出てきます。

pe-16.core=> (def ^:dynamic y 100)
#'pe-16.core/y
pe-16.core=> y
100
pe-16.core=> (meta #'y)
{:ns #<Namespace pe-16.core>, :name y, :dynamic true, :line 1, :file "NO_SOURCE_PATH"}

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

累乗 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? みたいな基本的な関数をちゃんと使えるようにしたいですね。覚えます。