CodeIQ:テトロミノビンゴの解答

オフラインリアルタイムどう書くの問題を解いていく過程で、
主催者の@nabetaniさんがCodeIQの問題を出題されているのを知り、
テストケースがそろっていて面白そうな問題を解いてみました。
CodeIQの問題は、時間制限があるらしいので、まずJuliaで解くことが多いのですが、
@nabetaniさんの問題は時間制限のきつくない問題が多いですのでPrologで解いています。

問題はこちら->http://nabetani.sakura.ne.jp/codeiq/tetromino_bingo/
解説と実装例->https://nabetani.hatenablog.com/entry/codeiq_tetromino_bingo

問題は4000件のデータを一括して扱うもので、答えはありませんでしたが、
1問1データタイプのサンプルだけでも50ほどありましたので、いくつかの方法で解いてみました。

パターンマッチ
元のカードのほかに新しいカードを用意し、データリストに元のカードの数字がなければ101で、
あったら、データリストのその数字のindexで新しいカードの同じ場所を埋めていき(makd/3)、
最後まで合わせ終わったら周りを101で囲み(makeb/4)、
checkb/2の中でカードをテトロミノのリストの幅や高さに合わせて切り取り(pxy1,member)、
回転(are/4)や反転(makep/2)をさせたものも含め、
五種のピースとパターンマッチさせ(pat/3)、（パターンが合って、その部分のカードの数字
(P)の最大値がそれに接する数字(A)の最小値より小さいときのみマッチする）
findallでそれらをすべて集め、
その中で、ピース内の数字の最大値が一番小さいテトロミノを選びます。
サンプル程度なら問題ありませんが、4000件のデータでは1分くらいかかります。

