:- data result/5. 
:- data numswitch/1. 

tyre(State, M, Dir) :- member(t(State, 0, _, Dir, State), M),!. 

tyre(State, M, Dir) :- 
	member(t(State, 0, _, Dir, NS), M), State \== NS, 
	member(t(NS, 0, _, Dir, State), M), !. 

tyre(State, M, Dir) :- 
	member(t(State, 0, _, Dir, NS), M), State \== NS, 
	member(t(NS, 0, _, Dir, NS2), M), State \== NS2, NS \== NS2, 
	member(t(NS2, 0, _, Dir, State), M), !. 
tyre(State, M, Dir) :- 
	member(t(State, 0, _, Dir, NS), M), State \== NS, 
	member(t(NS, 0, _, Dir, NS2), M), State \== NS2, NS \== NS2, 
	member(t(NS2, 0, _, Dir, NS3), M), State \== NS3, NS \== NS3, NS2 \== NS3, 
	member(t(NS3, 0, _, Dir, State), M), !. 

tyre(State, M, Dir) :- 
	member(t(State, 0, _, Dir, NS), M), State \== NS, 
	member(t(NS, 0, _, Dir, NS2), M), State \== NS2, NS \== NS2, 
	member(t(NS2, 0, _, Dir, NS3), M), State \== NS3, NS \== NS3, NS2 \== NS3, 
	member(t(NS3, 0, _, Dir, NS4), M), State \== NS4, NS \== NS4, NS2 \== NS4, NS3 \== NS4, 
	member(t(NS4, 0, _, Dir, State), M), !. 

escapecheck(Left, State, [0|_], naive, M) :- 
	noneleft(Left, naive), tyre(State, M, l), !. % Left escapee

escapecheck(_, State, [0], naive, M) :- 
	tyre(State, M, r), !.

escapecheck(Left, State, [tape(0,_)|_], comp, M) :- 
	noneleft(Left, comp), tyre(State, M, l), !.

escapecheck(_, State, [tape(0,_)], comp, M) :- 
	tyre(State, M, r), !. 

escapecheck(Left, State, Right, comp(K), M) :-
	escapecheck(Left, State, Right, adapt, M). 

escapecheck(Left, State, [tape(I,_)|_], adapt, M) :- 
	allblank(I), noneleft(Left, adapt), tyre(State, M, l), !.

escapecheck(_, State, [tape(I,_)], adapt, M) :- 
	allblank(I), tyre(State, M, r), !. 

noneleft([], naive).
noneleft([0], naive).
noneleft([], comp).
noneleft([tape(0,_)], comp).
noneleft([], adapt).
noneleft([tape(I,_)], adapt) :- allblank(I). 

getnum(N, N) :- int(N).
getnum(mill(N), Num) :- Num is N*1000000. % Num is N million.
getnum(bill(N), Num) :- Num is N*1000000000. % Num is N billion.
getnum(tens(N), Num) :- Num is 10**N. % Num is 10^N. 

watchlist(Inputs, Watch) :-
	member(watch(Watch), Inputs), !.
watchlist(Inputs, []) :-
	\+ member(watch(_Watch), Inputs).

checkhops(Watch, Trigger, Jump, Hops, _Ones, _Pos, _Type, _Left, State, Right, Trigger, Jump) :- 
	input(Right, In), \+ fire(Hops, Trigger, In, State, Watch), !. 

checkhops(Watch, Trigger, Jump, Hops, Ones, Pos, Type, Left, State, Right, NewTrigger, NewJump) :- 
	input(Right, In), fire(Hops, Trigger, In, State, Watch), !, 
	prettyprint(State, Left, Pos, Type, Right, Hops, Ones), 
	setnew(Trigger, Jump, NewTrigger, NewJump).

setnew(T, J, NT, J) :- NT is T + J. 

fire(Hops, Trigger, _In, _State, _Watch) :-
	Hops >= Trigger, !.

fire(Hops, Trigger, In, State, Watch) :-
	Hops < Trigger, 
	member(watch(State, In), Watch), !. 

fire(Hops, Trigger, _, State, Watch) :-
	Hops < Trigger, 
	member(watch(State), Watch), !. 

prettyprint(State, Left, Pos, Type, Right, Hops, Ones) :-
	length(Left,L), setblanks(Pos, Type, L, Blanks), 
	reverse(Left, PL), 
	leftprint(Blanks, PL, State, Right), 
	format("     Hops: ~d Ones: ~d Pos: ~d~n", [Hops,Ones,Pos]), 
	true.

outputstate(Pos, naive, State) :-
	padding(Pad), P1 is Pad + Pos - 1,
	nblanks(P1), format("{~k}~n", [State]).
outputstate(_Pos, comp, State) :- format("{~k}~n", [State]).
outputstate(_Pos, comp(_), State) :- format("{~k}~n", [State]).
	
setblanks(Pos, naive, L, Blanks) :-
	padding(Pad), 
	Blanks is Pad + Pos - L.
setblanks(_Pos, Type, _L, 0) :-
	member(Type, [comp,comp(_),adapt]).
	
input([tape(In,_)|_], In) :- !. 
input([In|_], In) :- is_input(In), !. 

is_input(0).
is_input(1).
is_input(2).
is_input(3).
is_input(4).
is_input(5).
is_tape([]).
is_tape([I|Rest]) :- is_input(I), is_tape(Rest). 

leftprint(Blanks, _PL, _State, Right) :-
	Blanks < 0, format("{too long on the left} ", []), pprint(Right).
leftprint(Blanks, PL, State, Right) :- 
	Blanks >= 0, nblanks(Blanks), pprint(PL), format("{~k}",[State]), pprint(Right).

padding(50). 
nblanks(N) :- N < 0, !, format("No space! ", []).
nblanks(0) :- !.
nblanks(N) :- N > 0, !, format(" ", []), N1 is N - 1, nblanks(N1). 

pprint([]). 
pprint([0|Rest]) :- !, format("0", []), pprint(Rest).
pprint([1|Rest]) :- !, format("1", []), pprint(Rest).
pprint([2|Rest]) :- !, format("2", []), pprint(Rest).
pprint([3|Rest]) :- !, format("3", []), pprint(Rest).
pprint([4|Rest]) :- !, format("4", []), pprint(Rest).
pprint([5|Rest]) :- !, format("5", []), pprint(Rest).
pprint([tape(1,C)|Rest]) :-
	int(C), C > 1, !, 
	format("~d^(~d) ", [1,C]), pprint(Rest).
pprint([tape(1,1)|Rest]) :-
	!, format("~d ", [1]), pprint(Rest).
pprint([tape(0,C)|Rest]) :-
	int(C), C > 1, 	!, 
	format("~k^(~d) ", [0,C]), pprint(Rest).
pprint([tape(0,1)|Rest]) :-
	!, format("~k ", [0]), pprint(Rest).
pprint([tape(T,C)|Rest]) :-
	% var(C), 
	C = v(V,_,_,_,_), 
	T = [_|_], !,
	format("{",[]), 
	pchars(T), 
	% format("}^(~k)",[C]), 
	format("}^(~k)",[V]), 
	pprint(Rest). 
pprint([tape(T,C)|Rest]) :-
	T = [_|_], % T is a list
	int(C), 
	C > 1, !, 
	format("{",[]), 
	pchars(T), 
	format("}^(~d)",[C]), 
	pprint(Rest). 
pprint([tape(T,C)|Rest]) :-
	T = [_|_], % T is a list
	int(C), 
	C = 1, !, 
	pchars(T), 
	pprint(Rest). 
pprint([tape(T,C)|Rest]) :-
	T = [_|_], % T is a list
	int(C), 
	C = 0, !, 
	pprint(Rest). 

pchars([]). 
pchars([0|Rest]) :- !, format("0",[]), pchars(Rest). 
pchars([1|Rest]) :- !, format("1",[]), pchars(Rest). 
pchars([2|Rest]) :- !, format("2",[]), pchars(Rest). 
pchars([3|Rest]) :- !, format("3",[]), pchars(Rest). 
pchars([4|Rest]) :- !, format("4",[]), pchars(Rest). 
pchars([5|Rest]) :- !, format("5",[]), pchars(Rest). 

countones(Left, Right, Ones) :-
	addones(Left, 0, O1), addones(Right, 0, O2),
	Ones is O1 + O2.

addones([], C, C) :- !.
addones([0|Rest], C, Ones) :-
	!, addones(Rest, C, Ones). 
addones([X|Rest], C, Ones) :-
	is_input(X), X \== 0, !, C1 is C + 1,
	addones(Rest, C1, Ones).
addones([tape(X,_)|Rest], C, Ones) :-
	allblank(X), 
	!, addones(Rest, C, Ones).
addones([tape(X,N)|Rest], C, Ones) :-
	is_tape(X), \+ allblank(X), !, addones(X,0,Xs), C1 is C + N*Xs, addones(Rest, C1, Ones).

updateLRNCB(Left, [_|Right], Output, l, NL, New) :-
	!, checkstate(Left, [InL|NL]), 
	Temp = [Output|Right], New = [InL|Temp],
	true.
updateLRNCB(Left, [_|Right], Output, r, [Output|Left], NR) :-
	!, checkstate(Right, NR),
	true.

updateLR(Left, [_|Right], Output, l, L, R) :-
	!, checkstate(Left, [InL|NL]), 
	Temp = [Output|Right], New = [InL|Temp],
 	collapseblanks(NL, L), collapseblanks(New, R), 
	true.
updateLR(Left, [_|Right], Output, r, L, R) :-
	!, checkstate(Right, NR),
 	collapseblanks([Output|Left], L), collapseblanks(NR, R), 
	true.

invert(tape(I,N), tape(RevI,N)) :- reverse(I,RevI).
invert(I,I) :- I \= tape(_,_). 

updateLRback(Left, [Current|Right], In, Output, l, NewLeft, NewRight) :-
	Right = [Output|Rest], !, 
	collapseblanks([Current|Left],NewLeft),
	collapseblanks([In|Rest],NewRight).

updateLRback(Left, [Current|Right], In, _Output, l, NewLeft, NewRight) :-
	Right = [],!, 
	collapseblanks([Current|Left],NewLeft),
	collapseblanks([In],NewRight).

updateLRback(Left, Right, In, Output, r, NewLeft, NewRight) :-
	Left = [Output|Rest], !, 
	collapseblanks(Rest, NewLeft),
	collapseblanks([In|Right], NewRight).

updateLRback(Left, Right, In, _Output, r, [], NewRight) :-
	Left = [], !, 
	collapseblanks([In|Right], NewRight).

updateLRfront(Left, [Current|NR], In, Output, l, RestL, [InL|Right]) :-
	In = Current, checkstate(Left, [InL|RestL]), Right = [Output|NR]. 

updateLRfront(Left, [Current|NR], In, Output, r, [Output|Left], Right) :-
	In = Current, checkstate(NR, Right).

collapseblanks([], []) :- !.
collapseblanks([X|Rest], [X|CRest]) :- is_input(X), !, collapseblanks(Rest, CRest). 
collapseblanks([tape(I,X)|Rest], [tape(I,X)|CRest]) :- is_input(In), member(In,I), !, collapseblanks(Rest, CRest). 
collapseblanks([0], [0]) :- !.
collapseblanks([0|Rest], [0|CRest]) :- 
	((is_input(In),member(In,Rest),!);(is_input(In), member(tape(I,_),Rest), member(In, I))), !, 
	collapseblanks(Rest, CRest).
