/* OSLIK
 * In 1998 by Jan Kratochvil <short@ucw.cz>
 * This software is public domain.
 * Prolog investigator had to be retarded and strongly suffered
 *   from progressive form of brain demency.
 */

dbg_ln(M):-write_ln(M).
%dbg_ln(_).

geths(150).

% Utility:

map(_,[]).
map(F,[H|T]):-call(F,H),map(F,T).

% l2ll/chop provided by the courtesy of Ghort
l2ll([],_,[]).
l2ll(BL,LEN,[LLh|LLt]):-chop(BL,LEN,LLh,BLr),l2ll(BLr,LEN,LLt).

chop(L,0,[],L):-!.
chop([],_,[],[]).
chop([X|BLt],LEN,[X|Lt],Lr):-LEN1 is LEN-1,chop(BLt,LEN1,Lt,Lr).

reversen(I,N,O):-reversen(I,N,[],O).
reversen([],_,D,D).
reversen(I,N,M,O):-chop(I,N,CHUNK,REST),append(CHUNK,M,BIGRED),reversen(REST,N,BIGRED,O).

dbgxy(X,I,_,O):-O is I+1,write_ln(['dbgxy:',X,'=',I,'->',O]).

forallc(Y,Y,_,_,_,D,_,D).
forallc(Y,Y1,Yr,X,F,I,D,O):-forall(Yr,[Y|X],F,I,D,M),Yi is Y+1,forallc(Yi,Y1,Yr,X,F,M,D,O).
forall([],X,F,I,D,O):-call(F,X,I,D,O).
forall([Y0,Y1|Yr],X,F,I,D,O):-Y1i is Y1+1,forallc(Y0,Y1i,Yr,X,F,I,D,O).
forall(Y,F,I,D,O):-reversen(Y,2,Yx),forall(Yx,[],F,I,D,O).

split(I,N,A,B):-split(I,N,[],A,B).
split(I,0,J,Jx,I):-reverse(J,Jx).
split([Ih|It],N,Aa,A,B):-
	Nd is N-1,split(It,Nd,[Ih|Aa],A,B).

replace(I,N,X,O):-
	split(I,N,Ia,[_|Ic]),append(Ia,[X|Ic],O).

prependn(I,N,[X1,X2],O):-
	split(I,N,Ia,[Ib|Ic]),dbg_ln(['Ia=',Ia,',Ib=',Ib,',Ic=',Ic]),append(Ia,[[X1,X2|Ib]|Ic],O).

hashval(ST,SThv):-
	concat('(',ST,STterm),hash_term(STterm,SThvr),
	geths(HS),SThv is SThvr mod HS.

addst(HASH,ST,STo,HASHn):-
	hashval(ST,SThv),prependn(HASH,SThv,[ST,STo],HASHn).
getst(HASH,ST,STo):-
	hashval(ST,SThv),nth0(SThv,HASH,PL),getkey(PL,ST,STo).

getkey([C,V|_],C,V):-dbg_ln(['getkey-final:C=',C,',V=',V]).
getkey([LhC,LhV|Lt],C,V):-dbg_ln(['getkey-iterate:C=',C,',V=',V,',LhC=',LhC,',LhV=',LhV,',Lt=',Lt]),getkey(Lt,C,V).

replist(_,0,[]).
replist(V,N,[V|Lt]):-Nd is N-1,replist(V,Nd,Lt).

hashsize([],0).
hashsize([Hh|Ht],N):-
	dbg_ln(['HASHSIZE:Hh=',Hh,',Ht=',Ht,',N=',N]),
	length(Hh,A),hashsize(Ht,B),N is A+B.

% Oslik:

saLX(I,X):-X is I mod 5.
saLY(I,Y):-Y is floor(I/5).
saLXY(I,X,Y):-saLX(I,X),saLY(I,Y).
saXYL(X,Y,I):-I is Y*5+X.
getXY(STl,X,Y,C):-saXYL(X,Y,L),nth0(L,STl,C).

foryi(I,I,_):-dbg_ln(['foryi-final: I=',I]).
foryi(Vyi,Vys,[Vxi,Vxs,Vdx,Vdy,STl,Vsx,Vsy,Vbx,Vby]):-
	dbg_ln(['foryi entered,Vxi=',Vxi,',Vyi=',Vyi,',Vsy=',Vsy,',Vys=',Vys,',Vxs=',Vxs]),
	((Vxi-Vsx>(-1),Vxi-Vsx<Vxs,Vyi-Vsy>(-1),Vyi-Vsy<Vys)->true
	;Gx is Vbx-Vdx+Vxi,Gy is Vby-Vdy+Vyi,
	getXY(STl,Gx,Gy,C),
	string_to_list('+',[C])),
	dbg_ln(['foryi middle,Vxi=',Vxi,',Vyi=',Vyi,',Vsy=',Vsy,',Vys=',Vys,',Vxs=',Vxs]),
	Vyi1 is Vyi+1,foryi(Vyi1,Vys,[Vxi,Vxs,Vdx,Vdy,STl,Vsx,Vsy,Vbx,Vby])
	,dbg_ln(['foryi leave, success,Vxi=',Vxi,',Vyi=',Vyi,',Vsy=',Vsy,',Vys=',Vys,',Vxs=',Vxs]).

