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).