collapseblanks([0|Rest], [0]) :- 
	Rest = [0|Rest1],
	\+ (is_input(In), member(In, Rest1)), \+ (is_input(In), member(tape(I,_),Rest1), member(In,I)), !. 
collapseblanks([tape(I,X)|Rest], [tape(I,X)|CRest]) :-
	!, collapseblanks(Rest, CRest). 

updatetape(Left, Right, t(State, In, InDir, NewState, Output, OutDir, _Steps), Type, NewLeft, NewRight, 1) :-
	Type = comp(_N),
	checktape(Left, Type, NL), 
	((State \== NewState, OutDir = l); (State == NewState, OutDir = l, different(NL, In));(State == NewState, InDir = l, OutDir = l)), !, 
	tapeconvert(Right, Output, NR), 
	transfertoright(NL, NR, Type, NewLeft, NewRight), 
	!, true.

updatetape(Left, [tape(In,Count)|Right], t(State, In, r, NewState, Output, l, _Steps), Type, NewLeft, NewRight, C1) :-
	Type = comp(_N),
	State == NewState, 
	checktape(Left, Type, NL), NL = [tape(I,C)|NewL], I == In, In == Output, !, 
	NewC is Count + C, NewR = [tape(In,NewC)|Right], !, 
	C1 is C + 1, !, 
	transfertoright(NewL, NewR, Type, NewLeft, NewRight), !.

updatetape(Left, [tape(In,Count)|Right], t(State, In, r, NewState, Output, l, _Steps), Type, NewLeft, NewRight, C1) :-
	Type = comp(_N),
	State == NewState, 
	checktape(Left, Type, NL), NL = [tape(I,C)|NewL], I == In, In \== Output, !, 
	behead([tape(In,Count)|Right], NR), checktape(NR, Type, New), !, 	
	C1 is C + 1, 
	attach(tape(Output,C1), New, Type, NewR), !, 
	transfertoright(NewL, NewR, Type, NewLeft, NewRight), 
	!.

updatetape(Left, Right, t(State, _In, InDir, NewState, Output, OutDir, _Steps), Type, NewLeft, NewRight, 1) :-
	Type = comp(_N),
	((State \== NewState, OutDir = r); (State == NewState, InDir = r, OutDir = r)), !, 
	tapeconvert(Right, Output, NR), !, 
	transfertoleft(Left, NR, Type, NewLeft, NewR), !, 
	checktape(NewR, Type, NewRight), 
	!.

updatetape(Left, [tape(In, Count)|Right], t(State, In, l, NewState, Output, r, _Steps), Type, NewLeft, NewRight, Count) :-
	Type = comp(_N),
	State == NewState, !, 
	attach(tape(Output,Count), Left, Type, NewLeft), !, 
	checktape(Right, Type, NewRight), !.

updatetape(Left, [tape(In,Count)|Right], t(State, In, InDir, NewState, Output, OutDir, _Steps), Type, NewLeft, NewRight, 1) :-
	Type = hyp(_N), State == NewState, InDir = r, OutDir = l, !, 
	checktape(Left, Type, [NewL|NL]), 
	Temp = [tape(Output,Count)|Right], NewRight = [NewL|Temp], NewLeft = NL.

updatetape(Left, [tape(In,Count)|Right], t(State, In, InDir, NewState, Output, OutDir, _Steps), Type, NewLeft, NewRight, 1) :-
	Type = hyp(_N), State == NewState, InDir = l, OutDir = r, !, 
	checktape(Right, Type, NewRight), 
	NewLeft = [tape(Output,Count)|Left], !. 

different(NL, In) :-	NL = [tape(I,_)|_], I \== In, !.
different(NL, In) :-	NL = [I|_], I \= tape(_,_), I \== In, !.

behead([tape(In,Count)|Rest], [tape(In,C1)|Rest]) :-
	integer(Count), Count > 1, !, C1 is Count - 1, !. 
behead([tape(_In,Count)|Rest], Rest) :- 
	integer(Count), !.
behead([tape(In,Count)|Rest], [tape(In,C1)|Rest]) :-
	Count = v(C,_,_,_,_), C .>=. 1, !, C1 .=. C - 1, C1 .>=. 0, !. 

attach(tape(In1,Count1), [tape(In2, Count2)|Rest], comp, [tape(In2, Count)|Rest]) :-
	In1 == In2, \+ (In2 == 0, Rest = []), integer(Count1), integer(Count2), !, Count is Count1 + Count2, !. 
attach(tape(In1,Count1), [tape(In2, Count2)|Rest], comp, Result) :-
	In1 == In2, \+ (In2 == 0, Rest = []), (Count1 = v(_,_,_,_,_); Count2 = v(_,_,_,_,_)), !, 
	append([tape(In1,Count1)], [tape(In2, Count)|Rest], Result), !. 
attach(tape(In1,_), [tape(In2, _)|Rest], comp, [tape(0,1)]) :-
	In1 == In2, In2 == 0, Rest = [], !.
attach(tape(In1,Count1), Tape, comp, [tape(In1, Count1)|Tape]) :-
 	Tape = [tape(In2, _)|_], 
	In1 \== In2, !. 
attach(tape(In,Count), [], comp, [tape(In,Count)]) :- !. 

attach(tape(In1,Count1), [tape(In2, Count2)|Rest], Type, [tape(In2, Count)|Rest]) :-
	member(Type, [comp(_N),hyp(_N),adapt]), In1 == In2, \+ (empty(In2), Rest = []), integer(Count1), integer(Count2), !, Count is Count1 + Count2, !. 
attach(tape(In1,Count1), [tape(In2, Count2)|Rest], Type, Result) :-
	member(Type, [comp(_N),hyp(_N),adapt]), In1 == In2, \+ (empty(In2), Rest = []), (Count1 = v(_,_,_,_,_); Count2 = v(_,_,_,_,_)), !, 
	append([tape(In1,Count1)], [tape(In2, Count)|Rest], Result), !. 

attach(tape(In1,_), [tape(In2, _)|Rest], Type, [tape(T,1)]) :-
	member(Type, [comp(N),hyp(N),adapt]),In1 == In2, empty(In2), Rest = [], !, tapeN(N,T).
attach(tape(In1,Count1), Tape, Type, [tape(In1, Count1)|Tape]) :-
 	member(Type, [comp(_N),hyp(_N),adapt]), Tape = [tape(In2, _)|_], 
	In1 \== In2, !. 
attach(tape(In,Count), [], Type, [tape(In,Count)]) :- member(Type, [comp(_N),hyp(_N),adapt]), !. 

attach(tape(In1,Count1), Tape, hyp(_N), [tape(In1, Count1)|Tape]) :-
	Tape = [I|_], I \= tape(_,_), !. 

empty([0]).
empty([0|Rest]) :- empty(Rest). 

tapeconvert([tape(In,Count)|Rest], In, [tape(In,Count)|Rest]) :- !.
tapeconvert([tape(In,Count)|Rest], Out, NewRight) :-
	In \== Out, integer(Count), Count >= 2, !, 
	C1 is Count - 1, 
	Temp = [tape(In,C1)|Rest], 
	NewRight = [tape(Out,1)|Temp], !, 
	true. 
tapeconvert([tape(In,Count)|Rest], Out, NewRight) :-
	In \== Out, integer(Count), Count = 1, Rest = [], !, 
	NewRight = [tape(Out,1)],!, 
	true. 

tapeconvert([tape(In,Count)|Rest], Out, NewRight) :-
	In \== Out, integer(Count), Count = 1, Rest \== [],  
	Rest = [tape(In2,C)|Rest1], integer(C), In2 = Out, !, C1 is C + 1, 
	NewRight = [tape(In2,C1)|Rest1],!, 
	true. 

tapeconvert([tape(In,Count)|Rest], Out, NewRight) :-
	In \== Out, integer(Count), Count = 1, Rest \== [],  
	Rest = [tape(In2,C)|_Rest1], integer(C), In2 \== Out, !, 
	NewRight = [tape(Out,1)|Rest],!, 
	true. 

tapeconvert([tape(In,Count)|Rest], Out, NewRight) :-
	In \== Out, integer(Count), Count = 1, Rest \== [],  
	Rest = [tape(In2,C)|Rest1], var(C), In2 = Out, !, C1 .=. C + 1, 
	NewRight = [tape(In2,C1)|Rest1],!, 
	true. 

tapeconvert([tape(In,Count)|Rest], Out, NewRight) :-
	In \== Out, integer(Count), Count = 1, Rest \== [],  
	Rest = [tape(In2,C)|_Rest1], var(C), In2 \== Out, !, 
	NewRight = [tape(Out,1)|Rest],!, 
	true. 

tapeconvert([tape(In,Count)|Rest], Out, NewRight) :-
	In \== Out, Count = v(C,_,_,_,_), !, 
	C1 .=. C - 1, C1 .>=. 0, 
	Temp = [tape(In,C1)|Rest], 
	NewRight = [tape(Out,1)|Temp],!, 
	true. 

transfertoright([tape(Cl, CountL)|RestL], [], _, RestL, [tape(Cl, 1)]) :-
	integer(CountL), CountL == 1, !. 
transfertoright([tape(Cl, CountL)|RestL], [], _, [tape(Cl,NewCL)|RestL], [tape(Cl, 1)]) :-
	integer(CountL), CountL > 1, !, NewCL is CountL - 1, !. 
transfertoright([tape(Cl, CountL)|RestL], [], _, [tape(Cl,NewCL)|RestL], [tape(Cl, 1)]) :-
	var(CountL), !, NewCL .=. CountL - 1, NewCL .>=. 0, !.  %% Too hard to update!


transfertoright([tape(Cl, CountL)|RestL], [tape(Cr,CountR)|RestR], _, RestL, [tape(Cr, NewCR)|RestR]) :-
	Cl == Cr, integer(CountL), integer(CountR), CountL == 1, !, NewCR is CountR + 1, !. 
transfertoright([tape(Cl, CountL)|RestL], [tape(Cr,CountR)|RestR], _, RestL, [tape(Cr, NewCR)|RestR]) :-
	Cl == Cr, integer(CountL), var(CountR), CountL == 1, !, NewCR .=. CountR + 1, !. %% Too hard to update!

transfertoright([tape(Cl, CountL)|RestL], [tape(Cr,CountR)|RestR], _, [tape(Cl,NewCL)|RestL], [tape(Cr, NewCR)|RestR]) :-
	Cl == Cr, integer(CountL), integer(CountR), CountL > 1, !, NewCL is CountL - 1, NewCR is CountR + 1, !. 
transfertoright([tape(Cl, CountL)|RestL], [tape(Cr,CountR)|RestR], _, [tape(Cl,NewCL)|RestL], [tape(Cr, NewCR)|RestR]) :-
	Cl == Cr, integer(CountL), var(CountR), CountL > 1, !, NewCL is CountL - 1, NewCR .=.  CountR + 1, !. %% Too hard to update!

transfertoright([tape(Cl, CountL)|RestL], [tape(Cr,CountR)|RestR], _, [tape(Cl,NewCL)|RestL], [tape(Cr, NewCR)|RestR]) :-
	Cl == Cr, var(CountL), !, NewCL .=. CountL - 1, NewCL .>=. 0, NewCR .=. CountR + 1, !. %% Too hard to update!

transfertoright([tape(Cl, CountL)|RestL], [tape(Cr,CountR)|RestR], _, RestL, NewR) :-
	Cl \== Cr, integer(CountL), CountL = 1, !, 
	Temp = [tape(Cr,CountR)|RestR], NewR = [tape(Cl,1)|Temp], !. 
