/* 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(_).

% 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).

% 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(ST,LEV):-
	dbg_ln(['DUMP_IT!:ST=',ST]),
	hash(ST,STo),
	dbg_ln(['DUMP_IT got STo=',STo]),
	dumpit(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(ST,LEV):-write_ln(['DUMP_IT FAILURE:ST=',ST,',LEV=',LEV]),halt.

final(STl):-
	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(STa,_)
	,flag('GOALS',GOALS,GOALS+1),(0 is GOALS mod 20->garbage_collect).
final(_).

addstate(ST,STo):-
	dbg_ln(['addstate:ST=',ST,',STo=',STo]),
	\+ hash(ST,_),
	assert(todo(ST)),flag('TODO',TODO,TODO+1),assert(hash(ST,STo)),flag('TOTAL',TOTAL,TOTAL+1)
%	,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').
addstate(_,_).

chkpos(Vxs,Vys,Vdx,Vdy,[STl,Vnbx,Vnby,Vsx,Vsy|D]):-
	dbg_ln(['chkpos entered,Vnbx=',Vnbx,',Vdx=',Vdx]),
	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,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'),
	addstate(ST2a,STa)
	,dbg_ln('On end of chkpos').
chkpos(_,_,_,_,_).

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(_,_).

foroibody(Vsx,Vsy,PLUS2,STl):-
	dbg_ln('foroibody'),
	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,Vnbx,Vnby,Vbx,Vby],'}']),
	trymove(C,[STl,Vnbx,Vnby,Vsx,Vsy,Vbx,Vby]).
foroibody(_,_,_,_).

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

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

process(ST):-dbg_ln(['process:ST=',ST]),string_to_list(ST,STl),final(STl),oneplus(STl,-1,0).
%runi(T):-T>1000.
runi(T):-0 is T mod 2000,garbage_collect,fail.
runi(_):-run.
run:-
	flag('TODO',TODO,TODO),flag('TOTAL',TOTAL,TOTAL),GONE is TOTAL-TODO,
%	(GONE>0,0 is GONE mod 100->format('~t~d~5|+~t~d~11|=~t~d~17|~n',[GONE,TODO,TOTAL]);true),
	TODO>0,todo(ST),retract(todo(ST)),flag('TODO',TODO,TODO-1),process(ST),!,runi(GONE).
run.

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):-assert(hash(ST,[])),flag('TOTAL',_,1),flag('TODO',_,1),assert(todo(ST)),run.
go:-flag('GOALS',_,0),runinit('{}{}#AB^#+CDv#+{}{}#').