Project Euler 4（1）

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(lambda x, y: x * 10 + y, a)

def is_palindromic(n):
    return n == to_number(reversed(list(gen_digits(n))))

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

こんなに短いコードでもかなり大変。
まずreduceを作る。

template<typename T, typename U>
auto reduce(T f, U *g) -> decltype(f(g->next(), g->next())) {
    decltype(f(g->next(), g->next()))   x = g->next();
    try {
        while(true)
            x = f(x, g->next());
    }
    catch(int e) {
        return x;
    }
}

Pythonのreduceは型がいい加減。まだあまりよくできていない。
C++0xではここでラムダが使える。

    return reduce([](int x, int y) { return x * 10 + y; }, g);

とりあえず、回文数の判定だけ。

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
class cGenerator {
public:
    virtual ~cGenerator() { }
    virtual T next() = 0;
};

template<typename T, typename U>
auto reduce(T f, U *g) -> decltype(f(g->next(), g->next())) {
    decltype(f(g->next(), g->next()))   x = g->next();
    try {
        while(true)
            x = f(x, g->next());
    }
    catch(int e) {
        return x;
    }
}

template<typename T>
auto list(T *g) -> vector<decltype(g->next())> {
    vector<decltype(g->next())> v;
    try {
        while(true)
            v.push_back(g->next());
    }
    catch(int e) {
        return v;
    }
}

template<typename T>
class reversed : public cGenerator<T> {
    vector<T>&  v;
    int k;
    
public:
    reversed(vector<T>& v) : v(v) { k = (int)v.size() - 1; }
    T next() {
        if(k == -1)
            throw(1);
        return v[k--];
    }
};

template<typename T>
class digits : cGenerator<T> {
    int     d;
    digits<T>   *g;
    
public:
    digits(int n) {
        g = NULL;
        if(n > 0)
            g = new digits(n / 10);
        d = n % 10;
    }
    
    int next() {
        if(g != NULL) {
            try {
                return g->next();
            }
            catch(int e) {
                g = NULL;
                return d;
            }
        }
        throw(1);
    }
};

template<typename T>
T to_numerize(cGenerator<T> *g) {
    return reduce([](int x, int y) { return x * 10 + y; }, g);
}

template<typename T>
bool is_palindromic(T n) {
    return n == to_numerize(new reversed<int>(list(new digits<T>(n))));
}

int main() {
    cout << is_palindromic(123) << endl;
    cout << is_palindromic(121) << endl;
}