estarguars113

Untitled

Oct 24th, 2012
584
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. functor
  2.  
  3. export
  4.    encontrar: Encontrar
  5.    aplicarMovimientos:AplicarMovimientos  
  6.    aplicarMovimiento:AplicarMovimiento
  7.  
  8. % Estructura de los datos estado(principal:P uno:U dos:D)
  9. fun {AplicarMovimiento S M}
  10.    case S of estado(principal:P uno:U dos:D)then
  11.      
  12.       local Lp PrimerosU UltimosU PrimerosP UltimosP PrimerosD UltimosD Subl in
  13.     % {Browse  P}
  14.      
  15.      Lp={Length P}
  16.      
  17.       %Si el movimiento se hace en la linea uno
  18.       case M of uno(N) then  
  19.      Subl=Lp-N
  20.  
  21.      {ParticionN U N PrimerosU UltimosU}
  22.      {ParticionN P Subl PrimerosP UltimosP}
  23.  
  24.              if(N<0)
  25.              then  estado(principal:{Append S.principal PrimerosU} uno:UltimosU dos:D)
  26.              elseif (N==0)then estado(principal:P uno:U dos:D)
  27.              else  estado(principal:PrimerosP  uno:{Append UltimosP U} dos:D)
  28.              end
  29.    
  30.        %Si el movimiento se hace en la linea dos
  31.        [] dos(N) then
  32.        Subl=Lp-N
  33.        {ParticionN D N PrimerosD UltimosD}
  34.        {ParticionN P Subl PrimerosP UltimosP}
  35.           if(N<0)
  36.           then estado(principal:{Append P UltimosD} uno:U dos:UltimosD)
  37.           elseif (N==0)then estado(principal:P uno:U dos:D)
  38.           else  estado(principal:PrimerosP uno:U dos:{Append UltimosP D})
  39.           end
  40.         end
  41.      end
  42.     end
  43. end
  44.  
  45. %Aplicar una secuencia de movimientos sobre un estado inicial
  46. fun {AplicarMovimientos S Ms}
  47.     case S of estado(principal:P uno:U dos:D)
  48.     then
  49.          case Ms
  50.          of nil then S
  51.          [] H|T then {AplicarMovimientos {AplicarMovimiento S H} T}
  52.          end
  53.    end
  54. end
  55.  
  56. %Procedimiento para particionar la lista en 2 sublistas de n y longitud total - n elementos, respectivamente
  57. proc {ParticionN L N ?H ?T}
  58.      if (N>0) then
  59.     case L of nil then skip
  60.     [] Ca|Co then {ParticionN Co (N-1) {Append H Ca} T}
  61.            end
  62.      end
  63. end
  64. %{Browse {ParticionN [a b c d e] 3 }}
  65.  
  66.  
  67.  
  68. %Funcion para invertir una lista
  69. fun {Invertir L}
  70.     case L of nil then nil
  71.     [] H|T  then {Append {Invertir T} [H]}
  72.     end
  73. end
  74.  
  75. {Browse {AplicarMovimiento estado(principal:[a b c d e] uno:[g] dos:[f]) uno(2)}}
  76.  
  77.  
  78. %Funcion para encontrar el total de vagones que tiene un tren
  79. fun {NumeroVagones S }
  80.     case S of estado(principal:P uno:U dos:D)then
  81.           local L L1 L2
  82.            in L={List.length P} L1={List.length U} L2={List.length D}
  83.            L+L1+L2
  84.      end
  85.     end
  86. end
  87.  
  88. %Determinar si 2 trenes tienen el mismo numero de vagones
  89. fun {IgualdadVagones Xs Ys}
  90.     ({NumeroVagones Xs}=={NumeroVagones Ys})
  91. end
  92.  
  93. %Comparar longitud de las listas
  94. fun {CompararItems L1 L2}
  95.     case L1 of
  96.     nil then true
  97.     [] H|T then
  98.        if(H==L2.1) then {CompararItems T L2.2}
  99.        else false
  100.        end
  101.     end
  102. end
  103.  
  104.  
  105. fun {CompararListas L1 L2}
  106.      if {List.length L1}=={List.length L2} 
  107.      then {CompararItems L1 L2}
  108.      else false
  109.      end
  110. end
  111.  
  112.  
  113.  
  114. % Detectar vagones repetidos al interior de un tren
  115. fun {DetectarRepetidos Ls Ant}      
  116.     if (Ls==nil) then false
  117.     elseif (Ant==Ls.1) then true
  118.     else {Or false {DetectarRepetidos Ls.2 Ls.1}}
  119.     end
  120. end
  121.  
  122.  
  123. %Devolver una lista con los estados intermedios que se generan, tras aplicarle una serie de movimientos sobre una estado inicial
  124. fun {EstadosIntermedios S Ms}
  125. case S of estado(principal:P uno:U dos:D)
  126.     then
  127.          case Ms of
  128.          nil then S
  129.          [] H|T then
  130.                local Actual
  131.                in Actual= {AplicarMovimiento S H}
  132.                Actual|{EstadosIntermedios Actual T}
  133.                end
  134.          end
  135.     end
  136. end
  137.  
  138.  
  139. %SubListas coincidentes
  140. fun {SublistasCoincidentes Xs Ys}
  141.    case Xs of
  142.       nil then nil
  143.    else {LongitudCoincidencia Xs Ys 0}|{SublistasCoincidentes Xs.2 Ys.2}
  144.    end
  145. end
  146. %Esto se puede optimizar tantisimo
  147.  
  148.      
  149.  
  150. %Longitud de las sublista coincidente
  151. fun {LongitudCoincidencia Xs Ys Cont}
  152.    case Xs of
  153.       nil then cont
  154.       [] H|T then
  155.       case Ys of
  156.          H1|T1 then
  157.          if(H==H1)then {LongitudCoincidencia T T1 (Cont + 1)}
  158.          else cont
  159.           end
  160.       end
  161. end
  162. end
  163.  
  164. %Devuelve la posicion del elemento e al interior de la lista l
  165.    fun {EncontrarPosicion E L Pos}
  166.       case L of
  167.      H|T then if(H==E) then pos
  168.      else {EncontrarPosicion e T (Pos + 1)}
  169.      end
  170.       end
  171.    end
  172.      
  173.  
  174. %Funcion que retorna la lista de movimientos para llevar el estado Xs al estado Ys
  175. fun {Encontrar Xs Ys}
  176.  
  177.    %Caso trivial
  178.    if(Xs==Ys)then uno(0)|nil
  179.    else
  180.       %Validar que el tamaño de los trenes sea el mismo
  181.       if({IgualdadVagones Xs Ys})
  182.       then
  183.      %Validar que no hallan vagones repetidos al interior de ningun tren
  184.      if({Not{Or {DetectarRepetidos Xs nil}{DetectarRepetidos Ys nil}}})
  185.        then
  186.           %Validar que los vagones de los trenes sean permutaciones sobre el mismo conjunto
  187.         if({CompararListas {Sort Xs '<'}{Sort Ys '<'}})
  188.         then
  189.            local ListaCoincidencias in
  190.           ListaCoincidencias={SublistasCoincidentes Xs Ys}
  191.           {EncontrarAux Xs Ys ListaCoincidencias}
  192.           end
  193.            end
  194.         end
  195.       end
  196.    end
  197. end
  198.  
  199.  fun {EncontrarAux Xs Ys Cs}
  200.     local L NCoincidencias NEquivocados Siguiente Antes Despues in
  201.        L={Length Xs}
  202.        NCoincidencias=Cs.1
  203.        %Caso 1:Sublistas iniciales coincidentes
  204.        if(NCoincidencias>0)
  205.        then NEquivocados=L- NCoincidencias
  206.        {EncontrarAux {Ultimos Xs NEquivocados}{Ultimos Ys NEquivocados}{Ultimos Cs NEquivocados}}
  207.  
  208.        %Caso 2:Sublistas inicialmente diferentes
  209.       else
  210.       Siguiente={EncontrarPosicion Ys.1 Xs 0}
  211.       Despues=   L-Siguiente+1
  212.       Antes=     L-Despues
  213.       %Movemos el bloque de tamaño Longitud de la lista-Siguiente +1
  214.       [dos(Despues) uno(Antes) dos(~1) uno(~Antes) dos(~(Despues-1))] | {EncontrarAux Xs.2 Ys.2 Cs.2}
  215.    end    
  216. end
  217. end
  218.  
  219. end
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×