Arantium Maestum

プログラミング、囲碁、読書の話題

Clojure入門 - Project Eulerを解いてみる 問9

第九問

a < b < c, a + b + c = 1000, a**2 + b**2 = c**2を満たす数字を算出。いわゆるピタゴラス数。

以下ネタバレ

総当たりならコードは楽だがO(n**3)で非常に重い。

a + b + c = 1000a < b < cをうまく組み込んで枝の刈り込みをしていきたい。

とりあえず数学ライブラリを読み込み。ceilfloorが使いたい。

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

bcが決まっているので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=bb=cになってしまう)書いた後で実はピタゴラス数の定義を使ってさらに絞り込めることに気が付いたがまあ置いておこう。

第二階層cの値ごとにnil[a b c]の入り混じったリストを返してくるので、それらをつなぎ合わせてnilを除外。

あとは引数に1000をいれて掛け合わせて終わり。

(println (map #(apply * %) (top-level 1000)))