```Prolog
%SWI-Prolog (version 7.4.2,version 7.6.4)
%:-initialization(start).   %ideone
%start.

pat('I',[[_,A1,A2,A3,A4,_],[A5,P1,P2,P3,P4,A6],[_,A7,A8,A9,A0,_]],X):-
     max_list([P1,P2,P3,P4],X),min_list([A0,A1,A2,A3,A4,A5,A6,A7,A8,A9],Y),X<Y.
pat('L',[[_,A0,_,_,_],[A1,P1,A2,A3,_],[A4,P2,P3,P4,A5],[_,A6,A7,A8,_]],X):-
     max_list([P1,P2,P3,P4],X),min_list([A0,A1,A2,A3,A4,A5,A6,A7,A8],Y),X<Y.
pat('O',[[_,A0,A1,_],[A2,P1,P2,A3],[A4,P3,P4,A5],[_,A6,A7,_]],X):-
     max_list([P1,P2,P3,P4],X),min_list([A0,A1,A2,A3,A4,A5,A6,A7],Y),X<Y.
pat('S',[[_,_,A0,A1,_],[_,A2,P1,P2,A3],[A4,P3,P4,A5,_],[_,A6,A7,_,_]],X):-
     max_list([P1,P2,P3,P4],X),min_list([A0,A1,A2,A3,A4,A5,A6,A7],Y),X<Y.
pat('T',[[_,A0,A1,A2,_],[A3,P1,P2,P3,A4],[_,A5,P4,A6,_],[_,_,A7,_,_]],X):-
     max_list([P1,P2,P3,P4],X),min_list([A0,A1,A2,A3,A4,A5,A6,A7],Y),X<Y.

pxy([['I']:[6:3,3:6],['L','S','T']:[4:5,5:4],['O']:[4:4]]).     %50ms mo tigawanai

rotate(L,L1):-L=[H|T],maplist([A,B]>>(B=[A]),H,H1),foldl(apall,T,H1,L1).   %90do kaiten
apall([],[],[]).
apall([H1|T1],[H2|T2],R):-apall(T1,T2,R1),H3=[H1|H2],R=[H3|R1].

rot(0,_,L,L):-!.     %member/2 wo tukau to L1 no hensuu ga R1 no naka no list no hensuu to pattern match site ismau
rot(N,L,R1,R):-N1 is N-1,rotate(L,L1),R2=[L1|R1],rot(N1,L1,R2,R).

makep(L,R):-rot(4,L,[L],R1),reverse(L,L1),rot(4,L1,[L1|R1],R).

makeb(L,W,I,R):-
     length(L1,W),maplist(=(I),L1),L2=[L1|L],append(L2,[L1],L3),
     maplist([A,B]>>(append([I],A,B)),L3,L4),maplist([A,B]>>(append(A,[I],B)),L4,R).

makd(_,[],[]).
makd(D,[H|T],R):-makd(D,T,R1),atomics_to_string(L1,",",H),makd1(D,L1,L),R=[L|R1].
makd1(_,[],[]).
makd1(D,[H|T],R):-makd1(D,T,R1),(nth1(N,D,H)->R=[N|R1];R=[101|R1]).

delh([_|T],T).

are(N1,N2,L,R):-(are2(N1,L,L1),are1(N2,L1,R));(delh(L,L2),are(N1,N2,L2,R)).
are1(N,L,R):-maplist(are2(N),L,R);(maplist(delh,L,L1),are1(N,L1,R)).
are2(N,L,R):-length(R,N),append(R,_,L).

checkb(L,R):-
     pxy(L1),member(L2:XY,L1),member(X:Y,XY),are(X,Y,L,L3),　　%pxy/1->テトロミノのサイズ
     makep(L3,L4),member(L5,L4),member(C,L2),pat(C,L5,N),R=N:C.

solve(S,L,R):-
     makd(S,L,L2),makeb(L2,5,101,L4),
     findall(L5,checkb(L4,L5),R1),(R1==[]->R='-';sort(R1,[_:R|_])),!.

start:-str(S),split_string(S,"\n\s","\s",L),data(S1),atomics_to_string(L1,",",S1),go(L1,L),!. 

go(_,[]):-!.
go(S,[A,B|T]):-atomics_to_string(L,"/",A),solve(S,L,R),disp(R,B),go(S,T).

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

data("74,72,90,23,68,36,35,41,67,18,1,89,39,80,47,10,45,40,26,91,6,98,73,53,44,24,52,63,46,59,28,92,13,94,66,49,3,87,64,4,88,76,96,9,29,85,42,82,25,51,86,19,83,14,77,78,58,62,81,22,93,15,2,20,33,57,37,48,38,34,79,17,65,60,11,31,27,5,69,32,95,99,50,16,70,75,12,7,56,21,97,30,8,61,55,84,54,71,43").

str("93,84,33,81,79/18,36,13,89,92/46,34,55,78,63/32,59,49,88,11/3,45,60,56,20  S
74,72,90,23,68/36,35,41,67,18/1,89,39,80,47/10,45,40,26,91/6,98,73,53,44        I
11,31,69,27,5/32,95,99,50,43/16,70,75,84,30/12,7,56,54,8/21,97,71,61,55         L
24,72,31,36,27/17,35,70,59,6/65,26,38,39,18/32,89,46,84,86/47,87,45,80,33       I
50,90,41,93,62/53,99,11,30,37/77,1,80,13,7/79,3,71,85,57/6,44,38,39,17   I
36,48,8,12,91/14,37,41,96,55/30,93,10,21,20/82,11,44,13,64/47,66,28,32,52       I
90,15,18,89,80/56,45,7,76,14/16,63,27,73,53/55,25,62,50,42/3,79,37,28,49        L
86,68,58,24,96/71,23,90,38,99/45,91,69,25,83/81,39,7,62,5/65,1,12,63,15         L
36,92,73,51,54/71,26,28,46,30/8,9,59,55,2/10,17,56,85,83/25,91,63,19,27         L
74,2,54,76,65/32,85,98,38,11/97,36,24,43,87/96,62,42,44,9/50,45,49,63,13        O
51,24,52,13,88/43,62,50,33,39/72,64,83,32,10/86,76,97,57,91/14,93,6,79,78       O
73,32,19,31,14/17,36,62,25,5/4,22,23,50,11/12,96,65,74,72/9,37,7,90,2   O
96,71,1,19,84/12,18,39,73,26/35,56,92,60,11/9,14,61,28,81/48,33,75,46,57        S
74,8,34,63,96/61,26,15,37,64/73,2,6,86,57/93,53,33,79,83/21,38,52,5,22  S
23,15,44,10,26/55,41,78,49,65/96,67,39,38,92/50,59,58,71,53/1,48,66,98,73       T
16,30,92,34,54/26,56,85,83,58/32,52,97,78,10/72,42,27,41,47/11,2,79,61,31       T
44,27,20,19,93/13,74,33,29,71/99,47,72,7,42/79,37,22,15,73/91,10,48,30,98       T
10,86,51,88,87/40,32,16,54,38/26,61,11,21,66/83,7,60,84,13/6,53,24,19,28        -
97,63,26,40,75/13,74,19,18,66/34,72,89,90,50/14,36,22,23,42/54,12,16,11,30      -
29,72,26,49,69/43,58,22,94,8/2,67,24,66,75/99,31,38,13,14/15,45,63,4,48         -
24,85,36,69,9/40,66,16,70,81/54,71,60,11,20/99,46,26,67,74/31,42,56,19,86       I
50,14,60,43,61/32,55,90,48,40/10,45,27,30,67/57,29,89,83,52/44,19,81,88,26      I
84,1,4,32,85/70,78,69,38,26/12,91,15,56,24/19,94,20,71,73/49,25,11,43,5         I
32,90,62,92,80/20,55,27,24,41/25,15,65,58,67/63,77,88,53,40/78,21,22,2,14       I
89,32,80,4,2/69,91,27,96,34/15,66,94,39,10/86,11,1,17,35/16,82,20,37,18         L
47,58,24,92,96/97,69,23,14,87/71,65,15,17,28/67,37,55,72,10/48,7,85,99,38       L
15,79,5,36,20/59,46,80,69,34/7,8,12,19,96/90,9,54,75,91/33,63,11,73,2   L
80,94,26,41,18/75,34,76,52,68/23,14,15,81,37/92,82,77,55,25/27,45,60,2,47       L
30,12,23,6,59/16,39,2,95,51/34,58,52,32,11/88,69,38,56,71/45,49,55,4,5  L
51,74,28,39,9/54,22,15,29,65/27,13,55,81,8/50,40,56,93,60/70,90,1,35,21         L
49,80,41,60,4/11,76,36,50,89/13,2,78,55,14/52,48,77,58,22/10,17,8,64,18         L
86,42,83,97,14/5,63,91,17,56/73,1,66,75,27/50,30,39,89,53/15,41,48,24,36        L
43,98,74,53,92/58,40,52,56,2/35,67,27,10,46/37,13,14,15,19/39,8,73,30,24        L
89,25,77,68,71/99,93,11,27,40/21,65,43,20,72/70,67,5,28,24/61,49,94,64,86       L
26,98,46,97,95/63,18,54,48,93/70,9,19,43,34/94,12,37,8,17/62,83,28,60,84        O
68,18,25,61,41/40,83,84,75,64/42,44,87,32,3/78,35,23,96,52/59,1,74,65,70        O
80,6,43,87,60/64,94,17,11,1/86,95,76,77,96/39,10,23,90,74/42,12,3,63,52         O
21,63,7,78,61/82,92,4,47,34/91,83,56,64,52/72,1,38,80,13/62,35,55,49,20         S
97,30,43,81,23/76,66,86,78,50/25,37,6,19,83/46,47,67,56,58/27,39,32,99,36       S
55,59,39,15,36/83,96,89,74,20/92,73,14,94,53/32,95,11,66,56/30,46,33,35,48      S
88,32,34,81,31/9,67,24,79,64/46,15,11,47,71/43,33,13,68,98/63,42,82,70,89       S
34,73,18,46,48/69,62,93,32,35/85,90,64,54,26/66,61,80,94,78/40,27,8,81,44       S
50,82,84,17,86/1,34,6,18,24/60,48,7,85,93/94,49,47,62,79/52,36,71,12,83         T
97,16,34,47,61/12,20,29,87,90/21,11,43,14,78/37,9,92,42,59/51,26,99,6,89        T
67,50,63,10,85/69,75,4,45,72/73,31,99,40,57/93,28,42,24,26/35,23,64,9,34        T
93,31,90,42,24/59,35,41,91,4/63,8,43,37,67/45,74,60,71,52/14,32,15,84,7         T
8,30,2,58,4/27,56,57,40,95/47,11,26,38,81/53,5,80,33,21/15,50,51,72,82  T
89,61,49,96,23/42,95,48,24,22/87,34,47,65,14/81,30,84,29,21/77,55,2,75,7        T
24,88,78,69,10/89,77,73,86,29/54,67,3,14,70/42,12,83,60,61/45,19,7,99,36        -
29,81,16,84,78/7,74,88,2,27/44,58,86,83,45/43,62,60,77,80/35,11,94,12,64        -
86,64,37,34,57/75,42,29,54,17/39,59,35,73,65/6,67,93,50,12/55,11,98,45,1        -
80,82,55,45,52/92,79,12,17,96/84,35,47,66,32/22,56,29,19,53/57,3,91,28,8        -
34,66,18,41,95/89,93,10,51,69/45,48,36,72,24/49,85,80,55,21/7,37,54,32,17       -
45,68,74,29,24/85,17,59,73,70/30,91,42,23,14/72,86,25,79,60/13,54,93,6,65       -
37,91,75,64,13/53,94,30,34,18/31,96,27,5,57/81,90,89,56,25/49,88,35,61,45       -
8,69,17,34,67/10,88,7,94,97/45,33,54,4,25/39,18,66,76,16/72,55,30,42,96         -
30,50,42,73,55/57,41,34,77,65/64,91,67,52,36/96,56,17,45,37/12,14,97,33,88      -").
```
逐次的にチェック
データの最初の数から、次の基準で容器（リスト）に入れていきます。
　n番目までの数を調べて、k個の容器に分かれているとする。
　n+1番目の数がカードになければn+2番目を調べる。
　あればその数の座標を計算して、chf/6でその数の上下左右の座標が、
　k個の容器のどれかにあるか調べ、
　　　あればその容器に加える。二つ以上の容器にあればその容器を一つにまとめる。
　　　なければ新しい容器を作りその中に座標を入れる。
容器の要素の数が4ならば、テトロミノの候補とパターンマッチさせます。
nth1/3を二つ使用してカード上の数字を探すとともに座標を求めています。

