Project Euler 14（1）

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^6 - 1
longer x y = if snd x >= snd y then x else y
main = print (fst (foldl1' longer [ (n,chain_length n) | n <- [1..limit] ]))

iterateは、

iterate f x = [ x, f x, f . f x, … ]

で、この問題の場合で、

iterate next 13 = [ 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 1, … ]

これをitertools.hに書き加えて利用した。

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

using namespace std;
using namespace itertools;

typedef long long int64;

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

int chain_length(int n) {
    return fst(head(filter([] (tuple<int,int64> x) { return snd(x) == 1; },
            zip(count<>(1), iterate(next, (int64)n)))));
}

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

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

Haskellの半分以下の実行時間だった。