オフラインどう書く第23回問題・CodeIQ(ヘックス上の最長狭義単調増加列)の解答

オフラインどう書く第23回問題と、同じ出題者のCodeIQの類題の解答です。

オフラインどう書く第23回問題
問題はこちら->http://nabetani.sakura.ne.jp/hena/ord23snakemoinc/

単純にsolveのbetween/3二つで探索開始位置を決め、
count/6と二番目のfindallで開始位置が同じで題意に沿う経路とその長さをすべて集め、
max_list/2でその最長を求め、最初のfindallですべての開始位置の最長を集め、
二番目のmax_listで全体の最長を求めています。

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

count(L,V,X,Y,R1,R):-
     member(DX:DY,[0:1,0:(-1),1:0,-1:0]),X1 is X+DX,Y1 is Y+DY,R2 is R1+1,
     ((X1>0,X1<6,Y1>0,Y1<6,nth1(X1,L,L1),nth1(Y1,L1,V1),V1>V)->
     count(L,V1,X1,Y1,R2,R);R=R2).

solve(L,R):-
     findall(M,(between(1,5,X),between(1,5,Y),nth1(X,L,L1),nth1(Y,L1,V),
     findall(N,count(L,V,X,Y,0,N),NL),max_list(NL,M)),ML),max_list(ML,R).

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

pre([]).
pre([_,B,Q,_|T]):-
     atomics_to_string(BL,"/",B),maplist(atom_chars,BL,L),maplist(aton,L,L1),
     solve(L1,R),disp(R,Q),pre(T).

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

aton(L,R):-maplist(atom_number,L,R).

