マンジラボ

Project Euler #016 – 2の1000乗

In: Project Euler

9 1月 2010

Project EulerをClojureでおさらいシリーズ。
Problem 16

オリジナルはこちら

日本語訳：

2¹⁵ = 32768 の各桁の数字の和は 3 + 2 + 7 + 6 + 8 = 26 である。

2¹⁰⁰⁰ の各桁の数字の和を求めよ。

何の問題もない。big-integerバンザイ。

以前Rubyで解いたもの：

#!/usr/bin/env ruby
 
p (2**1000).to_s.split('').inject(0){|s,x| s + x.to_i}

こういうときのRubyの記述力は異常。

今回はClojureで：

(ns euler.p016)
 
(defn pow
  "Return the N-th power of A."
  [a n]
  (apply * (replicate n a)))
 
(defn sum-of-digits
  "Return the sum of each digits of N."
  [n]
  (apply + (map #(Integer. (str %)) (str n))))
 
(println "Answer : " (sum-of-digits (pow 2 1000)))

Project Euler では各桁を合計する処理がたびたび必要になるので sum-of-digits はライブラリ化したほうがいいのかも。

View Comments
Tags: Clojure, Project Euler, Ruby

Project Euler #015 – 道順の組合せ

In: Project Euler

9 1月 2010

Project EulerをClojureでおさらいシリーズ。
Problem 15

オリジナルはこちら

日本語訳：

2×2のマス目の左上よりスタートして右下にたどり着く道順は6通りである。（ただし逆方向に引き返さないこととする）

20×20のマス目では何通りの道順が存在するかを求めよ。

₄₀C₂₀ ですね。以上。

久々に紙と鉛筆でもいける問題。
こういうのも嫌いじゃない。

以前Rubyで解いたバージョンはこちら：

#!/usr/bin/env ruby
 
# 40C20
p 21.upto(40).inject(1){|s,x| s*x} / 1.upto(20).inject(1){|s,x| s*x}

さて、次はClojure：

(ns euler.p015)
 
(defn fact
  "Return factorial of N."
  [n]
  (apply * (range 1 (inc n))))
 
(defn comb
  "Return number of combinations from N choose M."
  [n m]
  (/ (fact n)
     (fact m)
     (fact (- n m))))
 
(println "Answer : " (comb (* 20 2) 20))

せっかくなので階乗と組合せの関数でも定義してみた。

View Comments
Tags: Clojure, Project Euler, Ruby

Project Euler #014 – コラッツの問題

In: Project Euler

9 1月 2010

Project EulerをClojureでおさらいシリーズ。
Problem 14

オリジナルはこちら

日本語訳：

正の整数に対して次のように繰り返す数列を定義する。

n → n/2 （nが偶空の場合） n → 3n + 1 （nが奇数の場合）

この規則に沿って 13からはじめると、次の数列を生成する。

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13からはじまり1でおわる10項の数列とみることができる。
どの数からはじめても最終的には１になると考えられているがまだ証明はされていない。（コラッツの問題）

100万未満のどの数からスタートすれば最も長い数列を得られるかを求めよ。

注意：途中の項の数字が100万を越えてもかまわない。

計算の重複によるムダをいかに少なくするかがカギかな。

Nに対する数列の長さは再帰的に求めて、その値をキャッシュするのがよさげ。

以前Rubyで解いたバージョンはこちら：

#!/usr/bin/env ruby
 
def next_collatz(n)
  return 1 if n == 1
  return n / 2 if n.even?
  3 * n + 1
end
 
def get_chains_num(n)
  c = 1
  until n == 1
    n = next_collatz(n)
    c += 1
  end
  c
end
 
def (Chains = [0, 1]).[](n)
  return super if super
  if n < 2_000_000
    return Chains[n] = Chains[next_collatz(n)] + 1
  else 
    return get_chains_num(n)
  end
end
 
max = 0
point = 1
1.upto(1_000_000 - 1).each do |n|
  val = Chains[n]
  if val > max
    max = val 
    point = n
  end
end
 
p "At #{point} : chain length = #{max}"

Project Euler #002 のときと同様に配列の特異メソッドとして定義することで、Nに対するコラッツ数の長さの値をキャッシュしています。

これが意外と速い。
ruby1.9系だと20秒かかりませんでした。

さて、Clojureで書いてみます。

(ns euler.p014)
 
(defn collatz-length
  "Return chain length of Collatz sequence of N."
  [n]
  (cond (= n 1) 1
	(even? n) (inc (collatz-length (/ n 2)))
	:else (inc (collatz-length (inc (* 3 n))))))
 
(defn memoize-under
  "Apply memoize when arg is under limit."
  [limit f]
  (let [mem (atom {})]
    (fn [arg]
      (if (> arg limit)
	(f arg)
	(if-let [e (find @mem arg)]
	  (val e)
	  (let [ret (f arg)]
	    (swap! mem assoc arg ret)
	    ret))))))
 
(def collatz-length (memoize-under 400000 collatz-length))
 
(defn pick-grater-last
  "Pick coll of which last value is greater."
  [coll-1 coll-2]
  (if (> (last coll-1)
	 (last coll-2))
    coll-1
    coll-2))
 
(println "Answer : "
	 (first
	  (reduce pick-grater-last
		  (map #(vector % (collatz-length %))
		       (range 1 1000000)))))

キャッシュなしだと60秒を越えてしまったのでmemoizeを使うことに。

ところがmemoizeをそのまま使うとヒープの上限を越えてしまいました。

Javaのヒープを増やすという解決策は美しくないので、memoizeのソースを参考にして「ある数値以下の時だけmemoizeする関数」を定義することにしました。(memoize-under)

キャッシュがヒットする頻度の分布は下の方に偏向しているはず
memoizeはハッシュなのでヒットする回数の少ないものはかえってキャッシュ検索の効率を下げる

との考えから40万をキャッシュする値の上限にしてあります。

この方法だと20秒かからずに計算が終了しました。

View Comments
Tags: Clojure, Project Euler, Ruby

Clojureでメソッドチェイン風に記述するマクロ

In: Clojure

26 12月 2009

ClojureのAPIリストを眺めていたら面白いマクロがありました。 -> と ->> です。

Rubyのメソッドチェインのようなことができます。
例えば次のようなRubyでの処理は

123456789.to_s.length
=> 9

ClojureでもJavaのメソッドを直接使う場合は .. でチェインできます。

user> (.. 123456789 toString length)
=> 9

-> を使えばこれをClojure上の関数で実現できます。

user> (-> 123456789 str count)
=> 9

123を文字化して逆順にする場合

user> (-> 123 str reverse)
=> (\3 \2 \1)

reverseは文字のシーケンスを返すので

user> (->> 123 str reverse (apply str))
=> "321"

のようにします。今回は -> ではなく ->> をつかいました。

この -> と ->> の違いはなんでしょう。

簡単な例で検証してみます。

例）2に3を足してから4倍する

user> (-> 2 (+ 3) (* 4))
=> 20
 
user> (->> 2 (+ 3) (* 4))
=> 20

この例では同じ結果ですね。
次の場合はどうでしょう。

user> (-> 8 (* 6) (/ 2 3))
=> 8
 
user> (->> 8 (* 6) (/ 2 3))
=> 1/72

ここで違いがでました。

それぞれのマクロを展開してみます。

(-> 8 (* 6) (/ 2 3))) → (/ (* 8 6) 2 3)
 
(->> 8 (* 6) (/ 2 3))) → (/ 2 3 (* 6 8))

引数を複数とる関数を対して関数名の次に展開するのが ->
末尾に展開するが ->> という違いでした。

先の例では (apply str (文字のシーケンス)) という処理をしたいので ->> を使うことになります。

View Comments
Tags: Clojure, Ruby

Project Euler #013 – 巨大な整数の和

In: Project Euler

24 12月 2009

Project EulerをClojureでおさらいシリーズ。
Problem 13

オリジナルはこちら

日本語訳：

以下の50桁の数字100個を合計した数の上位10桁を求めよ。

37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690

big-integer を扱える言語ならなにも考えずに解ける問題。

Ruby

#!/usr/bin/env ruby
 
ans = 37107287533902102798797998220837590246510135740250
ans += 46376937677490009712648124896970078050417018260538
ans += 74324986199524741059474233309513058123726617309629
# ------------------------ SNIP ------------------------ 
ans += 20849603980134001723930671666823555245252804609722
ans += 53503534226472524250874054075591789781264330331690
 
p ans.to_s[0..9]

Clojure

(def big-nums
     [37107287533902102798797998220837590246510135740250
      46376937677490009712648124896970078050417018260538
      74324986199524741059474233309513058123726617309629
; ------------------------ SNIP ------------------------
      20849603980134001723930671666823555245252804609722
      53503534226472524250874054075591789781264330331690])
 
(println "Answer : " (apply str (take 10 (str (apply + big-nums)))))

カンタン。

View Comments
Tags: Clojure, Project Euler, Ruby

Project Euler #012 – 三角数

In: Project Euler

23 12月 2009

Project EulerをClojureでおさらいシリーズ。
Problem 12

オリジナルはこちら

日本語訳：

三角数の数列は自然数の和で生成される。

7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である。

よって最初の10項は:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

となる。

三角数の最初の7項について約数を挙げてみよう。

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

約数の数が5を越える最初の三角数は28であることがわかる。

約数の数が500を越える最初の三角数を求めよ。

約数の数を求めるアルゴリズムをどうするかの問題。

以前Rubyで解いたバージョンはこちら：

#!/usr/bin/env ruby
 
require 'mathn'
 
def divisor(n)
  result=[1]
  n.prime_division.each do |i|
    result = result + result.map {|x| (1..i[1]).map{|n| x*(i[0]**n)}}.flatten
  end
  result.flatten.sort
end
 
n = 1
tri = 1
begin
  n += 1
  tri += n 
end while divisor(tri).size <= 500
 
p tri

横着してmathnライブラリを使っています。

馬鹿正直に約数をすべて求めています、なんでこんなことしてたんだろ？？ものすごくムダなことを・・・しかもソートしてるしｗ

案の定、遅いです。

さて、Clojureで書いてみます。

(ns euler.p012
  (:use clojure.contrib.seq-utils))
 
(def triangular-nums
  (lazy-cat [0] (map + triangular-nums (iterate inc 1))))
 
(defn prime-factors
  "Return prime factors of N."
  [number]
  (loop [n number d 2 factors []]
    (cond (<= n d) (conj factors d)
	  (= 0 (rem n d)) (recur (/ n d) d (conj factors d))
	  :else (recur n (inc d) factors))))
 
(defn num-of-divisors
  "Return numbers of divisors N has."
  [n]
  (apply * (map #(inc (nth % 1))
		(frequencies (prime-factors n)))))
 
(println "Answer : "
	 (first (filter #(> (num-of-divisors %) 500)
			(drop 2 triangular-nums))))

prime-factors は Project Euler #003 の largest-prime-factor の変形です。

7項目三角数、28を例に流れを解説すると

prime-factors は素因数に分解
例： 28 → [2 2 7]

frequencies は登場する要素を[要素出現数]でまとめる関数。
clojure.contrib.seq-utils に含まれています。
例： [2 2 7] → [[2 2] [7 1]]

num-of-divisors で約数の組み合わせの数を計算しています。
例： (2+1) * (1+1) → 6

triangular-nums は三角数を生成する遅延シーケンス。
三角数は n(n+1)/2 でも求められます。
n と (n+1) は連続しているので、それを利用するとさらに計算量が減らせそうですね。

View Comments
Tags: Clojure, Project Euler, Ruby

Project Euler #011 – 4連続で最大の積

In: Project Euler

23 12月 2009

Project EulerをClojureでおさらいシリーズ。
Problem 11

オリジナルはこちら

日本語訳：

下の20×20の数字の中で斜めに連続する4つの数字が赤くマークされている。

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

この4つの数字の積は 26 × 63 × 78 × 14 = 1788696 である。

この20×20のなかで上下左右斜めのいずれかの方向に連続する4つの数字の積で最大のものを求めよ。

総当たりで計算する問題ですね。

各方向に4つの数字をとる際に20×20からはみ出ないように注意するだけ。

昔にRubyで解いたときのコードがこれ：

#!/usr/bin/env ruby
 
grid = []
grid << %w(08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08)
grid << %w(49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00)
grid << %w(81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65)
grid << %w(52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91)
grid << %w(22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80)
grid << %w(24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50)
grid << %w(32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70)
grid << %w(67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21)
grid << %w(24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72)
grid << %w(21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95)
grid << %w(78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92)
grid << %w(16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57)
grid << %w(86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58)
grid << %w(19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40)
grid << %w(04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66)
grid << %w(88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69)
grid << %w(04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36)
grid << %w(20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16)
grid << %w(20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54)
grid << %w(01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48)
 
grid.map!{|line| line.map!{|num| num.to_i}}
 
grid_num = 20
 
largest = 0
 
0.upto(grid_num-1).each do |y|
  0.upto(grid_num-1).each do |x|
    # to right
    if x < grid_num - 3
      prod = grid[y][x] * grid[y][x+1] * grid[y][x+2] * grid[y][x+3]
      largest = prod if prod > largest
    end
 
    # to down
    if y < grid_num - 3
      prod = grid[y][x] * grid[y+1][x] * grid[y+2][x] * grid[y+3][x]
      largest = prod if prod > largest
    end
 
    # to rightdown
    if x < grid_num - 3 && y < grid_num - 3
      prod = grid[y][x] * grid[y+1][x+1] * grid[y+2][x+2] * grid[y+3][x+3]
      largest = prod if prod > largest
    end
 
    # to leftdown
    if x > 3 && y < grid_num - 3
      prod = grid[y][x] * grid[y+1][x-1] * grid[y+2][x-2] * grid[y+3][x-3]
      largest = prod if prod > largest
    end
  end
end
 
p largest

恥ずかしいほどに同じようなコードが散在しています。これはなんとかしたい。

縦横斜めを「方向」というパラメータにしてまとめるとよさそうです。

方針としては

4つの方向を定義する
[開始点(x,y) 方向(x,y)]のセットを生成する(20×20×4)
グリッドからはみ出たものをフィルタで除く
残った組み合わせでグリッドから4つの数字を取り出す。
積をとる
最大値をとる

という流れでいけそうです。

ベクトルの加算は: (map + [y x] [dy dx])

グリッド要素(x,y)の取得は: (reduce nth grid [y x]) — 参考

でできますね。

(ns euler.p11
  (:use clojure.contrib.seq-utils))
 
(def num-text
  "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
   49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
   81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
   52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
   22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
   24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
   32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
   67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
   24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
   21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
   78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
   16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
   86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
   19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
   04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
   88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
   04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
   20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
   20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
   01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48")
 
(def num-grid
     (partition 20 (map #(Integer. %) (re-seq #"[0-9]+" num-text))))
 
(def directions [[0 1] [1 0] [1 1] [1 -1]])
 
(defn all-in-range?
  "Retuen true if all elements is in 0..19"
  [coll]
  (every? #(< -1 % 20) (flatten coll)))
 
(def possible-list-of-four
     (filter all-in-range?
	     (for [start-y (range 20)
		   start-x (range 20)
		   step-yx directions]
	       (take 4 (iterate #(map + % step-yx) [start-y start-x])))))
 
(defn prod-of-four
  "Return product of four number"
  [yx-coll]
  (apply * (map #(reduce nth num-grid %) yx-coll)))
 
(println "Answer : "
	 (apply max
		(map #(prod-of-four %) possible-list-of-four)))

うーん。いまいちだなぁ。

関数に汎用性がないのはともかく、possible-list-of-four などのムダな定義が目立つ。

小分けに関数が定義されているのは、無名関数がネストしそうになったのでやむをえずに。

なんかしっくりこない。

そもそも方針(2)で生成したセットがネストしているのでフィルタするときも mapがネストしてしまうのが理由かな。

(2)でセットを生成するときに(3)の「はみでるかどうか」の処理も同時にしてしまえばそれ以降がスッキリするんだけどなぁ。

あ、はみ出た値を参照したときに 0 を返す関数を定義すれば解決するかも。

(ns euler.p11
  (:use clojure.contrib.seq-utils))
 
(def num-text
  "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
   49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
   81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
   52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
   22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
   24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
   32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
   67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
   24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
   21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
   78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
   16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
   86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
   19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
   04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
   88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
   04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
   20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
   20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
   01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48")
 
(def num-grid
     (partition 20 (map #(Integer. %) (re-seq #"[0-9]+" num-text))))
 
(defn pick-value
  "Pick value at pos[y x]. Return 0 if pos is out of grid."
  [coll pos]
  (if (every? #(< -1 % 20) pos)
    (reduce nth coll pos)
    0))
 
(println "Answer : "
	 (apply max
		(for [start-x (range 20)
		      start-y (range 20)
		      step-yx [[0 1] [1 0] [1 1] [1 -1]]]
		  (apply * (take 4 (map #(pick-value num-grid %)
					(iterate #(map + % step-yx)
						 [start-y start-x])))))))