functor

export
   encontrar: Encontrar
   aplicarMovimientos:AplicarMovimientos
   aplicarMovimiento:AplicarMovimiento

% Estructura de los datos estado(principal:P uno:U dos:D)
fun {AplicarMovimiento S M}
   case S of estado(principal:P uno:U dos:D)then

      local Lp PrimerosU UltimosU PrimerosP UltimosP PrimerosD UltimosD Subl in
    % {Browse  P}

     Lp={Length P}

      %Si el movimiento se hace en la linea uno
      case M of uno(N) then
     Subl=Lp-N

     {ParticionN U N PrimerosU UltimosU}
     {ParticionN P Subl PrimerosP UltimosP}

             if(N<0)
             then  estado(principal:{Append S.principal PrimerosU} uno:UltimosU dos:D)
             elseif (N==0)then estado(principal:P uno:U dos:D)
             else  estado(principal:PrimerosP  uno:{Append UltimosP U} dos:D)
             end

       %Si el movimiento se hace en la linea dos
       [] dos(N) then
       Subl=Lp-N
       {ParticionN D N PrimerosD UltimosD}
       {ParticionN P Subl PrimerosP UltimosP}
          if(N<0)
          then estado(principal:{Append P UltimosD} uno:U dos:UltimosD)
          elseif (N==0)then estado(principal:P uno:U dos:D)
          else  estado(principal:PrimerosP uno:U dos:{Append UltimosP D})
          end
        end
     end
    end
end

%Aplicar una secuencia de movimientos sobre un estado inicial
fun {AplicarMovimientos S Ms}
    case S of estado(principal:P uno:U dos:D)
    then
         case Ms
         of nil then S
         [] H|T then {AplicarMovimientos {AplicarMovimiento S H} T}
         end
   end
end

%Procedimiento para particionar la lista en 2 sublistas de n y longitud total - n elementos, respectivamente
proc {ParticionN L N ?H ?T}
     if (N>0) then
    case L of nil then skip
    [] Ca|Co then {ParticionN Co (N-1) {Append H Ca} T}
           end
     end
end
%{Browse {ParticionN [a b c d e] 3 }}



%Funcion para invertir una lista
fun {Invertir L}
    case L of nil then nil
    [] H|T  then {Append {Invertir T} [H]}
    end
end

{Browse {AplicarMovimiento estado(principal:[a b c d e] uno:[g] dos:[f]) uno(2)}}


%Funcion para encontrar el total de vagones que tiene un tren
fun {NumeroVagones S }
    case S of estado(principal:P uno:U dos:D)then
          local L L1 L2
           in L={List.length P} L1={List.length U} L2={List.length D}
           L+L1+L2
     end
    end
end

%Determinar si 2 trenes tienen el mismo numero de vagones
fun {IgualdadVagones Xs Ys}
    ({NumeroVagones Xs}=={NumeroVagones Ys})
end

%Comparar longitud de las listas
fun {CompararItems L1 L2}
    case L1 of
    nil then true
    [] H|T then
       if(H==L2.1) then {CompararItems T L2.2}
       else false
       end
    end
end


fun {CompararListas L1 L2}
     if {List.length L1}=={List.length L2}
     then {CompararItems L1 L2}
     else false
     end
end



% Detectar vagones repetidos al interior de un tren
fun {DetectarRepetidos Ls Ant}
    if (Ls==nil) then false
    elseif (Ant==Ls.1) then true
    else {Or false {DetectarRepetidos Ls.2 Ls.1}}
    end
end


%Devolver una lista con los estados intermedios que se generan, tras aplicarle una serie de movimientos sobre una estado inicial
fun {EstadosIntermedios S Ms}
case S of estado(principal:P uno:U dos:D)
    then
         case Ms of
         nil then S
         [] H|T then
               local Actual
               in Actual= {AplicarMovimiento S H}
               Actual|{EstadosIntermedios Actual T}
               end
         end
    end
end


%SubListas coincidentes
fun {SublistasCoincidentes Xs Ys}
   case Xs of
      nil then nil
   else {LongitudCoincidencia Xs Ys 0}|{SublistasCoincidentes Xs.2 Ys.2}
   end
end
%Esto se puede optimizar tantisimo



%Longitud de las sublista coincidente
fun {LongitudCoincidencia Xs Ys Cont}
   case Xs of
      nil then cont
      [] H|T then
      case Ys of
         H1|T1 then
         if(H==H1)then {LongitudCoincidencia T T1 (Cont + 1)}
         else cont
          end
      end
end
end

%Devuelve la posicion del elemento e al interior de la lista l
   fun {EncontrarPosicion E L Pos}
      case L of
     H|T then if(H==E) then pos
     else {EncontrarPosicion e T (Pos + 1)}
     end
      end
   end


%Funcion que retorna la lista de movimientos para llevar el estado Xs al estado Ys
fun {Encontrar Xs Ys}

   %Caso trivial
   if(Xs==Ys)then uno(0)|nil
   else
      %Validar que el tamaño de los trenes sea el mismo
      if({IgualdadVagones Xs Ys})
      then
     %Validar que no hallan vagones repetidos al interior de ningun tren
     if({Not{Or {DetectarRepetidos Xs nil}{DetectarRepetidos Ys nil}}})
       then
          %Validar que los vagones de los trenes sean permutaciones sobre el mismo conjunto
        if({CompararListas {Sort Xs '<'}{Sort Ys '<'}})
        then
           local ListaCoincidencias in
          ListaCoincidencias={SublistasCoincidentes Xs Ys}
          {EncontrarAux Xs Ys ListaCoincidencias}
          end
           end
        end
      end
   end
end

 fun {EncontrarAux Xs Ys Cs}
    local L NCoincidencias NEquivocados Siguiente Antes Despues in
       L={Length Xs}
       NCoincidencias=Cs.1
       %Caso 1:Sublistas iniciales coincidentes
       if(NCoincidencias>0)
       then NEquivocados=L- NCoincidencias
       {EncontrarAux {Ultimos Xs NEquivocados}{Ultimos Ys NEquivocados}{Ultimos Cs NEquivocados}}

       %Caso 2:Sublistas inicialmente diferentes
      else
      Siguiente={EncontrarPosicion Ys.1 Xs 0}
      Despues=   L-Siguiente+1
      Antes=     L-Despues
      %Movemos el bloque de tamaño Longitud de la lista-Siguiente +1
      [dos(Despues) uno(Antes) dos(~1) uno(~Antes) dos(~(Despues-1))] | {EncontrarAux Xs.2 Ys.2 Cs.2}
   end
end
end

end