プロジェクトオイラー Problem 61 「巡回図形数」 †

Problem 61 「巡回図形数」 †

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.

三角数	P3,n=n(n+1)/2	1, 3, 6, 10, 15, ...
四角数	P4,n=n2	1, 4, 9, 16, 25, ...
五角数	P5,n=n(3n-1)/2	1, 5, 12, 22, 35, ...
六角数	P6,n=n(2n-1)	1, 6, 15, 28, 45, ...
七角数	P7,n=n(5n-3)/2	1, 7, 18, 34, 55, ...
八角数	P8,n=n(3n-2)	1, 8, 21, 40, 65, ...

3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.

1. この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
2. それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
3. 4桁の数の組で上の2つの性質をもつはこの組だけである.

三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.

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





解法
循環するのでどこから初めてもよく3角数から探索を始めます。
後は全探索するだけです。
探索が進むとリストが短くなるシンプルイズベストなコード。
比較的綺麗にかけたと思う。

今回は全探索してますが。
この問題、動的計画法を使えば計算量を下げる遊びができるのでそれもおすすめです。

初めに選んだ数の上2桁と、今まで使ったｎ角数をビットで管理最後に選んだ数の末尾2桁で管理し、解が一つしかないというヒントを使えば動的計画法の計算中にかなりの枝刈りを行えます。




f3(N,N1):-!,N1 is (N*(N+1))//2.
f4(N,N1):-!,N1 is N*N.
f5(N,N1):-!,N1 is (N*(N*3-1))//2.
f6(N,N1):-!,N1 is N*(2*N-1).
f7(N,N1):-!,N1 is (N*(5*N-3))//2.
f8(N,N1):-!,N1 is N*(3*N-2).

calc2(Siki,[Head,Tail]):-
      between(20,500,N),
      call(Siki,N,E),
      1000=<E,
      E=<9999,
      Head is E//100,
      Tail is E mod 100.

calc(List):-
      member(Siki,[f3,f4,f5,f6,f7,f8]),
      findall(E,calc2(Siki,E),List).

search([],Tail,Sum,Tail):-!,write(Sum).
search(Lists,Tail,Sum,FirstTop):-
      !,
      select(List,Lists,Lists1),
      member([Tail,Tail1],List),
      Sum1 is Sum+Tail*100+Tail1,
      search(Lists1,Tail1,Sum1,FirstTop).

main61:-
      findall(L,calc(L),[List3|Lists]),
      member([FirstTop,Tail],List3),
      Sum is FirstTop*100+Tail,
      search(Lists,Tail,Sum,FirstTop).