transfertoright([tape(Cl, CountL)|RestL], [tape(Cr,CountR)|RestR], _, [tape(Cl,NewCL)|RestL], NewR) :-
	Cl \== Cr, integer(CountL), CountL > 1, !, NewCL is CountL - 1, 
	Temp = [tape(Cr,CountR)|RestR], NewR = [tape(Cl,1)|Temp], !. 
transfertoright([tape(Cl, CountL)|RestL], [tape(Cr,CountR)|RestR], _, [tape(Cl,NewCL)|RestL], NewR) :-
	Cl \== Cr, var(CountL), !, NewCL .=. CountL - 1, NewCL .>=. 0, 
	Temp = [tape(Cr,CountR)|RestR], NewR = [tape(Cl,1)|Temp], !. %% Too hard to update!

transfertoright([tape(Cl, CountL)|RestL], Right, hyp(_N), RestL, [tape(Cl, CountL)|Right]) :-
	Right = [I|_Rest], I \= tape(_,_). 

transfertoright([], Right, comp, [], NewRight) :- 
	attach(tape(0,1), Right, comp, NewRight), !.
transfertoright([], Right, comp(K), [], NewRight) :- 
	tapeN(K, T), 
	attach(tape(T,1), Right, comp(K), NewRight), !.
transfertoright([], Right, adapt, [], NewRight) :- 
	attach(tape([0],1), Right, adapt, NewRight), !.
transfertoright([], Right, hyp(_K), [], [0|Right]) :- !. 
transfertoright([I|_Rest], Right, hyp(_K), [], [I|Right]) :- I \= tape(_,_), !. 

transfertoleft(Left, Right, Type, NewLeft, NewRight) :-
	transfertoright(Right, Left, Type, NewRight, NewLeft), !. 

checkstate([A|R], [A|R]) :- !.
checkstate([], [0]) :- !.  

checktape([A|R], _, [A|R]) :- !.
checktape([], comp, [tape(0,1)]) :- !. 
checktape([], comp(N), [tape(T,1)]) :- !, tapeN(N, T). 
checktape([], hyp(_N), [0]) :- !.
checktape([], adapt, [tape([0],1)]) :- !. 

tapeN(0, []). 
tapeN(N, [0|Rest]) :- N > 0, N1 is N-1, tapeN(N1, Rest). 

updateones(0,0,_Jump,Ones,Ones) :- !. 
updateones(X,Y,_Jump,Ones,Ones) :- is_input(X), X \== 0, is_input(Y), Y \== 0, !.
updateones(0,X,Jump,Ones,New) :-  is_input(X), X \== 0, !, New is Ones + Jump. 
updateones(X,0,Jump,Ones,New) :-  is_input(X), X \== 0, !, New is Ones - Jump. 

updateoneschunk(In, Out, Jump, OldOnes, NewOnes) :-
	addones(In, 0, Old), addones(Out, 0, New),
	NewOnes is OldOnes + Jump * (New - Old). 

updatelist(State, List, List) :- member(State, List), !.
updatelist(State, List, NewList) :- \+ member(State, List), !, append(List, [State], NewList).

%% Emulation routine.
emulate(M, B, Options, Ones, Hops, Status, Outputs) :-
	findtype(Options, Type), 
        setoptions(M, Options, Type, Inputs), 
        getnum(B, Bound), 
        retractall(result(_, _, _, _, _)), 
	initial(Type, Start), 
	machine(M, Type, Machine), 
	!, 
  	run(Start, Machine, Bound, Type, 0, 0, Inputs), 
        result(Machine1, Ones, Hops, Status, Outputs), 
	retract(result(Machine1, _Ones1, _Hops1, _Status1, _Outputs1)).

findtype(Options, naive) :- member(naive, Options). 
findtype(Options, adapt) :- member(adapt, Options). 
findtype(Options, comp(N)) :- member(comp(N), Options). 
findtype(Options, comp) :- member(comp, Options). 
findtype(Options, flex) :- member(flex, Options). 
findtype(Options, flex) :- \+ member(naive, Options), \+ member(comp(_), Options), \+ member(adapt, Options). 
 
setoptions(M, Options, Type, List) :-
	setstuff(Options, Type, I1), 
	settrigger(Options, trigger(Start, Jump)),
	setwatch(M, Options, Watch),
	append([trigger(Start, Jump)], I1, Temp),
	append(Watch, Temp, List). 

setstuff([], _Type, [pos(0)]). 
setstuff([max|Rest], Type, Inputs) :-
	setstuff(Rest, Type, Is),
 	append(Is, [onescount(0,0),status(increasing)], Inputs). 

setstuff([loop|Rest], Type, Inputs) :-
	setstuff(Rest, Type, Is),
	initial(Type, Start), 
	append(Is, [now(Start), history([])], Inputs). 

setstuff([hist|Rest], Type, Inputs) :-
	setstuff(Rest, Type, Is),
	initial(Type, Start), 
	append(Is, [now(Start), history([])], Inputs). 

setstuff([A|Rest], Type, Inputs) :-
	member(A, [notrace,trace,trace(_,_),watch(_,_),pivotal,nomax,noloop,naive,comp,comp(_),flex,adapt]), 
	setstuff(Rest, Type, Inputs).
setstuff([A|Rest], Type, Inputs) :-
	\+ member(A, [notrace,trace,trace(_,_),watch(_,_),pivotal,nomax,noloop,naive,comp,comp(_),flex,adapt]), 
	format("Unknown option ~k ignored~n", A), 
	setstuff(Rest, Type, Inputs).

settrigger(Options, trigger(0,0)) :-
	member(notrace, Options). 
settrigger(Options, trigger(1,1)) :-
	\+ member(notrace, Options),
	member(trace, Options). 
settrigger(Options, trigger(Start,Jump)) :-
	\+ member(notrace, Options),
	\+ member(trace, Options),
	member(trace(S, J), Options),
	getnum(S,Start), getnum(J,Jump),
	true. 
	
settrigger(Options, trigger(Start,Jump)) :-
	\+ member(notrace, Options), 
	\+ member(trace, Options),
	\+ member(trace(_Start, _Jump), Options), 
	trigger_defaults(Start, Jump).

trigger_defaults(10000000,10000000).

setwatch(M, Options, [watch(WatchList)]) :-
	extract(M, Options, WatchList). 
setwatch(_M, Options, []) :-
	\+ member(watch(_,_), Options). 

extract(_M, [], []). 
extract(M, [watch(S,I)|Rest], [watch(S,I)|Wlist]) :- 
	extract(M, Rest, Wlist).
extract(M, [pivotal|Rest], [watch(S)|Wlist]) :- 
	pivotal(M, S), 
	extract(M, Rest, Wlist).
extract(M, [Item|Rest], Wlist) :- 
	Item \== watch(_S,_I), Item \== pivotal, extract(M, Rest, Wlist).

initial(naive, state([], a, [0])).
initial(flex, state([], a, [0])).
initial(comp,  state([], a, [tape(0,1)])). 
initial(comp(K), state([], a, l, [tape(List,1)])) :- blanks(K, List).
initial(adapt, state([], a, l, [tape([0],1)])). 

blanks(0, []).
blanks(K, [0|Rest]) :- K > 0, K1 is K-1, blanks(K1, Rest).

machine(M, naive, M) :- !.
machine(M, comp, M) :- !. 
machine(M, flex, M) :- !. 
machine(M, adapt, M) :- !. 
machine(M, comp(K), Machine) :- 
	states(M, States), length(States, N), 
	inputs(M, Inputs), 
	tapes(Inputs, K, Tapes),
	paths(M, N, K, States, Tapes,  [], Machine).

states(M, States) :- states1(M, [], States). 
states1([], States, States).
states1([t(S,_,_,_,_)|Rest], StatesSoFar, States) :-
	add(S, StatesSoFar, NewSoFar),
	states1(Rest, NewSoFar, States). 

inputs(M, Inputs) :- inputs1(M, [], Inputs). 
inputs1([], Inputs, Inputs).
inputs1([t(_,I,_,_,_)|Rest], InputsSoFar, Inputs) :-
	add(I, InputsSoFar, NewSoFar),
	inputs1(Rest, NewSoFar, Inputs). 

add(Item, List, List) :-
	member(Item, List). 
add(Item, List, NewList) :-
	\+ member(Item, List), append(List, [Item], NewList). 

paths(_M, _N, _K, [], _Tapes, Machine, Machine).
paths(M, N, K, [State|Rest], Tapes, SoFar, Machine) :-
	pathstate(M, N, K, State, Tapes, SoFar, Machine1),
	paths(M, N, K, Rest, Tapes, Machine1, Machine).

pathstate(_M, _N, _K, _State, [], Machine, Machine).
pathstate(M, N, K, State, [Tape|Tapes], SoFar, Machine) :-
	transitions(M, N, K, State, Tape, Transitions),
	append(SoFar, Transitions, Machine1),  % simplistic; should insert into a tree, ie inserttree(OldMachine, Transitions, NewMachine)
	pathstate(M, N, K, State, Tapes, Machine1, Machine).

transitions(M, N, K, State, Tape, Transitions) :-
	B is truncate(N * K * 2**K), maxbound(B, Bound), 
	splitlast(Tape, T1, Tape2), reverse(T1, Tape1), !, 
 	wild_wombat(state([], State, Tape), M, Bound, naive, 0, 0, [pos(0),dir(r),size(K),trigger(1000000,1000000)], state(LFR,FR,RFR), Out1, Steps1), !, % Left case
 	wild_wombat(state(Tape1, State, Tape2), M, Bound, naive, 0, 0, [pos(0),dir(l),size(K),trigger(1000000,1000000)], state(LFL,FL,RFL), Out2, Steps2), !, % Right case
	reverse(LFR, RL), reverse(LFL, LL), 
	combine(RL, RFR, K, TapeR), combine(LL, RFL, K, TapeL), 
	Transitions = [t(State, Tape, l, FR, TapeR, Out1, Steps1), t(State, Tape, r, FL, TapeL, Out2, Steps2)], !. 

combine([0], Right, K, Right) :- length(Right, K), !. 
combine(Left, [0], K, Left) :-	length(Left, K), !. 
combine(Left, Right, K, New) :- length(Left, K1), length(Right, K2), K is K1 + K2, !, append(Left, Right, New). 

splitlast(T, T1, T2) :- append(T1, T2, T), length(T2, 1). 

cleanlast(Tape, K, Tape) :- 
	length(Tape, L), L =< K, !. 
cleanlast(Tape, K, CleanTape) :- 
	length(Tape, L), L > K, !, append(CleanTape, _, Tape), length(CleanTape, K). 

maniacal_monkey(_Options, state(Left, h, _, Right), _M, _Bound, _Ones, Hops, _Inputs, _TargetPos, state(Left, h, _, Right), r, Hops).

maniacal_monkey(_Options, state(Left, State, _InDir, Right), _M, Bound, _Ones, Hops, _Inputs, _TargetPos, state(Left, loop, _, Right), r, Hops) :- 
        State \== h, Hops >= Bound.

maniacal_monkey(_Options, state(Left, State, _InDir, Right), _M, Bound, _Ones, Hops, Inputs, TargetPos, state(Left, State, OppDir, Right), OppDir, Hops) :-
	State \== h, Hops < Bound, 
	member(pos(TargetPos), Inputs), 	
	member(dir(Dir), Inputs), opposite(Dir, OppDir).

