オフラインどう書くE15・CodeIQ:カーペットの解答

オフラインどう書くE15問題と同じ出題者の類題CodeIQ：カーペットの解答です。

E15の解答。
問題はこちら->http://nabetani.sakura.ne.jp/hena/orde15nohil/

図を眺め法則を見つけて解く方法と座標に直して解く方法で解きましたが、
ここでは前者の方針を採用します。
三角形が3進数に対応していますので与えられた数を3進数のリストに変換します(tenton/4)。
その際最上位桁に0を付け加えます。（より大きい三角形の左端の意味）
以下の規則に則って3進数のリストを集めます。
最小の三角形内(calc/3)
　左上と下、左上と右上とは隣どうしです。
　最下位の桁が0と最下位が1や2
大きな三角形内での異なる三角形どうし(calc/4)
　右の三角形の底辺の左端と左の三角形の底辺の右端は隣どうしです
　 .10\*\<\-\> .01* (例:21000<->20111, 3^3 ⇔ 3^2+3^1+3^0)
　三角形の頂点と下の三角形の底辺の左端は隣どうしです
　 .20\* ⇔ .02* (例:12000<->10222, 2x3^3 ⇔ 2x3^2+2x3^1+2\*3^0)
  具体的には三進数のリストの最下位から同じ値(X)が続く間は変数のリスト(L)に変数を加え,
  違う値(H)が出たら、X+Hが3でない場合に限り、Lの要素の値をHに変え、Xを追加し、
上位桁のリストと結合します。
集めた3進数のリストをthree/2で10進数に変換します。

```Prolog
%SWI-Prolog (version 7.4.2,version 7.6.4)
%:-initialization(start).   %ideone
%start.
tenton(0,_,[],L):-L=[0],!.
tenton(0,_,L,L):-!.
tenton(X,B,L,RL):-X1 is X div B,R1 is X-(X1*B),tenton(X1,B,[R1|L],RL).
                  
three(R0,R1):-ntoten(3,R0,0,R1).

ntoten(_,[],XR,XR):-!.
ntoten(B,[H|T],X,XR):-X1 is X*B+H,ntoten(B,T,X1,XR).

solve(X,RE):-
     tenton(X,3,[],L),reverse([0|L],[H|T]),calc(H,[],[H|T],R0),
     calc(L,H,R2),maplist(three,R2,R3),(var(R0)->RE=R3;(three(R0,R1),RE=[R1|R3])),!.
             
calc(L,0,R):-reverse(L,[_|T]),reverse([1|T],L1),reverse([2|T],L2),R=[L1,L2],!.
calc(L,_,R):-reverse(L,[_|T]),reverse([0|T],L1),R=[L1],!. 

calc(0,_,[],_):-!.         
calc(X,L,[X|T2],R):-calc(X,[_|L],T2,R),!.
calc(X,L,[H|T2],R):-(X+H=:=3->!;(maplist(=(H),L),reverse(T2,T3),append(T3,[X|L],R))). 

start:-                
     str(S),split_string(S,"\s\n","\s",L),maplist(split,L,L1),pre(L1).

split(S,L):-atomics_to_string(L,",",S).

pre([]):-!.
pre([_,[B],C|T]):-
     atom_number(B,BN),solve(BN,R),sort(R,R1),maplist(atom_number,C,C1),
     atomics_to_string(R1,",",S),
     (R1==C1->Str=" pass";Str=" fail"),write(Str),write(" "),writeln(S),pre(T).

str("0       21      19,22,23
1       0       1,2
2       1       0,3
3       2       0,6
4       3       1,4,5
5       4       3,9
6       9       4,10,11
7       15      11,16,17
8       27      13,28,29
9       32      30
10      47      45,51
11      65      63,69
12      80      78,162
13      199     198,201
14      204     200,205,206
15      243     121,244,245
16      493     492
17      508     507
18      728     726,1458
19      793     792,795
20      902     900,906
21      981     976,982,983
22      1093    1092,2187
23      1202    1200
24      1300    1299,1305
25      1962    1952,1963,1964
26      2188    2187,2190
27      2405    2403,2409
28      3326    3324
29      6561    3280,6562,6563
30      6612    6608,6613,6614
31      7058    7056,7062
32      8444    8442,8448
33      9841    9840,19683
34      15243   15239,15244,15245
35      19946   19944,19950
36      21148   21147
37      39365   39363
38      39366   19682,39367,39368
39      55694   55692,55698
40      57245   57243
41      66430   66429,66432
42      92740   92739
43      115250  115248
44      163031  163029
45      221143  221142,221157
46      410353  410352
47      412649  412647,412659
48      550391  550389
49      699921  699880,699922,699923
50      797161  797160,1594323
51      1000000         999999,1000002").
```

