針金を曲げて直角三角形を作るとき、1種類しか作れないものを見つける問題です。
ピタゴラス数の問題ですね。
75個解いたので、Level 3になったよ。年内に100を目標にしてたんだけど、届かなかったな。...
この記事は、Clojure Advent Calendar 2011の20日目の記事です。
[[2012/1/6 23:00 再修正]]
最新のswank-clojure (1,3.4)では、windowsのパス名の扱いの問題が解決していました。1.3.4以降のものを使えば、特に何もしないで使えます。
[[2011/12/26 23:00 修正]]
最初の投稿では、結局うまくいかなかったのですが、いろいろ調べたり方法を変えたりしてうまく行きました。
これまで、Project EulerとかCode Jamとかやるときには、ClojureBoxを使ってました。ClojureBoxは、立ちあげるとすぐにREPLが使えて便利なのですが、だいぶ前にメンテナンスが終了していて、1.3になる可能性がありません。
自分で1.3に入れ替えるのもそれほど難しく...
数を構成する数字を階乗したものの和で作る数列の長さを求める問題です。
3 -(3!)> 6 -(6!)> 720 -(7!+2!+0!)> 50402 -...
これをそのままやっては終らないので、別の方法を考えたのですけど、思いつかないし、改善方法は思いついたので、それで実装。
2分ちょいかかります。...
これもファレイ数列の問題です。
数えるだけなので、他にいい方法もありそうですが、70の方法で正面から解いてます。
ところが、初めに作ったものは再帰で実装して作ったデータを全部持っていたため。OutOfMemoryになってしまった
で、今ちょうど読んでいる、Joy of Clojureで、遅延評価のクイックソートのことが出ていたので、それを使ったらできた。
ついでにJoCに出ていた、名前付き引数を使ってデータ定義をしなくてもいいようにしてみたけれど、あまりよくないかな。...
これもファレイ数列の問題です。なんか、もうちょっといい方法が見つかりそうだんだけれども断念。まあ、1分弱で解けたからいいということにしよう。ファレイ数列の個数は、※wikipediaの画像を勝手に拝借してみた。と表わせるとのとのこと。 ここにでてくるφ(m)は前に出てきた、オイラーのトーシェント関数。このまま計算すると、1から1000000までの数を全部素因数分解する必要があって、ちょっと大変なんで、最初は20分近くかかってしまった。でも、素因数分解の関数(factors)を前のやつからちょっと工夫してやったら、1分を切った。factorsはもうちょっと高速化できるかもしれない。百万までの素数を作るのに、5秒くらいかるので、それを入れたら1分を切れないねぇ。...
ファレイ数列の問題です。Wikipediaの解説を見たら、解きかたは一瞬でわかります。この数列でa/bとc/dが隣りあっている場合、その間に新しい分数が加わるとすると、それは2数の中間数 (a+c)/(b+d) であるとのこと。ということは、問題の場合、2/5と3/8 について、 - 中間数Mを求める。 - 中間数Mの分母が1000000を超えたら、1つまえのものが答 - そうでなければ、Mと3/8について同様のことを続ける。この通りの実装でございます。
This file contains bidirectional Unicode text that may be interpreted...
これもトーシェント関数の問題です。普通に考えたら解けないのが分っているので、ちょっと考えます。今回は、n/φ(n)を小さくするので、問題69で考えたことからすると、素因数の種類は少ないほうがいいということになります。素因数を1つにするには、nは素数でなくてはならないのですが、nが素数のときのφ(n)は、n-1なので、これがpermutationになることはないでしょう。ということで、素因数を2つとしてみます。少なくとも問題にある87109の素因数は2つなので、最悪、これが答になります。さて、素因数が2つということは、n=p1*p2ということになります。 また、そのときのトーシェント関数の値は、φ(n) = φ(p1)*φ(p2) = (p1-1)*(p2-1)なので、掛けたときに10^7未満になる素数の組を作って、φ(n)とnがpermutationになるかどうか確認します。20秒弱で解けましたけど、終了条件が分ればもっと速く解けるんじゃないかと思うんだけど、思いつかない。...
オイラーのトーシェント関数φ(n)の問題です。まずは、普通に解いてみましがやっぱり15分もかかります。大きな数の素因数分解そのものに時間がかかるのが問題です。答が出たので、まあこれでもいいかな...と思っていたのですが、帰りの電車で考えていたら、ひらめきまして、やり直しました。※ 今回、OpenOfficeの数式エディタで数式を作ってみました。nの素因数分解がのようにあらわせるとき、φ(n)は、で得られます。問題の答は、n/φ(n)を求めます。最初のやりかたは、ここで、nを素因数分解して、この式をそのまま計算するものでした。このあと、この式を眺めていて別の方法を思いつきました。n/φ(n)の値はこういう値です。nが消えるところがポイントです。この式の値を大きくするということは、分母を小さくするということです。それには、掛け合わされているかっこの中を小さくすればすればよくて、かっこの中を小さくするには、pを小さくすればいいということがわかります。さらにその数が沢山あればなおいいですね。ということで、求めるnは、小さな素因数を沢山持つものであることになります。とはいっても、同じ素因数をいくら持っていても、pは増えませんので、これは、小さい素数から順に素因数として持つものということになります。ようするに、2、3、5...と、小さいほうから順に1000000を超えないように素数を掛けていくと答が出るということです。ただ、このやりかただと、重複している素因数がみつからないので、実際にもとめる数はこの数の倍数ということになります。...
この記事は、Clojure Advent Calendar 2011の5日目の記事です。
Clojure界隈では、というより他でもWeb系のいろいろが沢山なわけですが、仕事がそっち系でないのでそういう指向があまりないのです。
Clojureは今のところ趣味で、主にProject Eulerとか解くのに使っているわけですが、以前、デスクトップアプリ作ってみたのでその時のことを。
環境
---------------------------------------
- マシン
自宅ではLinux機メインでやってますけど、仕事ではWin機です。
- エディタ
いつもはエディタとしてxyzzyを使っているのですが、Clojureを使うには環境があまり整備されていないし(自分でなんとかしろ？ですよねぇ。)、ClojureBoxってのがあるようなので、入れちゃうことにしました。
でも、もうメンテされていないので、1.3.0にしたければ自分でやることになります。...
ペル方程式の問題です。って言ってますけど、わからないので、情報を調べていてこの方程式がペル方程式という物だということを知ったんですけどね。解く方法はわかったんですが、残念なことに、どうしてこうすれば答が出るのか理解できてません。そういうの多いんですけど、ちょっと悔しいね。もとのペル方程式は、 x^2 - Dy^2 = ±1の形をしています。これの最小解を求めるには、二次体(Q√D)がなんたらかんたらで、結局は連分数√Dの連分数展開の結果を使ってごにょごにょであるとのこと。詳しくはペル方程式でググってください。やりかただけ書くと、まずは√Dの連分数展開を求めます。平方根の連分数展開は、小数点以下が必ずループするので、こんな形になります。{a0: a1, a2, ... an, ,a1, ...}で、この、n-1番目までの結果を分数にしたものの分子と分母がそれぞれxとyの最小解になっているんだそうな。連分数展開は前の問題で作ったのがあるけど、ちょっと改変が必要。あと、結果は場合によっては、x^2...
魔方陣系の問題です。条件を見つけるためにちょっと試していたら、その場で答が出ちゃったという初めての経験をしました。ですけど、勉強のために、コードは書いてみました。魔方陣のセオリー通り、穴は図のA(外周)とB(内周)の様に2種類に分けられます。一列に並んだ数の合計を同じにするということは、 A1 + B1 + B2 A2 + B2 + B3 A3 + B3 + B4 A4 + B4 + B5 A5 + B5 + B1この5つが同じになるということです。これをXとすると全部の合計は、5X ということになります。次に、上の式から全部の合計は、 ...
18の問題と同じで、データが大きくなった問題。18を解いたときにもそれなりに考えて作ったんだけれども、電車に乗っているとにきいい方法を思いついたので、実装してみた。ライン数で10分の1くらいになったんじゃないかな？基本的な考えかたは18を解いたときと同じ。この問題は、最大の数だけわかればいいので、上からたどっていって、合計が大きくなるものを見付ければいい。たとえば下のような場面では、 o A B o o o X o oXの値に影響するのはA、Bの2つのみ。 それぞれAとBまでのルートの和が大きくなる方からXに来るのが大きいルート。例題の場合1: 32: 7 43: 2 4 64: 8 5 9 32列目は、それぞれ上が3なので、10と7。3列目。 10 7 /\...
eについて、ある段階まで連分数展開したものを分数表記したときの分子の数字の問題。これは、問題57で使った公式ですぐに解ける。問題57ではは√2だったけど、こんどはe。この方式は、連分数展開したときの 数列aを求める必要がある。64の答えを使ってもいいのだけれど、eの連分数は、 {2:1,2,1,1,4,1,1,6,1,1,8,1,....} になることが分っているので、これをつかう。a0 = 2 、このあとa1 = 1, a2 = 2, a3 = 1,a4 = 1, a5 = 4, a6 = 1,a7 = 1 a8 = 6, a9 = 1,のように規則的に並んでいる。これを、a[n] についての場合で分けるとこうなる。n=0 のときは2nを3で割った余りが2のときは ((n+1)/3)*2それ以外は1これで実装した。
...
平方根の正則連分数展開のループの繰り返し数の問題です。問題文にある通りに連分数展開をしていく処理を作りました。連分数にする手順は、以下の通りです。初めの数を以下の形にします。 √X + M-------- N最初は、M=0、N=1になります。これを帯分数にします。 √X + M'a + --------- Nになります。真分数の部分を連分数にするために逆数にします。 1a + ----------- N --------- √X...
XのN乗を考えたとき、Xの桁数nがNと同じになるような、ものはいくつあるかという問題。最初、なんのことかよくわからなかった。1の場合は、 1^1 =1、1^2=1、1^3=1 .... となって1^1だけ。2の場合は、 2^1 =1、 2^2=4 、 2^3=8 ... となってこれも2^1だけ。おやー。 で、昼休みが終り。次の日、あっと思って、基数を動かして書いてみた。1^1=1、2^1=1、3^1=3、.... 9^1=9、10^1=10 ... となって、1から9。1^2=2、2^2=4、3^2=9、4^2=16、5^2=25、.... 9^2=81、10^2=100 ... となって、4から9。考えてみれば、Xが10のとき、10^nは、かならずn+1桁になってしまうので、Xは1桁の数でしかありえない。この先を手で計算してもできそうだったけど、プログラムにしてみた。...
同じ数字でできている5組の3乗数をみつける問題。これも全数アタックHashを使って分類する方法を採った。3乗数を作って、含まれている数をリストにしてソートしたものをキーにして、Hashに入れる。Hashに入れたときに、5つたまったらそれが答え。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
...
四桁の3～8角数を任意の順に並べて輪を作る問題。全くいい方法を思いつかなかったので全数アタック。・ 4桁のX角数を全部リストアップしておく。・ 3～8の数の順列を全部リストアップしておく。・ 順列すべてについて、あてはまるものがあるかどうかを探す。・ 途中でみつかっても中断せず、すべて探すだいぶ長くなってしまった。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor...
どの2つを取ってつないでも素数になる5つの素数の組をさがす問題解くのにすごく手間どった。なにしろ計算が終らない。ロジックに問題があるのだとばかり思っていたら、そうではなくて、素数判定の考慮漏れだったという情無い落ち。といっても、解くのに15分以上かかってしまっているので、情無いのには変りない。全数アタック以外の方法を思いつかないし、出た答えを見ても、うまい枝刈りの方法も思いつかないので、現状ではこれがほぼベスト。8けた以上の数の素数判定が早くなれば、かなり減りそうだけれど、1分にはほど遠い感じ。方法はこんな感じ。素数の列を作る。2と5は題意から除外する。3 7 9 11 13 17 ......1こずつ取ってきて、組をつくる。そのときこういうことをする。a 自分だけの組b もともとあった組c もともとあった組すべてに自分を加えた組できたものを、要素の数の多い順に並べる。初めは(3)。...
勢いに乗って、予選の問題Cを解いた。今やらないと、しばらくできないような気がしたので。この問題、当日は時間が無くて手をつけられなくて、終了後に全数アタックで実装してSmallだけ解いた。でも、そのやりかただと例題の最後のやつ1つも解けないわけで、全面みなおし。かかった時間は、70msec弱。 上々かな。何個か手で解いてみて、数字を並べて眺めていて思った。もとの数から直接解答の数を作れないかな。これでほぼできたに等しい。虫食い算を解くようなもの。下の桁から繰り上がりとかを考えなから条件を詰めていって埋めていく。情報が少ないので、aとbを決定することはできないけれど、1のビットの合計を求めるのに支障はない。考えかた- Nのある桁が1だったときと0だったときのaとbの対応する桁がどうなるべきか、下の位からの繰り上がりの有無を加味して考える。表にしてみる繰り上がり N:0...
Clojure Programmingを予約してあったんだけど、発売日また延期されちゃって、どうやら年内には手に入りそうもない。そもそも、最初に買ったプログラミングClojureはいい本なのだけれども、対応バージョンが古いのと、もうちょっと真髄みないなものに触れたいと思って、すでに発売中のThe Joy of Clojureと比べて、表紙の絵と新しさでClojure Programmingを選択していたわけだけれども、もう待てません。予約をキャンセルして、The Joy of Clojureを買っちゃいました。届きました。うーん。やっぱりこの表紙は怪しい。まだ、本文は1ページも読んでない。LOLを返したら読みはじめます。評価が高い本なので、期待してます。Clojure Programmingは、来年になって、評価がよかったら買います。1.3のことが...
Code Jam Japan予選のB問題。 ふと思い出したときにちょこっと考えていたりしたんだけど、やりかた思いついたので、やってみた。 解けた。もうちょっと効率を上げたりできそうだけど、500msちょっとで解けたんだからまあこれでいいでしょう。予選当日に考えた方式は以下の通り。結果としてこの方式で解いた。戦略- 今日何を飲むかではなくて、このコーヒーはいつ飲むのかを考える。- 満足度の高いコーヒーから飲む日を決めていく。- 飲む日はどうやって決めるのか？たとえば - 期間が5日 - 満足度(S)10 賞味期限(T)が3日のコーヒーAが2杯(C) -...
先週の週末、娘が図書館で本を借りたいというので、ついていきました。家から数分のところにある南部図書館という小さな出張所なので、品揃えは貧弱です。これまでも、買い物帰りにぶらっと寄ったことはあったのですが、雑誌を読むくらいのことしかしてなかったのですが、一回りしてみることにしました。コンピューター関連書籍の棚を見てみると、お約束のWordやExelの本に混って、「Let Over Lambda」が置いてあるじゃありませんか。 ちょっとびっくり。借りちゃいました。今、仕事の行き帰りに読んでいいて、1/3くらいまで来ました。情報によれば、後半に山場があるそうなので、まだ、感想を言うのは早いのでしょうが、「マクロはこう使え」っていう本ですね。僕にはやっぱりマクロは難しいし、今一つピンとこない。よくある手法などを定型で効率よく扱えるようにできるのはとても便利です。そして、ライブラリとしてくくり出すよりも、はるかに自由度が高いのはよくわかります。新しい考えかたなんかむうまく実現できるし、さらに、DSLという概念を頭に入れてとりかかると方向性を見失わずに済む。でも、ちょっと、Common...
10月24日にJohn McCarthyさんが亡くなりました。僕が今この仕事をしているきっかけを作ってくれた人です。ありがとう。そのきっかけを久し振りに探してみました。ありました。 1983年5月のサインス誌です。これを見つけるまで、マーチン ガードナーさんの連載の「数学ゲーム」だったと思ってましたが、ダグラス ホススタッターさんの「メタマジック ゲーム」でしたが、1回半ほどでLispを紹介していました。それまでBASICしか触ったことがなかったので、こんな言語があることにかなり衝撃を受けたのを覚えています。このあと、大学の図書館で本を探したり、処理系を手に入れようとしてあちこち探しまわったりいろいろしました。...
incanterのことを調べていて、こんなのを見つけた。An Illustrated guide to multi-core parallelism in Clojureだいたい1年前のポストなんだけど、Java1.7で予定(当時は)されていたFork/Joinを使った新しいClojureの並列処理機能についての解説のスライドの紹介記事。このスライドはpmapの動作原理や、それに対する新しいpmap(pvmap)がどうよくなっているかなど書いてあって、Javaに疎い僕にはとても勉強になった。ところで、このスライドはこんな文章で始まっている。Concurrency is commonly mistaken for parallelism, but the two are distinct concepts. Concurrency is concerned with...
Code Jam Japan予選のA問題。当日終ってから考えたロジックを実装してみた。結果は上でき。 ということで、解説です。その方法は、逆順でのトレース。知りたい場所のカードが初めにどこにあったのかを考えるわけ。図を書いたので、貼りつけ。ソースはこれ
This file contains bidirectional Unicode text that may be interpreted or compiled differently...
今日は環境を調えて、6時間みっちり Code Jam やりました。結局 AとBのSmallだけしか時間内にできなかった。Cの問題はそれほど時間がかからなそうだったけど、順番に解くのにこだわりたくて、でも、結局だめだったけど。時間切れ後に、いちおう、CのSmallも解いてみた。次回は、1つぐらいLargeが解けるようになっていたい。問題が公開されているんで、一応僕の書いたコードを。あら。 Gistって修正すると、貼ったやつも変っちゃうんだね。便利なような不便なような。Gistベースで修正してるので、随時更新されます。前のを見たい人は、下の方のリンクからGistに直接アクセスしてくださいです(10/7)問題Aです。最初は書いてあるとおりに解いた。Smallだと数秒で解ける。修正版は、Largeでも250ms程度で解けた。 完了。
...
この週末にProject Eulerのサイトのデザインが変更になりました。Googleの変更に似た感じになっています。最近のトレンドなんでしょうか。僕はまだレベル2なんですけど、レベルを表わすマークも変更されてます。僕は前の立体の方が好きでしたね、だんだん角が増えていくので、ぱっと見てどんなだかわかるようになってました。 新しいやつは、上下が良くわからなくなってます。 それが狙いなんでしょうね。最近別件で忙しくて手をつけてませんけど、そろそろ涼しくなってきたことだし、再開しましょう...
前にclojureのmemoize関数の動きがだめだっていう話を書きました。このポストも関心のある方がいらっしゃるようなので、ちょっと追加の情報を。べつに目新しいものではありませんけど、日本語の情報が無いみたいなので。さて、 何がだめなのかをくりかえすと、再帰で定義されている関数をmemoizeを使ってメモ化しても、内部での 再帰呼び出しにメモ化が効かないという現象です。実はこれ、clojureの1.2からのことで、1.1では問題なく動きます。 これは、以下に出てくる解決策から考えると、1.2で、関数の名前の解決方法に変更があったためだと思われます。以下ちょっと長くなります。例によってフィボナッチ数を求める関数を再帰を使ってで定義して、1.1環境で実行してみます。user> (clojure-version)"1.1.0"(defn fib...
clojure関連のサイトを見ていたら、ソースコードの表示にgist使っているような感じのものがあった。調べてみたら、gistでそんな機能を提供してるらしい。 しらなかった。んで、使ってみた。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more...
前に書いたreduceのポストのトラフィックが意外に高くて気をよくしたのでもうちょっと書いてみる。reduceの使いかたはその1 (reduce f coll)その2 (reduce f val coll)fは2つの引数を採って1番目の引数と同じ形の値を返す関数。どちらの場合でも、collの要素を一つずつ2番目の引数にしながら、collが無くなるまで、fを呼び出していくけれど、一番最初に違いがある。その1の書式では、最初の引数は、collの1番目と2番目の要素になる。ということは、reduceの結果は要素と同じ形のものしか作れないことになる。しかし、その2では、最初の引数はvalと1番目の引数になる。これはreduceの結果がvalと同じ形になることを意味しているので、好きな結果を得ることができるのだ。さて、こんなデータがあるとする。(def sample-data...
自宅のパソコンが壊れちゃったので、新しいノートPCを買った。最近はいいやつが安く買えるので、思いきってCore i7のを買ってしまった。で、前に仕事パソコンでやった並列処理の速度を測ってみた。新PC Core i7 2630 クロック 2.00GHz コア数 4 MEM: 4GB旧PC Core?2 Duo SL9300 クロック 1.60GHz コア数 2 MEM: 2GBさらにi7はハイパースレッディングで仮想コアがあるのでOSからは8つのコアに見える。処理は 2の10000乗を10000個計算して、下2桁の合計を求めるもの。まずは単一スレッドでの実行。コードはこれ。(let...
ポツポツとPEを解いてきたのですが、思いついたなりに処理を作っていっているので、ロジックの先については、あまり外の情報を見ていない。それで、こうやってブログに上げるときにコードを見直してみたりすると、なんか、もっといいやりかたができなかったのかなぁとか思って、ちょっとWebで調べてみると唖然とすることが何度もあるわけです。しかも、contribの中にあるよって情報は、さらに愕然とする。でも自分で探そうとすると、grepしてみようにも単語が出てこないのでうまく探せないし、上から順に見ていくしかないとなったら、面倒になってやっぱり自分で下手な処理を作ってしまう。でも、そろそろちゃんと一通り見ておいたほうがよさそうな気がしてきたので、ちょっとここいらで手を止めて、いろいろ調べてみることにする。ということで、PEは少しお休み。60番で詰ってしまった言い訳でも...
reduceの使いどころ(その2も書きました)reduceって全部足すとかそんな使い方しかしてなかったんだけど、コレクションを全部なめて何かをつくる。という捉えかたをするツールであると捉えると、かなり強力なツールであることがちょっとわかってきた。たとえば、下の2つの処理は同じことをしている。 (reduce #(conj (* 2 %1) %2) [] [1 2 3]) (map #(* 2 %) [1 2 3])これならmapでやればいいわけだけれども、でも、逆に言えば、reduceの方がやりたいことを細かく指定できるということなわけ。ここでは、「2倍したものをベクターにつっこむ」ということを指定している。ここは好きにいじることができるので、いろいろなことができる。特にmapを作るような場合に有効なのではないかと思う。たとえば、下のような処理。ポーカーの問題のときに作ったんだけど、個数の多い順に数字を並べたいわけ。単目的ならもう少しすっきりできたと思うけど、group-sameがあったからこうなってる。(defn...
PE 59XORで暗号化された暗号を解く問題。コードは長いけどたいしたことやってない。キーは3文字だと分っているので、暗号文を3文字ずつで分解して、1番目 2番目 3番目だけからなるリストを作る。それぞれのリストは同じ文字でエンコードされているので、元の文章の文字の出現頻度と同じ頻度になっているはず。リストに含まれる数を出現頻度順に並べると先頭が最頻の文字。さて、英語の文章の最頻文字は「e」、かというとそうではなくて「スペース」です。スペースでデコードしたものを出してみると、それらしきものが現われました。文章をデコードする関数も作って調べてみると当り。;;;; Problem 59 : 2011/6/22;;"Elapsed time: 37.556729 msecs"(defn group-same "Split into same value group...
数字をぐるぐる四角に並べたときに、中心から角に向う線上にある数が素数である確率が10%を下まわるのは何周並べたときかという問題。n周めの角にくる数字は、nで表わせるので素数かどうか判定する。あと、n週での対象となる数の数もnで表わせるので計算して、割合を出す。;;;; Problem 58 : 2011/6/21"Elapsed time: 3646.419866 msecs"(defn corner-set [n] (let [side-len (- (* n 2) 1) bottom-right (expt side-len 2) bottom-left (- bottom-right (- side-len 1)) top-left (- bottom-right (* 2 (- side-len 1)))...
2の平方根の連分数を1000段まで順に展開したときの分数表現の分子の桁数がが分母の桁数を超えるのは何回あるかっていう問題。連分数の展開には一般項の公式があるのでそれをあてはめて計算。と、ここで、分母と分子の式が漸化式になっているんだが、大きくなるとメモリが足りなくなるので、memoizeを使ってメモ化したのだか効果なし。なんでだーって調べて分ったのがちょっと前のポスト。defn-memoを使って再定義したらちゃんとできた。;;;; Problem 57 : 2011/6/21;; "Elapsed time: 4859.538293 msecs"(defn cf-seq [n] (if (zero? n) 1 2))(defn cf-numerator [n] (cond (zero? n) 1 (= 1 n) (cf-seq...
1の1乗から100の100乗までの数で、各桁の数を足したものが一番大きくなるものを求める問題。そのまま計算したのでございます。;;;; Problem 56 : 2011/6/20;; "Elapsed time: 15482.925064 msecs"(reduce max (for [a (range 1 100) b (range 1 100)] (reduce + (num-to-list (expt a b))))...
ある数に対して逆順にした数を足すという操作を繰りかえしたとき、何回か後に回文数になる数を求める問題。そのまま実装。あ、最初の数が回文数でもそれはあてはまらないという条件があるので、ループの最初の1回だけ生で計算してる。;;;; Problem 55 : 2011/6/20;; "Elapsed time: 9821.708625 msecs"(defn reverse-and-add-if-not-palindrome [n] (let [revnum (list-to-num (reverse (num-to-list n)))] (if (= revnum n) true (+ n revnum))))(defn lychrel? [n] (loop [depth 1 num (+ n (list-to-num (reverse...
ポーカーの勝敗を判定する問題。やたら長いけど身は少ない。まず、ファイルを読み込んで、扱いやすくする。 [[8 :club] [10 :spade] [13 :club] [8 :heart] [4 :spade]]役を判定する関数(rank-hand)を使って、役で判定。同じ役ならのところがちょっと考えた。結局、同じ役なんだから、手札を枚数の多い順に並べて、 2 3 1 3 1 3 3 -> (3 3 3 3) (1 1) (2)1つだけにして (3 3 3 3) (1 1) (2) -> 3 1 2頭から大小比較すればいいということに気づいた。ところで、A,1,2.3.4 をストレートと判定していないことに、今、気づいたんだけど、答えはあってたみたい。;;;; Problem 54...
100桁以下の数について、含まれる数字を幾つか選んで作られる新しい数の種類が百万個を超えるのは幾つあるかという問題。言われた通りに計算しちゃったけど、nCrの答えって、rがnの真ん中にあるときが極大だから、それを使うともうちょっと速いはず。やらなかったけど。;;;; Problem 53 : 2011/6/16;; "Elapsed time: 473.81832 msecs"(defn fact [n] (reduce * (range 1 (inc n))))(defn composision [n r] (/ (fact n) (* (fact r) (fact (- n r)))))(count (filter #(> % 1000000) (for [n (range 2 101) r (range 1 100) :when...
1から6までの数を掛けてできる数が同じ数字で構成されている数字を見つける問題。-6を掛けても桁数が変らないということは、たとえば、3桁なら166まで、 6桁なら16666までということになる-最上位が1なので、1から6倍した場合、最上位の数は全て異なる数になるので、 桁数は6以上のはず。あとは全数チェック。答を見て、「あー。なんだよ。これかよ」と思った。 ちょっとくやしい。;;;; Problem 52 : 2011/6/15;; "Elapsed time: 3178.80848 msecs"(defn same-digits? [n m] (= (sort (num-to-list n)) (sort (num-to-list m))))(defn pe52-end-num [digit] (+ (expt 10 digit)...
素数のうち、表われる全ての同じ数字をいれかえてできる組を作ったとき、8つ素数の組ができるものを探す問題。* 8つの組ができるということは、置き換えるところに 10個の数字(0123456789)のうちの 8つを入れることができなければならない。このことから、- 1の位は入れ替え対象にならない。 <== 10個のなかに偶数が5つありすべて取り除くことができない。 1の位が偶数のとき2以外は素数ではない。- 入れ替える数は1つではない。 <== 10個の数字には3を法とすると0,1.2になるものがそれぞれ3つ以上あるため、 2つを取り除いても、かならず0,1.2になるものが含まれる。 また、対象の数を構成する残りの各桁の数の和は、3を法とすると0,1.2のいずれかになる。 ...
100万以下の素数で、もっとも大くの連続する素数の和で表わされるものを求める問題。そのまま解いた。素数のリストについて、初めから順に足していって、結果が素数になるかどうか都度判定する。素数でなくなったら、素数のリストの先頭をとりのぞいてまた同様のことをする。素数でなくなったときの情報を、前の結果と比べて結果を更新する。時間かかりすぎ。;;;; Problem 50 : 2011/6/14;; "Elapsed time: 276190.732342 msecs"(defn longest-seq [coll max-val] (loop [forward-coll [] rest-coll coll max-seq []] (if (empty? rest-coll) max-seq (let [next-foward...
同じ間隔で並んでいる3つの4桁の素数で、同じ数字で構成されているものを求める問題。まず、4桁の素数を全てについて、構成する数字をキーにしたmapに入れる。同じ数字で構成されているものは同じキーに関連付けられる。 ([1 4 8 7] , (1487 4817 8147))のような感じ。そして、その中の3つ以上の数が入っているものについて、等間隔にならんだ3数があれば取り出す。;;;; Problem 49 : 2011/6/14;; "Elapsed time: 93.160443 msecs"(defn seq-of-3 [coll] (for [a coll b coll c coll :when (= (- (* b 2) a) c) :when (< a b) ...
1から1000までの数nについてnのn乗の和を求める問題。そのまま解いただけ。最後の10桁だけ求めればいいので、足す前に11桁め以上を消してます。;;;; Problem 48 : 2011/6/13;; "Elapsed time: 217.941386 msecs"(reduce + (map #(rem (expt % %) 10000000000)(range 1 1001))...
4つの連続駿数で、全てが4種類の素数に因数分解できるようなものをみつける問題。1から順に全ての数を素因数分解して出てくる数字の種類を数え、もとの数とのペアにしたデータを作る。あたまから順に4つずつ取って、全部の数字の種類が4になった最初のものが答え。factorsは前に作った、素因数分解したものをリストで返す関数。時間かかりすぎ。;;;; Problem 47 : 2011/6/13;; "Elapsed time: 162902.866705 msecs"(take 1 (filter (fn [coll] (every? #(= 4 (first %)) coll)) (partition 4 1 (map #(vector (count (distinct (factors %)))...
奇数の合成数のうち、「素数と、何かの2乗の2倍の和」で表わされない最小の数を求める問題。なんか、全然エレガントじゃないけど、素数じゃない奇数について、その数以下の素数を引いた残りが平方数になっているかどうか判定した。;;;; Problem 46 : 2011/6/13;; "Elapsed time: 841.523433 msecs"(defn square? [n] (= (sqrt n) (int (sqrt n))))(defn not-prime-plus-double-sq [n] (every? false? (map (fn [pnum] (let [tstval (- n pnum)] (and (even? tstval) ...
三角数で五角数で六角数であるようなもので40755の次の数をみつける問題。三角数かどうかと五角数かどうかの判定は作ってある。六角数を順に作って三角数で五角数かどうかの確認をした。hexagonal?は使わないけど、作っておいた。;;;; Problem 45 : 2011/6/13;; "Elapsed time: 248.191879 msecs"(defn hexagonal [n] (* n (- (* 2 n) 1)))(defn hexagonal? [n] (zero? (rem (+ 1 (sqrt (+ 1 (* 8 n)))) 4)))(take 3(filter (fn [x] (and (triangle-num? n) (pentagonal? n))) (map hexagonal...
2つの五角数の和も差もまた五角数になるような組のうち、最小のものを求める問題。基本的にしらみつぶし。n番目の五角数について、(n-1)番目以前のそれぞれの五角数が条件に合うかどうか確認して、最初にみつかったものを答えにしている。五角数かどうかの判定は、n番目の五角数をxとするとx=n(3n-1)/23n^2-n-2x=0n=(1+sqrt(24x+1))/2だから、24倍して1を足したものの平方根に1を足したものが2で割りきれるかどうかで判定。;;;; Problem 44 : 2011/6/13;;"Elapsed time: 10744.530939 msecs";;;; Memoized!!??;; "Elapsed time: 38270.006104 msecs" (use 'clojure.contrib.math)(defn...
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...
文字のアルファベット順での位置(A=1として)をその文字の値として、単語の文字の値の和が三角数になるものの個数を数える問題。三角数かどうかの判定は、n番目の三角数xの式を変形してx = n(n+1)/2n^2 + n - 2x = 0n = ( 1 +/- sqrt(8x + 1)) / 2負の数にならないから、n = ( 1 + sqrt(8x + 1)) / 2ということで、8倍の平方根に1を足したものが2で割りきれるかどうかで判断します。文字->数値変換は、文字コードを使うといいのかもしれないけど、換算表を使った。ファイルからの読みこみのところは、今見るとwith-openの使いかたが間違ってるけど、動いたのでこのまま。;;;; Problem 42 : 2011/6/9"Elapsed time: 22.138288 msecs"(use '[clojure.contrib.duck-streams...