maniacal_monkey(Options, state(Left, State, InDir, [In|Right]), M, Bound, Ones, Hops, Inputs, TargetPos, Final, Out, Steps) :-
	State \== h, Hops <  Bound, In \== tape(_,_),  
 	member(t(State,In,Output,Dir,NewState), M), 
	hypout(Options, "MM", Hops, Left, State, Dir, InDir, [In|Right]), 
	updateLRNCB(Left, [In|Right], Output, Dir, NewLeft, NewRight), 
	Hops1 is Hops + 1, 
	updateones(In, Output, 1, Ones, Ones1), 
	updateinputs(Inputs, In, Output, Dir, Ones1, Hops1, 1, naive, NewLeft, NewState, NewRight, NewInputs), !, 
	opposite(Dir, OutDir), 
	maniacal_monkey(Options, state(NewLeft, NewState, OutDir, NewRight), M, Bound, Ones1, Hops1, NewInputs, TargetPos, Final, Out, Steps). 

maniacal_monkey(Options, state(Left, State, InDir, Right), M, Bound, Ones, Hops, Inputs, TargetPos, Final, OutD, StepsT) :-
 	State \== h, State \== loop, Hops <  Bound, Right = [tape(In,_Num)|_Rest], 
	states(M, Ss), length(Ss, N), 
	length(In, L), transitions(M, N, L, State, In, Trans),
	member(t(State,In,InDir,NewState,Out,OutDir,Steps), Trans), 
	State == NewState, 
	opposite(InDir, OutDir), 
	updatetape(Left, Right, t(State,In,InDir,NewState,Out,OutDir,Steps), hyp(L), NewLeft, NewRight, _Leap),
	Hops1 is Hops + 1, 
	maniacal_monkey(Options, state(NewLeft, NewState, InDir, NewRight), M, Bound, Ones, Hops1, Inputs, TargetPos, Final, OutD, StepsT). 

slithery_snake(state(Left, h, Right), _M, _Bound, _Type, _Ones, Hops, _Inputs, _LeftPos, _RightPos, state(Left, h, Right), r, Hops) :- !.

slithery_snake(state(Left, State, Right), _M, Bound, _Type, _Ones, Hops, _Inputs, _LeftPos, _RightPos, state(Left, loop, Right), r, Hops) :- 
        State \== h, Hops >= Bound, !.

slithery_snake(state(Left, State, Right), _M, Bound, naive, _Ones, Hops, Inputs, LeftPos, RightPos, state(Left, State, Right), OppDir, Hops) :-
	State \== h, Hops < Bound, 
	member(pos(N), Inputs), member(dir(Dir), Inputs), opposite(Dir, OppDir),
	outside(LeftPos, RightPos, N, OppDir), !.

slithery_snake(state(Left, State, [In|Right]), M, Bound, naive, Ones, Hops, Inputs, LeftPos, RightPos, Final, Out, Steps) :-
	State \== h, Hops <  Bound, !, 
 	member(t(State,In,Output,Dir,NewState), M), 
	updateLRNCB(Left, [In|Right], Output, Dir, NewLeft, NewRight), 
	Hops1 is Hops + 1, 
	updateones(In, Output, 1, Ones, Ones1), 
	updateinputs(Inputs, In, Output, Dir, Ones1, Hops1, 1, naive, NewLeft, NewState, NewRight, NewInputs), !, 
	slithery_snake(state(NewLeft, NewState, NewRight), M, Bound, naive, Ones1, Hops1, NewInputs, LeftPos, RightPos, Final, Out, Steps). 
	
updatemaxpos(L, R, N, N, R) :- N < L, !. 
updatemaxpos(L, R, N, L, N) :- N > R, !. 
updatemaxpos(L, R, N, L, R) :- N >= L, N =< R, !. 

wild_wombat(state(Left, h, Right), _M, _Bound, _Type, _Ones, Hops, _Inputs, state(Left, h, Right), r, Hops) :- !. 

wild_wombat(state(Left, State, Right), _M, Bound, _, _Ones, Hops, _Inputs, state(Left, loop, Right), r, Hops) :- 
	State \== h, Hops >= Bound, !. 

wild_wombat(state(Left, State, [_In|Right]), _M, Bound, naive, _Ones, Hops, Inputs, state(Left, State, Right), Out, Hops) :-
	State \== h, Hops < Bound, member(pos(N), Inputs), member(dir(Dir), Inputs), member(size(K), Inputs), 
	outofbounds(N, K, Dir, Out), !. 

wild_wombat(state(Left, State, [In|Right]), M, Bound, naive, Ones, Hops, Inputs, Final, Out, Steps) :-
	State \== h, Hops <  Bound, !, 
 	member(t(State,In,Output,Dir,NewState), M), % format("Updatnig~n", []), 
	updateLRNCB(Left, [In|Right], Output, Dir, NewLeft, NewRight),
	Hops1 is Hops + 1, 
	updateones(In, Output, 1, Ones, Ones1), 
	updateinputs(Inputs, In, Output, Dir, Ones1, Hops1, 1, naive, NewLeft, NewState, NewRight, NewInputs), !, 
	wild_wombat(state(NewLeft, NewState, NewRight), M, Bound, naive, Ones1, Hops1, NewInputs, Final, Out, Steps). 

run_backwards(state(Left, _State, Right), _M, Bound, _, _Ones, Hops) :- 
	(Hops >= Bound; (length(Left,L), L > 4); (length(Right,R), R > 4)), 
	true. 

run_backwards(state(Left, State, Right), M, Bound, naive, Ones, Hops) :-
	Hops <  Bound, length(Left,L), L =< 4, length(Right,R), R =< 4,	
 	member(t(NewState,In,Output,Dir,State), M), 
	updateLRback(Left, Right, In, Output, Dir, NewLeft, NewRight),
	Hops1 is Hops + 1, 
	updateones(Output, In, 1, Ones, Ones1), % format("Recurring~n", []), 
	run_backwards(state(NewLeft, NewState, NewRight), M, Bound, naive, Ones1, Hops1). 

run_forwards(state(Left, State, Right), _M, Bound, _, _TargetState, _TargetInput, Ones, Hops) :- 
	Hops >= Bound, prettyprint(State, Left, 0, naive, Right, Hops, Ones). 

run_forwards(state(Left, State, Right), _M, Bound, _, State, TargetInput, Ones, Hops) :- 
	0 < Hops, Hops < Bound, Right = [TargetInput|_], prettyprint(State, Left, 0, naive, Right, Hops, Ones).

run_forwards(state(Left, State, Right), M, Bound, naive, TargetState, TargetInput, Ones, Hops) :-
	Hops <  Bound, Right = [Current|_Rest], (State \== TargetState; (State = TargetState, TargetInput \== Current)), 
	prettyprint(State, Left, 0, naive, Right, Hops, Ones), 
 	member(t(State,In,Output,Dir,NewState), M), 
	updateLRfront(Left, Right, In, Output, Dir, NewLeft, NewRight),
	Hops1 is Hops + 1, 
	updateones(In, Output, 1, Ones, Ones1), 
	run_forwards(state(NewLeft, NewState, NewRight), M, Bound, naive, TargetState, TargetInput, Ones1, Hops1). 

meandering(M) :-
	member(t(S,I,_,_,h), M), 
	\+ run_backwards(state([],S,[I]), M, 100, naive, 0, 0). 

outofbounds(N, _K, r, l) :- N < 0, !. % range is 0..K-1.
outofbounds(N, K, r, r) :- N >= K, !.
outofbounds(N, _K, l, r) :- N > 0, !. % range is -(K-1) ..0. 
outofbounds(N, K, l, l) :- N + K =< 0, !.

outside(LeftPos, _RightPos, N, l) :- N < LeftPos, !. 
outside(_LeftPos, RightPos, N, r) :- N > RightPos, !. 

tapes(Inputs, 1, Tapes) :-
	collect(Inputs, Tapes). 
tapes(Inputs, N, Tapes) :-
	N > 1,!, N1 is N-1, 
	tapes(Inputs, N1, Previous), 
	prepend_inputs(Inputs, Previous, [], Tapes). 

collect([], []).
collect([I|Rest], Final) :-
	collect(Rest, Others), 
	append([[I]], Others, Final). 

prepend_inputs([], _, Tapes, Tapes). 
prepend_inputs([Input|Rest], Previous, SoFar, Tapes) :-
	prependtoall(Input, Previous, New),
	append(New, SoFar, NewSoFar),
	prepend_inputs(Rest, Previous, NewSoFar, Tapes). 

prependtoall(_, [], []).
prependtoall(Item, [List1|Rest1], [List2|Rest2]) :-
	append([Item], List1, List2),
	prependtoall(Item, Rest1, Rest2). 


switch(0,1).
switch(1,0).

% Main run routine. This is the heart of the emulation engine. 

run(State, M, Bound, flex, _Ones, _Hops, Inputs) :-
	run(State, M, 1000, naive, 0, 0, Inputs), !, % selects best compact mode by seeing which gives the shortest representation. 
	result(M, O1, H1, S, Outputs),  
	retract(result(M, O1, H1, S, Outputs)), 
	member(left(Left), Outputs),
	member(right(Right), Outputs), 
	convert_to_best(Left, Right, K), 
	initial(comp(K), Start), 
	machine(M, comp(K), Machine), !, 
	run(Start, Machine, Bound, comp(K), 0, 0, Inputs).

run(state(Left, h, Right), M, _Bound, Type, Ones, Hops, Inputs) :-
	member(Type, [naive,comp]), !, 
	convert(h, Left, Right, Type, Inputs, Ones, Hops, Outputs), 
	assertz(result(M, Ones, Hops, halts, Outputs)).

run(state(Left, h, _Dir, Right), M, _Bound, Type, Ones, Hops, Inputs) :-
	Type = comp(K),
	!, convert(h, Left, Right, Type, Inputs, Ones, Hops, Outputs), 
	assertz(result(M, Ones, Hops, halts, Outputs)).

run(state(Left, loop, _Dir, Right), M, _Bound, Type, Ones, Hops, Inputs) :-
	Type = comp(K),
	!, convert(h, Left, Right, Type, Inputs, Ones, Hops, Outputs), 
	assertz(result(M, Ones, Hops, loops(cycle), Outputs)).

run(state(Left, State, Right), M, Bound, Type, Ones, Hops, Inputs) :- 
	member(Type, [naive,comp]), State \== h, State \== loop, Hops >= Bound, !, 
	convert(State, Left, Right, Type, Inputs, Ones, Hops, Outputs), 
	assertz(result(M, Ones, Hops, going, Outputs)).

run(state(Left, State, _Dir,Right), M, Bound, Type, Ones, Hops, Inputs) :- 
	Type = comp(K),
	State \== h, State \== loop, Hops >= Bound, !, 
	convert(State, Left, Right, Type, Inputs, Ones, Hops, Outputs), 	
	assertz(result(M, Ones, Hops, going, Outputs)).

run(state(Left, State, Right), M, Bound, Type, Ones, Hops, Inputs) :-
 	member(Type, [naive,comp]), State \== h, State \== loop, Hops > 0, Hops < Bound,  blank(Type, Left, Right), !, 
 	convert(State, Left, Right, Type, Inputs, Ones, Hops, Outputs), 
 	assertz(result(M, Ones, Hops, blank, Outputs)).

