Euler : Problem 32

Posted by TAKAIY On 2011年5月22日日曜日 0 コメント
pandigitalな数字=全ての数字を1つ以上含んだ数字についての問題。

pandigitalな数字を作る関数を作った。1つ選んで、残りから1つ選んでっていう感じ。
1から5の数字で、0 0 0 0 0 を選ぶと
[1 2 3 4 5]
1 [2 3 4 5]
12 [3 4 5]
123 [4 5]
1234 [5]
12345 []

2 2 2 0 0 だと

[1 2 3 4 5]
3 [1 2 4 5]
32 [1 4 5]
325 [1 4]
3251 [4]
32514 []

まあ、たぶん、これを使わないで、普通に数字でやったほうが早かったとおもわれる。

問題の方は、1桁×4桁=4桁 と 2桁×3桁=4桁のパターンしかないので、1~9の数の全部の順列を作り、それぞれを2パターンに分解してあてはまるかどうか確認した。

全数検索の方法になってしまった。うまく候補を生成できるといいんだけど、直接値を作っていないので、スクリーニングしてもあまり時間の短縮が望めないので、やらなかった。

;;
;; Problem 32 : 2011/5/18
;; "Elapsed time: 41476.85055 msecs"

;; there is only two type.
;; 1digit * 4digit = 4digit
;; 2digit * 3digit = 4digit

(use 'clojure.contrib.math)

(defn num-list []
(for [a1 (range 9) a2 (range 8) a3 (range 7) a4 (range 6)
b1 (range 5) b2 (range 4) b3 (range 3)
c1 (range 2)]
(select-nums [a1 a2 a3 a4 b1 b2 b3 c1 0] [1 2 3 4 5 6 7 8 9])))

(defn list-to-num [digit-list]
(apply + (map #(* %1 (expt 10 %2)) (reverse digit-list) (iterate inc 0))))

(defn create-nums [col]
(let [[p pp] (split-at 4 col)
[mpcand4 mplir1] (map list-to-num (split-at 4 pp))
[mpcand3 mplir2] (map list-to-num (split-at 3 pp))
prod (list-to-num p)]
(if (< prod mpcand4)
nil
[[prod mpcand4 mplir1] [prod mpcand3 mplir2]])))

(reduce +
(distinct (map first
(filter #(= (first %) (* (second %) (last %)))
(filter (complement empty?)
(mapcat create-nums (num-list)))))))
;;

0 コメント:

コメントを投稿