プロジェクトオイラー問38

Problem 38 「パンデジタル倍数」 †

192 に 1, 2, 3 を掛けてみよう.

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

積を連結することで1から9の パンデジタル数 192384576 が得られる. 192384576 を 192 と (1,2,3) の連結積と呼ぶ.

同じようにして, 9 を 1,2,3,4,5 と掛け連結することでパンデジタル数 918273645 が得られる. これは 9 と (1,2,3,4,5) との連結積である.

整数と (1,2,...,n) (n > 1) との連結積として得られる9桁のパンデジタル数の中で最大のものはいくつか?

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2038

解法

9*(1,2,3,4,5)なのだからまあ試す数の先頭桁は9でしょう。

後は

４桁+５桁。

かそれ以下の数だけ調べればよいだけの話です。

perm([9,_,_,_]).
perm([9,_,_]).
perm([9,_]).
perm([9]).

to_num([],Num,Num):-!.
to_num([X|Xs],Num,Result):-
      !,
      member(X,[0,1,2,3,4,5,6,7,8,9]),
      Num1 is Num*10+X,
      to_num(Xs,Num1,Result).

calc(_,_,List,_):-
      length(List,Len),
      Len>9,
      !,
      fail.
calc(_,_,List,List):-
      msort(List,[49,50,51,52,53,54,55,56,57]),
      !.
calc(N,M,List,Result):-
      !,
      N1 is N*M,
      M1 is M+1,
      number_codes(N1,Add),
      append(List,Add,List1),
      calc(N,M1,List1,Result).
search(Num2):-
      perm(List),
      to_num(List,0,Num),
      calc(Num,1,[],List2),
      number_codes(Num2,List2).
last([E],E):-!.
last([_|Rest],Result):-
      !,
      last(Rest,Result).

main38:-
      findall(E,search(E),List),
      sort(List,List1),
      last(List1,Ans),
      write(Ans).