run(state(Left, State, _Dir, Right), M, Bound, Type, Ones, Hops, Inputs) :-
	Type = comp(K),
 	State \== h, State \== loop, Hops > 0, Hops < Bound,  blank(adapt, Left, Right), !, 
 	convert(State, Left, Right, Type, Inputs, Ones, Hops, Outputs), 
 	assertz(result(M, Ones, Hops, blank, Outputs)).

run(state(Left, State, Right), M, Bound, Type, Ones, Hops, Inputs) :-
  	member(Type, [naive,comp]), State \== h, State \== loop, Hops > 0, Hops < Bound, escapecheck(Left, State, Right, Type, M), !, 
  	convert(State, Left, Right, Type, Inputs, Ones, Hops, Outputs), 
  	assertz(result(M, Ones, Hops, loops(cycle), Outputs)).

run(state(Left, State, _Dir, Right), M, Bound, Type, Ones, Hops, Inputs) :-
	Type = comp(K),
  	State \== h, State \== loop, Hops > 0, Hops < Bound, escapecheck(Left, State, Right, Type, M), !, 
  	convert(State, Left, Right, Type, Inputs, Ones, Hops, Outputs), 
  	assertz(result(M, Ones, Hops, loops(cycle), Outputs)).

run(state(Left, State, [In|Right]), M, Bound, naive, Ones, Hops, Inputs) :-
	State \== h, State \== loop, Hops <  Bound, \+ member(t(State,In,_Output,_Dir,_NewState), M), !, 
  	convert(State, Left, [In|Right], naive, Inputs, Ones, Hops, Outputs), 
  	assertz(result(M, Ones, Hops, abort, Outputs)).

run(state(Left, State, [tape(In,Num)|Right]), M, Bound, comp, Ones, Hops, Inputs) :-
	State \== h, State \== loop, Hops <  Bound, \+ member(t(State,In,_Output,_Dir,_NewState), M), !, 
  	convert(State, Left, [tape(In,Num)|Right], comp, Inputs, Ones, Hops, Outputs), 
  	assertz(result(M, Ones, Hops, abort, Outputs)).

run(state(Left, State, InDir, [tape(In,Num)|Right]), M, Bound, comp(N), Ones, Hops, Inputs) :-
	State \== h, State \== loop, Hops <  Bound, \+ member(t(State,In,InDir,_NewState,_Out,_OutDir,_Steps), M), !, 
  	convert(State, Left, [tape(In,Num)|Right], comp(N), Inputs, Ones, Hops, Outputs), 
  	assertz(result(M, Ones, Hops, abort, Outputs)).

run(state(Left, State, [In|Right]), M, Bound, naive, Ones, Hops, Inputs) :-
	State \== h, State \== loop, Hops <  Bound, !, 
 	member(t(State,In,Output,Dir,NewState), M), 
	updateLR(Left, [In|Right], Output, Dir, NewLeft, NewRight),
	Hops1 is Hops + 1, 
	updateones(In, Output, 1, Ones, Ones1), 
	updateinputs(Inputs, In, Output, Dir, Ones1, Hops1, 1, naive, NewLeft, NewState, NewRight, NewInputs), !, 
	run(state(NewLeft, NewState, NewRight), M, Bound, naive, Ones1, Hops1, NewInputs). 

run(state(Left, State, Right), M, Bound, comp, Ones, Hops, Inputs) :-
	State \== h, State \== loop, Hops <  Bound, !, 
	Right = [tape(In,_)|_], 
 	member(t(State,In,Output,Dir,NewState), M), 
	updatetape(Left, Right, t(State,In,Output,Dir,NewState), comp, NewLeft, NewRight, Leap),!, 
	Hops1 is Hops + Leap, 
	updateones(In, Output, Leap, Ones, Ones1), !, 
	updateinputs(Inputs, In, Output, Dir, Ones1, Hops1, Leap, comp, NewLeft, NewState, NewRight, NewInputs), !, 
	run(state(NewLeft, NewState, NewRight), M, Bound, comp, Ones1, Hops1, NewInputs). 

run(state(Left, State, InDir, Right), M, Bound, comp(N), Ones, Hops, Inputs) :-
	State \== h, State \== loop, Hops <  Bound, !, 
	Right = [tape(In,_)|_], 
        member(t(State,In,InDir,NewState,Out,OutDir,Steps), M), 
	updatetape(Left, Right, t(State,In,InDir,NewState,Out,OutDir,Steps), comp(N), NewLeft, NewRight, Leap),!, 
	Hops1 is Hops + Leap * Steps, 
	updateoneschunk(In, Out, Leap, Ones, Ones1), !, % format("Chunk done~n", []), 
	updateinputs(Inputs, In, Out, OutDir, Ones1, Hops1, Leap, comp(N), NewLeft, NewState, NewRight, NewInputs), !, 
	opposite(OutDir, NewDir), 
	run(state(NewLeft, NewState, NewDir, NewRight), M, Bound, comp(N), Ones1, Hops1, NewInputs). 

next_occurrence(state(Left, State, Right), M, Bound, Pattern, Hops, state(Left, State, Right)) :- 
	State \== h, State \== loop, Hops < Bound, Hops > 0, 
	same_pattern(state(Left, State, Right), Pattern). 

next_occurrence(state(Left, State, [In|Right]), M, Bound, Pattern, Hops, NextState) :- 
	State \== h, State \== loop, Hops < Bound, 
 	member(t(State,In,Output,Dir,NewState), M), 
	updateLR(Left, [In|Right], Output, Dir, NewLeft, NewRight),!, 
	Hops1 is Hops + 1, !, 
	% prettyprint(NewState, NewLeft, 1, naive, NewRight, Hops1, 0), 
	next_occurrence(state(NewLeft, NewState, NewRight), M, Bound, Pattern, Hops1, NextState). 
	
same_pattern(State, Pattern) :-
	compact_state(State, CS), matches(CS, Pattern).

matches(state(Left, State, Right), state(PL, State, PR)) :-
	matches1(Left, PL), matches1(Right, PR).

matches1([], []).
matches1([tape(I,_)|Rest1], [tape(I,_)|Rest2]) :-
	matches1(Rest1, Rest2).

convert_tape(Tape, N, Tape) :-	N = 0, !. 
convert_tape(Tape, N, NewTape) :-
	N > 0, 
	length(Tape, T), PadLength is (N - (T mod N)) mod N, 
	blanks(PadLength, Blanks), append(Tape, Blanks, NT),
	reverse(NT, Rev),!, 
	convert_to_blocks([], N, Rev, NewTape).

convert_to_blocks(SoFar, _N, [], SoFar) :- !. 
convert_to_blocks(SoFar, N, Tape, NewTape) :-
	length(Tape, T), T > 0, !, 
	append(Block, Rest, Tape), length(Block, N), 
	reverse(Block, B),
	attach(tape(B,1), SoFar, comp(N), Temp),!, 
	convert_to_blocks(Temp, N, Rest, NewTape), !. 

convert_to_best(Left, Right, K) :-
	reverse(Left, L), append(L, Right, Tape), 
	convert_tape(Tape, 2, T2), length(T2, L2), !, 
	convert_tape(Tape, 3, T3), length(T3, L3), !, 
	convert_tape(Tape, 4, T4), length(T4, L4), !, 
	convert_tape(Tape, 5, T5), length(T5, L5), !, 
	shortest(L2,L3,L4,L5, K). 

shortest(T2, T3, T4, T5, 2) :-	T2 =< T3, T2 =< T4, T2 =< T5, !.
shortest(T2, T3, T4, T5, 3) :-	T3 =< T2, T3 =< T4, T3 =< T5, !. 
shortest(T2, T3, T4, T5, 4) :-	T4 =< T2, T4 =< T3, T4 =< T5, !.
shortest(T2, T3, T4, T5, 5) :-	T5 =< T2, T5 =< T3, T5 =< T4, !. 

hyprun(Current, M, Bound, Type, Initial, Target, Hops, Used, Status) :-
	hyprun([], Current, M, Bound, Type, Initial, Target, Hops, Used, Status).
hyprun(Options, Current, M, Bound, Type, Initial, Target, Hops, Used, Status) :-
	retractall(numswitch(_)), assert(numswitch(0)), %% awful hack to bound the number of switch attempts. There must be a cleaner way to do this!
	hyprun_real(Options, Current, M, Bound, Type, Initial, Target, [], Hops, Used, Status).

hyprun_real(_Options, state(_, h, _, _), _M, _Bound, hyp(_N), _, Target, _History, _Hops, _, halts(Target)) :- 
	!, true. 
hyprun_real(_Options, state(_Left, loop, _Dir, _Right), _M, _Bound, _K, _Initial, _Target,  _History,_Hops, _, loops(cycle)) :- 
	!, true. 
hyprun_real(_Options, state(Left, State, Dir, Right), _M, Bound, _K, _Initial, state(TL, State, Dir, TR),  _History, Hops, Used, target(Used,Hops)) :-
	State \== h, State \== loop, Hops > 0, Hops < Bound, 
	variant(left, TL, Left),
	variant(right, TR, Right), 
        !. 

hyprun_real(_Options, state(Left, _State, _Dir, Right), _M, Bound, _K, _Initial, state(TL, _, _, TR),  _History, Hops, _, going) :-
	State \== h, State \== loop, Hops > 0, Hops < Bound, 
 	delete_trail_blanks(Left, L1), 
 	delete_trail_blanks(Right, R1), 
  	length(TL, T1), length(TR, T2), length(L1, L), length(R1, R), L + R >=  4 * (T1 + T2), % format("Too long~n", []), 
	!, fail. 

hyprun_real(_Options, state(_Left, State, _InDir, Right), M, Bound, hyp(_K), _Initial, _Target,  _History, Hops, _, abort) :-
 	State \== h, State \== loop, Hops <  Bound, Right = [In|_Rest], is_input(In), \+ member(t(State,In,_Out,_Dir, _NS), M), !, 
	true. 

hyprun_real(Options, state(Left, State, InDir, Right), M, Bound, hyp(K), Initial, Target,  History, Hops, Used, Status) :-
 	State \== h, State \== loop, Hops <  Bound, 
	Right = [In|_Rest], is_input(In), 
 	member(t(State,In,Output,Dir,NewState), M), 
	hypout(Options, "Case 1", Hops, Left, State, Dir, InDir, Right), 
	updateLR(Left, Right, Output, Dir, NewLeft, NewRight),
	opposite(Dir, NewDir), 
	append([state(NewLeft, NewState, NewDir, NewRight)], History, NewHistory), 
	Hops1 is Hops + 1, !, %% can commit to this ... 
	hyprun_real(Options, state(NewLeft, NewState, NewDir, NewRight), M, Bound, hyp(K), Initial, Target, NewHistory, Hops1, Used, Status). 

hyprun_real(Options, state(Left, State, InDir, Right), M, Bound, hyp(K), Initial, Target, History, Hops, Used, Status) :-
 	State \== h, State \== loop, Hops < Bound, 
	Right = [tape(In,Num)|_Rest], int(Num), 
	states(M, Ss), length(Ss, N), 
	length(In, L), transitions(M, N, L, State, In, Trans),
	member(t(State,In,InDir,NewState,Out,OutDir,Steps), Trans), 
	hypout(Options, "Case 1a", Hops, Left, State, OutDir, InDir, Right), 
	updatetape(Left, Right, t(State,In,InDir,NewState,Out,OutDir,Steps), hyp(L), NewLeft, NewRight, _Leap), 
	opposite(OutDir, NewDir), 
	append([state(NewLeft, NewState, NewDir, NewRight)], History, NewHistory), 
	Hops1 is Hops + 1, !, %% can commit to this ... 
	hyprun_real(Options, state(NewLeft, NewState, NewDir, NewRight), M, Bound, hyp(K), Initial, Target,  NewHistory, Hops1, Used, Status). 