カーペット 
問題とテストケースについてこちらのお世話になりました。解答もあります。
->https://blog.goo.ne.jp/r-de-r/e/83b7f830d93b31f74d1d9dcde7694228

この問題も図から法則を見つける方法と座標に変換する方法で解きましたが、
ここでは座標に変換する方法を採用します。
8個（組）で正方形を作り、正方形の中では縦横3個（組）ずつ並びますので、
入力値から1を引き8進数に直し、上位桁から、
正方形中の並び方と座標の対応リスト(tox/1,toy/1)に従い、
正方形の中のxy座標（3進数）に直し、3をかけて足してゆき全体のxy座標を導きます(getxy/3)。
次いで隣(cal/1)の新しい座標を求め、下位桁から逆に3進数のリストに変換し、
toxとtoyを逆に使って8進数に変換し(getl/3)、
ntoten8/2で10進数に変え、最後に1を足します(getn/2)。

```Prolog

%SWI-Prolog (version 7.4.2,version 7.6.4)
%:-initialization(solve).  %ideone
%solve.
ntoten8(L,R):-ntoten(8,L,0,R),!.

ntoten(_,[],XR,XR):-!.
ntoten(B,[H|T],X,XR):-X1 is X*B+H,ntoten(B,T,X1,XR).

tenton(0,_,[],L):-L=[0],!.
tenton(0,_,L,L):-!.
tenton(X,B,L,RL):-X1 is X div B,R1 is X-(X1*B),tenton(X1,B,[R1|L],RL).


tox([0:0,1:1,2:2,3:2,4:2,5:1,6:0,7:0]).
toy([0:0,1:0,2:0,3:1,4:2,5:2,6:2,7:1]).

cal([[0,-1],[1,0],[0,1],[-1,0]]).

getxy([H],[X1,Y1],[X2,Y2]):-
     tox(LX),member(H:X,LX),toy(LY),member(H:Y,LY),X2 is X1*3+X,Y2 is Y1*3+Y,!.
getxy([H|T],[X0,Y0],R):-
     tox(LX),member(H:X,LX),toy(LY),member(H:Y,LY),X1 is X-1,Y1 is Y-1,
     X2 is X0*3+X,Y2 is Y0*3+Y,getxy(T,[X2,Y2],R),!.

getl([0,0],R,R):-!.
getl([X,Y],L,R):-
     divmod(X,3,D1,M1),X1 is M1,divmod(Y,3,D2,M2),Y1 is M2,
     tox(LX),member(H:X1,LX),toy(LY),member(H:Y1,LY),L1=[H|L],getl([D1,D2],L1,R),!.

getn([X,Y],R):-
     cal(L1),member([X1,Y1],L1),X2 is X+X1,Y2 is Y+Y1,
     X2>=0,Y2>=0,X3 is X2,Y3 is Y2,getl([X3,Y3],[],L2),ntoten8(L2,R1),R is R1+1.

solve:-
     f69(N,A),N1 is N-1,tenton(N1,8,[],L),getxy(L,[0,0],[X,Y]),
     findall(R1,getn([X,Y],R1),R2),sort(R2,R),disp(R,A),fail.
solve.

disp(R,A):-(R==A->Str=" pass";Str=" fail"),write(Str),write(" "),writeln(R).

f69(1,[2,8]).
f69(2,[1,3]).
f69(4,[3,5,16]).
f69(10,[9,11]).
f69(101,[100,102,183]).
f69(1011,[1001,1010,1012,1021]).
f69(10008,[9996,10001,10007]).
f69(2341,[2340,2342,7607,29843]).
f69(16385,[15799,16386,16392,21651]).
f69(18725,[18724,18726,60855,238739]).
f69(902876,[902875,902877,4190208]).
f69(1000000,[999580,999993,999999]).
```