Clojure入門 - Project Eulerを解いてみる 問9
a < b < c
, a + b + c = 1000
, a**2 + b**2 = c**2
を満たす数字を算出。いわゆるピタゴラス数。
以下ネタバレ
総当たりならコードは楽だがO(n**3)
で非常に重い。
a + b + c = 1000
とa < b < c
をうまく組み込んで枝の刈り込みをしていきたい。
とりあえず数学ライブラリを読み込み。ceil
やfloor
が使いたい。
(use 'clojure.math.numeric-tower)
ヘルパー関数
(defn square [x] (* x x)) (defn is-triplet [a b c] (= (+ (square a) (square b)) (square c)))
再帰で書こうかとも考えたのだが、階層が三つしかなく、一つ一つのレベルでやることが微妙に違うので階層ごとに関数を書く。
まず最下層。
(defn low-level [b c total] (let [a (- total (+ b c))] (if (is-triplet a b c) [a b c])))
b
とc
が決まっているのでa
も一義的に決まる。あとはピタゴラス数かどうか判定して、そうであれば[a b c]
を返す。違う場合の返り値はnil
。
次の階層。
(defn mid-level [c total] (let [remainder (- total c) min-b (ceil (/ remainder 2)) max-b (min remainder (dec c))] (map #(low-level % c total) (range min-b max-b))))
c
が決まっているのでb
に対してけっこう縛りが出てくる。b
の取りうる数字の最小値と最大値をrange
で表して下層の関数にmap
する。
最上層。
(defn top-level [total] (let [min-c (floor (/ total 3)) max-c (- total 2)] (filter #(not (nil? %)) (apply concat (map #(mid-level % total) (range min-c max-c))))))
c
も取りえるレベルは1~1000なんてことはなく、実は最小値は335。(334だとa=b
かb=c
になってしまう)書いた後で実はピタゴラス数の定義を使ってさらに絞り込めることに気が付いたがまあ置いておこう。
第二階層c
の値ごとにnil
と[a b c]
の入り混じったリストを返してくるので、それらをつなぎ合わせてnil
を除外。
あとは引数に1000をいれて掛け合わせて終わり。
(println (map #(apply * %) (top-level 1000)))