Project Euler を解いているときに、素数生成とかの細かい関数を作っているのだけれど、10個以上になってきたので、まとめることにした。あらためて見てみると、変だったり、もう少し汎用的にしたほうがよかったりするものが目について、直し始めちゃって泥沼化寸前。そのなかで、同じような計算をたくさんしているところで気になっていたのが、CPUの使用率が50%を超えないこと。mapなんかは自動的に並列処理してくれるのだと思っていたからちょっと意外だった。黒猫本(と呼ばれているかどうかは知らない)にも、STMとかの機能の説明はあるけど、並列化するための方法については書かれていなかった。「自分でJavaのThreadを呼ばなければならんのかい!」と思っていたら、pmapというのを見つけた。で、実際どうなのかを調べてみた。なんか適当に時間のかかる処理ということで、適当に2のX乗をY個足す処理にした。mapでやるとこんな感じ。(let...
循環させても素数のままの素数の問題。循環させた数のリストを作る関数を作った。0の扱いでひっかかったりして、結局文字列化して操作する方式になった。あとは全数検査途中に偶数とか5とかが入っていたら対象からはずすとかしたらちょっと速くなるかも。;;;; Problem 35 : 2011/5/19;; "Elapsed time: 18328.781172 msecs"(def *prime-list* (atom []))(create-prime-list-under 1000000);;get all ratate num(require '[clojure.contrib.string :as ccstr])(defn rotate-num-str [num-str] (str (ccstr/drop (dec (.length num-str))...
1ケタになるまで最上位や最下位の数を取っていっても素数のままの素数の問題。数字をリスト化して操作最上位や最下位が素数でないものと、途中に偶数を含んでいるものものははずしてチェックした。member?関数を作った、every?とかを使って代用できたかも。;;;; Problem 37 : 2011/5/19;; "Elapsed time: 5385.057877 msecs"(defn member? [n col] (not-every? false? (map #(= n %) col)))(defn list-to-num [digit-list] (apply + (map #(* %1 (expt 10 %2)) (reverse digit-list) (iterate inc 0))))(defn num-to-list [num]...
十進でも二進でも回文数になっているなっている数をさがす問題。そのまま解いちゃってるけど、一応、奇数じゃないと二進で回文にならないからそこだけ考慮してる。;;;; Problem 36 : 2011/5/19;; "Elapsed time: 4715.235037 msecs"(defn palindromic? [str] (= str (ccstr/join "" (reverse str))))(reduce + (filter #(and (palindromic? (str %)) (palindromic? (Integer/toBinaryString %))) (range 1 1000000 2))...
それぞれの桁の数の階乗の和が元の数と同じになるような数についての問題。全数アタックで30秒くらいかかってる。数をリストで生成したけど、数として作って分解したほうが速かったかどうか？;;;; Problem 34 : 2011/5/18;; "Elapsed time: 29005.216026 msecs";; (fact 0) -> (def fact (memoize (fn [n] (if (< n 2) 1 (* n (fact (dec n)))))))(reduce + (map (fn [n] (let [x (reduce + (map fact (drop-while zero? n))) y (list-to-num...
分数の上下からおなじ数字を取り除いても値が変らないものについての問題。調べてみると、2パターンしかなくて、[ax]/[ya] = x/y [xa]/[ay] = x/y片方計算すれば、其を逆数にしたものがもう一方になるはず。また、aとxとyは全部異なる数であることもわかる。ということで、1から9の数字からa,x,yの3つの数字を選んで分数を作って、あてはまるかどうか計算する。;;; Problem 33 : 2011/5/18;; "Elapsed time: 12.869792 msecs";; type;; [ax]/[ay] = x/y;; a=0 or x=y :: not allowed;; [xa]/[ya/ = x/y;; x=y :: not allowed;;;; [ax]/[ya] = x/y;; [xa]/[ay] =...
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パターンに分解してあてはまるかどうか確認した。全数検索の方法になってしまった。うまく候補を生成できるといいんだけど、直接値を作っていないので、スクリーニングしてもあまり時間の短縮が望めないので、やらなかった。;;;;...
金種を組みあわせて2ポンドを作る問題。金額の大きい順に個数を割りあてて樹形図を作るイメージ。2￡ 1￡ ... 0 0 1 21 0 12データ構造体は、 <残りの金額> <金種ごとの枚数のリスト> という感じ。;;;; Problem 31 : 2011/5/16;; "Elapsed time: 604.414248 msecs";;data structure(defstruct coin-table :rest-amount :coin-list)(defn next-list [in-table coin] (for [num (take-while #(<= (* % coin) (:rest-amount in-table)) (iterate inc 0))]...
なんか、「ClojureはLisp-1だから名前空間が無い」っていう記述をよく見るなぁ、と思っていたら、Wikipediaの日本語版の説明もそうなっていた。なおした。でも、基本 Lisp-2 の道を歩いてきたので、関数名の前に #' って書かなくていいのは便利だなぁと思う反面、なんかムズムズする。 あと、つい、変数名に string とか list とか使っちゃって、「あー」とかなる。Lisp-1とは関係ないけど、[]がリストでない = 評価されない のは地味に便利。 (list xx xx) でなくて [xx xx]って書ける。そろそろちょっと実用的なものでも作ってみようかなぁ。いやいや。 とりあえず、50まで行ってか...
30番まで来た。6桁のときの各桁の5乗の合計は、9^5*6 = 354294 で6桁7桁のときは、9^5*7 = 413343 6桁になっちゃうので、7桁以上の数で条件にあてはまるものは無い。全部計算して条件に合うのものだけ抽出して計算。;;;; Problem 30 : 2011/5/;; "Elapsed time: 24452.933823 msecs"(reduce #(+ %1 (first %2)) 0 (drop 2 (filter #(= (first %) (second %)) (for [a1 (range 10) a2 (range 10) a3 (range 10) a4 (range 10) a5 (range 10) a6 (range 10)] ...
全部作って重複を省いて足す。それだけ。;;;; Problem 29 : 2011/5/13;; "Elapsed time: 98.855302 msecs"(count (distinct (for [a (range 2 101) b (range 2 101)] (expt a b)))...
四角形にならべた数の対角線の合計の問題中心から出る4つの対角線の数列の差分をとってみると2階差分が全部81 3 13 31 57 91 2 10 18 26 34 8 8 8 8だから、n番目の数はan^2+bn+c の形で表わせる。2階差分が8だから a=1、nを0始まりにすると、 c=1 に決って、bだけ対角線ごとに異なって、右下方向 -2左下方向 0左上方向 2右上方向 4結局、1周分の角の合計は 16n^2+4n+4あとはnの値が出れば、任意のところの合計が計算できる。。 対応する辺の長さは1,3,5... と増えていくから L=2n-1になり、n=(L+1)/2この通りに式にする。;;;; Problem 28 : 2011/5/13;; "Elapsed time: 1.278934 msecs"(defn...
この問題はちょっと気合が入った。まず、f(n) = n2 + an + b とすると、2階微分 f''(n) = 2 なので、nが1増えると、増分が2ずつ増えることになります。n2+n+41でできる数列はたしかにそうなってます。元 41 43 47 53 61 71 83 97 113 ...増分 2 4 6 8 10 12 14 16 ...n2-79n+1601 のほうは、元 1601 1523 1447 1373 1301 1231 1163 1097 1033 ...増分 -78 -76 -74 -72 -70 -68 -66 -64 ...ちゃんと2づつ増えてます。あと、こっちの数列を良く見てみると1601 1523 1447 ...省略... 47 43 41 41 43 47 ...省略... 1447...
循環小数の循環列の問題。なにしろわからなかったから、調べてみると、おもしろいねぇ。・循環列の長さは最大でも「最大の約数-1」らしい。 ってことは、素数だけ気にしてればいい。・素数nの場合、1/nの循環列の長さkは 10^kをnで割ったあまりが1である最小のkということで効率よく求められそう。今回の答えは、下のloopの length-prime-list に束縛したリストを10個ぐらい計算してみたところで分っていたので、本来はこれだけでOK。ちゃんとたしかめようとするとちょっと面倒ってところ。;;;; Problem 26 : 2011/5/11;; "Elapsed time: 63.869011 msecs"(def *prime-list* (atom []))(create-prime-list-under...
最初に1000桁になるフィボナッチ数は？って問題だけど、順に計算してみたらできたからそのまま。遅延評価の恩恵ですかねぇ。かなりclojureらしいソースになってんじゃないかと自画自賛。;;;; Problem 25 : 2011/5/10;; "Elapsed time: 0.373232 msecs"(defn fibo ([] (concat [1 1] (fibo 1 1))) ([x y] (let [next-num (+ x y)] (lazy-seq (cons next-num (fibo y next-num))))))(take 1 (drop-while #(< (first %) (expt 10 999)) (map list (my-fibo)...
順列の1000000番目はなに？って問題だけど、樹形図を考えてこんな手順にした。先頭に0があるやつは、 9! で 362880通り。1000000をこえない先頭に1があるやつも、 9! で 362880通り。1000000をこえない先頭に2があるやつは、 9! で 362880通りで、1000000をこえてしまうから、先頭は2次は20で始まるやつは、8! で 40320通りで1000000をこえない....って順に求めていく。;;;; Problem 24 : 2011/5/10;; "Elapsed time: 1.543492 msecs" (def fact-tree [362880 40320 5040 720 120 24 6 2 1])(use 'clojure.contrib.math)(loop [fact-tree fact-tree...
これはちょっと完全に撃沈しちゃってます。このソースは、結果を出すのに2時間もかかってる。とりあえずは、過剰数のリスト作成。;;;; Problem 23 : 2011/5/10;; step1 : "Elapsed time: 7139855.954877 msecs" (ouch!)(def *prime-list* (atom []))(create-prime-list-under 100000);; factors ;;(defn factors [n];; (foctors 12) => (2 2 3)(defn multi-plus [lst] ;; multi-plus : (2 2 2) -> (+ 8 4 2 1) (if (empty? lst) 1 (+ (apply * lst) (multi-plus...
こんな問題もあるんだねって感じ。ただ順に処理するぐらいしか方法はなさそうなのでその通りにやったんだけれど、文字->数字変換のところで、文字の16進表現から直接値を出そうかと思ったけど、そういうのに依存するのってどうなの？と思ったので、mapで表を作ったのが工夫といえば工夫かな。Javaの関数をいくつか呼んでる。;;;; Problem 22 : 2011/5/9;; "Elapsed time: 49.662736 msecs"(use '[clojure.contrib.duck-streams :only (reader read-lines)])(def char-val '{\A 1 \B 2 \C 3 \D 4 \E 5\F 6 \G 7 \H 8 \I 9 \J 10\K 11 \L 12 \M 13 \N 14 \O 15\P 16 \Q...
自分以外の約数の和がお互いの値になっているようなものの和を求める問題です。約数の和は、約数を求めて足すのかなと思って調べてみたら、公式があった。たとえば、ある数の素因数表示が a^n * b^mであったとすると、約数の和は (1 + a + a^2 + .. + a^n) * (1 + b + b^2 + .. + b^m) で表わせるんだそうな。 なるほどね。この式を展開してみるとたしかにすべての約数が出てくるよね。ってことで、1から順に数xを取って xの約数の和 y yの約数の和 z x = z かつ、x != y であるようなものだけ残してやるわけです。で、前に作った、素数のリスト生成と素因数分解処理を持ってきて、素因数分解の結果から、約数の和を求める関数を作った。;;;; Problem 21 : 2011/5/5;;"Elapsed time:...
やっと20番目まで来た。100!を計算して各ケタ足したんだけど、他のやりかたあるんだろうか。;;;; Problem 20 : 2011/4/27;; "Elapsed time: 7.363226 msecs";; momoise : from clojure.org(use 'clojure.contrib.math)(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)))))(defn fact [n] (if (= n 1)...
公式とかつかってもよさそうだったけど、順にやってみることにした。1年の最初の曜日を与えると、各月の1日の曜日を返す処理を作って、1900年1月1日から順に1日が何曜日か計算してます。もっと汎用的な処理を作るべきかなぁ。;;;; Problem 19 : 2011/4/27;; "Elapsed time: 0.492521 msecs" 1900-1900;; "Elapsed time: 1.898565 msecs" 1900-2000(def month-non-leap [31 28 31 30 31 30 31 31 30 31 30 31])(def month-leap [31 29 31 30 31 30 31 31 30 31 30 31])(defn leap-year? [year] (cond (not (zero? (rem year...
あとから巨大版が出てくるから、ここで工夫をしないとだめだよみたいなことが書いてある。これも動的計画法って感じでしょうか。一応、O(n)だし。;;;; Problem 18 : 2011/4/27;; "Elapsed time: 9.528585 msecs"(def org-data '((75) (95 64) (17 47 82) (18 35 87 10) (20 4 82 47 65) (19 1 23 75 3 34) (88 2 77 73 7 63 67) (99 65 4 28 6 16 70 92) (41...
