Project Euler 4（5） - inamori’s diary

この問題を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, 1000)))))

このPythonのproductは数学で言う直積（direct product）を意味している。要するに2つの引数は互いに独立しているということである。

from itertools import product

for x, y in product(range(2), range(2)):
    print x, y

とすると、それぞれは0,1を出すので、

しかし、この問題は、100×101を計算したら101×100は計算する必要はない。x ≤ yとすればよい。Haskellで書くと、

main = print (foldl1' max (filter is_palindromic
             [ x * y | x <- [100..999], y <- [x..999] ]))

Pythonなら、

print reduce(max, ifilter(is_palindromic,
        (x * y for x in xrange(100, 1000) for y in xrange(x, 1000))))

すなわち、2つ目の引数は1つ目の引数の値に依存するようにすればよい。これをC++0xで実現できないだろうか。
少し考えると、2つ目の引数をラムダにすればよいことがわかる。

[] (int x) { return range<>(x, 1000); }

これに1つ目の引数から出てきた値を代入すればよい。その機構を、例えばdependently_productとでも名前をつけて作れば答えが出てくる。

#include <iostream>
#include "itertools.h"

using namespace std;
using namespace itertools;

template<typename T, typename U, typename V, typename W, typename X>
class cDependentlyProduct {
    T&  gen1;
    X&  fo;
    U   gen2;
    V   v;
    
public:
    cDependentlyProduct(T& g1, X& g) : gen1(g1), fo(g) {
        v = gen1.next();
        gen2 = fo(v);
    }
    tuple<V,W> next() {
        if(gen2.exists_next()) {
            return make_tuple(v, gen2.next());
        }
        else {
            v = gen1.next();
            gen2 = fo(v);
            return next();
        }
    }
    bool exists_next() {
        return gen2.exists_next() || gen1.exists_next();
    }
};

template<typename T, typename X>
auto dependently_product(T& g1, X& fo) ->
        cDependentlyProduct<T,decltype(fo(g1.next())),decltype(g1.next()),
                                    decltype(fo(g1.next()).next()),X> {
    return cDependentlyProduct<T,decltype(fo(g1.next())),decltype(g1.next()),
                            decltype(fo(g1.next()).next()),X>(g1,fo);
}

bool is_palindromic(int n) {
    return n == to_number(digits(n));
}

int main() {
    cout << reduce1(max<int>,
            filter(is_palindromic,
            map([] (tuple<int,int> x) { return fst(x) * snd(x); },
            dependently_product(range<>(100, 1000),
            [] (int x) { return range<>(x, 1000); })))) << endl;
}

ただ、この名前は長いので、productという名前で直積のほうも依存するほうも使えるようにできないだろうか。すなわち、2つ目の引数にrangeのようなもの（iterableと呼ぼう）とラムダをどちらも取れて適当に判別できるようにしたい。
ラムダは実体は関数オブジェクトで()演算子を持っている。上の例だとたぶんこんな感じ。

    range<> operator ()(int x) { return range<>(x, 1000); }

試行錯誤した結果、次のようなコードで実現できた。

#include <iostream>
#include "itertools.h"

template<typename T>
bool has_paren(T& g, decltype(g.operator())) { return true; }

template<typename T>
bool has_paren(...) { return false; }

template<typename T>
void f(T& g) {
    if(has_paren<T>(g, 0))
        std::cout << "lambda" << std::endl;
    else
        std::cout << "iterable" << std::endl;
}

int main() {
    f([] (int x) { return x + 1; });    // lambda
    f(itertools::range<>(2));           // iterable
}

()演算子を持てばラムダと判断することにする。has_paren関数で引数の()演算子の返り値の型を拾おうとして失敗すればSFINAEでその下のhas_parenを実行する。そのときは()演算子を持たないことになる。これはアイディアだけで実際にはメタ関数にする。このhas_parenでcDependentlyProductとcProductに振り分ける。

itertools.h

#include <iostream>
#include "itertools.h"

using namespace std;
using namespace itertools;

bool is_palindromic(int n) {
    return n == to_number(digits(n));
}

int main() {
    cout << reduce1(max<int>,
            filter(is_palindromic,
            map([] (tuple<int,int> x) { return fst(x) * snd(x); },
            product(range<>(100, 1000),
#if 1
            [] (int x) { return range<>(x, 1000); })))) << endl;
#else
            range<>(100, 1000))))) << endl;
#endif
}

相当苦労したおかげで、実行時間が半分になった。