/* Busca Bidirecional em Profundidade x Profundidade */

:- op(35, xf,  e_a_meta     ).
:- op(35, xfx, atinge_a_meta).
:- op(35, xfx, transforma   ).
:- op(30, xfx, em           ).
:- op(35, xfx, nao_produz_circulos_em).
:- dynamic(countinicio/1).
:- dynamic(countmeta/1).
:- dynamic(tempo/1).

/********************************************************************/
/********************* Predicado Principais *************************/

resolva :- init_dynamic, 
	estado_inicial( Inicio ),  Meta e_a_meta, 
	busca_bidirectional( [[ r(raiz, Inicio) ]], [[r(meta, Meta)]], SolucaoDeInicio, SolucaoDeMeta ),
	imprimatempo,
	imprima( SolucaoDeInicio ), nl, nl,
	imprima( SolucaoDeMeta ), nl. 

busca_bidirectional( LLSolDeInicio, LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ) :-
	procura( LLSolDeInicio, LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ).

busca_bidirectional( [HeadIni|TailIni], [HeadMeta|TailMeta], SolucaoDeInicio, SolucaoDeMeta) :-
	ache_todos( ExtensaoAteUmFilhoIni, estende_ate_filho( HeadIni, ExtensaoAteUmFilhoIni ), ExtensoesIni ),
	soma_ini(ExtensoesIni),
	ap( ExtensoesIni, TailIni, ListaEstendidaIni ),
	ache_todos( ExtensaoAteUmFilhoMeta, estende_ate_filho( HeadMeta, ExtensaoAteUmFilhoMeta ), ExtensoesMeta ),
	soma_meta(ExtensoesMeta),
	ap( ExtensoesMeta, TailMeta, ListaEstendidaMeta ),
	busca_bidirectional( ListaEstendidaIni, ListaEstendidaMeta, SolucaoDeInicio, SolucaoDeMeta ).

estende_ate_filho( [r(Ramo,N)|Trajetoria], [r(Op,Filho), r(Ramo,N)|Trajetoria] ) :-
	operacao( Op ) transforma N em Filho,
	not Filho nao_produz_circulos_em Trajetoria.

Estado nao_produz_circulos_em Trajetoria :-
	membro( r( Operacao, Estado ), Trajetoria ).

/* En esta Linea se debe hacer comparacion Bidirectional */

r( RamoIni, ML ) atinge_a_meta r( RamoMeta, MP ):- 
	ML = MP.



/* nueva comparacion */

procura( LLSolDeInicio, LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ) :-
	procura2( LLSolDeInicio, LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ).

procura( [_|LTailSolIni] , LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ) :-
	procura( LTailSolIni, LLSolDeMeta, SolucaoDeInicio, SolucaoDeMeta ).

procura2( [[ HeadIni|TailIni ] | _], [[ HeadMeta|TailMeta ] | _], SolucaoDeInicio, SolucaoDeMeta ) :-
	HeadIni atinge_a_meta HeadMeta,
	SolucaoDeInicio = [ HeadIni  | TailIni  ],
	SolucaoDeMeta   = [ HeadMeta | TailMeta ], !.

procura2( LLSolDeInicio, [_|LTailMeta], SolucaoDeInicio, SolucaoDeMeta ) :-
	procura2( LLSolDeInicio , LTailMeta, SolucaoDeInicio, SolucaoDeMeta ).
	
/*********************************************************************/
/*********************** Base de Conhecimentos ***********************/

operacao(esq) 	transforma [A,*,C,D,E,F,H,I,J] em [*,A,C,D,E,F,H,I,J].
operacao(esq) 	transforma [A,B,C,D,*,F,H,I,J] em [A,B,C,*,D,F,H,I,J].
operacao(esq) 	transforma [A,B,C,D,E,F,H,*,J] em [A,B,C,D,E,F,*,H,J].
operacao(esq) 	transforma [A,B,*,D,E,F,H,I,J] em [A,*,B,D,E,F,H,I,J].
operacao(esq) 	transforma [A,B,C,D,E,*,H,I,J] em [A,B,C,D,*,E,H,I,J].
operacao(esq) 	transforma [A,B,C,D,E,F,H,I,*] em [A,B,C,D,E,F,H,*,I].

operacao(cima) 	transforma [A,B,C,*,E,F,H,I,J] em [*,B,C,A,E,F,H,I,J].
operacao(cima) 	transforma [A,B,C,D,*,F,H,I,J] em [A,*,C,D,B,F,H,I,J].
operacao(cima) 	transforma [A,B,C,D,E,*,H,I,J] em [A,B,*,D,E,C,H,I,J].
operacao(cima) 	transforma [A,B,C,D,E,F,*,I,J] em [A,B,C,*,E,F,D,I,J].
operacao(cima) 	transforma [A,B,C,D,E,F,H,*,J] em [A,B,C,D,*,F,H,E,J].
operacao(cima) 	transforma [A,B,C,D,E,F,H,I,*] em [A,B,C,D,E,*,H,I,F].

