オフラインどう書く第2回参考問題　　　第8回参考問題・第8回問題

16進数と2進数間の変換にひと手間加えた問題で、
tenton/4(10進数->n進数のリスト)やntoten/3(n進数のリスト->10進数)を作ってあったので、
比較的簡単に解けた問題をあつめました。

二値画像の回転
問題はこちら->https://qiita.com/Nabetani/items/9d80de41903775296ca6

手順通り解けばよい問題ですしrotate/2(90度回転)をすでに作っていましたので比較的簡単でした。
簡単な操作の連続なので悪い癖でsolveにだらだら書き継いたらごちゃごちゃしましたので、
行列を作るまでのforとrotateと行列を数字に戻し更に文字にするbackに分けました。
for/3で入力の文字列の先頭に"0x"をつけて処理系が16進数であることを認識できるようにし、
number_string/2で16進数の入力を10進数にし、tenton/4で2進数のリストに変換、
さらに4桁の倍数に足りない部分（前）に0を加えます。
その後tomat/5で必要な部分を取り出して、行列(正方形)に変え、
rotate/2で90度回転した行列をつくります。
back/3では行列を2進数のリストに戻し、４桁の倍数に足りない部分（後）に0を加え、
tomat/5で4桁づつの行列にし、各行をntoten/3で十進数に戻し更に16進数表示に変更、
最後に更に整形します。
  

```Prolog
%swi-Prolog  version 7.4.2
%begin.
%:-initialization(begin).   %　ideone

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).
                  
ntoten(B,L,R):-ntoten(B,L,0,R).
ntoten(_,[],XR,XR):-!.
ntoten(B,[H|T],X,XR):-X1 is X*B+H,ntoten(B,T,X1,XR).

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].

conv(X,R):-char_type(R,xdigit(X)).

tomat(0,_,_,M,M).
tomat(N,M,L,TL,R):-
     tomat1(M,L,L1,[],TL1),N1 is N-1,append(TL,[TL1],TL2),tomat(N1,M,L1,TL2,R).
tomat1(0,T,T,L,R):-
     reverse(L,R).
tomat1(N,[H|T],RT,L,R):-
     N1 is N-1,tomat1(N1,T,RT,[H|L],R).

for(N,S,LM):-string_concat("0x",S,S1),number_string(X,S1),tenton(X,2,[],L),
     length(L,M),Y is (4 - M) mod 4,length(L1,Y),maplist(=(0),L1),append(L1,L,L2),
     tomat(N,N,L2,[],LM).

back(N,LM1,R):-flatten(LM1,LM2),Y1 is (4- N*N) mod 4,
     length(L3,Y1),maplist(=(0),L3),append(LM2,L3,R1),length(R1,N1),N2 is N1 div 4,
     tomat(N2,4,R1,[],R2),maplist(ntoten(2),R2,R3),maplist(conv,R3,R4),
     number_string(N,NS),concat_atom(R4,R5),atomics_to_string([NS,":",R5],R).
     
solve(N,S,R):-for(N,S,LM),rotate(LM,LM1),back(N,LM1,R).

go([]):-!.
go([A,B|T]):-
     concat_atom([N,S],":",A),atom_number(N,N1),solve(N1,S,R),write(A),write("->"),write(R),
     (R==B->Str=" ok";Str=" no"),write(" "),write(Str),write("\n"),go(T).

ston([],[]):-!.
ston([H|T],L):-ston(T,L1),number_string(N,H),L=[N|L1].

begin:-str(S),split_string(S,"\s,\n","\s",L),go(L),!.

str("3:5b8 3:de0
1:8 1:8
2:8 2:4
2:4 2:1
2:1 2:2
3:5d0 3:5d0
4:1234 4:0865
5:22a2a20 5:22a2a20
5:1234567 5:25b0540
6:123456789 6:09cc196a6
7:123456789abcd 7:f1a206734b258
7:fffffffffffff 7:ffffffffffff8
7:fdfbf7efdfbf0 7:ffffffffffc00
8:123456789abcdef1 8:f0ccaaff78665580
9:112233445566778899aab 9:b23da9011d22daf005d40").
```
エントロピー符号
問題はこちら->http://nabetani.sakura.ne.jp/hena/ord8entco/

16進数を2進数に変換すとき、小さい桁が左になるように並べる問題なので、
一文字づつcha/2の中のconv/2で16進数の文字を10進数の数字に変換し、
tentonで2進数のリストにし、4桁に足りない部分（前）に0を加え、
最後にriverseを行います。それをmaplistとflattenでつなます。
find/4のmemberと逆向きに使ったappendで符号の候補に合致する部分リストを選んでいきます。

