読者です 読者をやめる 読者になる 読者になる

project euler problem 9 answer

良心に苛まれながらも貼る。

SICPにも似たような問題があった。SWI-Prologでグローバルスタックを拡張して実行した。

% ペアを作る(おまけ)
integer_pairs_new(PairSeed) :- PairSeed = [[[1, 1] | Tail], Tail].
integer_pairs(PairSeed, Pair, NextPairSeed) :-
        [Head, Tail] = PairSeed,
        [Pair | Rest] = Head,
        integer_pairs_generate_next_seed(Pair, [Rest, Tail], NextPairSeed), !.
integer_pairs_generate_next_seed([X, X],PairSeedRest, NextPairSeed) :-
        [RestHead, Appender1] = PairSeedRest,
        X1 is X + 1,
        Appender1 = [[X1, X], [X1, X1] | Appender2],
        NextPairSeed = [RestHead, Appender2].
integer_pairs_generate_next_seed([X, Y],PairSeedRest, NextPairSeed) :-
        [RestHead, Appender1] = PairSeedRest,
        X1 is X + 1,
        Appender1 = [[X1, Y] | Appender2],
        NextPairSeed = [RestHead, Appender2].

% 三組のペアを作る
integer_triples_new(TriplesSeed) :- TriplesSeed = [[[1, 1, 1] | Tail], Tail].
integer_triples(TriplesSeed, Pair, NextTriplesSeed) :-
        [Head, Tail] = TriplesSeed,
        [Pair | Rest] = Head,
        integer_triples_generate_next_seed(Pair, [Rest, Tail], NextTriplesSeed), !.
integer_triples_generate_next_seed([X, X, X],TriplesSeedRest, NextTriplesSeed) :-
        [RestHead, Appender1] = TriplesSeedRest,
        X1 is X + 1,
        Appender1 = [[X1, X, X],[X1, X1, X], [X1, X1, X1] | Appender2],
        NextTriplesSeed = [RestHead, Appender2].
integer_triples_generate_next_seed([X, X, Z],TriplesSeedRest, NextTriplesSeed) :-
        [RestHead, Appender1] = TriplesSeedRest,
        X1 is X + 1,
        Appender1 = [[X1, X, Z], [X1, X1, Z] | Appender2],
        NextTriplesSeed = [RestHead, Appender2].
integer_triples_generate_next_seed([X, Y, Z],TriplesSeedRest, NextTriplesSeed) :-
        [RestHead, Appender1] = TriplesSeedRest,
        X1 is X + 1,
        Appender1 = [[X1, Y, Z] | Appender2],
        NextTriplesSeed = [RestHead, Appender2].

% 探す
search(Seed, Result) :-
        integer_triples(Seed, [A,B,C], Next),
        ((C*C + B*B =:= A*A,write([A,B,C]),nl,flush,
         A+B+C =:= 1000) ->
         Result is A * B * C;
         search(Next, Result)).

problem9(Result) :-
        integer_triples_new(Seed),
        search(Seed, Result).