hyprun_real(Options, state(Left, State, InDir, Right), M, Bound, hyp(K), Initial, Target, History, Hops, Used, Status) :-
 	State \== h, State \== loop, Hops < Bound, Right = [tape(In,Num)|_Rest], Num = v(_,_,_,_,_), 
	states(M, Ss), length(Ss, N), 
	length(In, L), transitions(M, N, L, State, In, Trans),
	member(t(State,In,InDir,NewState,Out,OutDir,Steps), Trans), 
	State == NewState, opposite(InDir, OutDir), % !, % can do naive cycle, so go with it ... 
	hypout(Options, "Case 2", Hops, Left, State, OutDir, InDir, Right), 
	updatetape(Left, Right, t(State,In,InDir,NewState,Out,OutDir,Steps), hyp(L), NewLeft, NewRight, _Leap), % !, 
	opposite(OutDir, NewDir), 
	append([state(NewLeft, NewState, NewDir, NewRight)], History, NewHistory), 
	Hops1 is Hops + 1, !, %% can commit to this ... 
	hyprun_real(Options, state(NewLeft, NewState, NewDir, NewRight), M, Bound, hyp(K), Initial, Target,  NewHistory, Hops1, Used, Status). 

hyprun_real(Options, state(Left, State, InDir, Right), M, Bound, hyp(K), Initial, Target, History, Hops, Used, Status) :-
 	State \== h, State \== loop, Hops <  Bound, Right = [tape(In,Num)|Rest], Num = v(_,_,_,_,_), 
	states(M, Ss), length(Ss, N), 
	length(In, I), % I > 1, 
	transitions(M, N, I, State, In, Trans),
	member(t(State,In,InDir,NewState,_Out,OutDir,_Steps), Trans), \+ (State == NewState, opposite(InDir, OutDir)), 
	InDir = l,  
	delete_trail_blanks(Left, LL), length(LL, L), length(In, I), % 
        LeftPos is 0 - (L+1), RightPos is I-1, 
	slithery_snake(state(Left, State, In), M, 1000, naive, 0, 0, [pos(0),dir(l),size(K),trigger(1000000,1000000)], LeftPos, RightPos, state(NewL,NewS,NewR), Dir, _), 
	State == NewS, opposite(InDir, Dir), 
	hypout(Options, "Reptile 1", Hops, Left, State, OutDir, InDir, Right), 
	append(In, Left, FakeLeft),
	align(FakeLeft, NewL, Left2, Left1, NewI), 
	append(In, L4, Left1), 
	append(L4, L3, NewI), 

	append(L4, [tape(L3,Num)], Left2, TempLeft), orienttape(left, TempLeft, NewLeft), 

	opposite(Dir, NewDir), 
	append([state(NewLeft, NewS, NewDir, NewR)], History, NewHistory), 
	Hops1 is Hops + 1, checkstate(Rest, NR), addused(resilient_reptiler, Used, NewUsed), 
	hyprun_real(Options, state(NewLeft, NewS, NewDir, NR), M, Bound, hyp(K), Initial, Target, NewHistory, Hops1, NewUsed, Status), !. 

hyprun_real(Options, state(Left, State, InDir, Right), M, Bound, hyp(K), Initial, Target, History, Hops, Used, Status) :-
 	State \== h, State \== loop, Hops <  Bound, Right = [tape(In,Num)|Rest], Num = v(_,_,_,_,_), 
	states(M, Ss), length(Ss, N), 
	length(In, I), 
	transitions(M, N, I, State, In, Trans),
	member(t(State,In,InDir,NewState,_Out,OutDir,_Steps), Trans), \+ (State == NewState, opposite(InDir, OutDir)), 
	InDir = r, 
	delete_trail_blanks(Rest, RR), length(RR, R), R1 is R + 1, LeftPos is 0 - (I-1), RightPos is R1, 
	splitlast(In, I1, I2), reverse(I1, NewL), 
	append(I2, Rest, NRight),
	slithery_snake(state(NewL, State, NRight), M, 1000, naive, 0, 0, [pos(0),dir(r),size(K),trigger(1000000,1000000)], LeftPos, RightPos, state(NewLeft,NewS,NewR), Dir, _), 
	NewR = [_|RealR], % Gone one to the left too many, so ignore first element of NewR ...
	State == NewS, opposite(InDir, Dir), 
	hypout(Options, "Reptile 2", Hops, Left, State, OutDir, InDir, Right), 

	append(In, Rest, FakeRight), 
	align(FakeRight, RealR, Right2, Right1, NewI), 
	append(In, R4, Right1), 
	append(R4, R3, NewI), 
	append(R4, [tape(R3,Num)], Right2, NR), 

        checkstate(Left, [NL|NewLefty]),

	append([NL], NR, NewRight), 
	opposite(Dir, NewDir), 
	append([state(NewLeft, NewState, NewDir, NewRight)], History, NewHistory), 
	Hops1 is Hops + 1, addused(resilient_reptilel, Used, NewUsed), 
	hyprun_real(Options, state(NewLefty, NewS, NewDir, NewRight), M, Bound, hyp(K), Initial, Target, NewHistory, Hops1, NewUsed, Status), !. 

hyprun_real(Options, state(Left, State, InDir, Right), M, Bound, hyp(K), Initial, Target, History, Hops, Used, Status) :-
  	State \== h, State \== loop, Hops <  Bound, Right = [tape(In,Num)|Rest], Num = v(_,_,_,_,_), 
 	states(M, Ss), length(Ss, N), 
 	length(In, I), 
 	transitions(M, N, I, State, In, Trans),
 	member(t(State,In,InDir,NewState,_Out,OutDir,_Steps), Trans), \+ (State == NewState, opposite(InDir, OutDir)), 
 	InDir = l,  
        bigswitch(Left, InDir, Right, SLeft, SRight), hypmax(large,Max), Bound1 is Max // 2, 
	hypout(Options, "Case 6", Hops, Left, State, OutDir, InDir, Right), 
 	maniacal_monkey(Options, state(SLeft, State, InDir, SRight), M, Bound1, 0, 0, [pos(0),dir(l),size(K),trigger(1000000,1000000)], I, state(NewL,NewS,_NDir,_NewR), Dir, _), 
 	State == NewS, 
 	opposite(InDir, Dir), 

	append(In, SLeft, FakeLeft),
	align(FakeLeft, NewL, Left2, Left1, NewI),
	append(In, L4, Left1),
	append(L4, L3, NewI),
	append(L4, [tape(L3,Num)], Left2, TempLeft), orienttape(left, TempLeft, NewLeft),

 	opposite(Dir, NewDir), NewRight = Rest, 
	append([state(NewLeft, NewS, NewDir, NewRight)], History, NewHistory), 
 	Hops1 is Hops + 1, 
 	addused(maniacal_monkeyrs, Used, NewUsed), 
 	hyprun_real(Options, state(NewLeft, NewS, NewDir, NewRight), M, Bound, hyp(K), Initial, Target, NewHistory, Hops1, NewUsed, Status). 
 
hyprun_real(Options, state(Left, State, InDir, Right), M, Bound, hyp(K), Initial, Target, History, Hops, Used, Status) :-
  	State \== h, State \== loop, Hops <  Bound, Right = [tape(In,Num)|Rest], Num = v(_,_,_,_,_), 
 	states(M, Ss), length(Ss, N), 
 	length(In, I), 
 	transitions(M, N, I, State, In, Trans),
 	member(t(State,In,InDir,NewState,_Out,OutDir,_Steps), Trans), \+ (State == NewState, opposite(InDir, OutDir)), 
	InDir = r,   
        bigswitch(Left, InDir, Right, SLeft, SRight),  
	hypout(Options, "Case 7", Hops, Left, State, OutDir, InDir, Right), 
 	TPos is 0 - I, hypmax(large,Max), Bound1 is Max // 2, 
 	maniacal_monkey(Options, state(SLeft, State, InDir, SRight), M, Bound1, 0, 0, [pos(0),dir(l),size(K),trigger(1000000,1000000)], TPos, state(_NewL,NewS,_NDir,NewR), Dir, _), 
 	State == NewS, opposite(InDir, Dir), % Check that we end up in the right state 

	NewR = [_|RealR], 
	append(In, Rest, FakeRight), 
	append(FakeRight, RealR, Right2, Right1, NewI),
	append(In, R4, Right1),
	append(R4, R3, NewI),
	append(R4, [tape(R3,Num)], Right2, NR),
	checkstate(Left, [NL|NewLeft]),
	append([NL], NR, NewRight), 

 	opposite(Dir, NewDir), 
	append([state(NewLeft, NewS, NewDir, NewRight)], History, NewHistory), 
 	Hops1 is Hops + 1, addused(maniacal_monkeyls, Used, NewUsed), 
 	hyprun_real(Options, state(NewLeft, NewS, NewDir, NewRight), M, Bound, hyp(K), Initial, Target, NewHistory, Hops1, NewUsed, Status). 
 
hyprun_real(Options, state(Left, State, InDir, Right), M, Bound, hyp(K), Initial, Target, History, Hops, Used, Status) :-
    	State \== h, State \== loop, Hops <  Bound, Right = [tape(In,Num)|_Rest], Num = v(_,_,_,_,_), 
    	states(M, Ss), length(Ss, N), 
    	length(In, L), transitions(M, N, L, State, In, Trans),
    	member(t(State,In,InDir,NewState,_Out,OutDir,_Steps), Trans), \+ (State == NewState, opposite(InDir, OutDir)), 
	numswitch(NSwitch), switchmax(SMax), NSwitch < SMax, retractall(numswitch(_)), NS is NSwitch + 1, assert(numswitch(NS)), 
        bigswitch(Left, InDir, Right, NewLeft, NewRight),  

	hypout(Options, "Case 3", Hops, Left, State, OutDir, InDir, Right), 
 	Hops1 is Hops + 1, 
	append([state(NewLeft, State, InDir, NewRight)], History, NewHistory), 
 	addused(bigswitch, Used, NewUsed), 
    	hyprun_real(Options, state(NewLeft, State, InDir, NewRight), M, Bound, hyp(K), Initial, Target, NewHistory, Hops1, NewUsed, Status), !. 
 
