Euler : Problem 61

Posted by YpsilonTAKAI On 2011年11月19日土曜日 0 コメント
四桁の3～8角数を任意の順に並べて輪を作る問題。

全くいい方法を思いつかなかったので全数アタック。





・ 4桁のX角数を全部リストアップしておく。
・ 3～8の数の順列を全部リストアップしておく。
・ 順列すべてについて、あてはまるものがあるかどうかを探す。
・ 途中でみつかっても中断せず、すべて探す

だいぶ長くなってしまった。

;; Problem 61 : 2011/11/16
;;"Elapsed time: 1208.733513 msecs"
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; triangle, pentagonal, hexagonal, and so on.
;; 3
(require '[clojure.contrib.math :as math])
(defn triangle-num [n]
(/ (* n (+ 1 n)) 2))
(defn triangle-num? [n]
(zero? (rem (- (Math/sqrt (+ (* 8 n) 1)) 1) 2)))
;; 4
(defn square-num [n]
(* n n))
(defn square-num? [n]
(= (math/expt (int (Math/sqrt n)) 2) n))
;; 5
(defn pentagonal [n]
(/ (* n (- (* 3 n) 1)) 2))
(defn pentagonal? [n]
(zero? (rem (+ 1 (Math/sqrt (+ 1 (* 24 n)))) 6)))
;; 6
(defn hexagonal [n]
(* n (- (* 2 n) 1)))
(defn hexagonal? [n]
(zero? (rem (+ 1 (Math/sqrt (+ 1 (* 8 n)))) 4)))
;; 7
(defn heptagonal [n]
(/ (* n (- (* 5 n) 3)) 2))
(defn heptagonal? [n]
(zero? (rem (+ 3 (Math/sqrt (+ 9 (* 40 n)))) 10)))
;; 8
(defn octagonal [n]
(* n (- (* 3 n) 2)))
(defn octagonal? [n]
(zero? (rem (+ 1 (Math/sqrt (+ 1 (* 3 n)))) 3)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; main
(defn n-digit-xgonal-num [typep n]
(filter typep (range (Math/round (Math/pow 10 (dec n)))
(Math/round (Math/pow 10 n)))))
(defn split-into-2digit [num-list]
(map (fn [num]
(let [r (rem num 100)]
[(/ (- num r) 100) r]))
num-list))
(defn remove-1digit-at-second [num-list]
(filter (fn [[_ r]] (>= r 10)) num-list))
(defn get-pe61-xgonal-list [typep]
(remove-1digit-at-second
(split-into-2digit
(n-digit-xgonal-num typep 4))))
(def get-child
(let [xgonal-dat {3 (get-pe61-xgonal-list triangle-num?)
4 (get-pe61-xgonal-list square-num?)
5 (get-pe61-xgonal-list pentagonal?)
6 (get-pe61-xgonal-list hexagonal?)
7 (get-pe61-xgonal-list heptagonal?)
8 (get-pe61-xgonal-list octagonal?)}]
(fn [digit-set xgonal]
(let [tail-2digit (second digit-set)]
(filter #(= tail-2digit (first %)) (xgonal-dat xgonal))))))
(defn get-next-level [digit-set xgonal]
(map #(conj digit-set %) (get-child (last digit-set) xgonal)))
(require '[clojure.contrib.combinatorics :as combx])
(defn get-pe61-all-path []
(combx/permutations (range 7 2 -1)))
(defn search-all-path-depth [org-path]
(loop [search-pool (map vector (get-pe61-xgonal-list octagonal?))
path org-path]
(cond (empty? search-pool) '()
(empty? path) (filter #(= (first (first %)) (second (last %))) search-pool)
:else (recur
(mapcat #(get-next-level % (first path)) search-pool)
(next path)))))
(defn pe61 []
(filter (complement empty?)
(mapcat search-all-path-depth (get-pe61-all-path))))
view raw pe_61.clj hosted with ❤ by GitHub


- triangle-num ～ octagonal
- n-digit-xgonal-num
  生成する関数とチェックする関数を両方用意した。
  4桁の数が必要なので、4桁の整数からチェックする関数でフィルターする方法を採った。

- split-into-2digit
  上位と下位の2桁ずつにわけたベクタを生成

- remove-1digit-at-second
  10の位が0の数は、題意に合わないので除外する。

- get-pe61-xgonal-list
  上記の関数をつかって、x角数のリストを作る。
  [[12 34] [56 78] ....]

- get-child
  とある4桁数 [xx yy] に続くx角数のをすべて求める。

- get-pe61-all-path
  3～7の数の全ての順列を返す。
  ※ 8角数から始めることにしたので、8は入っていない。

- search-all-path-depth
  ある順列について、8角数から始めてその順に最後まで並べたときに、
  先頭の2桁と末尾の2桁が同じであればその列を返す。

- pe61
  全ての順列について、上の関数を呼び出して、解だけ出力する。


他にいいロジックがありそうだけど、思いつかない。



ラベル: ,

0 コメント:

コメントを投稿