operacao(dir) 	transforma [A,*,C,D,E,F,H,I,J] em [A,C,*,D,E,F,H,I,J].
operacao(dir) 	transforma [A,B,C,D,*,F,H,I,J] em [A,B,C,D,F,*,H,I,J].
operacao(dir) 	transforma [A,B,C,D,E,F,H,*,J] em [A,B,C,D,E,F,H,J,*].
operacao(dir) 	transforma [*,B,C,D,E,F,H,I,J] em [B,*,C,D,E,F,H,I,J].
operacao(dir) 	transforma [A,B,C,*,E,F,H,I,J] em [A,B,C,E,*,F,H,I,J].
operacao(dir) 	transforma [A,B,C,D,E,F,*,I,J] em [A,B,C,D,E,F,I,*,J].

operacao(baixo) transforma [A,B,C,*,E,F,H,I,J] em [A,B,C,H,E,F,*,I,J].
operacao(baixo) transforma [A,B,C,D,*,F,H,I,J] em [A,B,C,D,I,F,H,*,J].
operacao(baixo) transforma [A,B,C,D,E,*,H,I,J] em [A,B,C,D,E,J,H,I,*].
operacao(baixo) transforma [*,B,C,D,E,F,H,I,J] em [D,B,C,*,E,F,H,I,J].
operacao(baixo) transforma [A,*,C,D,E,F,H,I,J] em [A,E,C,D,*,F,H,I,J].
operacao(baixo) transforma [A,B,*,D,E,F,H,I,J] em [A,B,F,D,E,*,H,I,J].

/********************************************************************/
/************************ Testes  ***********************/

/*Test A*/
/*
estado_inicial([1,2,3,4,5,6,7,8,*]).

[3,*,1,2,5,6,4,7,8] e_a_meta.
*/

/*Test B*/
/*
estado_inicial([1,2,3,4,5,6,7,8,*]).

[*,3,1,2,5,6,4,7,8] e_a_meta.
*/

/*Test C*/
/*
estado_inicial([1,2,3,4,5,6,7,8,*]).

[2,3,1,*,5,6,4,7,8] e_a_meta.
*/

/*Test D*/
/*
estado_inicial([1,2,3,4,5,6,7,8,*]).

[2,3,*,1,5,6,4,7,8] e_a_meta.
*/

/* Test E */

estado_inicial([1,2,3,4,5,6,7,8,*]).

[1,2,3,5,*,6,4,7,8] e_a_meta.



/********************************************************************/
/************************ Predicados de Ajuda ***********************/
init_dynamic :-
	asserta(countinicio(0)), asserta(countmeta(0)), 
	ticks(Tempo), asserta(tempo(Tempo)).

imprimatempo :- ticks(Tempo2), retract(tempo(Tempo)),
	write('*********** Resultados **********'),nl,nl,
	write('O Tempo Rodado em ticks :'), 
	Ticks is Tempo2 - Tempo,
	write(Ticks),nl,nl.

soma_ini([]):-!.
soma_ini([Head|Tail])  :- retract(countinicio(N)), 
	Tot is N + 1, asserta(countinicio(Tot)), 
	soma_ini(Tail),!.
soma_meta([]):-!.
soma_meta([Head|Tail]) :- retract(countmeta(N)), 
	Tot is N + 1, asserta(countmeta(Tot)), 
	soma_meta(Tail),!.

ap([],X,X) :- !.
ap([X|Y],Z,[X|W]) :- ap(Y, Z, W).

membro(X,[X|_]) :- !.
membro(X,[_|Y]) :- membro(X,Y).

ache_todos(X, Y, Z) :- findall(X, Y, Z), !.
ache_todos(_, _, []).

imprima([r(raiz,Raiz)]) :- !,
	write('Estado Inicial( Busca De Inicio - Profundidade)  : '),
	write(Raiz), write('.'),nl,
	retract(countinicio(Nos)), write('Nos Expandidos:'), write(Nos),nl.

imprima([r(meta,Meta)]) :- !,
	write('Estado Final  ( Busca De Meta   - Profundidade)  : '),
	write(Meta), write('.'),nl,
	retract(countmeta(Nos)), write('Nos Expandidos:'), write(Nos),nl.
 
imprima([r(Ramo,Nodo)|R]) :- imprima(R), nl,
	write(Ramo), write(' e ,portanto, temos: '), nl,
	tab(4),write(Nodo), write('.').