hyprun_real(Options, state(Left, State, InDir, Right), M, Bound, hyp(K), Initial, Target, History, Hops, Used, Status) :-
  	State \== h, State \== loop, Hops <  Bound, Right = [tape(In,Num)|Rest], Num = v(_,_,_,_,_), 
 	states(M, Ss), length(Ss, N), 
 	length(In, I), 
 	transitions(M, N, I, State, In, Trans),
 	member(t(State,In,InDir,NewState,_Out,OutDir,_Steps), Trans), \+ (State == NewState, opposite(InDir, OutDir)), 
	\+ member(maniacal_monkeyrr, Used), %% Don't do this twice! 
 	InDir = l,  
	hypout(Options, "Case 8", Hops, Left, State, OutDir, InDir, Right), 
        zerocase(Initial, InitZero),
 	zerocase(Target, TargetZero), hypmax(large,Max), Bound1 is Max // 2, 
 	hyprun_real(Options, InitZero, M, Bound1, hyp(K), InitZero, TargetZero, [], 0, [], Status1), Status1 = target(_,_), 
 	nonzerocase(state(Left, State, InDir, Right), InitNonZero), 
 	nonzerocase(Target, TargetNonZero), 
 	maniacal_monkey(Options, InitNonZero, M, Bound1, 0, 0, [pos(0),dir(l),size(K),trigger(1000000,1000000)], I, state(NewL,NewS,_NDir,NewR), Dir, _), 
  	State == NewS, % format("State same~n", []), 
 	opposite(InDir, Dir), % format("Direction correct~n", []), % Check that we end up in the right state 

 	InitNonZero = state(LeftNZ, State, _, _RightNZ),

	append(In, LeftNZ, FakeLeft),
	align(FakeLeft, NewL, Left2, Left1, NewI),
	append(In, L4, Left1),
	append(L4, L3, NewI),
	append(L4, [tape(L3,Num)], Left2, TempLeft), orienttape(left, TempLeft, NewLeft),

 	opposite(Dir, NewDir), append(In, Rest, NewRight), 
	append([state(NewLeft, NewState, NewDir, NewRight)], History, NewHistory), 
 	Hops1 is Hops + 1, 
 	addused(maniacal_monkeyrr, Used, NewUsed), 
 	hyprun_real(Options, state(NewLeft, NewS, NewDir, NewRight), M, Bound, hyp(K), Initial, TargetNonZero, NewHistory, Hops1, NewUsed, Status). 
 
hyprun_real(Options, state(Left, State, InDir, Right), M, Bound, hyp(K), Initial, Target, History, Hops, Used, Status) :-
  	State \== h, State \== loop, Hops <  Bound, Right = [tape(In,Num)|Rest], Num = v(_,_,_,_,_),
 	states(M, Ss), length(Ss, N), 
 	length(In, I), 
 	transitions(M, N, I, State, In, Trans),
 	member(t(State,In,InDir,NewState,_Out,OutDir,_Steps), Trans), \+ (State == NewState, opposite(InDir, OutDir)), 
	\+ member(maniacal_monkeylr, Used), %% Don't do this twice! 
 	InDir = r,  
        zerocase(Initial, InitZero),
 	zerocase(Target, TargetZero), hypmax(large,Max), Bound1 is Max // 2, 
	hypout(Options, "Case 9", Hops, Left, State, OutDir, InDir, Right), 
 	hyprun_real(Options, InitZero, M, Bound1, hyp(K), InitZero, TargetZero, [], 0, [], Status1), Status1 = target(_,_), 
  	nonzerocase(state(Left, State, InDir, Rest), state(NZL, State, InDir, NZR)), nonzerocase1(left, [tape(In,Num)], NZI), 
 	NZI = [First|RestNZI], append([First], NZR, RestR), 
 
	append(RestNZI, NZL, RestL), 
  	nonzerocase(Target, TargetNonZero), 

  	TPos is 0 - I, 
	hypout([], "Monkey R", Hops, RestL, State, OutDir, InDir, RestR), 
 	maniacal_monkey(Options, state(RestL, State, InDir, RestR), M, Bound1, 0, 0, [pos(0),dir(l),size(K),trigger(1000000,1000000)], TPos, state(NewL,NewS,_NDir, NewR), Dir, _), 
  	State == NewS, opposite(InDir, Dir), % Check that we end up in the right state 

	NewR = [_|RealR], 
	append(In, Rest, FakeRight), 
	append(FakeRight, RealR, Right2, Right1, NewI),
	append(In, R4, Right1),
	append(R4, R3, NewI),
	append(R4, [tape(R3,Num)], Right2, NR),
	checkstate(Left, [NL|NewLeft]),
	append([NL], NR, NewRight), 

	opposite(Dir, NewDir), 
	append([state(NewLeft, NewState, NewDir, NewRight)], History, NewHistory), 
 	Hops1 is Hops + 1, addused(maniacal_monkeylr, Used, NewUsed), 
 	hyprun_real(Options, state(NewLeft, NewS, NewDir, NewRight), M, Bound, hyp(K), state(NZL, State, InDir, NZR), TargetNonZero, NewHistory, Hops1, NewUsed, Status). 

constancy_condition(_V0, _M, _M0, K) :- K = 1.
constancy_condition(V0, M, M0, K) :- 
	K > 1, 
	Temp1 is (M * V0 + M0) mod K,
	Temp2 is V0 mod K,
	Temp1 = Temp2. 

expression(_V, 0, T2, T2). 
expression(V, 1, 0, V). 
expression(V, 1, T2, Exp) :- T2 \== 0, Exp = V + T2. 
expression(V, T1, 0, Exp) :- T1 \== 1, Exp = T1*V. 
expression(V, T1, T2, Exp) :- T1 \== 1, T2 \== 0, Exp = T1*V + T2. 


hypout(Options, _String, _Hops, _Left, _State, _Dir1, _Dir2, _Right) :-
	\+ member(trace, Options). 
hypout(Options, String, Hops, Left, State, Dir1, Dir2, Right) :-
	member(trace, Options),
	hypprettyprint(String, Hops, Left, State, Dir1, Dir2, Right).

hypprettyprint(String, Hops, Left, State, Dir1, Dir2, Right) :-
	reverse(Left, PL), 
	format("(~d) ~s: ", [Hops,String]), pprint(PL), format("{~k ~a ~a}", [State, Dir1, Dir2]), pprint(Right), nl, 
	true. 
 
align(L1, L2, Right2, Right1, Right3) :- 
	normalise(L1, Rt), normalise(L2, Nt), 
	sameandnew(Rt, Nt, Right2, Right1, Right3), !. 
 
addused(I, Used, Used) :- member(I, Used).
addused(I, Used, [I|Used]) :- \+ member(I, Used).
 
maxbound(B, B) :- B =< 1000, !. 
maxbound(B, 1000) :- B > 1000, !. 
  
bigswitch(Left, l, Right, Left, NewRight) :-
   	!, Right = [tape(In, Num)|Rest],  
    	append(In, Rest1, Rest), % Rest commences with In, so ... 
     	append(In, [tape(In, Num)], Rest1, NewRight).
 
bigswitch(Left, r, Right, NewLeft, NewRight) :-
    	!, Right = [tape(In, Num)|Rest],  
    	reverse(In, InL), 
    	append(InL, Rest1, Left), % Left commences with InL, so ...
     	append(ToL, NewR, In), length(NewR, 1), reverse(ToL, ToLeft), 
    	append(ToLeft, [tape(In, Num)], Rest1, NewLeft), append(NewR, Rest, NewRight). 
  
smallswitch(Left, l, Right, Left, NewRight) :-
   	!, Right = [tape(In, Num)|Rest],  
    	append(In, Rest1, Rest), % Rest commences with In, so ... 
  	append(I1, I2, In), append(I1, [tape(In,Num)], I2, Temp), append(Temp, Rest1, NewRight). 
  
smallswitch(Left, r, Right, NewLeft, NewRight) :-
    	!, Right = [tape(In, Num)|Rest],  
    	reverse(In, InL), 
    	append(InL, Rest1, Left), % Left commences with InL, so ...
  	append(ToL, NewR, In), length(NewR, L), L > 0,  reverse(ToL, ToLeft), 
    	append(ToLeft, [tape(In, Num)], Rest1, NewLeft), append(NewR, Rest, NewRight). 
  
divide(In, Rest, SoFar, Mult, Other) :-
  	append(In, Rest1, Rest),
  	append(In, SoFar, NewSoFar), 
  	divide(In, Rest1, NewSoFar, Mult, Other).
  
divide(In, Rest, SoFar, SoFar, Rest) :-
 	\+ append(In, _Rest1, Rest).
  
makesame(T1, T2, T1, T2) :-
  	length(T1,N), length(T2,N),!.
makesame(T1, T2, NT1, T2) :-
  	length(T1, N1), length(T2, N2), N2 > N1, !, Num is N2 - N1, 
  	blanks(Num,B),
  	append(T1, B, NT1).
makesame(T1, T2, T1, NT2) :-
  	length(T1, N1), length(T2, N2), N1 > N2, !, Num is N1 - N2, 
  	blanks(Num,B),
  	append(T2, B, NT2).
  
% Old and New have common suffix Common, and different prefices Diff1 and Diff2 respectively.
sameandnew(Old, New, Common, Diff1, Diff2) :-
  	reverse(Old, O), reverse(New, N),
  	agree(O, N, [], Comm, D1, D2),
  	reverse(Comm, Common),
  	reverse(D1, Diff1),
  	reverse(D2, Diff2).
  
% agree(Tape1, Tape2, [], Common, Rest1, Rest2)
% Tape1 and Tape2 have the common prefix Common and different suffices Rest1 and Rest2 respectively
agree([], Suffix, SoFar, SoFar, [], Suffix).
agree(Suffix, [], SoFar, SoFar, Suffix, []).
agree([T1|RestT1], [T2|RestT2], SoFar, SoFar, [T1|RestT1], [T2|RestT2]) :-
	T1 \== T2. 
agree([T1|RestT1], [T2|RestT2], SoFar, Common, Rest1, Rest2) :-
  	T1 == T2, append(SoFar, [T1], NewSoFar),
  	agree(RestT1, RestT2, NewSoFar, Common, Rest1, Rest2). 
  
sametape(N,T1,T2) :- length(T1, Temp), N >= Temp, delete_trail_blanks(T1, T), delete_trail_blanks(T2, T), !.
sametape(N,T1,T2) :- length(T1, Temp), N < Temp, 
 	delete_trail_blanks(T1, T3), delete_trail_blanks(T2, T4),
 	append(P1, _, T3), length(P1, N), append(P1, _, T4), !.
 
blank(naive, [], [0]) :- !.
blank(naive, [0], [0]) :- !.
blank(comp, [], [tape(0,_)]) :- !. 
blank(comp, [tape(0,_)], [tape(0,_)]) :- !. 
blank(comp(_), [], [tape(0,_)]) :- !. 
blank(comp(_), [tape(0,_)], [tape(0,_)]) :- !. 
blank(adapt, [], [tape(0,_)]) :- !. 
blank(adapt, [tape(0,_)], [tape(0,_)]) :- !. 
 
zerocase(state(Left, State, InDir, Right), state(ZL, State, InDir, ZR)) :-
 	zerocase1(Left, ZL), 
 	zerocase1(Right, ZR).
 
zerocase1([], []).
zerocase1([I|Rest], [I|Z]) :- is_input(I), zerocase1(Rest, Z).
zerocase1([tape(_I,_X)|Rest], Z) :- zerocase1(Rest, Z).
 
nonzerocase(state(Left, State, InDir, Right), state(ZL, State, InDir, ZR)) :-
	nonzerocase1(left, Left, ZL), 
 	nonzerocase1(right, Right, ZR).
 
nonzerocase1(_, [], []).
nonzerocase1(Dir, [1|Rest], [1|Z]) :- nonzerocase1(Dir, Rest, Z).
nonzerocase1(Dir, [0|Rest], [0|Z]) :- nonzerocase1(Dir, Rest, Z).
nonzerocase1(Dir, [tape(I,X)|Rest], New) :-
	nonzerocase1(Dir, Rest, NZ), 
	orient(Dir, I, NewI), 
 	append(NewI, [tape(I,X)], NZ, New). 
 
updatehops(Hops, Leap, Steps, Hops1) :-
	integer(Steps), integer(Leap), Hops1 is Hops + Leap * Steps. 
updatehops(Hops, Leap, Steps, Hops1) :-
 	(var(Steps); (integer(Steps), var(Leap))), !, Hops1 is Hops + 1. 

