回文数

回文数とは前から読んでも後ろから読んでも同じ自然数、例えば13231などのことで、なぜかよくProject Eulerで出てきます。
回文数は再帰的に生成することができます。例えば、131という回文数があれば、これを10倍して10001の倍数を足すことで、11311,21312,…という回文数を作ることができます。Pythonではこれを非常に自然に書くことができます。

def gen_palindromic(k, B, l = 0):
    if l == k:
        return range(1)
    elif l == k - 1:
        return range(B)
    else:
        begin = 1 if l == 0 else 0
        m = B ** (k - l - 1) + 1
        return (n * B + d * m for d in range(begin, B)
                            for n in gen_palindromic(k, B, l + 2))

k桁の10進の回文数を昇順に出します。順番にこだわらなければ、最後のforの順番を変えると速くなります。
itertools::productを使うとC++でも同じように書けます。

#include "itertools.h"

using namespace std;
using namespace itertools;

int pow(int n, int e) {
    if(e == 0)
        return 1;
    
    const int   m = pow(n, e / 2);
    return e % 2 == 1 ? n * m * m : m * m;
}

shared_ptr<cIterable<int>> palindromic(int k, int B, int l = 0) {
    if(l == k)
        return range(1);
    else if(l == k - 1)
        return range(B);
    else {
        const int   begin = l == 0 ? 1 : 0;
        const int   m = pow(B, k - l - 1) + 1;
        return map([B,m] (tuple<int,int> x) { return fst(x) * m + snd(x) * B; },
                            product(range(begin, B), palindromic(k, B, l + 2)));
    }
}

こちらのほうがPythonより2桁速くなりました。
Problem 36を解いておきましょう。itertools.hも少し直しました。

#include "itertools.h"

using namespace std;
using namespace itertools;

typedef long long   ll;

ll pow(ll n, int e) {
    if(e == 0)
        return 1;
    
    const ll    m = pow(n, e / 2);
    return e % 2 == 1 ? n * m * m : m * m;
}

shared_ptr<cIterable<ll>> palindromic(int k, int B, int l = 0) {
    if(l == k)
        return range((ll)1);
    else if(l == k - 1)
        return range((ll)B);
    else {
        int begin = l == 0 ? 1 : 0;
        ll  m = pow((ll)B, k - l - 1) + 1;
        return map([B,m] (tuple<ll,int> x) { return fst(x) * B + snd(x) * m; },
                        product(palindromic(k, B, l + 2), range(begin, B)));
    }
}

shared_ptr<cIterable<ll>> pali(int n, int B) {
    return map(snd<int,ll>, product(range(1, n + 1),
                            [B] (int k) { return palindromic(k, B); }));
}

bool is_palindromic(ll n) {
    ll  n_ = n;
    ll  m = 0;
    while(n_) {
        m = m * 2 + n_ % 2;
        n_ /= 2;
    }
    return m == n;
}

int main() {
    const int   N = 13;
    cout << sum(filter(is_palindromic, pali(N, 10))) << endl;
}