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

project euler problem 4 answer

二時間くらいかかっているorz

戦略は大きいほうから順に回文数を探し、因子を探していくというもの。ごく普通のもの。

split_at(N, [Lcar | Lcdr], [Lcar | F], R) :-
        N > 0, N1 is N - 1, split_at(N1, Lcdr, F, R), !.
split_at(_, [], [], []).
split_at(0, L, [], L).

% 回文数の判別
is_palindrome_number(N) :-
        number_chars(N, Chars),
        length(Chars, Length),
        (Length =:= 1 -> true;
        Middle =  Length // 2,
        split_at(Middle, Chars, Left, Right),
        reverse(Left, LeftSide),
        (Length mod 2 =:= 0 ->
         RightSide = Right;
         split_at(1, Right, _, RightSide)),
        LeftSide = RightSide).

% ゾロ目の数を作る
make_repdigit(Base, Length, Result) :- make_repdigit_sub(Base, Length, Result, 0).
make_repdigit_sub(_, 0, Acc, Acc) :- !.
make_repdigit_sub(Base, Length, Result, Acc) :-
        Length > 0,
        Len1 is Length - 1,
        AccNext is Acc * 10 + Base,
        make_repdigit_sub(Base, Len1, Result, AccNext).

% 数字の桁数
number_length(Number, Length) :- number_atom(Number, A), atom_length(A, Length).

% Nが二つのLength桁の積で表せる可能性を持つか
have_factor_possibility(N, Length) :-
        N > 0,
        Len is Length - 1, make_repdigit(9,Len, Digit),
        N > Digit * Digit.

% N以下の回文数のうちProductLength桁の二つの数の積で表せる最大のものを返す
find_largest_palindrome_factor(N, ProductLength, Result) :-
        have_factor_possibility(N, ProductLength),
        (is_palindrome_number(N) -> search_factor(N, ProductLength, Result));
        N1 is N - 1,
        find_largest_palindrome_factor(N1, ProductLength, Result).
% 総当たりで探す
search_factor(N, ProductLength, Result) :-
        make_repdigit(9, ProductLength, Digit),
        search_factor_sub(N, ProductLenght, Digit,Result).
search_factor_sub(N, ProductLength, Digit, Result) :-
        number_length(Digit, ProductLength),
        D1 is Digit - 1,
        ((N mod Digit =:= 0, Rem is N // Digit, number_length(Rem, ProductLength)) ->
         Result = [N, Digit, Rem];
         search_factor_sub(N, ProductLength, D1, Result)).

problem4(Result) :- find_largest_palindrome_factor(1000000, 3, Result).