```Prolog

%swi-Prolog  version 7.4.2
%start.
%:-initialization(start).   %　ideone

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).

conv(X,R):-char_type(R,xdigit(X)).
cha(C,R):-
     conv(N,C),tenton(N,2,[],L3),length(L3,M),M1 is 4-M,length(L4,M1),
     maplist(=(0),L4),append(L4,L3,L5),reverse(L5,R).

find(_,[],_,"*invalid*").
find(DL,L,R1,FR):-
     member(S:X,DL),append(S,L1,L),!,
     (S=[1,1,1]->(reverse(R1,R11),atomics_to_string(R11,R12),FR=R12:L1);
     (R2=[X|R1],find(DL,L1,R2,FR))).
find(_,_,_,"*invalid*").

solve(DL,S,R):-
     atom_chars(S,L),maplist(cha,L,L1),flatten(L1,L2),find(DL,L2,[],R1),
     (R1="*invalid*"->R=R1;
     (length(L2,N2),R1=RS:L3,length(L3,N3),N is N2-N3,number_string(N,NS),atomics_to_string([RS,":",NS],R))).

start:-
     str1(D),atomics_to_string(L1,"\n",D),pre1(L1,DL),str2(P),split_string(P,"\s,\n","\s",L2),pre(DL,L2),!.

pre(_,[]).
pre(DL,[_,B,C|T]):-
     solve(DL,B,R),(R==C,Str=" ok ";Str=" no "),write(" "),write(Str),writeln(R),pre(DL,T).

pre1([],[]).
pre1([H|T],R):-
     pre1(T,R1),split_string(H,"\s","\s",[S,A]),atom_chars(S,L),maplist(atom_number,L,L1),R=[L1:A|R1].

str1("000        t
0010     s
0011     n
0100     i
01010    d
0101101          c
010111   l
0110     o
0111     a
10       e
1100     r
1101     h
111      end").

str2("0         16d9d4fbd       ethanol:30
1       df      e:5
2       ad7     c:10
3       870dcb  t:6
4       880f63d         test:15
5       a57cbe56        cat:17
6       36abef2         roll:23
7       ad576cd8        chant:25
8       3e2a3db4fb9     rails:25
9       51aa3b4c2       eeeteee:18
10      ad5f1a07affe    charset:31
11      4ab8a86d7afb0f  slideshare:42
12      ac4b0b9faef     doctor:30
13      cafebabe        nlh:17
14      43e7    sra:15
15      53e7    eera:15
16      86cf    tera:16
17      b6cf    hon:15
18      0       *invalid*
19      c       *invalid*
20      d       *invalid*
21      e       *invalid*
22      babecafe        *invalid*
23      8d      *invalid*
24      ad      *invalid*
25      af      *invalid*
26      ab6e0   *invalid*
27      a4371   *invalid*
28      a4371   *invalid*
29      96e3    *invalid*
30      0dc71   *invalid*
31      2a9f51  *invalid*
32      a43fb2  *invalid*
33      ab6e75  *invalid*
34      a5dcfa  *invalid*
35      ca97    *invalid*
36      6822dcb         *invalid*").
```
ビットボンバーマン
問題はこちら->http://nabetani.sakura.ne.jp/hena/ord8biboma/

前題と同じように16進数を2進数にし、地図（行列）に変換した後普通に縦横探索しました。
縦横のビット演算で解く方法があるのでしょうか？
Prologで解きましたので、リストのリストを壁用(WL)・爆弾用(BL)・爆風用(EL)の3つ用意しました。
tom/2の中で前題と同じくcha/2で一文字ずつ2進数を作り、繋げて、tomat/5で行列にします。
ただしcha/2の中でreverseは使っていません。
tomat/5でもう一つ値の決まっていないリストのリスト(EL)を作ります。
checkb/4でBLから爆弾の座標を割り出し、縦横探索して、
その移動先に壁があるかWLでチェックし、壁に当たるまでELに1をセットします。
その後リストを平坦にし、ELの値の決まっていないところに0をセットし、0を二つ追加し、
先頭が0になることが有るので4桁づつに分けて2進数->10進数->16進数表示にし、
最後に文字に直します。

