Project Euler 14（2）

メモ化を使うと速くなる。0に初期化しておき、nextで辿って0でないところに着いたら、そこまで辿った開始数での長さがわかる。このときに最初に0でないところまで辿りたいがtakewhileではその手前で終わってしまう。こういうのはよくあることだが、どうすべきなのだろうか。ここではラムダに参照をもぐらせて値を取ってくるというインチキくさいことをやっている。

itertools.h

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

using namespace std;
using namespace itertools;

typedef long long int64;

const int64 N = (int)1e6;

std::vector<int>    v_length(N + 1, 0);

long long next(int64 n) {
    if(n % 2 == 0)
        return n / 2;
    else
        return 3 * n + 1;
}

int chain_length(int n) {
    int p;
    vector<int64>   v = list(takewhile(
            [&p] (int64 x) { return x >= N || v_length[p=x] == 0; },
            iterate(next, (int64)n)));
    
    int l = v_length[p];
    for(int k = 0; k < (int)v.size(); k++) {
        if(v[k] <= N)
            v_length[v[k]] = l + v.size() - k;
    }
    return l + v.size();
}

tuple<int,int> longer(tuple<int,int> x, tuple<int,int> y) {
    return snd(x) >= snd(y) ? x : y;
}

int main() {
    v_length[1] = 1;
    cout << fst(reduce1(longer, map(
            [] (int n) { return make_tuple(n, chain_length(n)); },
            range<>(N / 2, N)))) << endl;
}