%%% -*- prolog -*-

noah([],[]).
noah([A,B|X],[[A,B]|Y]) :- noah(X,Y).

noah_v2(X,Y) :- hack_hunks(X,Y,2).

noah_v3([],[]).
noah_v3(X,Y) :- Y=[[_,_]|_], hack_hunks(X,Y).

%% define hack_hunks/2 in terms of hack_hunks/3 taking extra Len arg
hack_hunks_v1(X,Y) :- hack_hunks_v1(X,Y,_). 

hack_hunks_v1([],[],_).
hack_hunks_v1([E|X],[[E|Y]|Z],Len) :-
	append(Y,XmY,X),
	length([E|Y],Len),
	hack_hunks_v1(XmY,Z,Len).

%% define directly, by requiring uniform hunk length
hack_hunks([],[]).
hack_hunks([X1|X],[[X1|X]]).	% Not: "hack_hunks(X,[X])." because hack_hunks([],[[]]) is wrong
hack_hunks([X1|X],[[X1|A],B|Y]) :-
	length_leq(A,X),	% trick, prevent nonterminating search of longer and longer A
	length_eq([X1|A],B),	% first two hunks must have same length
	append(A,XmA,X),	% "X minus A" means X with prefix A chopped off
	hack_hunks(XmA,[B|Y]).

%% utilities for enforcing list length constraints
length_eq([],[]).
length_eq([_|X],[_|Y]) :- length_eq(X,Y).

length_leq_v1([],_).
length_leq_v1([_|X],[_|Y]) :- length_leq_v1(X,Y).

length_leq(X,Y) :- length_eq(Z,Y), append(X,_,Z).

%% permutation
perm([],[]).
perm([E|X],Y) :-
	length_eq([E|X],Y),	% trick to prevent uncontrolled search of longer and longer U & Y
	append(U,[E|V],Y), append(U,V,W), perm(X,W).

%% world's worst sorting algorithm!
sorted([]).
sorted([_]).
sorted([A,B|X]) :- A<B, sorted([B|X]).

worst_sort(X,Y) :- perm(X,Y), sorted(Y).

%%
one_move([x,x,o|P], [o,o,x|P]).
one_move([o,x,x|P], [x,o,o|P]).
one_move([S|P1],[S|P2]) :- one_move(P1,P2).

%% move_seq(Ps) :- all_eq_len(Ps), move_seq_aux(Ps).
move_seq(Ps) :- move_seq_aux(Ps).
move_seq_aux([_]).
move_seq_aux([P1,P2|Ps]) :- move_seq_aux([P2|Ps]), one_move(P1,P2).

%% all_eq_len([]).
%% all_eq_len([_]).
%% all_eq_len([X1,X2|Xs]) :- length_eq(X1,X2), all_eq_len([X2|Xs]).

all_eq_len([]).
all_eq_len([_]).
all_eq_len([X1,X2]) :- length_eq(X1,X2).
all_eq_len([X1,X2,X3|Xs]) :- all_eq_len([X2,X3|Xs]), length_eq(X1,X2).

%% invoke with
%%   make_puzzle([o,o,o,o,x,o,o,o,o,o,o,o,o,o,o,o,o,o,o,o,o,o,o],10,S).

make_puzzle(Final, Nmoves, Start) :-
	length(Seq,Nmoves),
	append(_,[Final],Seq),
	move_seq([Start|Seq]).