オフラインどう書く第28回問題・CodeIQ(ぐるぐる曼荼羅)の解答

どう書く第27回問題と、解法が似ている同じ出題者のCodeIQの「ぐるぐる曼荼羅」の解答です。

どう書く第28回問題
問題はこちら->http://nabetani.sakura.ne.jp/hena/ord28spirwa/

通った道を新しい壁と考えます。
答が載っている問題だけなら迷路と同様に解けそうですが、
追加の大きな数の問題もありますので、漸化式を考えます。
東西南北のm周目の道の長さをe(m),w(m),s(m),n(m),壁の厚さをx1(m),x2(m)とすると
　x1(m+1)=x1(m)+2,x2も同様、e(m+1)=e(m)+1-1、w,s,nも同様
一周の歩数をcとし十字路の根元での重複を考えると、
　c=((e+1)+(w+1)+(s+1)+(n+1)+x1+x2)*2-4
これらを用いm周目の壁の厚さと道の長さ(wall/2)、一周の歩数(len/2)を求めます。
1周目からの積算が入力値を超える時の道の状態と残りの歩数(find/4)を求め、
chan/2で各辺での向きを変えるまでの歩数を計算し、　
calc/4で12個ある直線（辺）の歩数を順に引いて現在の位置と次の方向を出します。
道の状態と残りの歩数は容易に解けたのですが、そのあとは力任せです。
（北へ行く道の長さが1のときだけ周の終わりの方向が違うのをどのように処理するか等）。
追加問題の答はyancyaさんの
https://gist.github.com/yancya/2ec935c838c8a6aff9a6
より拝借しました。

```Prolog
%SWI-Prolog ver 7.6.4,7.4.2 

%start.
%:-initialization(start).   %ideone

len([X1,X2,X3,Y1,Y2,Y3],R):-R is (X1+X2+X3+Y1+Y2+Y3+4)*2-4.
wall([X1,X2,X3,Y1,Y2,Y3],[X1,X21,X3,Y1,Y21,Y3]):-X21 is X2+2,Y21 is Y2+2.
%twall(N,[X1,X2,X3,Y1,Y2,Y3],[X1,X21,X3,Y1,Y21,Y3]):-X21 is X2+ 2*N,Y21 is Y2+2*N.
%tlen(N,[X1,X2,X3,Y1,Y2,Y3],R):-R is (((X1+X2+X3+Y1+Y2+Y3)-2)*N+2*2*(N-1))*2+8*N.

chan([X1,X2,X3,Y1,Y2,Y3],[X31,Y21,X3,Y3,X21,Y3,X1,Y21,X1,Y1,X22,Y12]):-
     X31 is X3+1,Y21 is Y2-1,X21 is X2-1,X22 is X2-1,Y12 is Y1-1.

find(M,N,L,R):-
     len(L,N1),wall(L,L1),N2 is N-N1,(N2=<0->R=[L1,N];(M1 is M+1,find(M1,N2,L1,R))).

calc(N,[H1|T1],[_|T2],R):-N1 is N-H1,N1>0,!,calc(N1,T1,T2,R).
calc(_,[_,0],[H2|_],R):-!,R=H2.
calc(N,[H1|_],[H2,H3|_],R):-N1 is N-H1,(N1=:=0->R=H3;R=H2).

solve(N,[DN,DE,DS,DW],R):-
     N1 is N+1,L=[DW,1,DE,DN,1,DS],find(0,N1,L,[L1,M]),chan(L1,L2),
     calc(M,L2,[e,s,w,s,w,n,w,n,e,n,e,s,e],R).

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

pre([]).
pre([_,B,C|T]):-
     split_string(B,":","",[H|[N]]),split_string(H,",","",L),
     maplist(atom_number,L,L1),atom_number(N,N1),solve(N1,L1,R),disp(R,C),pre(T).

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

str("0       2,3,5,4:85      S
1       1,2,3,4:1       E
2       1,2,3,4:2       S
3       1,2,3,4:3       S
4       1,2,3,4:4       W
5       1,2,3,4:27      E
6       1,2,3,4:63      E
7       1,2,3,4:40      W
8       1,4,3,2:40      S
9       3,3,3,3:30      S
10      3,3,3,3:31      E
11      3,3,3,3:32      E
12      3,3,3,3:70      S
13      3,3,3,3:71      E
14      3,3,3,3:72      E
15      1,1,1,1:7       N
16      1,2,1,1:7       W
17      1,6,1,1:7       S
18      1,8,1,1:7       E
19      1,1,1,1:30      N
20      1,2,1,1:30      W
21      1,5,1,1:30      S
22      1,8,1,1:30      E
23      9,9,9,9:99      W
24      5,6,3,8:3       E
25      5,8,1,1:11      W
26      2,8,1,2:18      S
27      3,2,3,1:20      N
28      3,3,8,1:28      N
29      2,5,1,2:32      E
30      2,5,1,6:33      E
31      1,2,5,7:34      N
32      3,6,5,6:36      E
33      6,2,8,1:39      S
34      3,1,2,3:41      W
35      1,1,3,4:45      W
36      1,3,1,2:46      N
37      4,4,4,4:49      W
38      3,1,4,4:55      N
39      6,6,2,1:56      W
40      3,2,1,2:59      S
41      2,7,7,1:60      S
42      3,1,1,1:63      N
43      4,6,4,1:78      E
44      7,5,3,6:79      W
45      7,8,3,1:81      E
46      3,2,5,2:82      S
47      1,1,3,4:84      N
48      7,4,1,5:88      S
49      3,6,5,3:89      S
50      1,4,2,3:92      N
51      1,3,4,5:93      W
52      2,4,8,1:94      W
53      3,6,1,7:99      S
54      1234,2345,3456,4567:978593417  E
56      1234,2345,3456,4567:978593418  S
57      31415,92653,58979,32384:9812336139   W
58      31415,92653,58979,32384:9812336140   S
59      314159,265358,979323,84626:89099331642  S
60      314159,265358,979323,84626:89099331643  W").
```

