プロジェクトオイラー問６１ - c21coterie @ ウィキ

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

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) は以下の面白い性質を持つ.

この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
4桁の数の組で上の2つの性質をもつはこの組だけである.
三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.

解法
全探索でいい気もしますが。
一応動的計画法で解いてみました。
巡回するのでどの数から初めても問題ありません。
よって三角数を最初にして。
その後は

• 　三角数の1000と100の位、
• 　使用済みのｎ角数をビットで管理
• 　一番最後に選んだ数の下２桁

この３つを主キーに、そこまでの合計値を主キーに対する値として動的計画法で回します。
ｎ個だけ角数から選んだ状態からn+1個選んだ状態を計算します。
解が唯一であるというヒントを頼りに、主キーが同じになったものは一つだけ残して他は廃棄します。
効率化できたかどうかは微妙なところです。

ps3(N,N3):-
	N3 is (N*(N+1))//2.
ps4(N,N4):-
	N4 is N^2.
ps5(N,N5):-
	N5 is (N*(N*3-1))//2.
ps6(N,N6):-
	N6 is N*(2*N-1).
ps7(N,N7):-
	N7 is (N*(5*N-3))//2.
ps8(N,N8):-
	N8 is N*(3*N-2).
ps(Siki,[P1,P2]):-
	between(1,200,N),
	call(Siki,N,Pa),
	1000=<Pa,
	Pa=<9999,
	P1 is Pa//100,
	P2 is Pa mod 100.

ps_w(Siki,Result):-
       findall(R,ps(Siki,R),Result).


one_calc([Top,Bits,Tail,Sum],Ps,[Top,Bits1,Tail1,Sum1]):-
	between(0,5,No),
	(Bits /\ (1<<No))=:=0,
	Bits1 is Bits \/ (1<<No),
	nth0(No,Ps,P),
	member([Tail,Tail1],P),
	Sum1 is Sum+Tail*100+Tail1.

next_calc(DP,Ps,Result):-
	member(E,DP),
	one_calc(E,Ps,Result).

myunion([],Set,[Set]):-!.
myunion([[Top,Bits,Tail,_]|Rest],[Top,Bits,Tail,Sum],Result):-
	!,
	myunion(Rest,[Top,Bits,Tail,Sum],Result).
myunion([Set|Rest],Set1,[Set1|Result]):-
	!,
	myunion(Rest,Set,Result).

to_seed([],[]):-!.
to_seed([[Top,Tail]|Rest],[[Top,1,Tail,Sum]|Result]):-
	Sum is Top*100+Tail,
	to_seed(Rest,Result).

ok_list([],[]):-!.
ok_list([[Top,_,Top,Sum]|Rest],[Sum|Result]):-
	!,
	ok_list(Rest,Result).
ok_list([_|Rest],Result):-
	!,
	ok_list(Rest,Result).

dp(6,DP,_):-
	!,
	ok_list(DP,Ans),
	write(Ans).
dp(Deep,DP,Ps):-
	!,
	findall(Re,next_calc(DP,Ps,Re),NextDP),
	sort(NextDP,[Top|NextDP1]),
	myunion(NextDP1,Top,NextDP2),
	Deep1 is Deep+1,
	dp(Deep1,NextDP2,Ps).
main61:-
ps_w(ps3,Ps3),
	ps_w(ps4,Ps4),
 	ps_w(ps5,Ps5),
	ps_w(ps6,Ps6),
	ps_w(ps7,Ps7),
	ps_w(ps8,Ps8),
	PsAll =[Ps3,Ps4,Ps5,Ps6,Ps7,Ps8],
        to_seed(Ps3,Seed),
	dp(1,Seed,PsAll)
.