```Prolog
%SWI-Prolog (version 7.4.2,version 7.6.4)
%:-initialization(start).   %ideone
%start.

pat('I',[[0:0,0:1,0:2,0:3],[0:0,1:0,2:0,3:0]]).
pat('L',[[0:0,0:1,0:2,1:0],[0:0,1:0,2:0,2:1],[0:0,1: -2,1:(-1),1:0],[0:0,0:1,1:1,2:1],[0:0,1:0,1:1,1:2],[0:0,1:0,2:(-1),2:0],[0:0,0:1,0:2,1:2],[0:0,0:1,1:0,2:0]]).
pat('O',[[0:0,0:1,1:0,1:1]]).
pat('S',[[0:0,1:0,1:1,2:1],[0:0,0:1,1:(-1),1:0],[0:0,1:(-1),1:0,2:(-1)],[0:0,0:1,1:1,1:2]]).
pat('T',[[0:0,1:0,1:1,2:0],[0:0,1:(-1),1:0,1:1],[0:0,1:(-1),1:0,2:0],[0:0,0:1,0:2,1:1]]).

bingo([],_,_,'-').       
bingo([H|T],L,PL,R):-
     nth1(Y,L,Z),nth1(X,Z,H),!,chf(PL,X:Y,[X:Y],[],PL1,R1),length(R1,N),       
     (N==4->checkb(R1,R);bingo(T,L,[R1|PL1],R)).
bingo([_|T],L,PL,R):-bingo(T,L,PL,R).

checkb(L,R):-sort(L,[X:Y|_]),maplist(red(X:Y),L,L1),sort(L1,L2),pat(R,PL),member(L2,PL).

chf([],_,R,PR,PR,R).
chf([H|T],X:Y,L,PL,PR,R):-
     (chf1(H,X:Y)->(append(H,L,L1),PL1=PL);(L1=L,PL1=[H|PL])),chf(T,X:Y,L1,PL1,PR,R).   %PL->list of list,H->list,L->list of one element
chf1(P,X:Y):- member(X1:Y1,[1:0,-1:0,0:1,0:(-1)]),X2 is X+X1,Y2 is Y+Y1,member(X2:Y2,P).

red(X1:Y1,X:Y,X2:Y2):-X2 is X-X1,Y2 is Y-Y1.

solve(S,L,R):-bingo(S,L,[],R1),atom_string(R1,R).

start:-str(S),split_string(S,"\n\s","\s",L),data(S1),atomics_to_string(L1,",",S1),go(L1,L),!.  % atomics_to_string(L,"\n ",S) to suruto saigo ni atom_chars(S1,S) ga hituyou

go(_,[]).
go(S,[A,B|T]):-
     atomics_to_string(L,"/",A),maplist([E,F]>>atomics_to_string(F,",",E),L,L3),solve(S,L3,R),disp(R,B),go(S,T).  

disp(R,A):-(R==A->Str=" pass ";Str=" fail "),write(Str),writeln(R).
```
同じ方法ですが辞書にカードの数字とその座標を登録しています。nth1/3使用の2-3倍の速さです。