str("0  01224/82925/69076/32298/21065   6       0,1,2,3,6,8
1       03478/12569/03478/12569/03478   10      0,1,2,3,4,5,6,7,8,9
2       09900/28127/87036/76545/87650   10      0,1,2,3,4,5,6,7,8,9
3       77777/77777/77777/77777/77777   1       7
4       00000/11111/22222/33333/44444   5       0,1,2,3,4
5       01234/12345/23456/34567/45678   9       0,1,2,3,4,5,6,7,8
6       10135/21245/43456/55567/77789   8       0,1,2,4,5,7,8,9
7       33333/33333/55555/55555/77777   2       3,5
8       01234/11234/22234/33334/44444   5       0,1,2,3,4
9       98765/88765/77765/66665/55555   5       5,6,7,8,9
10      01234/10325/23016/32107/45670   8       0,1,2,3,4,5,6,7
11      34343/43434/34343/43434/34343   2       3,4
12      14714/41177/71141/17414/47141   3       1,4,7
13      13891/31983/89138/98319/13891   4       1,3,8,9
14      01369/36901/90136/13690/69013   5       0,1,3,6,9
15      02468/24689/46898/68986/89864   6       0,2,4,6,8,9
16      86420/68642/46864/24686/02468   5       0,2,4,6,8
17      77777/75557/75357/75557/77777   3       3,5,7
18      53135/33133/11111/33133/53135   3       1,3,5
19      01356/23501/45024/61246/13461   5       0,1,3,5,6
20      46803/68025/91358/34792/78136   4       0,3,5,8
21      66788/56789/55799/43210/33211   9       0,1,2,3,5,6,7,8,9
22      40000/94321/96433/97644/98654   9       0,1,2,3,4,6,7,8,9
23      58950/01769/24524/24779/17069   6       0,2,4,5,7,9
24      97691/01883/98736/51934/81403   4       0,3,4,6
25      92049/27798/69377/45936/80277   5       3,6,7,8,9
26      97308/77113/08645/62578/44774   5       0,1,4,6,8
27      90207/17984/01982/31272/60926   6       0,1,2,7,8,9
28      62770/65146/06512/15407/89570   4       0,1,2,6
29      93914/46889/27554/58581/18703   5       2,4,6,7,8
30      42035/12430/60728/30842/90381   5       0,3,4,7,8
31      90347/53880/67954/95256/68777   6       0,3,5,6,7,9
32      05986/60473/01606/16425/46292   5       0,4,7,8,9
33      18053/90486/24320/04250/03853   5       0,2,3,4,8
34      36865/13263/67280/18600/12774   5       0,3,5,6,8
35      72456/72052/79971/14656/41151   5       1,2,5,7,9
36      94888/28649/05561/76571/97567   5       0,5,6,7,9
37      50214/94693/88718/78922/55359   5       0,2,6,7,8
38      76502/99325/17987/31737/93874   7       0,2,3,5,6,7,9
39      87142/14764/13014/00248/73105   6       0,1,3,4,7,8
40      24573/71679/48704/19786/91834   7       1,4,5,6,7,8,9
41      20347/61889/06074/61263/20519   7       0,1,2,6,7,8,9
42      74344/97459/97302/14439/35689   6       0,3,4,6,8,9
43      04794/52198/50294/09340/24160   5       1,2,4,7,9
44      41065/69344/64698/54167/43348   7       1,3,4,6,7,8,9
45      39947/15696/03482/19574/70235   7       0,3,4,5,7,8,9
46      92767/16790/84897/69765/75734   7       3,4,5,6,7,8,9
47      09654/79610/05070/23456/74687   8       0,2,3,4,5,6,7,8
48      73998/98799/98707/05633/23915   8       0,2,3,5,6,7,8,9
49      35661/17480/89723/64335/27217   7       1,2,3,4,6,8,9
50      02489/77571/84873/03879/84460   7       0,2,4,5,7,8,9").
```

ヘックス上の最長狭義単調増加列
出題者のコメント
　http://nabetani.hatenablog.com/entry/2018/09/30/173106
具体的な問題とテストケースはこちらのお世話になりました。
　https://blog.goo.ne.jp/r-de-r/e/f27280c6a56a2c79d4163efd7ff567f3

基本的には前の問題と同じ解き方ですが、
https://qiita.com/smallbigcats/items/77ee33dd8d4ebe37d025
などと同様、座標を一列の数字にしましたので、countでの座標の計算法が変わっています。
2021.03.08三行追加
数字で表された座標のリストn(Co)にアルファベットをくっつけ新しいリストにします。
計算した移動先の候補が図形の範囲内かどうかは、
それが座標のリスト(CL)に含まれているかどうかをcount/4で調べて判断します。
探索開始位置もリストの最後から順に調べるだけで済みます。
またメモ化有りのほうは、count1/5のように、ある座標からすでに調べた経路の最長値がR1で、
次の経路を調べるとき、その最初の座標の値がメモに有ったら、
その値Vに1を足した数とR1の大きいほうが、その位置からすでに調べた経路の最長値になります。
メモになければ普通に探索します。
ある座標からの経路を全て調べたら、その最長値をメモに登録します。

```Prolog
%SWI-Prolog version 7.4.2,7.6.4
%メモ化無し
%start
%:-initialization(start).   %ideone
%メモ化有り
%start1
%:-initialization(start1).  %ideone

n([1,2,3,4,
11,12,13,14,15,
21,22,23,24,25,26,
31,32,33,34,35,36,37,
42,43,44,45,46,47,
53,54,55,56,57,
64,65,66,67]).

count(N:A,CL,R1,R):-
     member(X,[1,-1,10,-10,11,-11]),N1 is N+X,R2 is R1+1,
     ((member(N1:A1,CL),A1>A)->count(N1:A1,CL,R2,R);R=R2).

solve([],_,0):-!.
solve([H|T],CL,R):-
     solve(T,CL,R1),findall(N,count(H,CL,0,N),NL),
     max_list(NL,M),(M>R1->R=M;R=R1).

count1(_,_,[],_,1).
count1(Memo,N:A,[H|T],CL,R):-
     count1(Memo,N:A,T,CL,R1),N1 is N+H,
     ((member(N1:A1,CL),A1>A)->(nth1(N1,Memo,V),(nonvar(V)->R is max(R1,V+1);
     (count1(Memo,N1:A1,[1,-1,10,-10,11,-11],CL,R2),
     nth1(N1,Memo,R2),R is max(R1,R2+1))));R=R1).

solve1(_,[],_,0):-!.
solve1(Memo,[H:X|T],CL,R):-
     solve1(Memo,T,CL,R1),nth1(H,Memo,V),(nonvar(V)->R is max(R1,V);
     (count1(Memo,H:X,[1,-1,10,-10,11,-11],CL,M),nth1(H,Memo,M),(M>R1->R=M;R=R1))).

join(X,Y,Z):-Z=X:Y.

start:-
     f47(S,A),atomics_to_string(L,"/",S),maplist(atom_codes,L,L1),
     flatten(L1,L2),maplist(plus(-96),L2,L3),
     n(Co),maplist(join,Co,L3,L4),solve(L4,L4,R),judg(R,A),fail.
start.

start1:-        %Memoization
     f47(S,A),atomics_to_string(L,"/",S),maplist(atom_codes,L,L1),
     flatten(L1,L2),maplist(plus(-96),L2,L3),length(Memo,67),
     n(Co),maplist(join,Co,L3,L4),solve1(Memo,L4,L4,R),judg(R,A),fail.
start1.

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

f47("javc/fhqvv/nerncj/actuybv/unrutf/sxgff/xjdi",10).
f47("kmyv/fuhxe/hhnnvr/dygmgwo/jbwkfu/zqthb/jxbl",9).
f47("ukps/kjcrl/ymfsqq/kbzfidr/dktjby/submc/ktps",8).
f47("zxgm/jzcwp/yacivm/ibckuek/bgoznq/svqfp/gfwn",7).
f47("pfqr/qvplf/kkrxqk/tbvravh/hurwxp/vnvwv/xjzt",6).
f47("onjw/cmtxj/jntmsv/ffttgre/sxsveu/deuey/qygd",5 ).
f47("neoo/boifu/dpgzxz/jhlqwwi/oijunp/fseev/tpwj",11).
f47("abcd/rstue/qpqrvf/povwswg/onutxh/nmzyi/mlkj",26).
f47("dddd/dcccd/dcbbcd/dcbabcd/dcbbcd/dcccd/dddd",4).
f47("gggg/ffffg/eeeefg/ddddefg/cccdef/bbcde/abcd",7).
f47("kjih/xyzag/wvutbf/jklmsce/ihgnrd/bcfoq/adep",26).
f47("dddd/ddddd/ccccdd/cccccdd/bbbccd/bbbcc/abbc",2).
f47("mmmm/mmmmm/mmmmmm/mmmmmmm/mmmmmm/mmmmm/mmmm",1).
f47("yxwv/zkjiu/slcbht/rmdagst/qnefru/popqv/zyxw",26).

```