:- use_module(library(lists),[append/3, flatten/2]).

antwerpen(N,Commands) :-
	exchange(N,b,c,a,Cbc),
	exchange(N,a,c,b,Cac),
	append(Cbc,Cac,Commands).

exchange(N,PegB,PegC,PegA,Commands) :-
	make_tower(N,PegA,PegB,PegC,C1),
	invert_commandsequence(C1,PegB,PegC,[],C2),
	append(C1,C2,Commands).

make_tower(1,PegA,PegB,PegC,Commands) :- !,
	Commands = [(PegB->PegA),(PegC->PegA)].
make_tower(N,PegA,PegB,PegC,Commands) :-
	N1 is N - 1,
	make_tower(N1,PegB,PegA,PegC,C1),
	C2 = [(PegC->PegA)],
	move_tower(N1,PegB,PegC,PegA,C3),
	C4 = [(PegB->PegA)],
	move_tower(N1,PegC,PegA,PegB,C5),
	flatten([C1,C2,C3,C4,C5],Commands).

move_tower(1,PegA,PegB,PegC,Commands) :- !,
	Commands = [(PegA->PegC),(PegA->PegC),
		    (PegA->PegB),(PegC->PegB),(PegC->PegB)].
move_tower(N,PegA,PegB,PegC,Commands) :-
	N1 is N - 1,
	move_tower(N1,PegA,PegB,PegC,C1),
	C2 = [(PegA->PegC),(PegA->PegC)],
	move_tower(N1,PegB,PegC,PegA,C3),
	C4 = [(PegA->PegB)],
	move_tower(N1,PegC,PegA,PegB,C5),
	C6 = [(PegC->PegB),(PegC->PegB)],
	move_tower(N1,PegA,PegB,PegC,C7),
	flatten([C1,C2,C3,C4,C5,C6,C7],Commands).

invert_commandsequence([],_,_,In,In).
invert_commandsequence([(A->B)|R],X,Y,In,Out) :-
	switch(A,X,Y,A1), switch(B,X,Y,B1),
	invert_commandsequence(R,X,Y,[(B1->A1)|In],Out).

switch(A,A,B,B) :- !.
switch(A,B,A,B) :- !.
switch(A,_,_,A).