パターンがあるので、それを数えるのがいいかなと思ったんだけど、それだと、手で計算できちゃうので、なんならということで、1000までの数字を読み下ろす関数を作ってみた。
user> (writedown 999)
"nine hundred and ninety nine"
ということで、あえて力ずく。
関係ないけど、four で fourteen なのに forty なんだね。「u」はどこへいっちゃうんだろ。
この問題を解くまで気づかなかったというか、忘れていたというか、ねぇ。
;;
;; Problem 17 : 2011/4/22
;; "Elapsed time: 106.548179 msecs"
(def number-table
'{ 1 "one"
2 "two"
3 "three"
4 "four"
5 "five"
6 "six"
7 "seven"
8 "eight"
9 "nine"
10 "ten"
11 "eleven"
12 "twelve"
13 "thirteen"
14 "fourteen"
15 "fifteen"
16 "sixteen"
17 "seventeen"
18 "eihgteen"
19 "nineteen"
20 "twenty"
30 "thirty"
40 "forty"
50 "fifty"
60 "sixty"
70 "seventy"
80 "eighty"
90 "ninety"
100 "hundred" })
(defn writedown-tys [n]
(cond (<= n 0) nil
(< n 20)
(number-table n)
:else
(apply str (interpose " "
(list (number-table (* 10 (floor (/ n 10))))
(number-table (rem n 10)))))))
(defn writedown-hdrs [n]
(cond (<= n 0) nil
:else (apply str (interpose " "
(list (number-table n)
"hundred")))))
(defn writedown [n]
(if (= n 1000)
"one thousand"
(let [hundreds (floor (/ n 100))
tys (rem n 100)]
(apply str
(interpose " "
(filter #(not (nil? %))
(list
(writedown-hdrs hundreds)
(if (and (> hundreds 0) (> tys 0))
"and"
nil)
(writedown-tys tys))))))))
(loop [nums (range 1 1001) total 0]
(if (empty? nums)
total
(recur (rest nums)
(+ total
(.length (.replace (writedown (first nums)) " " ""))))))
;;
2の1000乗に出てくる数字を全部足すといくつ？ って問題です。
とりあえず作ってみたら動いちゃったので、そのまま。
計算して、各桁足してます。
芸が無い。
;;
;; Problem 16 : 2011/4/22
;; "Elapsed time: 16.475557 msecs"
(use 'clojure.contrib.math)
(loop [num (expt 2 1000)
result 0]
(if (< num 1)
result
(recur (floor (/ num 10))
(+ result (rem num 10)))))
;;
碁盤の目の通路の問題です。
まあ、普通にやるんだったら、組み合わせで解くんだけれども、やってみたら、すごく時間がかかる。
んで、交差点ごとの数を数えあげる方法を実装してみた。
動的計画法にあたるかな？
3x3だと
1 1 1
1 2 3
1 3 6
てな感じ。
実際の計算で使っているのは update-child と 最後のループのところだけ。
あとは、データ作成のためのもの。
;;
;; Problem 15 : 2011/4/22
;;"Elapsed time: 32.748855 msecs"
;; too long time
(use 'clojure.contrib.combinatorics)
(count (combinations (range 40) 20))
;; grid parameter
(def *grid-x-max* 21)
(def *grid-y-max* 21)
;; data structure
;; [x y] {:val:next-node }
(defstruct grid-node
:val :next-node)
;; create child node list
(defn get-grid-child [x y]
(filter #(not (nil? %))
(vector (if (< x (dec *grid-x-max*))
[(inc x) y])
(if (< y (dec *grid-y-max*))
[x (inc y)]))))
;; create new *nodes* table
(def *nodes*
(loop [val-list (for [i (range *grid-x-max*) j (range *grid-y-max*)]
(let [data (struct grid-node (atom 0)(get-grid-child i j))]
[[i j] data]))
res-map {}]
(if (empty? val-list)
res-map
(recur (rest val-list)
(assoc reset!
(first (first val-list))
(second (first val-list)))))))
;; display *nodes* :val data
(defn disp-node-table [table]
(partition *grid-x-max*
(for [i (range *grid-x-max*) j (range *grid-y-max*)]
@(:val (table [i j])))))
;; update child
(defn update-child [parent-val child-list]
(if (not (empty? child-list))
(let [target-child (first child-list)]
(do
(swap! (:val (*nodes* target-child)) #(+ parent-val %))
(update-child parent-val (rest child-list))))))
;; set initial val
(reset! (:val (*nodes* [0 0])) 1)
;; calc all nodes
(loop [nodes-in-my-hand [[0 0]]]
(if (not (empty? nodes-in-my-hand))
(let [target (first nodes-in-my-hand)
child-node (:next-node (*nodes* target))]
(do
(update-child @(:val (*nodes* target)) child-node)
(recur (distinct (into (apply vector (rest nodes-in-my-hand)) child-node)))))))
;;
角谷の予想(コラッツの予想)の問題です。
この問題、中学生ぐらいのころに手計算でノートいっぽいに数字を書いてみたりしてたので、ちょっとなつかしい。
1から逆にたどって系統樹を作ってやればいいかなと思ったんだけど、「途中で百万を超えてもかまわない」という条件があるので、逆にたどるのは戻ってくる可能性を考慮しなければならないということなんだけれど、そこのところがうまく表現できなくて断念。
1から順にしらべることになっちゃいました。
この問題、中学生ぐらいのころに手計算でノートいっぽいに数字を書いてみたりしてたので、ちょっとなつかしい。
1から逆にたどって系統樹を作ってやればいいかなと思ったんだけど、「途中で百万を超えてもかまわない」という条件があるので、逆にたどるのは戻ってくる可能性を考慮しなければならないということなんだけれど、そこのところがうまく表現できなくて断念。
1から順にしらべることになっちゃいました。
;;結局つかわなかった関数
;; Problem 14 : 2011/4/15
;; "Elapsed time: 54894.586881 msecs"
;; momoise : from clojure.org
(defn memoize [f]
(let [mem (atom {})]
(fn [& args]
(if-let [e (find @mem args)]
(val e)
(let [ret (apply f args)]
(swap! mem assoc args ret)
ret)))))
;; hotpo step count
(defn hotpo-count
([n] (hotpo-count n 0))
([n count]
(cond (= n 1) (inc count)
(even? n) (hotpo-count (/ n 2) (inc count))
:else (hotpo-count (+ (* n 3) 1) (inc count)))))
(def hotpo-count (memoize hotpo-count))
(loop [n 1 max-list [0 0]]
(if (> n 1000000)
max-list
(let [hotpo (hotpo-count n)]
(if (< (nth max-list 1) hotpo)
(recur (inc n) [n hotpo])
(recur (inc n) max-list)))))
;;
;;
(defn half-or-triple-plus-one [n]
(if (= n 1) (list 1)
(let [next-num (if (even? n) (/ n 2) (+ (* n 3) 1))]
(lazy-seq
(cons n (half-or-triple-plus-one next-num))))))
(defn hotpo-prev-node
([] (rev-ho31 1))
([n]
(let [tpo (/ (- n 1) 3)]
(if (or (<= tpo 1)
(not (zero? (mod (- n 1) 3))))
(list (* n 2))
(list (* n 2)
(/ (- n 1) 3))))))
;;
でかい数の足し算。
前の13桁だけ足して答を出した。 まあ、もとのデータを文字列で読んじゃったから、なんのことはない。
前の13桁だけ足して答を出した。 まあ、もとのデータを文字列で読んじゃったから、なんのことはない。
;;
;; Problem 13 : 2011/4/14
;; "Elapsed time: 4.569016 msecs"
(reduce + (map #(new BigInteger (apply str (take 13 %))) target-list))
(def target-list [
"37107287533902102798797998220837590246510135740250"
"46376937677490009712648124896970078050417018260538"
"74324986199524741059474233309513058123726617309629"
"91942213363574161572522430563301811072406154908250"
"23067588207539346171171980310421047513778063246676"
"89261670696623633820136378418383684178734361726757"
--- crop ---
"77158542502016545090413245809786882778948721859617"
"72107838435069186155435662884062257473692284509516"
"20849603980134001723930671666823555245252804609722"
"53503534226472524250874054075591789781264330331690"])
;;
三角数に関する問題。 だけど、三角数の性質とは関係ないのかな？
始めは逆の探索で、約数が500個以上ある数を求めて、それが三角数かどうか確認するって方法をやろうとしたんだけど、挫折した。三角数かどうか確認する関数も作ったけど、使わなかった。挫折した方法のときに必要だね。
結局、小さいほうから全調べ方式。
いつかリベンジしてやる。
factorsは前につくったやつで、そこで素数の一覧も使ってる。
時間には素数を作る時間は入ってない。
三角数を作る方法を2通り試したけど、とくに時間は変らないみたい。
始めは逆の探索で、約数が500個以上ある数を求めて、それが三角数かどうか確認するって方法をやろうとしたんだけど、挫折した。三角数かどうか確認する関数も作ったけど、使わなかった。挫折した方法のときに必要だね。
結局、小さいほうから全調べ方式。
いつかリベンジしてやる。
factorsは前につくったやつで、そこで素数の一覧も使ってる。
時間には素数を作る時間は入ってない。
三角数を作る方法を2通り試したけど、とくに時間は変らないみたい。
;;
;; Problem 12 : 2011/4/14
;; "Elapsed time: 1954.309557 msecs"
;; pre defined func : factors [n]
;; (foctors 12) => (2 2 3)
;; count divisor
;; when n = f1^a * f2^b * ... * fn^x
;; divisor count = (a+1)*(b+1)* ... (x+1)
(defn count-divisor [n]
(let [ ftr (factors n)]
(reduce *
(for [tgt (distinct ftr)]
(inc (count (filter #(= % tgt) ftr)))))))
;; nth triangle num
(defn nth-triangle-num [n]
(/ (* n (inc n)) 2))
(loop [n 1]
(let [triangle-num (nth-triangle-num n)
divisor-num (count-divisor triangle-num)]
(if (> divisor-num 500)
(list n triangle-num divisor-num)
(recur (inc n)))))
;; triangle num seq
;;"Elapsed time: 1933.932106 msecs"
(defn triangle-num
([] (tri 2 1))
([n sum]
(lazy-seq
(cons sum (tri (inc n) (+ n sum))))))
(loop [triangle-num-list (triangle-num)]
(if (> (count-divisor (first triangle-num-list)) 500)
(first triangle-num-list)
(recur (rest triangle-num-list)))))
;; did not use
;; check triangle num
(defn triangle-num? [n]
(let [double-square-int (int (sqrt (* n 2)))
num-1 double-square-int
num-2 (inc num-1)]
(= (/ (* num-1 num-2) 2) n)))
;;