ぐるぐる曼荼羅
作者のコメント（解説ではない）はこちら->http://nabetani.hatenablog.com/
問題とテストケースについてはこちらのお世話になりました。
https://blog.goo.ne.jp/r-de-r/e/3b3069a9c6051ae288ffd739be7e773f

正方形が基本ということで漸化式を出すのは容易なのに場合分けが大変そうなので
回避しようかと思いましたが、出題者お気に入りとのことなので挑戦しました。
n周目の一辺のマスの数B(n)、一周のマスの数S(n)は 
B(n+1)=B(n)*2+2,S(n+1)=S(n)*2+4,(=B(n)*4*2+4=B(n+1)*4-4)
漸化式に従って、mand/4で与えられた数字を含む四角の辺のマス目の個数(X1)と、
その前の四角の最後の数字(Y)（＝前の四角までの合計）を計算し、
それをもとに、与えられた数字の周囲の数字を求めます。
1と四角の左上の3マスは統合できなかったので別に計算しました。
辺と隅も別に計算、結局6通りの場合分けになりました。
3通りくらいにできればよかったのですが。
速さに問題がないので、プログラム中の式はまとめず計算の意味が分かるようにしてあります。

```Prolog
%SWI-Prolog ver 7.6.4,7.4.2 

%start.
%:-initialization(start).
mand(1,_,_,[1,1]):-!.              %s(N,1,1,R).
mand(N,X,Y,R):-
    X1 is X*2+2,X2 is (X1-1)*4, Y1 is Y+X2,(Y1>=N->R=[X1,Y];mand(N,X1,Y1,R)),!.   %X1->hen,X2->syuu Y->mae no danaki made no goukei

calc(1,_,[2,3,5,6,8,9,11,12]):-!.
calc(X,[X1,Y],R):-   %saisyo no masu,Y->goukei = maeno sikaku no saigo
    X=:=Y+1,!,A6 is X+1,A1 is Y,A2 is Y+(X1-1)*4,A3 is A2+3,A4 is A2+4,
    R=[A1,A6,A2,A3,A4].
calc(X,[X1,Y],R):-         %niban me no masu
    X=:=Y+2,!,A2 is X-1,A6 is X+1,A1 is Y,Y3 is Y+(X1-1)*4,
    A3 is Y3+5,A4 is Y3+6,R=[A1,A2,A6,A3,A4].
calc(X,[X1,Y],R):-         %saigo no masu
    X=:=Y+(X1-1)*4,!,A1 is X-1,A4 is X+1,A5 is X+2,A6 is Y+1,
    A2 is X+(X1*2+1)*4-2,A3 is A2+1,R=[A6,A1,A4,A5,A2,A3].
calc(X,[X1,Y],R):-     %kado
    N is X-Y,X2 is X1-1,divmod(N,X2,D,0),D<4,!,A6 is X+1,A1 is X-1,
    A2 is Y+X2*4+1+X2*2*D+3*(D-1),A3 is A2+1,A4 is A3+2,A5 is A4+1,R=[A1,A6,A2,A3,A4,A5].
calc(X,[X1,Y],R):-      %hen
     N is X-Y,X2 is X1-1,D is N div X2,A2 is Y+X2*4+1+N*2+3*D,A3 is A2+1,
     A1 is X-1,A6 is X+1,Y1 is Y+1-((X1-2) div 2-1)*4,A4 is Y1+(X-Y-2-1-D*3) div 2,     % -1-> div
     R=[A4,A1,A6,A2,A3].

solve(N,R):-mand(N,1,1,[X1,Y]),calc(N,[X1,Y],R).


start:-
     f(N,A),solve(N,R),split_string(A,"\s","\s",L),maplist(number_string,AL,L),
     disp(R,AL),fail.
start.

disp(R,C):-(R==C->Str=" yes ";Str=" no  "),write(Str),writeln(R).

f(1,"2 3 5 6 8 9 11 12").
f(2,"1  3 13 16 17").
f(3,"1  2  4 18 19").
f(4,"3  5 20 21 23 24").
f(5,"1  4  6 25 26").
f(6,"1  5  7 27 28").
f(7,"6  8 29 30 32 33").
f(8,"1  7  9 34 35").
f(10,"9 11 38 39 41 42").
f(11,"1 10 12 43 44").
f(12,"1 11 13 45 46").
f(13,"2 12 14 15 47 48").
f(48,"13  47  49 129 130").
f(17,"2 16 18 58 59").
f(21,"4 20 22 66 67").
f(22,"21 23 68 69 71 72").
f(23,"4 22 24 73 74").
f(26,"5 25 27 79 80").
f(30,"7 29 31 87 88").
f(31,"30 32 89 90 92 93").
f(32,"7 31 33 94 95").
f(35,"8  34  36 100 101").
f(39,"10  38  40 108 109").
f(40,"39  41 110 111 113 114").
f(41,"10  40  42 115 116").
f(45,"12  44  46 123 124").
f(10000000000000,"4999999999769 9999999999999 10000000000001 20000000000474 20000000000475").
```