http://projecteuler.net/index.php?section=problems&id=23 まず28123以下の自然数の配列を作り、過剰数を求めて、それらの和に対し配列の値を0にして、最後に配列の和を取る。 iterableに対してproductがうまく動かなかったので、iterableを修正した。

http://projecteuler.net/index.php?section=problems&id=22 単語を拾うのをiterableになるように実装して、単語をソートする。しかし、iterableのsortedがあったほうが便利なので作ってみた。 cout << sum(map(score, zip(itertools::count<>(1), sorted(li…

http://projecteuler.net/index.php?section=problems&id=20 これも前にで作った多倍長整数クラスを使えば簡単。掛け算は足し算を繰り返すだけ。ただし、単純に足すだけだと芸がないのでバイナリ法を使った。 #include <iostream> #include "itertools.h" #include "lo</iostream>…

http://projecteuler.net/index.php?section=problems&id=19 曜日の定義は1900年なのに数えるのは1901年から。何度でも騙される。 1日の曜日を出すiterableを定義する。そして、iterableの長さを得る関数を作った。数えてもいいが、zipを使えば1行で書ける。…

http://projecteuler.net/index.php?section=problems&id=18 整数をルートに割り当てる。次に左右どちらに行くかを2進数で表して各桁が0か1かで決める。それを関数化するとiterateでルートが作れる。

http://projecteuler.net/index.php?section=problems&id=16 Problem 13で作った多倍長整数クラスを使えば簡単。足し算を繰り返すだけ。その後各桁の数字をatで拾ってくる。itertools.h #include <iostream> #include "itertools.h" #include "longint.h" using namesp</iostream>…

http://projecteuler.net/index.php?section=problems&id=15 Combinationは再帰で書くと簡単。なのでメタプログラミングしてみた。 #include <iostream> template<int N, int M> struct C { static const long long value = C<N,M-1>::value * (N - M + 1) / M; }; template<int N> struct C<N, 0> { stat</n,></int></n,m-1></int></iostream>…

メモ化を使うと速くなる。0に初期化しておき、nextで辿って0でないところに着いたら、そこまで辿った開始数での長さがわかる。このときに最初に0でないところまで辿りたいがtakewhileではその手前で終わってしまう。こういうのはよくあることだが、どうすべ…

http://projecteuler.net/index.php?section=problems&id=14 Haskellで書くとこんな感じ。 import Data.List next n = if mod n 2 == 0 then div n 2 else 3 * n + 1 chain_length n = head [ k | (k,m) <- zip [1..] (iterate next n), m == 1 ] limit = 10…

http://projecteuler.net/index.php?section=problems&id=13 1要素で1桁を表す多倍長整数クラスを適当にでっちあげた。

この問題をHaskellで書くと、 main = print (foldl1' max (filter is_palindromic [ x * y | x <- [100..999], y <- [100..999] ])) Pythonで書くと、 print reduce(max, ifilter(is_palindromic, (x * y for x, y in product(xrange(100, 1000), xrange(100…

ジェネレータの次があるかをexists_next()で問い合わせるようにした。ちょっとコードが煩雑になった。filterとtakewhileはコードがかなり重複しているような気がする。なんとかならないだろうか。 itertools.hを変えただけで、非常に速くなった。Haskellより…

Haskellで import Data.List digits 0 = [] digits n = (digits (div n 10)) ++ [mod n 10] is_palindromic n = n == (foldr (\x y -> x + y * 10) 0 (digits n)) main = print (foldl1' max (filter is_palindromic [ x * y | x <- [100..999], y <- [100..…

VC10 β2にmake_tupleがあるんだ。調べようと調べようと思って忘れていた。 #include <iostream> #include <tuple> using namespace std; int main() { auto t = make_tuple(1, 2, 3); cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << endl; } >cl /EHsc tuple.</tuple></iostream>…

http://projecteuler.net/index.php?section=problems&id=3 例えば次のようなコードを考える。 #include <iostream> #include "itertools.h" using namespace std; using namespace itertools; class cCeil { int n; public: cCeil(int n) : n(n) { } int operator()(i</iostream>…

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

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; …

テンプレート引数がいちいちついて回るのは、クラスを関数で包めば回避できる。例えば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>…

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

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

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

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

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

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…

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

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

http://projecteuler.net/index.php?section=problems&id=4 Pythonでこう書くのを真似したい。 from itertools import ifilter, product def gen_digits(n): if n > 0: for d in gen_digits(n / 10): yield d yield n % 10 def to_number(a): return reduce(…

http://projecteuler.net/index.php?section=problems&id=3 素因数分解をする。 C++ではタプルが使えるのでこれを使う、pairでもいいが。 #include <iostream> #include <tuple> using namespace std; typedef tuple<int,int> Fact; int main() { Fact f = Fact(2, 3); cout << get<0>(</int,int></tuple></iostream>…

takewhileもfilterと同じように定義する。

cGeneratorクラスを作って、next()で値を返すクラスはこれを継承することにする。 template<typename T> class cGenerator { public: virtual ~cGenerator() { } virtual T next() = 0; }; 本当はポインタなんか使いたくない。いちいちdeleteしなければならないのが嫌。</typename>…