% A hacky piece, and one that is called a lot. A prime candidate for optimisation.   
updateinputs(Inputs, _In, _Output, Dir, Ones, Hops, Leap, Type, NewLeft, NewState, NewRight, NewInputs) :-
 	\+ member(onescount(_Max, _HopsMax), Inputs),
 	\+ member(status(_Status), Inputs), 
 	\+ member(history(_History), Inputs), 
 	\+ member(now(_Now), Inputs), !, 
 	updatepos(Inputs, Dir, Leap, NI), 
 	member(trigger(Trigger,Jump), NI), delete(NI, trigger(Trigger,Jump), NIs), 
	member(pos(Pos), NIs), watchlist(NIs, Watch), 
	checkhops(Watch, Trigger, Jump, Hops, Ones, Pos, Type, NewLeft, NewState, NewRight, NewTrigger, NewJump), 
	NewInputs = [trigger(NewTrigger,NewJump)|NIs], !. 

updateinputs(Inputs, In, Output, Dir, Ones, Hops, Leap, Type, NewLeft, NewState, NewRight, NewInputs) :-
 	\+ member(onescount(_Max, _HopsMax), Inputs),
 	\+ member(status(_Status), Inputs), 
	member(history(History), Inputs), 
 	member(now(Now), Inputs), !, append([Now], History, NewHistory), 
	delete(Inputs, history(History), Inps),
 	delete(Inps, now(Now), Is), 
 	updateinputs(Is, In, Output, Dir, Ones, Hops, Leap, Type, NewLeft, NewState, NewRight, NewI),!, 
 	append(NewI, [now(state(NewLeft, NewState, NewRight)),history(NewHistory)], NewInputs). 

updateinputs(Inputs, In, Output, Dir, Ones, Hops, Leap, Type, NewLeft, NewState, NewRight, NewInputs) :-
 	member(onescount(Max, HopsMax), Inputs),
	member(status(Status), Inputs), !, 
 	delete(Inputs, onescount(Max, HopsMax), Inps),
 	delete(Inps, status(Status), Is), 
 	updatecount(Max, HopsMax, Ones, Hops, NewMax, NewHopsMax), 
 	updatestatus(In, Output, Status, NewStatus), 
        !, 
 	updateinputs(Is, In, Output, Dir, Ones, Hops, Leap, Type, NewLeft, NewState, NewRight, NewI),!, 
 	append(NewI, [onescount(NewMax,NewHopsMax),status(NewStatus)], NewInputs). 
 
updatepos(Inputs, Dir, Leap, [pos(NewPos)|Ins]) :-
 	member(pos(Pos), Inputs),
 	delete(Inputs, pos(Pos), Ins),
 	setpos(Pos, Dir, Leap, NewPos),!. 

setpos(Pos, l, Leap, NewPos) :- NewPos is Pos - Leap, !. 
setpos(Pos, r, Leap, NewPos) :- NewPos is Pos + Leap, !. 
 
updatestatus(In, In, S, S) :- !.
updatestatus(0,X, increasing, increasing) :- is_input(X), X \== 0, !. 
updatestatus(X,0, decreasing, decreasing) :- is_input(X), X \== 0, !. 
updatestatus(0,X, decreasing, increasing) :- is_input(X), X \== 0, !. 
updatestatus(X,0, increasing, decreasing) :- is_input(X), X \== 0, !. 
 
updatecount(Max, HopsMax, Ones, _Hops, Max, HopsMax) :-
	Max >= Ones, !. 
updatecount(Max, _HopsMax, Ones, Hops, Ones, Hops) :-
 	Max < Ones, !.
 
convert(State, Left, Right, Type, Inputs, Ones, Hops, Outputs) :-
	member(onescount(Max, HopsMax), Inputs),
	!,
	delete(Inputs, onescount(Max, HopsMax), Is),
	convert(State, Left, Right, Type, Is, Ones, Hops, Os),
	append([max(Max),hopsmax(HopsMax)], Os, Outputs).

convert(_State, Left, Right, _Type, Inputs, _Ones, _Hops, Outputs) :-
	\+ member(onescount(_Max, _HopsMax), Inputs),
	append([left(Left),right(Right)], Inputs, Outputs).

loopcheck(Left, State, Right, Type, _M,  Inputs) :- 
	member(Type, [naive,comp]), 
	member(history(History), Inputs), 
	member(state(Left, State, Right), History). 

trigger(1000000).

%% Code for "compiling" monster machines, such as the recent Ligocki 3-state 3-symbol busy beaver candidate. 

record(FileName, State, Left, Right, Hops) :-
	pretprint(State, Left, Right, Hops), 
	tell(FileName), 
	pretprint(State, Left, Right, Hops), 
	told.

pretprint(State, Left, Right, Hops) :-
	reverse(Left, PL), 
	pprint(PL), format("{~k}",[State]), pprint(Right), 
	countones(Left, Right, Ones),
	format("     Hops: ~d Ones: ~d~n", [Hops,Ones]).

next([I|R], I, R). 
next([], 0, []). 
nextk([I|R], _K, I, R). 
nextk([], K, tape(Init,1), []) :- number(0, K, Init). 

% compile("logicki33", 2, [t(a,0,1,r,b),t(a,1,2,r,c),t(a,2,1,l,a),t(b,0,2,l,a),t(b,1,1,r,b),t(b,2,1,r,h),t(c,0,2,r,b),t(c,1,2,r,a),t(c,2,1,l,c)]).
compile(Name, K, M) :-
	string2term(Name, Atom), 
	append(Name, ".pl", FileNameString),
	string2term(FileNameString, File),
	append(Name, "-out", OutFileNameString),
	string2term(OutFileNameString, OutFile),
	tell(File),
	machine(M, comp(K), Machine), 
	number([0], K, Init), 
	format("% Here be dragons ... ~n", []), 
	format("% :- ensure_loaded\(standalone\).~n", []), 
	format("go_~k :- ~k([],a,tape\(", [Atom,Atom]), display(Init), format(",1\),l,[],0).~n", []), 
	specialise(Atom, K, Machine, OutFile), 
	told. 

specialise(_, _, [], _).
specialise(Name, K, [Trans|Rest], File) :-
	specialise_trans(Name, K, Trans, File),
	specialise(Name, K, Rest, File).

% Need to add cases which deal with the same state and same direction for speed ups ... 
specialise_trans(Name, K, t(State,In,InDir,NewState,Out,OutDir,Steps), _File) :-
	NewState \== h,
	format("~k\(L,~k,tape\(", [Name,State]),display(In), format(",N\),~k,R,H\) :- ", [InDir]), 
	opposite(OutDir,NewDir), 
	format(" update\(L,R,~k,~k,", [State,NewState]), display(In), format(",",[]), display(Out), format(",N,~d,~k,~k,NL,NR,NI,", [K,InDir,OutDir]), 
	hopcalc(State, NewState, InDir,OutDir, Steps), 
	format(" !, ~k\(NL,~k,NI,~k,NR,H1\).~n", [Name,NewState,NewDir]).

specialise_trans(Name, K, t(State,In,InDir,NewState,Out,OutDir,Steps), File) :-
	NewState == h,
	format("~k\(L,~k,tape\(", [Name,State]),display(In), format(",N\),~k,R,H\) :- ", [InDir]), 
	format(" update\(L,R,~k,~k,", [State,NewState]), display(In), format(",",[]), display(Out), format(",N,~d,~k,~k,NL,NR,NI,", [K,InDir,OutDir]), 
	hopcalc(State, NewState, InDir,OutDir, Steps), 
	format(" record\(~k,h,NL,[NI|NR],H1\).~n", [File]).

directionstring(r, "R", "L").
directionstring(l, "L", "R").
	
hopcalc(State, NewState, InDir,OutDir, Steps) :-
	State == NewState, opposite(InDir,OutDir), 
	format("Leap\), H1 is H+Leap*~d,", [Steps]).
hopcalc(State, NewState, InDir,OutDir, Steps) :-
	\+ (State == NewState, opposite(InDir,OutDir)), 
	format("_\), H1 is H+~d,", [Steps]).

addtape(I, [], [I]).
addtape(tape(I1,N1), [tape(I2,N2)|Rest], NewTape) :-
	I1 \== I2, append([tape(I1,N1)],[tape(I2,N2)|Rest], NewTape). 
addtape(tape(I1,N1), [tape(I2,N2)|Rest], [tape(I2,N)|Rest]) :-
	I1 == I2, N is N1+N2.

update(L, R, _State, _NewState, In, Out, Num, K, InDir, OutDir, NewL, NewR, NewI,1) :-
	Num > 1, InDir = l, OutDir = l, !, N1 is Num - 1, 
	addtape(tape(In,N1), R, Temp), addtape(tape(Out,1),Temp, NewR),
	nextk(L, K, NewI, NewL). 

update(L, R, _State, _NewState, _In, Out, Num, K, InDir, OutDir, NewL, NewR, NewI,1) :-
	Num = 1, InDir = l, OutDir = l, !,  
	addtape(tape(Out,1), R, NewR),
	nextk(L, K, NewI, NewL). 

update(L, R, State, NewState, In, Out, Num, _K, InDir, OutDir, NewL, NewR, NewI,1) :-
	Num > 1, InDir = l, OutDir = r, State \== NewState, !, N1 is Num - 1,  
	addtape(tape(Out,1),L, NewL), NewR = R, NewI = tape(In,N1), 
	true.  

update(L, R, State, NewState, _In, Out, Num, K, InDir, OutDir, NewL, NewR, NewI,1) :-
	Num = 1, InDir = l, OutDir = r, State \== NewState, !,  
	addtape(tape(Out,1), L, NewL), 
	nextk(R, K, NewI, NewR), 
	true. 

update(L, R, State, NewState, _In, Out, Num, K, InDir, OutDir, NewL, NewR, NewI,Num) :-
	InDir = l, OutDir = r, State == NewState, !, 
	addtape(tape(Out,Num),L, NewL), nextk(R, K, NewI, NewR). 

update(L, R, _State, _NewState, In, Out, Num, K, InDir, OutDir, NewL, NewR, NewI,1) :-
	Num > 1, InDir = r, OutDir = r, !, N1 is Num - 1, 
	addtape(tape(In,N1), L, Temp), addtape(tape(Out,1),Temp, NewL), 
	nextk(R, K, NewI, NewR).

update(L, R, _State, _NewState, _In, Out, Num, K, InDir, OutDir, NewL, NewR, NewI,1) :-
	Num = 1, InDir = r, OutDir = r, !, 
	addtape(tape(Out,1), L, NewL),
	nextk(R, K, NewI, NewR). 

update(L, R, State, NewState, In, Out, Num, _K, InDir, OutDir, NewL, NewR, NewI,1) :-
	Num > 1, InDir = r, OutDir = l, State \== NewState, !, N1 is Num - 1,
	addtape(tape(Out,1),R, NewR), NewL = L, NewI = tape(In,N1). 

update(L, R, State, NewState, _In, Out, Num, K, InDir, OutDir, NewL, NewR, NewI,1) :-
	Num = 1, InDir = r, OutDir = l, State \== NewState, !, 
	addtape(tape(Out,1), R, NewR), 
	nextk(L, K, NewI, NewL).

update(L, R, State, NewState, _In, Out, Num, K, InDir, OutDir, NewL, NewR, NewI,Num) :-
	InDir = r, OutDir = l, State == NewState, !, 
	addtape(tape(Out,Num), R, NewR),
	nextk(L, K, NewI, NewL).