forxi(I,I,_):-dbg_ln(['forxi-final: I=',I]).
forxi(Vxi,Vxs,[Vys|D]):-
	dbg_ln(['forxi enter, Vxi=',Vxi,',Vxs=',Vxs]),
	foryi(0,Vys,[Vxi,Vxs|D]),
	dbg_ln(['forxi middle, Vxi=',Vxi,',Vxs=',Vxs]),
	Vxi1 is Vxi+1,forxi(Vxi1,Vxs,[Vys|D])
	,dbg_ln(['forxi leave, success, Vxi=',Vxi,',Vxs=',Vxs]).

fillass([X,Y],STl,C,STlN):-
	saXYL(X,Y,L),replace(STl,L,C,STlN).

moveass([X,Y],STl,[STlO,Vsx,Vsy],STlN):-
	dbg_ln(['INSIDE moveass:',X,Y,Vsx,Vsy]),
	NX is X-Vsx,NY is Y-Vsy,
	saXYL(NX,NY,NL),saXYL(X,Y,L),
	nth0(L,STlO,C),replace(STl,NL,C,STlN)
	,dbg_ln(['FINISH moveass:C=',C]).

dumpit(_,[],-1).
dumpit(HASH,ST,LEV):-
	dbg_ln(['DUMP_IT!:HASH=',HASH,',ST=',ST]),
	getst(HASH,ST,STo),
	dbg_ln(['DUMP_IT got STo=',STo]),
	dumpit(HASH,STo,LEVd),
	dbg_ln(['DUMP_IT got LEVd=',LEVd]),
	LEV is LEVd+1,
	write('> /-------\\ forwardtrace: level='),write_ln(LEV),
	dumpst(ST)
	,dbg_ln('DUMP_IT finished!').
dumpit(HASH,ST,LEV):-write_ln(['DUMP_IT FAILURE:HASH=',HASH,',ST=',ST,',LEV=',LEV]),halt.

final(STl,HASH):-
	string_to_list('A',[AC]),getXY(STl,3,1,AC),
	string_to_list('B',[BC]),getXY(STl,4,1,BC),
	string_to_list('C',[CC]),getXY(STl,3,2,CC),
	string_to_list('D',[DC]),getXY(STl,4,2,DC),
	string_to_list(ST,STl),string_to_atom(ST,STa)
	,write_ln('*** GOAL'),dumpit(HASH,STa,_)
	.
final(_,_).

addstate(ST,STo,[[HASH,DOo],[HASHn,DOn]]):-
	dbg_ln(['addstate:ST=',ST,',STo=',STo,',HASH=',HASH,',DOo=',DOo,',DOn=',DOn]),
	\+ getst(HASH,ST,_),
	append(DOo,[ST],DOn),
	addst(HASH,ST,STo,HASHn)
%	,write('***addstate new (HASHo='),write(HASH),write(';ST='),write(ST),write_ln('):'),dumpst(ST),write_ln('+++ was from:'),dumpst(STo)
%	,write_ln('***addstate:'),dumpst(ST)
	,dbg_ln(['on addstate end, DOn=',DOn]).
addstate(_,_,[H,H]).

chkpos(Vxs,Vys,Vdx,Vdy,[STl,HIST,Vnbx,Vnby,Vsx,Vsy|D]):-
	dbg_ln(['chkpos entered,Vnbx=',Vnbx,',Vdx=',Vdx,',HIST=',HIST]),
	Vnxb is Vnbx-Vdx,Vnyb is Vnby-Vdy,
	Vnxb>(-1),Vnxb+Vxs<6,Vnyb>(-1),Vnyb+Vys<6,
	forxi(0,Vxs,[Vys,Vdx,Vdy,STl,Vsx,Vsy|D]),
	Vgx is Vnbx-Vdx,Vgy is Vnby-Vdy,
	Vgxe is Vgx+Vxs-1,Vgye is Vgy+Vys-1,
	dbg_ln(['HERE IT IS:',Vxs,Vys,Vdx,Vdy,STl,HIST,Vnbx,Vnby,D,'Vgx,Vgy=',Vgx,Vgy,',Vgxe,Vgye=',Vgxe,Vgye]),
	string_to_list('+',[PLUSC]),
	forall([Vgx,Vgxe,Vgy,Vgye],'fillass',STl,PLUSC,STl1),
	dbg_ln('AFTER fillass'),
	forall([Vgx,Vgxe,Vgy,Vgye],'moveass',STl1,[STl,Vsx,Vsy],STl2),
	dbg_ln('AFTER moveass'),
