私は、prologでメモ化を実装するのはassert/1を使わないと難しいと思っていたのですが、
functorを使えば簡単にできることに気づきました。
そんなことも知らなかったのかといわれるかもしれませんが、
ネットを検索しても出ていませんでしたので、記録しておこうとおもいます。
メモ化なら再帰、再帰なら木構造ということで問題を探しました。
問題はこちら->http://nabetani.sakura.ne.jp/hena/orde11tredis/
ざっとプログラムを説明します。
木構造を用い、情報としては距離のみを用いています。
DX,DYは目的の二数から現在の節点までの距離で、
初期値は大きな数、現在の節点が目的の数なら0、親ノードに移るたび1づつ増えます。
TDは二数の距離で、子ノードのDX及びDYの最小値の和+2と子ノードのTDの最小値の小さいほうとなります。
functorで作った変数に一度マッチしたら変更しないからうまくいくのだろうと思います。
もしメモの内容を更新するプログラムがあったら使えないだろうと思います。
(連想で、length(L,N)でリストを作ってメモに使ってみましたところ、可能でしたが遅かったです）。
この問題の場合、普通のの再帰でも高速で、効果がはっきりしませんでしたので、
以前解いた問題->https://qiita.com/smallbigcats/items/f3d0833ed800832fcaa6
｜
（間違いに気づいたので2018.3.8変更）
に、メモ化プログラムを追加しておきました。
最初は普通の再帰プログラム。
dtree(D,_,Y,10000,10000,10000):-D<Y,!.
dtree(Y,_,Y,10000,0,10000):-!.
dtree(X,X,Y,DX,DY,TD):-
!,branch(X,L),(L==[]->(DX=0,DY=10000,TD=10000);
(tree2(L,X,Y,_,DY1,_),DX=0,is(DY,+(DY1,1)),TD=DY)).
dtree(D,X,Y,DX,DY,TD):-branch(D,L),(L==[]->(DX=10000,DY=10000,TD=10000);
(tree2(L,X,Y,DX1,DY1,TD1),is(DX,+(1,DX1)),is(DY,+(1,DY1)),TD=TD1)).
tree2([H],X,Y,DX,DY,TD):-dtree(H,X,Y,DX,DY,TD).
tree2([H|T],X,Y,DX,DY,TD):-
dtree(H,X,Y,DX1,DY1,TD1),tree2(T,X,Y,DX2,DY2,TD2),
is(DX,min(DX1,DX2)),is(DY,min(DY1,DY2)),TD3 is DX+DY+2, min_member(TD,[TD3,TD1,TD2]).
branch(D,L1):-K is D div 2,numlist(2,K,L0),include(mod0(D),L0,L),maplist(plus(1),L,L1).
%branch(D,L):-K is D div 2,findall(Z,(between(2,K,Z0),is(0,mod(D,Z0)),is(Z,+(1,Z0))),L).
mod0(D,X):-0 is D mod X.
solve(D,X,Y,N):-dtree(D,X,Y,_,_,N).
go([]):-!.
go([A,B,C,D|T]):-
concat_atom([B1,B2],:,B),atom_chars(C1,C),
atom_number(B1,N1),atom_number(B2,N2),atom_number(C1,N3),
(N2>N3->solve(N1,N2,N3,N);solve(N1,N3,N2,N)),
write(A),write("->"),write(N),atom_chars(D1,D),atom_number(D1,D2),
(N==D2,Str=" pass";Str=" fail"),write(" "),write(Str),write("\n"),go(T).
start:-str(S),split_string(S,"\s,\n","\s",L),go(L),!.
%start.
str("0 50:6,3 1
1 98:5,11 4
2 1000:33,20 7
3 514:9,18 8
4 961:5,4 3
5 1369:1369,3 2
6 258:16,12 5
7 235:13,3 2
8 1096:19,17 8
9 847:7,17 6
10 1932:3,5 2
11 2491:4,8 3
12 840:421,36 2
13 1430:37,111 3
14 496:17,9 2
15 891:6,10 1
16 1560:196,21 2
17 516:20,12 5
18 696:30,59 2
19 1760:5,441 2
20 1736:11,26 5
21 1518:17,34 4
22 806:63,16 5
23 1920:3,97 2
24 1150:13,22 4
25 920:116,5 1
26 2016:7,337 2
27 408:9,25 2
28 735:36,8 2
29 470:5,31 2
30 2100:12,351 3
31 870:36,10 1
32 1512:253,13 2
33 697:12,15 3
34 1224:5,14 2
35 986:125,17 3
36 864:12,13 3
37 500:21,51 2
38 819:33,21 4
39 594:55,3 2
40 638:17,24 3").
次にメモ化プログラム。
dtree(D,_,Y,10000,10000,10000,_):-D<Y,!.
dtree(Y,_,Y,10000,0,10000,_):-!.
dtree(D,_,_,DX,DY,TD,F):-
arg(D,F,V),nonvar(V),!,V=(A,B,C),DX=A,DY=B,TD=C.
dtree(X,X,Y,DX,DY,TD,F):-
!,branch(X,L),(L==[]->(DX=0,DY=10000,TD=10000);
(tree2(L,X,Y,_,DY1,_,F),DX=0,is(DY,+(DY1,1)),TD=DY)),
arg(X,F,(DX,DY,TD)).
dtree(D,X,Y,DX,DY,TD,F):-
branch(D,L),(L==[]->(DX=10000,DY=10000,TD=10000);
(tree2(L,X,Y,DX1,DY1,TD1,F),
is(DX,+(1,DX1)),is(DY,+(1,DY1)),TD=TD1)),arg(D,F,(DX,DY,TD)).
tree2([H],X,Y,DX,DY,TD,F):-
dtree(H,X,Y,DX,DY,TD,F).
tree2([H|T],X,Y,DX,DY,TD,F):-
dtree(H,X,Y,DX1,DY1,TD1,F),tree2(T,X,Y,DX2,DY2,TD2,F),
is(DX,min(DX1,DX2)),is(DY,min(DY1,DY2)),TD3 is DX+DY+2, min_member(TD,[TD3,TD1,TD2]).
branch(D,L1):-K is D div 2,numlist(2,K,L0),include(mod0(D),L0,L),maplist(plus(1),L,L1).
%branch(D,L):-K is D div 2,findall(Z,(between(2,K,Z0),is(0,mod(D,Z0)),is(Z,+(1,Z0))),L).
mod0(D,X):-0 is D mod X.
solve(D,X,Y,N):-functor(F,x,D),dtree(D,X,Y,_,_,N,F).
go([]):-!.
go([A,B,C,D|T]):-
concat_atom([B1,B2],:,B),atom_chars(C1,C),
atom_number(B1,N1),atom_number(B2,N2),atom_number(C1,N3),
(N2>N3->solve(N1,N2,N3,N);solve(N1,N3,N2,N)),
write(A),write("->"),write(N),atom_chars(D1,D),atom_number(D1,D2),
(N==D2,Str=" pass";Str=" fail"),write(" "),write(Str),write("\n"),go(T).
start:-str(S),split_string(S,"\s,\n","\s",L),go(L),!.