ブログ移転しました
ザネリは列車を見送った ⊂（ﾟДﾟ⊂⌒｀つ≡≡≡
HaskellでProject Euler(Problem 7～9)
おいらのオイラー。
Problem 7. 10001st prime
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
最初の6個の素数は 2, 3, 5, 7, 11, 13 であり、6番目の素数は13だということが分かる。
10001番目の素数を求めよ。
3～の奇数を、isPrime で素数かどうか判定する。
isPrime はすでに素数として判定された list の中の検査する値の
平方根以下の値で割り切れるかどうかを検査している。
はじめに prime' 3 [] ではなくて prime' 3 [2] と素数のリストにあらかじめ 2 を入れておいて
length list >= n = list で終わらせることも考えたが、
m が奇数のみであるのに isPrime で m `mod` 2 /= 0 も実行するのは無駄かなぁ、と思い、
n=1 の場合のみ特別扱いとした。
最適化オプション「-O」をつけてコンパイルして5秒くらい…。
もう少し速くならないものかとしてみたものがこちら。
すでに検査済みの素数の最大値側から順に割り切れるか検査するより
最小値側から順に検査したほうが割り切れる値が見つかるのが早いと思い、
素数のリストを保持する list と、他の素数で割り切れるか検査するための list' を分けてみた。
list は降順、list' は昇順。
これは速い。ghci 上でも2秒くらい、最適化オプションをつけてコンパイルすると1秒くらい。
うーん…しかし見るからに無駄そうな処理をしていて、本当にこれでいいものやら。
list'++[m] も要素数が大きくなれば遅くなるように思うんだけどな。
Problem 8. Largest product in a series
Find the greatest product of five consecutive digits in the 1000-digit number.
以下の1000桁の数字の中の5つの連続する数の積の最大値を求めよ。
(問題文に掲載されている1000桁の数字は省略)
愚直にやるとこうなった。
1000桁の数字を文字列にし、最初の5文字を1文字ずつ数値化して掛けた値と
現在保持している最大値の大きいほうを選んで再帰する。
any (== '0') num はやってもやらなくても実行時間に差が見られなかったけど、
5つの数字の中に0が含まれていれば積は必ず0になるので
積を求めて現在の最大値と比較する処理を省くために入れてみた。
Problem 9. Special Pythagorean triplet
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
ピタゴラスの三項とは、a < b < c のとき、
a^2 + b^2 = c^2 を満たす3つの自然数の組み合わせである。
例えば 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である。
a + b + c = 1000 を満たすピタゴラスの三項がちょうど一つだけ存在する。
abc の積を求めよ。
とりうる a と b と 1000 - a - b の組み合わせをリスト内包表記で作って、
その組み合わせがピタゴラスの定理に当てはまるかどうかを検査する。
組み合わせを作ってから pythagorean' を再帰させるのではなくて、
組み合わせを作る段階で検査すればいいのでは、と思い書き直したのがこちら。
ぬおお…えらく短くなってくれた…！
(やっていることの分かりやすさはひょっとしたら9-1のほうが分かりやすいかもしれないけど…)
9-1, 9-2 ともに、ghci 上では1秒くらい、
最適化オプションつきでコンパイル後だとほぼ一瞬で実行が終わる。
HaskellでProject Euler(Problem 5 補足)
また [1..100]＞＞=pen さんに色々アドバイスをいただいた。
Problem 5 修正版1
「リストの中の自分以外の要素で自分を割り切れる数があれば除外」という
自前の処理で divisors を作っていたが、19, 18…1 のリストの前半部分とした。
(確かに結局自前の処理で欲しかったリストはこれだけで得られた)
また、candidates の最後の値 (foldl1 (*) divisors) は product divisors としたほうがいいが、
nの値によっては (n * 2) > (product divisors) となり、
candidates が空リストになってしまうので、
終了値を指定しない無限リストとすることにした。
Problem 5 修正版2
やっていることはほとんど同じだけど、filter 関数で条件に該当する値のみ取ってきている箇所を
リスト内包表記で書くとこうなる。
最適化オプション
今まで ghci でhsファイルをロードして実行確認していたが、
ghc -O hoge.hs と最適化オプションをつけてコンパイル後に実行すると
速くなる場合が多いようなので、
今回からコンパイル後にも実行確認することに。
euler5-3.hs, euler5-4.hs ともにコンパイル後では1秒程度で終わってくれる。
HaskellでProject Euler(Problem 4～6)
おいら頑張るよ！
何だか問題の難度にだいぶムラがあるような…
今回は問題自体易しかったのか、Haskellだから簡単に書けたのか、
気づいていないだけでもっと効率の良い方法があるのか。
Problem 4. Largest palindrome product
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
回文数はどちらから読んでも同じ値である。
2桁の数の積からなる回文の最大値は 9009 = 91 × 99 である。
3桁の数の積からなる回文の最大値を求めよ。
リスト内包表記でn～mの全ての組み合わせの積のリストを作り、
それを降順にソートしたリストに対し、
isPalindrome 関数で回文であるかどうかを検査する。
isPalindrome ではまず数値を文字列に変換し、文字列の長さの半分の値を取り、
先頭から半分までの文字列と逆順にしてから先頭から半分までの文字列が一致すれば回文とみなす。
元の文字列と逆順にした文字列が一致すれば回文とみなす。
降順にソートしているため、isPalindrome でフィルタしたリストの head を取れば回文の最大値となる。
始め、sortBy (\x y -> compare y x) でソートせずに積のリストをそのまま使用して
isPalindrome でフィルタした後 head ではなく maximum で最大値を取得していたが、
そのほうが若干遅いようでこのようになった。
愚直なやり方だったけど、これで事足りるような。パフォーマンスも申し分無い。
Problem 5. Smallest multiple
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
2520は1から10の全ての数値で割り切れる最小値である。
同じように1から20の全ての数値で割り切れる最小値を求めよ。
この問題、Haskellでは最小公倍数を求める関数lcmがあるので、ワンライナーで書ける。
foldl1 lcm [1..20]
しかし、これではあんまりなので、泥臭く自分で書くことに挑戦。
まず、1～19までのリストを作る。
(nを20ずつインクリメントして再帰するため、リストから20を省ける)
次に、リストの中の自分以外の要素で自分を割り切れる数があれば、それを除外したリストを作る。
(18で割り切れるということは2でも3でも6でも9でも割り切れるので、
これらの数は検査対象外として良い)
そうして作ったリストの全ての要素で割り切れる数が出現するまで20から20ずつインクリメントして
smallestMultiple'を呼び続ける。
全ての要素で割り切れる数が出現すれば、その値を返す。
期待通り動いてくれてはいるが…これは遅い…20秒くらいかかる。 少し修正してこうなった。
divisors は前のバージョンと同じように
自分以外の要素で自分を割り切れる数を除外したリストを作っている。
異なるのは reverse しているところだが、これによってけっこうパフォーマンスに差が出る。
candidates は答えの候補となる数値のリスト。
20 から 20 ずつ増加し、最大値は divisors を全て掛けた値としている。
これらのリストを作り、candidates の中からdivisors 全てで割れるもののみフィルタし、
その先頭を解答としている。
19で割れるもののほうが少ないため、reverse して先に19から検査したほうが速くなるのかな。
だいぶマシにはなったけど…それでも8秒くらいかかる。
が、今のところこれより良い案が思いつかなかった…。
Problem 6. Sum square difference
The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)^2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
最初の10個の自然数の二乗の和は 1^2 + 2^2 + ... + 102 = 385、
和の二乗は (1 + 2 + ... + 10)^2 = 552 = 3025、
これらの数の差は 3025 - 385 = 2640 である。
最初の100個の自然数の二乗の和と和の二乗の差を求めよ。
ぬーん、何のひねりも無く書いて、実行もほぼ一瞬で終わるので
これでいいか、という感じだが…まだ改善の余地、または別解があるだろうか…。
HaskellでProject Euler(Problem 3 補足)
前回の記事に対して Twitter でアドバイスをいただき、色々と改良できた。
Problem 3 修正版1
isPrimeFactor だった場合、n が m の二乗でも割れるかもしれないので、
m で割れるだけ割るため divide 関数を用意した。
divide 関数では、divMod を使用して商と余りを一度に出している。
また、 n を素因数分解するとき、2 ～ sqrt(n) までの数字を調べればよいので、
再帰の終了条件を n < m ^ 2 = n:list とした。
(参考:素因数分解は２～平方根まででOK)
Problem 3 修正版2
さらに修正したバージョンがこちら。
再帰の終了条件になったら n を加えたリストを返して、その head を取っているので
そもそも素因数を list に持ち続ける必要がなくなったため、引数から除外。
isPrimeFactor 関数で検査しなくても、n が m で割り切れない場合、divide 関数が n を返すので
isPrimeFactor 関数を除外。
divide 関数で割れるだけ割った結果 1 になった場合の m はその時点での唯一の素因数なので、
再帰の終了条件に divided == 1 = m を追加。
HaskellでProject Euler(Problem 1～3)
Haskellでプロジェクトオイラーに挑んでみる。おいら頑張るよ。
きっとおいらの数学力やHaskell力が低いせいだろうけど、
何だかロジックは正しいはずだけど値を大きくすると処理時間がクソ遅いから
速くなるよう部分的に書き直すことに苦労した印象が。
Problem 1. Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
10未満の自然数のうち、3 または 5 の倍数のものは 3, 5, 6, 9 でがあり、これらの合計は 23 になる。
1000 未満の 3 または 5 の倍数の合計を求めよ。
少し汎用性を持たせたつもりで、何の倍数かも渡せるようにしてみた。
リスト内包表記で muls に渡した値のいずれかで割り切れる値のみのリストを作り、foldl1 で畳み込む。
もっといいやり方があるかもしれないけど、あまり悩まずすんなり解けた、かな。
Problem 2. Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
フィボナッチ数列の項は前の2つの項の和である。
最初の2項を 1, 2 とすれば、最初の10項は以下の通りである。
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。
まず、そもそもフィボナッチ数列を求める関数を作るのに苦労した。
はじめ何も考えずに
fib 0 = 1 fib 1 = 2 fib n = fib (n-2) + fib (n-1)
としていたが、これだと数が大きくなりにつれ遅くなり、400万はとてもじゃないけど無理そうだった。
一旦諦めてHaskellのフィボナッチ数列生成関数をこの辺りを参考にしたコピペ版がこちら。
期待通り動いてくれてはいるが、これは自力では思いつかなそう。
何とか自分で考えて書いたバージョンがこちら。
fibList 関数を再帰的に呼び出して、逆順のフィボナッチ数列のリストを作っている。
リストの先頭2要素(fstElem,sndElem)を足して次項の値を求めて、それをリストの先頭に足していく。
引数のパターンマッチで、リストの先頭要素・第二要素・リスト全体を使いたかったのでasパターンを用いている。
作られたリストの先頭を取ると、その項のフィボナッチ数となる。
実行はほぼ一瞬で完了する。
Problem 3. Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
13195 の素因数は 5, 7, 13, 29 である。
600851475143 の素因数のうち最大のものを求めよ。
少し考えたけどものすごく時間がかかるものしか書けなかった…ので
検索して見つけた高速な因数分解を使用したバージョンをまず書いてみた。
(まず書いてみたも何も、ほぼコピペだけど…)
もう少し考えて自力で書いたバージョンがこちら。
primeFactors 関数を再帰的に呼び出している。 nが目的の値、mが2から始めてnまで再帰呼び出し中にインクリメントする値、listが素因数のリスト。
isPrimeFactor 関数で素因数かどうかを検査する。
mがすでに追加されている素因数のリストのいずれでも割り切れず、
nを割り切れる値なら素因数としている。
最初、8行目を「isPrimeFactor = primeFactors n (m + 1) (m:list)」と
nの値を変化させずに再帰呼び出しするようにしていたが、
それでは処理が非常に遅く(2から600851475143まで1ずつインクリメントして全ての値を検査しないと再帰終了条件とならない)
euler3-1.hsからヒントを得てmが素因数なら n / m の値を新しいnとして
再帰呼び出しするようにしてみた。
CoffeeScript によるデザインパターン(Iterator)
『Rubyによるデザインパターン』をCoffeeScriptで書く試み。
目次
外部イテレータ
今回は工夫の余地があまり無さそうだけど、とりあえず原書通りに ArrayIterator クラスを作ってみる。
var array = ["red", "green", "blue"];
var i = new ArrayIterator(array);
while (i.hasNext()) console.log("item: " + i.nextItem());
// 「item: red」
// 「item: green」
// 「item: blue」
内部イテレータ
CoffeeScript の for を使って表現する。
a = [10, 20, 30]
console.log "The element is #{element}" for element in a
「The element is 10」「The element is 20」「The element is 30」が順に表示される。
なお、前回の CompositeパターンでArray を継承した composite3.coffee を作成したが、
あの場合の CompositeTask でも上記の for が使用できる。
task = new MakeBatterTask()
console.log "Sub task: #{subTask.constructor.name}" for subTask in task
「Sub task: AddDryIngredientsTask」「Sub task: MixTask」が順に表示される。
複数のイテレータを同時に扱う
何だか収まりが悪い気がするが、こちらを今回の完成形としよう。
var array1 = [1,3,5,7,9]; var array2 = [2,6,10]; console.log(merge(array1, array2)); // [1, 2, 3, 5, 6, 7, 9, 10]
specs2で単体テスト
merge メソッドはイテレータの本来の目的ではないが、ついでにテスト。
