オフラインどう書く過去問(E01)解答

問題はこちら->http://nabetani.sakura.ne.jp/hena/orde01rotbk/

Bouwkamp表示のまま回転させる方法を思いつきませんでしたので、
おそらく座標をもとにBouwkamp表示にしたのでしょうから、素直に座標に戻しました。
この問題もPrologでsort/4を使って解こうとしましたが、うまくいきませんでした。
Juliaでは、同様の関数を使って解けました。
まずtoxyで初期値x=y=0として、
最初のグループの矩形の左辺と下辺の座標を決めて座標のリストに入れ、
下辺のy座標でソートして一番上の矩形の左端から次のグループの矩形を接続し、
左辺と下辺の座標を決めて座標のリストに入れソートし、
下辺のY座標を更新することを繰り返してすべての矩形の座標を確定。
(更新したら、用済みの矩形は新しい座標のリストに移す)
その後図形を回転させる代わりに、toboで新しい座標のリストのy座標を降順に
更にx座標を昇順にソートし、左下から(X=0から)左辺のX座標が同じでy方向に連続な矩形を
同グループにいれBouwkamp表示を作りました。

```Julia
#julia 0.52 0.6

str="0 	4:(55,44,48)(40,4)(52)(26,29)(23,3)(20,31,21)(5,47)(43)(9,17)(1,8)(32)(25) 	(32,31)
1 	6:(33,29,50)(4,25)(37)(15,35)(16,9)(7,2)(17)(42,18)(6,11)(8,27)(24)(19) 	(6,17,2)
2 	7:(60,50)(23,27)(24,22,14)(7,16)(8,6)(12,15)(13)(2,28)(26)(4,21,3)(18)(17) 	(4,16)
3 	6:(99,73,56)(17,39)(68,22)(36,25)(57,42)(9,16)(2,7)(10,28)(23)(15,87,18)(72)(69) 	(10,36,22)
4 	7:(79,49,66,63)(32,17)(3,60)(29,57)(55,22,2)(20,14)(15,28)(33,9)(24)(11,134)(123) 	(29,17)
5 	7:(159,129)(57,72)(56,39,25,16,23)(9,7)(2,28)(36)(42,15)(17,22)(87)(10,18)(73)(68)(60) 	(10,28)
6 	14:(113,71,68)(32,36)(42,29)(13,44,4)(40)(62,37,38,31)(7,108)(25,12)(11,34)(23)(77,10)(67) 	(36)
7 	8:(145,125)(53,72)(45,11,9,16,31,33)(2,7)(13)(8,15)(21)(14,32)(30,37,19)(80)(18,73)(62)(55) 	(31)
8 	1:(175,140,164)(35,29,52,24)(28,160)(6,23)(130,86)(43,60)(26,17)(77)(44,68)(174)(5,155)(150) 	(174,130,175)
9 	6:(240,168,187)(149,19)(206)(163,77)(86,82,58)(40,18)(22,202)(4,78)(192,61)(62)(48,13)(35,118)(83) 	(4,82)
10 	5:(100,73,59)(14,45)(56,31)(58,42)(25,51)(19,36,26)(16,18,8)(2,17)(10)(77)(74)(28)(23,30)(44,7)(37) 	(2,19,56,73)
11 	8:(100,88,76)(27,49)(12,19,39,18)(95,11,6)(3,24)(5,1)(21)(20)(16)(2,47)(77,45)(92)(69,26)(17,60)(43) 	(19)
12 	11:(262,196,203)(83,106,7)(210)(161,84,17)(36,41,23)(18,111)(31,5)(64)(77,38)(102)(73,248)(238)(175) 	(248)
13 	9:(117,79,74)(5,69)(84)(71,46)(20,49)(25,39,57,29)(82,14)(78)(35,18)(13,12,50)(1,11)(4,10)(33,6)(27) 	(1,12)
14 	7:(163,95,78)(17,61)(68,44)(24,81)(89,94,72)(15,66)(42,45)(84,5)(79,20)(59,3)(26,22)(16,50)(4,34)(30) 	(30,26,3)
15 	10:(100,95,69)(26,43)(11,16,77,17)(88,12)(6,5)(1,20)(19)(60)(39)(18,21)(45,92)(76,27,3)(24)(49,2)(47) 	(47,2)
16 	8:(120,78,102)(34,20,24)(14,6)(2,10,23,91)(8)(53,13)(75,45)(36)(4,32)(30,47,25)(22,3)(19,107)(105)(88) 	(4,36,13)
17 	13:(119,124,96)(28,68)(114,5)(117,40)(56,52)(4,48)(21,15,24)(106,8)(6,9)(98,38,16)(13,20)(22,7)(75)(60) 	(20)
18 	2:(302,277,246)(57,189)(25,117,109,26)(235,92)(83)(8,135,49)(90,127)(81,157)(53,37)(5,76)(304)(288)(233) 	(53,90,92)
19 	13:(158,109,240)(49,60)(114,82,11)(71)(126,267)(62,52)(10,42)(40,32)(8,51,141)(48)(14,37)(39,9)(23)(7,53)(46) 	(60)
20 	8:(132,113,251)(19,36,58)(107,27,17)(10,21,22)(25,12)(1,20)(13)(80)(32,6)(26)(23,35)(130)(121,245)(127,3)(124) 	(26,6)
21 	4:(187,127,194)(60,67)(131,76,40)(33,72,156)(44,29)(19,10)(55,21)(82)(13,27,4)(23)(34)(50)(190,30)(160,2)(158) 	(60,127)
22 	12:(239,245)(132,107)(124,121)(27,25,32,23)(3,118)(35,115)(113,19)(12,13)(17,10)(6,26)(21,1)(20)(36)(22,80)(58) 	(124,245)
23 	3:(176,152)(24,38,90)(80,63,43,14)(52)(20,23)(17,26,40)(37,42,86)(72,25)(16,10)(6,4)(49,19,8,5)(47)(3,44)(11)(30) 	(17,63)
24 	15:(171,181)(95,76)(93,88)(19,30,27)(42,40,32)(5,83)(3,15,29,78)(21,12)(9,18)(8,54)(4,25)(2,46)(22)(44)(1,24)(23) 	(93,181)
25 	13:(152,88,112)(64,24)(44,92)(200,12,4)(8,7,33)(1,6)(16,5)(11)(27)(18,15)(3,31,73)(29,19)(10,9)(40)(39)(77,2)(75) 	(3,15)
26 	13:(484,316,379)(108,145,63)(82,360)(42,66)(29,198)(18,24)(308,194)(119)(69,50)(168,80)(114,149)(440)(387,35)(352) 	(379)
27 	12:(181,191)(93,88)(24,23,54,46,44)(1,22)(25)(2,42)(4,18)(8,40)(29)(9,21,32)(15,12)(3,30)(5,103,27)(98)(19,95)(76) 	(21)
28 	18:(83,79,123)(35,44)(52,31)(21,36,9)(27,60,89)(48,25)(10,20,33)(23,12)(2,5,13)(11,3)(8)(102,49,45)(16,73)(4,57)(53) 	(123)
29 	4:(649,439,456)(214,208,17)(473)(6,55,147)(385,260,4)(175,49)(104)(12,135)(116)(81,94)(125,216)(203,7)(615)(510)(419) 	(81,175,4)
30 	17:(100,114,48,53)(43,5)(58)(23,20)(61,25,14)(3,75)(11,47,96)(36)(95,49)(24,51)(37,105,27)(78)(9,28)(59,26,19)(7,40)(33) 	(58,5)"

function toxy(bo)
    tl1=[[0,0,0]]
    tl2=[]
    for gr in bo
        sort!(tl1,by= x->x[1])
        sort!(tl1,by= x->x[2])
        x,y,w=shift!(tl1)
        push!(tl2,[x,y,w])
        x2=x
        while tl1!=[]
            x1,y1,w1=tl1[1]
            if x1>x+w || y!=y1
               break
            end
            x,w=x+w,w1
            push!(tl2,shift!(tl1))
        end
        for n0 in gr
            n=parse(Int,n0)
            push!(tl1,[x2,y+n,n])
            x2=x2+n
        end
    end
    return append!(tl2[2:end],tl1)
end

function tobo(tl)
    tmp=[]
    nbo=[]
    sort!(tl,by= x-> x[2],rev=true)
    sort!(tl,by= x-> x[1])
    x,y=0,tl[1][2]
    for (x1,y1,w1) in tl
        if x1==x && y1==y
            push!(tmp,w1)
        else
            push!(nbo,tmp)
            tmp=[w1]
        end
        x,y=x1,y1-w1
    end
    return push!(nbo,tmp)
end

function solve(n,bo)
    return tobo(toxy(bo))[parse(Int,n)]
end

function main()
    str1=split(str,"\n")
    for s in str1
        s1=split(s," ")
        s2=split(s1[2],":")
        w= matchall(r"\(.+?\)", s2[2])
        bo=[]
        for i in w
            i=i[2:end-1]
            push!(bo,split(i,","))
        end
        ans1=solve(s2[1],bo)
        ans="("*join(ans1,",")*")"
        if ans==strip(s1[3])
            sel="pass"
        else
            sel="fail"
        end
        print(sel," ",ans,"\n")
    end
end

@time main()

```
次はPrologです。
座標からBouwkamp表示にするのにtoxy/3を逆向きに使えればよかったのですが、
Prologといえどさすがに無理でしたので新しく関数（tobo/2）を作りました。
sort/4でy座標で降順にソートした後x座標で昇順にソートすると順序が狂いますので、
toxyではy座標をキーとし、toboではYの前後を逆にして(newY=maxY-oldY）、
x座標をキーとしてkeysort/2を使いました。
xy/4の中のWの計算は、下辺が同じ高さの部位の長さが必要かと思って入れましたが、
実際は左端のx座標のみでよかったので使用していません。

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

exch([],[]).
exch([A-B-W|T],L):-exch(T,L1),L=[B-A-W|L1].

toxy([H],[],R):-
     xy(0-0-0,H,[],R).
toxy([H2|T2],L,R):-
     toxy(T2,L1,R1),keysort(R1,[H1|T1]),same(T1,H1,P,[H1],L2,T3),
     xy(P,H2,[],L3),append(T3,L3,R),append(L1,L2,L).

same([Y-X-W|T],Y-X1-W1,P,L,R,T2):-X=:=X1+W1,W2 is W+W1,same(T,Y-X1-W2,P,[Y-X-W|L],R,T2).
same(T,P,P,L,L,T).

xy(_,[],L,L).
xy(Y-X1-W1,[H|T],L,R):-
     X is X1+H,W is W1-H,Y1 is Y+H,L1=[Y1-X1-H|L],xy(Y-X-W,T,L1,R).    

tobo([X-Y-W|T],R):-bo(T,[X-Y-W],[],R).
bo([],[X],L,R):-
     reverse([[X]|L],R).
bo([X-Y-W|T],[X1-Y1-W1|T1],L,R):-
     (X=\=X1;Y=\=Y1+W1),!,reverse([X1-Y1-W1|T1],GL),bo(T,[X-Y-W],[GL|L],R).
bo([X-Y-W|T],[X1-Y1-W1|T1],L,R):-
     Y=:=W1+Y1,bo(T,[X-Y-W|[X1-Y1-W1|T1]],L,R).

rev(L,R):-last(L,Y-_-_),rev(Y,L,R).
rev(_,[],[]).
rev(N,[Y-X-W|T],L):-rev(N,T,L1),Y1 is N-Y,L=[Y1-X-W|L1].

chan([],[]).
chan([_-_-W|T],L):-chan(T,L1),L=[W|L1].

solve(N,L,R):-
     reverse(L,L1),toxy(L1,L2,L3),append(L2,L3,L4),rev(L4,L5),   
     exch(L5,L51),keysort(L51,L6),tobo(L6,R1),nth1(N,R1,R2),chan(R2,R).         

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

sp([],[],[],[]).
sp([')'|T],LC,LN,LG):-
     !,sp(T,LC,LN,LG).
sp([','|T],LC1,LN1,LG):-
     !,sp(T,LC,LN,LG),number_chars(N,LC),LN1=[N|LN],LC1=[].
sp(['('|T],LC1,LN1,LG1):-
     !,sp(T,LC,LN,LG),number_chars(N,LC),LG1=[[N|LN]|LG],LC1=[],LN1=[].
sp([X|T],LC1,LN,LG):-
     sp(T,LC,LN,LG),LC1=[X|LC].

pre([]).                                                                          

pre([_,B,Q|T]):-
     atomics_to_string(L,':',B),L=[X,Y],atom_number(X,N),atom_chars(Y,BL),
     sp(BL,_,_,LG),solve(N,LG,R),disp(R,Q),pre(T).
disp(R,A):-
     atomics_to_string(R,',',S1),atomics_to_string(['(',')'],S1,S),
     (A==S->Str=" pass ";Str=" fail "),write(Str),writeln(S).

str("0  4:(55,44,48)(40,4)(52)(26,29)(23,3)(20,31,21)(5,47)(43)(9,17)(1,8)(32)(25)      (32,31)
1       6:(33,29,50)(4,25)(37)(15,35)(16,9)(7,2)(17)(42,18)(6,11)(8,27)(24)(19)         (6,17,2)
2       7:(60,50)(23,27)(24,22,14)(7,16)(8,6)(12,15)(13)(2,28)(26)(4,21,3)(18)(17)      (4,16)
3       6:(99,73,56)(17,39)(68,22)(36,25)(57,42)(9,16)(2,7)(10,28)(23)(15,87,18)(72)(69)        (10,36,22)
4       7:(79,49,66,63)(32,17)(3,60)(29,57)(55,22,2)(20,14)(15,28)(33,9)(24)(11,134)(123)       (29,17)
5       7:(159,129)(57,72)(56,39,25,16,23)(9,7)(2,28)(36)(42,15)(17,22)(87)(10,18)(73)(68)(60)  (10,28)
6       14:(113,71,68)(32,36)(42,29)(13,44,4)(40)(62,37,38,31)(7,108)(25,12)(11,34)(23)(77,10)(67)      (36)
7       8:(145,125)(53,72)(45,11,9,16,31,33)(2,7)(13)(8,15)(21)(14,32)(30,37,19)(80)(18,73)(62)(55)     (31)
8       1:(175,140,164)(35,29,52,24)(28,160)(6,23)(130,86)(43,60)(26,17)(77)(44,68)(174)(5,155)(150)    (174,130,175)
9       6:(240,168,187)(149,19)(206)(163,77)(86,82,58)(40,18)(22,202)(4,78)(192,61)(62)(48,13)(35,118)(83)      (4,82)
10      5:(100,73,59)(14,45)(56,31)(58,42)(25,51)(19,36,26)(16,18,8)(2,17)(10)(77)(74)(28)(23,30)(44,7)(37)     (2,19,56,73)
11      8:(100,88,76)(27,49)(12,19,39,18)(95,11,6)(3,24)(5,1)(21)(20)(16)(2,47)(77,45)(92)(69,26)(17,60)(43)    (19)
12      11:(262,196,203)(83,106,7)(210)(161,84,17)(36,41,23)(18,111)(31,5)(64)(77,38)(102)(73,248)(238)(175)    (248)
13      9:(117,79,74)(5,69)(84)(71,46)(20,49)(25,39,57,29)(82,14)(78)(35,18)(13,12,50)(1,11)(4,10)(33,6)(27)    (1,12)
14      7:(163,95,78)(17,61)(68,44)(24,81)(89,94,72)(15,66)(42,45)(84,5)(79,20)(59,3)(26,22)(16,50)(4,34)(30)   (30,26,3)
15      10:(100,95,69)(26,43)(11,16,77,17)(88,12)(6,5)(1,20)(19)(60)(39)(18,21)(45,92)(76,27,3)(24)(49,2)(47)   (47,2)
16      8:(120,78,102)(34,20,24)(14,6)(2,10,23,91)(8)(53,13)(75,45)(36)(4,32)(30,47,25)(22,3)(19,107)(105)(88)  (4,36,13)
17      13:(119,124,96)(28,68)(114,5)(117,40)(56,52)(4,48)(21,15,24)(106,8)(6,9)(98,38,16)(13,20)(22,7)(75)(60)         (20)
18      2:(302,277,246)(57,189)(25,117,109,26)(235,92)(83)(8,135,49)(90,127)(81,157)(53,37)(5,76)(304)(288)(233)        (53,90,92)
19      13:(158,109,240)(49,60)(114,82,11)(71)(126,267)(62,52)(10,42)(40,32)(8,51,141)(48)(14,37)(39,9)(23)(7,53)(46)   (60)
20      8:(132,113,251)(19,36,58)(107,27,17)(10,21,22)(25,12)(1,20)(13)(80)(32,6)(26)(23,35)(130)(121,245)(127,3)(124)  (26,6)
21      4:(187,127,194)(60,67)(131,76,40)(33,72,156)(44,29)(19,10)(55,21)(82)(13,27,4)(23)(34)(50)(190,30)(160,2)(158)  (60,127)
22      12:(239,245)(132,107)(124,121)(27,25,32,23)(3,118)(35,115)(113,19)(12,13)(17,10)(6,26)(21,1)(20)(36)(22,80)(58)         (124,245)
23      3:(176,152)(24,38,90)(80,63,43,14)(52)(20,23)(17,26,40)(37,42,86)(72,25)(16,10)(6,4)(49,19,8,5)(47)(3,44)(11)(30)       (17,63)
24      15:(171,181)(95,76)(93,88)(19,30,27)(42,40,32)(5,83)(3,15,29,78)(21,12)(9,18)(8,54)(4,25)(2,46)(22)(44)(1,24)(23)       (93,181)
25      13:(152,88,112)(64,24)(44,92)(200,12,4)(8,7,33)(1,6)(16,5)(11)(27)(18,15)(3,31,73)(29,19)(10,9)(40)(39)(77,2)(75)       (3,15)
26      13:(484,316,379)(108,145,63)(82,360)(42,66)(29,198)(18,24)(308,194)(119)(69,50)(168,80)(114,149)(440)(387,35)(352)      (379)
27      12:(181,191)(93,88)(24,23,54,46,44)(1,22)(25)(2,42)(4,18)(8,40)(29)(9,21,32)(15,12)(3,30)(5,103,27)(98)(19,95)(76)      (21)
28      18:(83,79,123)(35,44)(52,31)(21,36,9)(27,60,89)(48,25)(10,20,33)(23,12)(2,5,13)(11,3)(8)(102,49,45)(16,73)(4,57)(53)    (123)
29      4:(649,439,456)(214,208,17)(473)(6,55,147)(385,260,4)(175,49)(104)(12,135)(116)(81,94)(125,216)(203,7)(615)(510)(419)   (81,175,4)
30      17:(100,114,48,53)(43,5)(58)(23,20)(61,25,14)(3,75)(11,47,96)(36)(95,49)(24,51)(37,105,27)(78)(9,28)(59,26,19)(7,40)(33)        (58,5)").
```