Instantly share code, notes, and snippets.

# kohyama/pep011.clj Last active Dec 10, 2015

Project Euler Problem 11
 (require '[clojure.string :as s]) (require '[clojure.test :refer (deftest run-tests is)]) (defn trans [[& rows]] (apply (partial map list) rows)) (defn flip [mat] (map reverse mat)) (defn rot45 [mat] (let [w (count (first mat)) h (count mat) r-mat (reverse mat)] (map (partial remove nil?) (for [i (range (- 1 h) w)] (map #(get (vec %) %2) r-mat (iterate inc i)))))) (deftest test-mat-utils (let [mat '((a b c d) (e f g h) (i j k l))] (is (= (trans mat) '((a e i) (b f j) (c g k) (d h l)))) (is (= (flip mat) '((d c b a) (h g f e) (l k j i)))) (is (= (rot45 mat) '(( a ) ( e b ) (i f c ) ( j g d) ( k h ) ( l )))))) (defn text2mat [conv ; converter for each column fs ; field separater in regular expression rs ; record separater in regular expression text] (map #(map conv %) (map #(s/split % fs) (s/split text rs)))) (deftest test-text2mat (is (= (text2mat (fn [^String s] (.toUpperCase s)) #"," #"\n" "a,b,c,\nd,e,f,\ng,h,i,\n") '(("A" "B" "C") ("D" "E" "F") ("G" "H" "I")))) (is (= (text2mat #(Integer/parseInt %) #"\s" #"\n" (s/trim " 11 12 13 21 22 23 31 32 33 ")) '((11 12 13) (21 22 23) (31 32 33))))) (def input " 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 ") (defn pep011 ([] (pep011 4 input)) ([n text] ; for example n 2 text "1 2 3\n4 5 6\n7 8 9" (let [mat (text2mat #(Integer/parseInt %) #"\s" #"\n" (s/trim text))] ; mat '((1 2 3) (4 5 6) (7 8 9)) (->> (concat ; '( mat ; (1 2 3) (4 5 6) (7 8 9) (trans mat) ; (1 4 7) (2 5 8) (3 6 9) (rot45 mat) ; (1) (4 2) (7 5 3) (8 6) (9) (rot45 (flip mat))) ; (3) (6 2) (9 5 1) (8 4) (7)) (mapcat (partial partition n 1)) ; '((1 2) (2 3) ... (5 1) (8 4)) (map (partial apply *)) ; '(2 6 ... 5 32) (apply max))))) ; 72 (deftest test-pep011 (is (= (pep011 2 " 3 1 4 1 5 9 2 6 5 ") 54)) (is (= (pep011 3 " 3 1 4 1 5 9 2 6 5 3 5 8 ") 180))) (pep011)
Owner Author

### kohyama commented Dec 26, 2012

 Project Euler Problem 11 「与えられた 20x20 の数値の行列の中で縦, 横, 両斜めのいずれかの方向に隣接した四個の数値の積で最大の数値は何か」 ということです. 「空白を桁区切り, 改行を行区切りとして文字列で与えられた数値の行列の中で, 縦, 横, 両斜めのいずれかに方向に与えられた数だけ隣接した数値の積で最大の数値は何か」という問題として, いくつかの入力を与えて, 動作を確認すること. ヘルパー関数は, この問題にしか使えないものにならないよう, 汎用的で明解な動作仕様を与え, テストを書く事. などを自分なりの課題として解きました.

### tnoda commented Dec 28, 2012

 二次元配列を 45 度回転 させる `rot45` があれば後は `partition` だけで数列を切り出せるんですね．なるほど．私は配列の index 操作が苦手なのか，まだ `rot45` がどうして配列を 45 度回転できるのか理解できていないので，あとで考えてみます．
Owner Author

### kohyama commented Dec 28, 2012

 rot45 の動作はこんな感じです. ``````mat '((a b c d) (e f g h) (i j k l)) | (let [w (count (first mat)) | h (count mat) | r-mat (reverse mat)] V w 4 h 3 r-mat '((i j k l) (e f g h) (a b c d) | (for [i (range (- 1 h) w)] | (map #(get (vec %) %2) r-mat (iterate inc i))) V | % | %2 | i | r-mat | (iterate inc i) | #(get (vec %) %2) ---+-----------+------------------+------------------- -2 | (i j k l) | -2 | nil | (e f g h) | -1 | nil | (a b c d) | 0 | a ---+-----------+------------------+------------------- -1 | (i j k l) | -1 | nil | (e f g h) | 0 | e | (a b c d) | 1 | b ---+-----------+------------------+------------------- 0 | (i j k l) | 0 | i | (e f g h) | 1 | f | (a b c d) | 2 | c ---+-----------+------------------+------------------- 1 | (i j k l) | 1 | j | (e f g h) | 2 | g | (a b c d) | 3 | d ---+-----------+------------------+------------------- 2 | (i j k l) | 2 | k | (e f g h) | 3 | h | (a b c d) | 4 | nil ---+-----------+------------------+------------------- 3 | (i j k l) | 3 | l | (e f g h) | 4 | nil | (a b c d) | 5 | nil '((nil nil a) (nil e b) ( i f c) ( j g d) ( k h nil) ( l nil nil)) | (map (parital remove nil?) ... ) V '(( a ) ( e b ) (i f c ) ( j g d) ( k h ) ( l )) ``````

### tnoda commented Jan 3, 2013

 @kohyama 解説ありがとうございます．`for` で何をやっているのかわからなかったのですが，図解で理解できました．`nil` で padding されているだけで，この段階で既に 45 度回転されていたんですね．最後の `(map (partial filter identity) ...)` の役割もよくわかりました．重ねて感謝です． インデックスに頼るのは苦手なので，私だったらどう書くか，．．．というのをちょっと考えてみます． 重箱ですが，`nil` 除去なら `(partial filter identity)` より `(partial remove nil?)` が好みです．この場合はどちらでもいいんですけど．
Owner Author

### kohyama commented Jan 4, 2013

 @tnoda さん. 確かに, `nil` 除去なら `filter identity` より `remove nil?` の方が意図が伝わり易いですね. そうさせていただきます.

### tnoda commented Jan 6, 2013

 インデックスに頼るのは苦手なので，私だったらどう書くか，．．．というのをちょっと考えてみます．