```Prolog
%swi-Prolog  version 7.4.2
%begin.
%:-initialization(begin).   %　ideone

tenton(B,X,L):-tenton(X,B,[],L).
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).

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

conv(X,R):-char_type(R,xdigit(X)).
cha(C,R):-
     conv(N,C),tenton(N,2,[],L3),
     length(L3,M),M1 is 4-M,length(L4,M1),maplist(=(0),L4),append(L4,L3,R).

tomat(0,_,_,M,M).
tomat(N,M,L,TL,R):-
     tomat1(M,L,L1,[],TL1),plus(1,N1,N),append(TL,[TL1],TL2),tomat(N1,M,L1,TL2,R).
tomat1(0,T,T,L,R):-
     reverse(L,R).
tomat1(N,[H|T],RT,L,R):-
     plus(1,N1,N),tomat1(N1,T,RT,[H|L],R).

add0(L,R):-length(L,N),plus(N1,N,4),length(L1,N1),maplist(=(0),L1),append(L1,L,R).

tom(L,R):-
     atom_chars(L,L1),maplist(cha,L1,L4),flatten(L4,L5),tomat(5,6,L5,[],R).

checkb(0,_,_,_).
checkb(Y,BL,WL,L):-Y1 is Y-1,checkb(Y1,BL,WL,L),checkb1(Y,6,BL,WL,L).
checkb1(_,0,_,_,_).
checkb1(Y,X,BL,WL,L):-
     X1 is X-1,checkb1(Y,X1,BL,WL,L),((nth1(Y,BL,BL1),nth1(X,BL1,V),V=:=1)
     ->bon(Y,X,[1:0,-1:0,0:1,0:(-1)],WL,L);true).

bon(_,_,[],_,_).
bon(Y,X,[Y1:X1|T],WL,L):-bon(Y,X,T,WL,L),bon1(Y,X,WL,Y1:X1,L).

bon1(Y,X,_,_,_):-X<1;Y<1;X>6;Y>5.
bon1(Y,X,WL,Y1:X1,L):-
     (nth1(Y,WL,WL1),nth1(X,WL1,1))->true;
     (nth1(Y,L,L1),nth1(X,L1,1),plus(X,X1,X2),plus(Y,Y1,Y2),bon1(Y2,X2,WL,Y1:X1,L)).

form([]).
form([H|T]):-form(T),(H==1->true;H=0).

solve(W,B,R):-
     tom(W,WL),tom(B,BL),length(L,30),tomat(5,6,L,[],EL),checkb(5,BL,WL,EL),
     flatten(EL,L2),form(L2),append(L2,[0,0],L3),tomat(8,4,L3,[],L4),
     maplist(ntoten(2),L4,L5),maplist(conv, L5,L6),atomics_to_string(L6,R).

go([]):-!.
go([_,A,B|T]):-
     concat_atom([S1,S2],"/",A),solve(S1,S2,R),write(A),write("->"),write(R),
     (R==B->Str=" ok";Str=" no"),write(" "),write(Str),write("\n"),go(T).

ston([],[]):-!.
ston([H|T],L):-ston(T,L1),number_string(N,H),L=[N|L1].

begin:-str(S),split_string(S,"\s,\n","\s",L),go(L),!.

str("0  802b1200/01400c20       53c40cfc
1       28301068/84080504       d64fef94
2       100a4010/80010004       e241850c
3       81020400/000000fc       0e3cfbfc
4       80225020/7e082080       7fdd24d0
5       01201200/40102008       fe1861fc
6       00201000/01000200       43c48f08
7       00891220/81020408       ff060c1c
8       410033c0/0c300000       3cf0c000
9       00000000/01400a00       7bf7bf78
10      00000000/20000a00       fca2bf28
11      00000000/00000000       00000000
12      00cafe00/00000000       00000000
13      aaabaaaa/50000000       51441040
14      a95a95a8/56a56a54       56a56a54
15      104fc820/80201010       ea30345c
16      4a940214/05000008       05000008
17      00908000/05000200       ff043f48
18      00c48c00/fe1861fc       ff3873fc
19      00000004/81020400       fffffff0
20      111028b0/40021100       e08fd744
21      6808490c/01959000       17f7b650
22      30821004/81014040       c75de5f8
23      0004c810/10003100       fe4937c4
24      12022020/88200000       edf08208
25      2aa92098/01160000       45165964
26      00242940/10010004       fc43c43c
27      483c2120/11004c00       33c3de10
28      10140140/44004a04       eda3fe3c
29      0c901d38/72602200       f36da280").
```