```Prolog
%SWI-Prolog (version 7.4.2,version 7.6.4)
%:-initialization(start).   %ideone
%start.

pat('I',[[0:0,0:1,0:2,0:3],[0:0,1:0,2:0,3:0]]).
pat('L',[[0:0,0:1,0:2,1:0],[0:0,1:0,2:0,2:1],[0:0,1: -2,1:(-1),1:0],[0:0,0:1,1:1,2:1],[0:0,1:0,1:1,1:2],[0:0,1:0,2:(-1),2:0],[0:0,0:1,0:2,1:2],[0:0,0:1,1:0,2:0]]).
pat('O',[[0:0,0:1,1:0,1:1]]).
pat('S',[[0:0,1:0,1:1,2:1],[0:0,0:1,1:(-1),1:0],[0:0,1:(-1),1:0,2:(-1)],[0:0,0:1,1:1,1:2]]).
pat('T',[[0:0,1:0,1:1,2:0],[0:0,1:(-1),1:0,1:1],[0:0,1:(-1),1:0,2:0],[0:0,0:1,0:2,1:1]]).

bingo([],_,_,'-').           %tikuji
bingo([H|T],L,PL,R):-
     get_dict(H,L,Z)->(chf(PL,Z,[Z],[],PL1,R1),length(R1,N),       %nth yori dic ga hayai
     (N==4->checkb(R1,R);bingo(T,L,[R1|PL1],R)));bingo(T,L,PL,R).

checkb(L,R):-sort(L,[X:Y|_]),maplist(red(X:Y),L,L1),sort(L1,L2),pat(R,PL),member(L2,PL).

chf([],_,R,PR,PR,R).
chf([H|T],X:Y,L,PL,PR,R):-
     (chf1(H,X:Y)->(append(H,L,L1),PL1=PL);(L1=L,PL1=[H|PL])),chf(T,X:Y,L1,PL1,PR,R).   %PL->list of list,H->list,L->list of one element
     chf1(P,X:Y):- member(X1:Y1,[1:0,-1:0,0:1,0:(-1)]),X2 is X+X1,Y2 is Y+Y1,member(X2:Y2,P).

makd(0,[],[]).
makd(Y,[H|T],R):-makd(Y1,T,R1),Y is Y1+1,atomics_to_string(L1,",",H),makd1(Y,L1,_,L),append(L,R1,R).
makd1(_,[],0,[]).
makd1(Y,[H|T],N,R):-makd1(Y,T,N1,R1),N is N1+1,R=[H=N:Y|R1].

red(X1:Y1,X:Y,X2:Y2):-X2 is X-X1,Y2 is Y-Y1.

solve(S,L,R):-bingo(S,L,[],R1),atom_string(R1,R).

start:-str(S),split_string(S,"\n\s","\s",L),data(S1),atomics_to_string(L1,",",S1),go(L1,L),!. 

go(_,[]).
go(S,[A,B|T]):-atomics_to_string(L,"/",A),
     makd(_,L,L3),D=dic{}.put(L3),solve(S,D,R),disp(R,B),go(S,T).

disp(R,A):-(R==A->Str=" pass ";Str=" fail "),write(Str),writeln(R).
```
本来の問題の答えは上のコードを少し変えて、1秒程度でI:222,L:1111,O:333,S:666,T:777と出ます。
ところで、出題者のコードを実行できれば答えがわかることに（うかつなことに）最近気づき、
試したところ運よくそのまま動いたのですが、
答えがI:214,L:1115,O:317,S:684,T:778となり間違えたのかと思いました。
しかし、私の結果が偶然とは思えないのと、いくら考えても誤りが見つからないためいろいろ探して、
https://github.com/calotocen/CodeIQ/blob/tetrominobingo-1.0-release/テトロミノ＋ビンゴ！/solve.rb
に私の答えと同じ答えが有りましたので安心しました。@calotocenさん有難うございます。