%	dumpsl(STl2),
%	dbg_ln('AFTER moveass AFTER dumpsl'),
	string_to_list(ST2,STl2),string_to_atom(ST2,ST2a),
	dbg_ln('AFTER 1st string_to_list'),
	string_to_list(ST,STl),string_to_atom(ST,STa),
	dbg_ln(['BEFORE addstate:HIST=',HIST]),
	addstate(ST2a,STa,HIST)
	,dbg_ln(['On end of chkpos,HIST=',HIST]).
chkpos(_,_,_,_,[_,[H,H]|_]).

trymove(C,D):-string_to_list('{',[C]),chkpos(2,1, 0, 0,D).
trymove(C,D):-string_to_list('}',[C]),chkpos(2,1,+1, 0,D).
trymove(C,D):-string_to_list('^',[C]),chkpos(1,2, 0, 0,D).
trymove(C,D):-string_to_list('v',[C]),chkpos(1,2, 0,+1,D).
trymove(C,D):-string_to_list('#',[C]),chkpos(1,1, 0, 0,D).
trymove(C,D):-string_to_list('A',[C]),chkpos(2,2, 0, 0,D).
trymove(C,D):-string_to_list('B',[C]),chkpos(2,2,+1, 0,D).
trymove(C,D):-string_to_list('C',[C]),chkpos(2,2, 0,+1,D).
trymove(C,D):-string_to_list('D',[C]),chkpos(2,2,+1,+1,D).
trymove(_,[_,[H,H]|_]).

foroibody(Vsx,Vsy,PLUS2,STl,HIST):-
	dbg_ln(['foroibody:HIST=',HIST]),
	saLXY(PLUS2,Vbx,Vby),Vnbx is Vbx+Vsx,Vnby is Vby+Vsy,
	Vnbx>(-1),Vnbx<5,Vnby>(-1),Vnby<4,
	dbg_ln(['Vnbx=',Vnbx,',Vnby=',Vnby]),
	getXY(STl,Vnbx,Vnby,C),
	dbg_ln(['trymove{',C,[STl,HIST,Vnbx,Vnby,Vbx,Vby],'}']),
	trymove(C,[STl,HIST,Vnbx,Vnby,Vsx,Vsy,Vbx,Vby]).
foroibody(_,_,_,_,[H,H]).

foroi([],_,_,[H,H]).
foroi([[Vsx,Vsy]|Voffs],PLUS2,STl,[HISTo,HISTn]):-
	foroibody(Vsx,Vsy,PLUS2,STl,[HISTo,HISTm]),
	foroi(Voffs,PLUS2,STl,[HISTm,HISTn]).

oneplus(STl,[HISTo,HISTn],PLUSi,CNT):-
	dbg_ln(['CNT=',CNT,',HISTo=',HISTo,',HISTn=',HISTn]),
	PLUSi1 is PLUSi+1,chop(STl,PLUSi1,_,STlr),string_to_list('+',[PLUSC]),nth0(PLUS2x,STlr,PLUSC),PLUS2 is PLUSi1+PLUS2x,
	foroi([[0,-1],[+1,0],[0,+1],[-1,0]],PLUS2,STl,[HISTo,HISTm]),
	CNT1 is CNT+1,oneplus(STl,[HISTm,HISTn],PLUS2,CNT1).
oneplus(_,[H,H],_,2).
oneplus(STl,[H,H],_,CNT):-write_ln(['ONEPLUS FAILURE:CNT=',CNT]),dumpsl(STl),halt.

process(ST,[[HASHo,DOo],HISTn]):-string_to_list(ST,STl),final(STl,HASHo),oneplus(STl,[[HASHo,DOo],HISTn],-1,0).
%runi(T,_):-T>1000.
runi(T,_):-0 is T mod 2000,garbage_collect,fail.
runi(_,D):-run(D).
run([_,[]]).
run([HASH,[DOh|DOt]]):-
	process(DOh,[[HASH,DOt],[HASHn,DOn]]),
	hashsize(HASHn,TOTAL2),TOTAL is floor(TOTAL2/2),length(DOn,TODO),GONE is TOTAL-TODO,
%	(0 is GONE mod 100->format('~t~d~5|+~t~d~11|=~t~d~17|~n',[GONE,TODO,TOTAL]);true),
	!,
	runi(GONE,[HASHn,DOn]).

st2ll(ST,LL):-string_to_list(ST,BL),l2ll(BL,5,LL).
	
dumpc(C):-string_to_list(S,[C]),write(S).
dumpl(L):-write('  | '),map('dumpc',L),write_ln(' |').
dumpst(ST):-
	st2ll(ST,LL),dumpll(LL).
dumpll(LL):-map('dumpl',LL),write_ln('  \\-------/').
dumpsl(BL):-l2ll(BL,5,LL),dumpll(LL).

runinit(ST):-string_to_atom(ST,STa),geths(HS),replist([],HS,HASHi),addst(HASHi,STa,[],HASH),run([HASH,[STa]]).
%HIST <=> [[[StrState,ParentStrState]...],[Todo..]]
go:-runinit('{}{}#AB^#+CDv#+{}{}#').