Gera Código

Considere um computador com n registos, , organizados em anel, de modo a que apenas seja possível:

• mover o valor do registo r_i para r_i+1, , com a instrução move(i);
• mover o valor do registo r_n para r₁, com a instrução move(n);
• trocar o conteúdo de quaisquer dois registos, com a instrução troca(i,j), i < j.

Dados os conteúdos iniciais de todos os registos (alguns registos podem conter ``wild cards'') e os conteúdos finais desejados de todos os registos (mais uma vez são admitidos ``wild cards''), pretende-se que implemente o predicado geraCodigo/3, que gera uma sequência de instruções mínima, de move/1 e troca/2, capaz de transformar o estado inicial da máquina no estado final, ou então que falhe se isso for impossível.
O predicado geraCodigo/3 recebe no primeiro argumento uma lista com o conteúdo inicial dos registos; no segundo argumento o conteúdo final dos registos; e retorna, no terceiro argumento e se possível, a sequência de instruções que efectuam a transição. Exemplo:

         ?- geraCodigo([a,b,c,d],[a,d,a,b],L).
            L = [move(2), move(1), troca(2,3), troca(2,4)]

Os ``wild cards'' são representados com um *. No estado inicial, um * tem o significado de ``não se sabe o conteúdo''; no estado final, significa ``não interessa o conteúdo''. Eis alguns exemplos:

         ?- geraCodigo([a,*,c],[c,a,*],L).
            L = [troca(1,2), troca(1,3)]
            ou
            L = [move(1), move(3)]
            ou muitas outras solucoes correctas

         ?- geraCodigo([a,b,c],[a,a,*],L).
            L = [move(1)]