2010-03-01から1ヶ月間の記事一覧

itertools.h(3)

VC10β2で先取りしたC++0xの機能を用いてHaskell風に書けるようにするためのライブラリ。一部は趣味でPython風の名前になっていたりする。ここを常に参照することにする。勝手に追加される。 破壊的な変更がされる場合は別にエントリーを立てる。

Project Euler 96

http://projecteuler.net/index.php?section=problems&id=96 マスに可能な数字を次々に当てはめていき矛盾が無い解を出すだけ。それなりに速い。

Project Euler 2(2)

takewhileもfilterと同様に定義する。 N以下まで値を出すときに、 const int N = (int)4e6; takewhile([] (int n) { return n <= N; }, fib()); これだとNが見えない。[]の中にNを書いて、 const int N = (int)4e6; takewhile([N] (int n) { return n <= N; …

Project Euler 95

http://projecteuler.net/index.php?section=problems&id=95 次を配列にしておく。

Project Euler 1(4)

テンプレート引数がいちいちついて回るのは、クラスを関数で包めば回避できる。例えばmapなら、 template<typename T, typename U, typename V> class cMap { T& func; U& gen; public: cMap(T& f, U& g) : func(f), gen(g) { } V next() { return func(gen.next()); } }; template<typename T, typename U> auto map(T& f</typename></typename>…

Project Euler 94

http://projecteuler.net/index.php?section=problems&id=94 Pell方程式に帰着される。 pells m n = (next m n):[ next p q | (p, q) <- pells m n ] where next m n = (m * 2 + n * 3, m + n * 2) limit = 10^9 main = print (sum (takeWhile (<= limit) [ …

Project Euler 284(2)

各桁の数字のリストを作ったら速くなった。Pythonのリストは遅いはずなのに。じゃあ、ということでHaskellで書いたら、どうも遅延評価してくれないらしく、やたらとメモリを食う。おかしいな。

Project Euler 93

http://projecteuler.net/index.php?section=problems&id=93 演算子の配列は、 operators = [ (+), (-), (*), (/) ] けれど、実際の演算は、 op = (+) n = op 1 2 -- 3 と、前置にしなければならない。 0割りを回避するところで、演算子が(/)かどうかを直接…

Project Euler 284

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=284 2時間以上経ってやっと問題見たが、もう7人も解けている。 今日・明日もほとんどPCの前にいる時間無いのに。 問題理解したつもりだけど、そんなに簡単な問題に思えない。…

Project Euler 92

http://projecteuler.net/index.php?section=problems&id=92 1000までは1か89になるまで辿って89になればSetに入れる。それより大きい場合は1000以下になるまで辿る。この問題の範囲内では1回で1000以下になるはず。

Project Euler 11

http://projecteuler.net/index.php?section=problems&id=11 縦・横・斜めに次々に数を出すジェネレータを作る。4つ取るのはHaskellのような自作のtakeで。どちらに進むかは関数オブジェクトをテンプレートで与える。 最初の座標を与えるのに、2つのrangeのp…

itertools.h(2)

今まで書いてきた、Pythonのitertoolsに入ってたりそれに近かったり頻繁に使うクラスや関数をここにまとめておき、常に参照することにする。勝手に追加される。 破壊的な変更がされる場合は別にエントリーを立てる。

Project Euler 91

http://projecteuler.net/index.php?section=problems&id=91 点Pを軸上以外に取って、Pを通りOPに垂直に直線を引く。その直線上の格子点がQ。 f n = 3 * n * n + sum [ g (x,y) | x <- [1..n], y <- [1..n] ] g (x,y) = (min (div x dx) (div (n - y) dy)) +…

Project Euler 90

http://projecteuler.net/index.php?section=problems&id=90 組合せを出して判定するだけ。

Project Euler 10

http://projecteuler.net/index.php?section=problems&id=10 エラトステネスのふるいを書いてみた。偶数は無視して、20000を単位とした大きさの範囲ごとにふるいにかけた。この問題は200万までだが、一桁増やして実行時間を調べたところ、この大きさがもっと…

Project Euler 89

http://projecteuler.net/index.php?section=problems&id=89 1000の位だけ特別扱い。

Project Euler 283(3)

単に問題文の最後を読み間違えていただけ、というかちゃんと読んでいなかっただけだった。

Project Euler 88

http://projecteuler.net/index.php?section=problems&id=88 雑にSetを使って。コンパイルして最適化オプションつけたら非常に速くなった。

Project Euler 283(2)

うーん、できたと思うんだが、どこが間違っているのかわからない。

Project Euler 87

http://projecteuler.net/index.php?section=problems&id=87 素直に取りうる値のリストを作ってSetに入れて大きさを見る。 import Data.Set (fromList, size) is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:[ n …

Project Euler 283

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=283 1時間寝坊。まだ誰も解けていないようだ。今日もあまり時間取れないのに。

Project Euler 86

http://projecteuler.net/index.php?section=problems&id=86 l(m2 - n2) か 2lmn のどちらかがM。

Project Euler 9

http://projecteuler.net/index.php?section=problems&id=9 いつものようにピタゴラス数の式を使うと、 a + b + c = 2lm(m + n) これが1000になる。約数を出すオブジェクトを作ればよいが、これがなかなか大変だった。

Project Euler 84

http://projecteuler.net/index.php?section=problems&id=84 基本的にProblem 280と同じだが、圧倒的に複雑。遷移確率を求めて、100回目の分布を計算する。しかし、どこかが間違っているらしい。結果的には正しい答えが出てくるが。 以前はどうやったのかコ…

Project Euler 7(2)

takewhileなどのジェネレータは関数を引数に持つ。しかし、型指定をしたくないのでラムダは使えず、関数の型も限られたものになる。引数が一つであればいいが、他に環境からもってくることができない。 そこで、関数は2つの引数を取るものも使えるようにし、…

Project Euler 85

http://projecteuler.net/index.php?section=problems&id=85 Pythonで解いたときと違う方法を採った。2000000, 1999999, 2000001, ...という数に対して三角数の積になっていないか調べる。

Project Euler 7

http://projecteuler.net/index.php?section=problems&id=7 Haskellなら、 is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime [3,5..]) n = 10001 pair = head (filter (\(k,_) -> k == n) (zip [1…

itertools.h

今まで書いてきた、Pythonのitertoolsに入ってたりそれに近かったり頻繁に使うクラスや関数をここにまとめておき、常に参照することにする。勝手に追加される。 破壊的な変更がされる場合は別にエントリーを立てる。

Project Euler 81,82,83

http://projecteuler.net/index.php?section=problems&id=81 http://projecteuler.net/index.php?section=problems&id=82 http://projecteuler.net/index.php?section=problems&id=83 3題とも同じアルゴリズムで計算できる。違うのは初期のマスと最小を取る…

Project Euler 4(2)

productを書きたかったが、なかなか大変だった。タプルで返したかったが、うまくいかない。しかたなくvectorで返すことにした。 productの絡みで、cGeneratorを継承したらcopyメソッドが必要ということにした。今さらだが、mapも作った。 動かしてみたら、Py…