Euler : Problem 43

Posted by TAKAIY On 2011年6月29日水曜日 0 コメント
0から9の10桁のパンデジタルの数で、条件に合うものの総和を求める問題。

条件から
- d4 が偶数であること
- d3 + d4 + d5 が3で割りきれること。
- d6 が 0 か 5 であること。
がわかる。

また、[d6d7d8]が11で割りきれるとき、d6が0だと、d7とd8が同じ数字でなければならなくなるので、
d6は0でない。なので、d6は 5。
そして、5ではじまる3桁(5[d7d8])の11の倍数は
506 517 528 539 561 572 583 594 の8つ (550もだけれどは5が2回でてきちゃうのでだめ)
それと、d4が偶数という条件も入れて、全ての数列を作成して、残りの条件に合うかどうか確認した。


;;
;; Problem 43 : 2011/6/10
;; "Elapsed time: 724.777311 msecs"

;; d2d3d4=406 is divisible by 2 => d4 is even.
;; d3d4d5=063 is divisible by 3 => d3+d4+d5 is divisible by 3
;; d4d5d6=635 is divisible by 5 => d6 is 0 or 5
;; d5d6d7=357 is divisible by 7
;; d6d7d8=572 is divisible by 11 => !
;; d7d8d9=728 is divisible by 13
;; d8d9d10=289 is divisible by 17
;;
;; if d6 == 0 := d7 and d8 should same. no way.
;; d6 = 5
;; d6d7d8 -> [5]d7d8 is a multiple of 11
;; -> 506 517 528 539 561 572 583 594 (550 is not match the criteria)
;;
;; d678 [5 0 6] [5 1 7] [5 2 8] [5 3 9] [5 6 1] [5 7 2] [5 8 3] [5 9 4]
;; d4 [0 2 4 6 8]

(use 'clojure.set)
(use 'clojure.contrib.math)

(defn list-diff [base col]
(vec (difference (set base) (set col))))

(defn create-digits [[d6 d7 d8 d4 :as col]]
(let [rest-list (list-diff (range 10) col)]
(for [d1 (range 6) d2 (range 5) d3 (range 4) d5 (range 3) d9 (range 2) ]
(let [[d1 d2 d3 d5 d9 d10] (select-nums [d1 d2 d3 d5 d9 0] rest-list)]
[d1 d2 d3 d4 d5 d6 d7 d8 d9 d10]))))

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

(defn filter-43 [[d1 d2 d3 d4 d5 d6 d7 d8 d9 d10]]
(and (zero? (rem (+ d3 d4 d5) 3))
(zero? (rem (list-to-num [d5 d6 d7]) 7))
(zero? (rem (list-to-num [d7 d8 d9]) 13))
(zero? (rem (list-to-num [d8 d9 d10]) 17))))

(let [d6784 (for [d678 [[5 0 6] [5 1 7] [5 2 8] [5 3 9]
[5 6 1] [5 7 2] [5 8 3] [5 9 4]]
d4 [0 2 4 6 8]
:when (not-any? #(= % d4) d678)]
(conj d678 d4))]
(reduce + (map list-to-num (filter filter-43 (mapcat create-digits d6784)))))
;;

0 コメント:

コメントを投稿