オフラインどう書く第25回問題と、同じ出題者のCodeIQの問題の解答です。
オフラインどう書く第25回問題
問題はこちら->http://nabetani.sakura.ne.jp/hena/ord25rotcell/
5x5の配列(bo)に文字を入れ、
指定の二升(一升の場合も)の外側の四辺の座標とその文字を、
辺を一周するように順に座標の配列と文字の配列(リスト)に入れていき、(chan/4)
文字の配列の最後の文字を先頭に移動した後
座標の配列と照らし合わせて元のマス目に戻します。(chan/4)
これで辺や角にかかるものも指定文字が一つのものも処理できます。
盤の元のマス目に戻す部分が、変数を再代入できない言語では面倒なのでJuliaでかきました。
#Julia ver 1.53,1.41
str="0 ab,gg,uj,pt,an,ir,rr hpqsvwxy
1 gs,ok abcdftvwxy
2 gs,sg,ok none
3 aa,bb,hh,nn hiostwxy
4 ae,ko,uy,cw bdgilnqsvx
5 am,gs,am,gs,am,gs,am,gs cfhkmqrvwx
6 ay none
7 gs,ay defjkoptuv
8 bx,ay none
9 ft,ay defjkoptuv
10 ab,cd,ef,gh,ij,kl,mn,op,qr,st,uv,wx cdjmnry
11 wx,uv,st,qr,op,mn,kl,ij,gh,ef,cd,ab kmoxy
12 am,cj,ac,em,ss,cy,aa,ee,ff,vp none
13 uf,oq,gn,ss,ca,hv,ej none
14 cc,wk,uu,ws,bk,aa,vv bei
15 tr,ou,ll,pp,jh,vf,yy,nr,rr,oo rxy
16 ky,ov,ri,qm,nn,ee,ws,em,ca,ak biju
17 ty nosx
18 ll,uh,hq,ss,nx,ry,ku,ab,jj efouv
19 yl,mu,qj,ss,ep mnqru
20 kj,ee,qk fglruv
21 xi,wd,hf ciknqr
22 fx,ak,cc,ce bdhijnp
23 li,jf,pp,qm,hg,sf akntuwx
24 jw bcdeglqv
25 uk,oe,xr dglmoqsy
26 bb,ov,pd,dd,xk,is,hh,xd,xx,kq,pp,ku cfhjopqvy
27 iq,fn,il,ww,ox,la,or,ga,wg,ef,us cfgjopvxy
28 km,po abcdenqrst
29 tc,mh,cw abefjkoptu
30 fm,jx,xx,pi,gs,au,uq,ut,ap,vb cdghjmortux
31 ik,xl,si abcdflorvwx
32 nu,cc,lv,bu,tt,ww,xk,ia,in,sa,my abcefgpqrstu
33 tt,ak,xh,tk,oo,yr,na,yv,gm,vh degiklmnquwx
34 kk,ob,kk,fm,xk acdegjlopqruy
35 uq,ko,pf,yy,ig,tu,ve,ve,qy,mh,oo,dv befjkoqrtuwxy
36 aj,hb,ar,ii,np,ki,hg,vd cefhjlmopqtwxy
37 vv,sf,ww,my,mm,sq,fb,ly,fu,ls bfghkmnptuvwxy
38 jj,bp,gs abdefijkprtuvwxy
39 sv,sn,mn,gn,gi abcdefhjnpqtuvxy"
function solve(inp)
function chan(x1,x2,y1,y2)
for x in x1-1:x2+1
if x>0 && x<6 && y1>1 && y1<6
push!(xy,[x,y1-1])
push!(al,bo[x,y1-1])
end
end
for y in y1:y2
if y>0 && y<6 && x2>0 && x2<5
push!(xy,[x2+1,y])
push!(al,bo[x2+1,y])
end
end
for x in x2+1:-1:x1-1
if x>0 && x<6 && y2>0 && y2<5
push!(xy,[x,y2+1])
push!(al,bo[x,y2+1])
end
end
for y in y2:-1:y1
if y>0 && y<6 && x1>1 && x2<6
push!(xy,[x1-1,y])
push!(al,bo[x1-1,y])
end
end
if al!=[]
pushfirst!(al,pop!(al))
for i in xy
bo[i[1],i[2]]=popfirst!(al)
end
end
end
bo=Array{Char,2}(undef,5,5)
boo=similar(bo)
xy,al,xb,yb,ans=[],[],[],[],[]
for s in 'a':'y'
bo[mod(Int(s)-97,5)+1,div(Int(s)-97,5)+1]=s
end
for s in inp
boo=copy(bo)
for a in s
for x in 1:5
for y in 1:5
if a==bo[x,y]
push!(xb,x)
push!(yb,y)
end
end
end
end
sort!(xb)
sort!(yb)
chan(xb[1],xb[2],yb[1],yb[2])
xy,al,xb,yb=[],[],[],[]
end
for y in 1:5
for x in 1:5
if bo[x,y]!=boo[x,y]
push!(ans,bo[x,y])
end
end
end
if ans==[]
ans=["none"]
end
sort!(ans)
end
function main()
str1=split(str,"\n")
for s in str1
s1=split(s," ")
s2=split(s1[2],",")
ans=join(solve(s2))
if ans==strip(s1[3])
sel="pass"
else
sel="fail"
end
print(sel," ",ans,"\n")
end
end
main()
初期状態の升の座標と文字をくっつけてリストに放り込めば、
盤を作る必要がありませんので、Prologでも書きました。
make1/2でXY座標と文字を対応付けてリストを作っています。
calc/4で二升(一升の場合も)の外周のX座標とY座標を求めています。
rot/10で動く部分の文字と座標を別のリストに入れていき、L21=[H|T],append(T,[H],L22)
で文字列のリストの先頭を最後に持っていきます。
動いた文字列のリスト、その部分の座標のリスト、動かない部分のリストができます。
solve1に戻って、con/2で動いた部分の座標と文字列を対応させ、
appendで残りの部分と合わせます。
%SWI-Prolog v7.4.2,7.6.4
%start.
%:-initialization(start). %ideone
con(X:Y,Z,X:Y:Z).
rot(L,XS,YS,XB,YB,X,Y,L1,L2,R):-
(select(X:Y:C,L,L0)->(L11=[X:Y|L1],L21=[C|L2]);(L0=L,L11=L1,L21=L2)),
((X=:=XS,Y=:=YS+1)->((L21==[]->L22=L21;(L21=[H|T],append(T,[H],L22))),R=[L0,L11,L22]);
((X=:=XS,Y>YS+1)->(Y3 is Y-1,X3=X);
((X=:=XB,Y<YB)->(Y3 is Y+1,X3=X);
((Y=:=YS,X<XB)->(X3 is X+1,Y3=Y);
((Y=:=YB,X>XS)->(X3 is X-1,Y3=Y))))),
rot(L0,XS,YS,XB,YB,X3,Y3,L11,L21,R)).
makel(0,[]).
makel(N,R):-
N1 is N-1,makel(N1,R1),divmod(N1,5,D,M),N2 is N+96,atom_codes(S,[N2]),
Y is D+1,X is M+1,R=[X:Y:S|R1].
calc(X1,X2,XS,XB):-X1=<X2->(XS is X1-1,XB is X2+1);(XS is X2-1,XB is X1+1).
solve1(L,[[C1,C2]|T],R):-
member(X1:Y1:C1,L),member(X2:Y2:C2,L),calc(X1,X2,XS,XB),calc(Y1,Y2,YS,YB),
rot(L,XS,YS,XB,YB,XS,YS,[],[],[L0,L1,L2]),
(T==[]->R=L2;(maplist(con,L1,L2,R1),append(R1,L0,L3),solve1(L3,T,R))).
solve(L,R):-makel(25,L0),maplist(atom_chars,L,L1),solve1(L0,L1,R1),sort(R1,R),!.
start:-
str(S),split_string(S,"\n","",S1),pre(S1),!.
pre([]).
pre([S|T]):-
split_string(S,"\s","\s",[_,B,Q]),atomics_to_string(L,",",B),
solve(L,R),disp(R,Q),pre(T).
disp(R,Q):-
(R=[]->S="none";atom_string(R,S)),
(S==Q->Str=" pass ";Str=" fail "),write(Str),writeln(S).
str("0 ab,gg,uj,pt,an,ir,rr hpqsvwxy
1 gs,ok abcdftvwxy
2 gs,sg,ok none
3 aa,bb,hh,nn hiostwxy
4 ae,ko,uy,cw bdgilnqsvx
5 am,gs,am,gs,am,gs,am,gs cfhkmqrvwx
6 ay none
7 gs,ay defjkoptuv
8 bx,ay none
9 ft,ay defjkoptuv
10 ab,cd,ef,gh,ij,kl,mn,op,qr,st,uv,wx cdjmnry
11 wx,uv,st,qr,op,mn,kl,ij,gh,ef,cd,ab kmoxy
12 am,cj,ac,em,ss,cy,aa,ee,ff,vp none
13 uf,oq,gn,ss,ca,hv,ej none
14 cc,wk,uu,ws,bk,aa,vv bei
15 tr,ou,ll,pp,jh,vf,yy,nr,rr,oo rxy
16 ky,ov,ri,qm,nn,ee,ws,em,ca,ak biju
17 ty nosx
18 ll,uh,hq,ss,nx,ry,ku,ab,jj efouv
19 yl,mu,qj,ss,ep mnqru
20 kj,ee,qk fglruv
21 xi,wd,hf ciknqr
22 fx,ak,cc,ce bdhijnp
23 li,jf,pp,qm,hg,sf akntuwx
24 jw bcdeglqv
25 uk,oe,xr dglmoqsy
26 bb,ov,pd,dd,xk,is,hh,xd,xx,kq,pp,ku cfhjopqvy
27 iq,fn,il,ww,ox,la,or,ga,wg,ef,us cfgjopvxy
28 km,po abcdenqrst
29 tc,mh,cw abefjkoptu
30 fm,jx,xx,pi,gs,au,uq,ut,ap,vb cdghjmortux
31 ik,xl,si abcdflorvwx
32 nu,cc,lv,bu,tt,ww,xk,ia,in,sa,my abcefgpqrstu
33 tt,ak,xh,tk,oo,yr,na,yv,gm,vh degiklmnquwx
34 kk,ob,kk,fm,xk acdegjlopqruy
35 uq,ko,pf,yy,ig,tu,ve,ve,qy,mh,oo,dv befjkoqrtuwxy
36 aj,hb,ar,ii,np,ki,hg,vd cefhjlmopqtwxy
37 vv,sf,ww,my,mm,sq,fb,ly,fu,ls bfghkmnptuvwxy
38 jj,bp,gs abdefijkprtuvwxy
39 sv,sn,mn,gn,gi abcdefhjnpqtuvxy").
CodeIQ71マス目を回す
問題とテストケースはこちらのお世話になりました。
https://blog.goo.ne.jp/r-de-r/e/6dfc168a3355d255e4fe353b1c631e1c
方法は前題と同じですが一マスの周りになりましたので、簡単になりました。
穴が開いている座標は枠外と同じ扱いになります。
#Julia ver 1.53,1.41
function solve(bo,inp)
cl=[(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1)]
function chan(x1,y1)
xy,al=[],[]
for (x,y) in cl
if 0<x1+x && x1+x<5 && 0<y1+y && y1+y<5 && bo[x+x1][y+y1]!='-'
push!(xy,[x1+x,y+y1])
push!(al,bo[x1+x][y+y1])
end
end
if al!=[]
pushfirst!(al,pop!(al))
for i in xy
tmp=split(bo[i[1]],"")
tmp[i[2]]=string(popfirst!(al))
bo[i[1]]=join(tmp,"")
end
end
end
for s in inp
for x in 1:4, y in 1:4
if s==bo[x][y]
chan(x,y)
break
end
end
end
bo
end
function f(str)
s1=split(str,r"\s+")
s2=split(s1[1],"/")
ans=join(solve(map(x->strip(x),s2),s1[2]),"/")
if ans==strip(s1[3])
sel="pass"
else
sel="fail"
end
print(sel," ",ans,"\n")
end
f("abc-/d-ef/g-hi/opqr codeiq pac-/o-dh/e-qf/grbi")
f("---y/-x--/----/---z xyz ---y/-x--/----/---z")
f("al-d/yteq/ukwg/-pmc yptawa ka-d/luye/cmpq/-wtg")
f("y---/-o-e/v--b/---a eaeyyvva y---/-o-e/v--b/---a")
f("s-jq/----/p---/-cy- yccpyycs s-jq/----/y---/-cp-")
f("epns/cvbz/igrd/mqyo ydcmzvs iebn/cpqy/mogs/rvdz")
f("kiy-/-ogn/ebua/vq-l euvoei bqo-/-vik/engy/lu-a")
f("-ply/-wb-/zg-s/m-e- zpgeyelz -blp/-wm-/gz-s/e-y-")
f("e-sr/l---/----/---k lslek e-sr/l---/----/---k")
f("---q/-wr-/---a/---- qrqwawqrww ---a/-qr-/---w/----")
f("fhkr/-qip/zldy/cgvu pcgvrpkciu gfdi/-cvh/lzyk/ruqp")
f("klfs/r-cw/mdnb/tp-- ppsffmpw kbfm/r-tw/dncl/sp--")
f("tm--/ukfh/oldy/jcxa dyxjcuo ht--/jolm/cfuk/xayd")
Prologでも書きました。
升目の文字がアルファベット順ではなく入力にスラッシュやハイフンも入っていますので、
入力をリストに変換したり(solveの大部分)答えを文字列にもどす(back/4)のが面倒です。
しかし座標:文字のリストに穴の開いた升は入れませんので、
升目を回している間(solve1/3)は穴の部分を意識する必要はありません。
rot/7で中心となる文字から計算された周囲の座標がリスト中にあるかどうか調べるのに
組み込みのselect/3を使っていて効率が悪いですが、この程度のデータ量なら問題ありません。
2022年4月4日更新
バグがありました。
操作をしても状態が変わらない場合を見逃していました。
CodeIQの問題は、だいたいsolveの最後をfailにして回していますので、誤答は検出できますが、
エラーが検出できないのをうっかりしていました。
rot/7の先頭に一行追加します。
%SWI-Prolog v7.4.2,7.6.4
%solve.
%:-initialization(solve).
dir([(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1)]).
con(X:Y,Z,X:Y:Z).
rot(L,_,_,[],[],L2,R):-R=[L,[],L2]. %2022.4.4追加
rot(L,_,_,[],[H|T],L2,R):-append(T,[H],L1),R=[L,L1,L2].
rot(L,X,Y,[(Y1,X1)|T],L1,L2,R):-
X2 is X+X1,Y2 is Y+Y1,(select(Y2:X2:C,L,L0)->(L21=[C|L2],L11=[Y2:X2|L1]);
(L0=L,L11=L1,L21=L2)),rot(L0,X,Y,T,L11,L21,R).
makel(_,[],[]).
makel(N,[H|T],R):-
N1 is N+1,makel(N1,T,R1),(H=='-'->R=R1;(divmod(N1,4,D,M),
Y is D+1,X is M+1,R=[Y:X:H|R1])).
back(5,_,_,[]).
back(Y,5,L,R):-
Y1 is Y+1,back(Y1,1,L,R).
back(Y,X,L,R):-
X1 is X+1,back(Y,X1,L,R1),
(member(Y:X:C,L)->R2=[C|R1];R2=['-'|R1]),(X=:=1->R=['/'|R2];R=R2),!.
solve1(L,[C1|T],R):-
member(Y1:X1:C1,L),dir(D),
rot(L,X1,Y1,D,[],[],[L0,L1,L2]),
maplist(con,L1,L2,R1),append(R1,L0,L3),(T==[]->R=L3;solve1(L3,T,R)),!.
solve:-
f(S0),split_string(S0,"\s","\s",[S,M,A]),atomics_to_string(L,"/",S),
maplist(atom_chars,L,L1),flatten(L1,L2),atom_chars(M,ML),makel(-1,L2,L0),
solve1(L0,ML,R1),back(1,1,R1,[_|R2]),atom_string(R2,R),disp(R,A),fail.
solve.
disp(R,A):-(R==A->Str=" pass";Str=" fail"),write(Str),write(" "),writeln(R),!.
f("abc-/d-ef/g-hi/opqr codeiq pac-/o-dh/e-qf/grbi").
f("---y/-x--/----/---z xyz ---y/-x--/----/---z").
f("al-d/yteq/ukwg/-pmc yptawa ka-d/luye/cmpq/-wtg").
f("y---/-o-e/v--b/---a eaeyyvva y---/-o-e/v--b/---a").
f("s-jq/----/p---/-cy- yccpyycs s-jq/----/y---/-cp-").
f("epns/cvbz/igrd/mqyo ydcmzvs iebn/cpqy/mogs/rvdz").
f("kiy-/-ogn/ebua/vq-l euvoei bqo-/-vik/engy/lu-a").
f("-ply/-wb-/zg-s/m-e- zpgeyelz -blp/-wm-/gz-s/e-y-").
f("e-sr/l---/----/---k lslek e-sr/l---/----/---k").
f("---q/-wr-/---a/---- qrqwawqrww ---a/-qr-/---w/----").
f("fhkr/-qip/zldy/cgvu pcgvrpkciu gfdi/-cvh/lzyk/ruqp").
f("klfs/r-cw/mdnb/tp-- ppsffmpw kbfm/r-tw/dncl/sp--").
f("tm--/ukfh/oldy/jcxa dyxjcuo ht--/jolm/cfuk/xayd").