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

codegen(Initial,Final,Instrs) :-
        preprocess(Initial,_,Vali),
        preprocess(Final,Final1,Valf),
        \+ (member(X,Valf), \+ member(X,Vali)),
        once((length(Instrs,_),
	      effectuate(Instrs,Initial,Final1))).

preprocess([],[],[]) .
preprocess([X|IR],[Y|FR],Symb) :-
        ( X = (*) ->
            preprocess(IR,FR,Symb)
        ;
	    Y = X,
            Symb = [X|RS],
            preprocess(IR,FR,RS)
        ).

effectuate([],Final,Final).
effectuate([Instr|RI],Initial,Final) :-
	apply_instr(Instr,Initial,Initial2),
	effectuate(RI,Initial2,Final).

apply_instr(swap(I,J),Initial,Final) :-
	append(BeforeI,[XI|AfterI],Initial),
	append(BeforeJ,[XJ|AfterJ],AfterI),
	append(BeforeJ,[XI|AfterJ],NewAfterI),
	append(BeforeI,[XJ|NewAfterI],Final),
	length(BeforeI,I1),
	length(BeforeJ,J1),
	I is I1 + 1,
	J is I1 + J1 + 2.
apply_instr(move(From),Initial,Final) :-
	append(Front,[X|Back],Initial),
	( Back == [] ->
	    Initial = [_|Rest],
	    Final = [X|Rest]
	;
	    Back = [_|Back1],
	    append(Front,[X,X|Back1],Final)
	),
	length(Front,I),
	From is I + 1.