Página 1 de 1

Reto: misioneros y caníbales

NotaPublicado: 2010-04-01 19:52 @869
por explorer
En una orilla de un río se juntaron tres misioneros y tres caníbales. Necesitaban pasar a la otra orilla del río, pero solo contaban con una canoa, donde podía ir una o dos personas cada vez.

El problema estaba en que, en ningún momento, el número de caníbales en una orilla no podía ser superior al de misioneros, ya que estos podrían ser devorados(*).

Hay que encontrar una forma de pasar a las seis personas de un lado a otro del río.

Se pide:

* Encontrar todas las soluciones posibles. Cada solución incluye una serie de estados, que no se repiten, en el que existen un número de misioneros y caníbales en cada orilla, y una canoa en una de ellas. Cada estado pasa al siguiente a través del movimiento de personas con la ayuda de la canoa.

* Encontrar la solución más corta.


(*) Otra versión del problema es justo al revés: los caníbales no pueden estar en minoría, ya que serían bautizados "a la fuerza" por los misioneros. El juego sigue siendo el mismo.

Solución de BlackShell.

Re: Reto: misioneros y caníbales

NotaPublicado: 2010-05-16 15:07 @672
por explorer
Esta es una posible solución. Se usa la pila entre llamadas recursivas de la función que recorre cada posible viaje, como almacén de ese viaje y sistema de vuelta atrás en caso de llegar a un callejón sin salida.

Los estados del viaje son los mismos que representan el propio viaje.

Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1. #!/usr/bin/perl
  2. #
  3. # minisioneros_canibales.pl
  4. #
  5. # Autor
  6. #   Joaquín Ferrero
  7. #
  8. # Descripción:
  9. #   Tres misioneros junto con tres caníbales quieren pasar de una orilla a
  10. #   otra de un río. Solo disponen de una canoa en la que pueden ir como máximo
  11. #   dos personas. Y además, no pueden quedarse en ninguna de las dos orillas,
  12. #   un número superior de caníbales que de misioneros.
  13. #
  14. # Entradas
  15. #   Ninguna
  16. #
  17. # Parámetros
  18. #   Ninguna.
  19. #   Opcionalmente, dos números, primero el número de viajeros en una orilla, y
  20. #   y segundo, la capacidad máxima de la barca.
  21. #
  22. # Salidas
  23. #   El esquema de movimiento de las personas que cruzan el río.
  24. #
  25. # Historial
  26. #    2010-05-16 : Versión inicial
  27. #
  28.  
  29.  
  30. ###############################################################################
  31. ### Librerías
  32. use common::sense;
  33. use Memoize;
  34. use open 'locale';
  35.  
  36.  
  37. ###############################################################################
  38. ### Constantes
  39. use constant {MISIONEROS => 0, CANIBALES => 1};
  40. use constant {IZQ        => 0, DER       => 1};
  41.  
  42.  
  43. ###############################################################################
  44. ### Variables
  45. my $viaje_más_corto;
  46. my $número_de_pasos;
  47. my $número_de_viajes_posibles;
  48.  
  49. my $VIAJEROS     = 3;               # Valores por defecto
  50. my $LIMITE_BARCA = 2;
  51.  
  52. my $BARCA = '\___/';                # Representación gráfica
  53. my $RÍO   = '~~~~~~~~';
  54.  
  55. my $estado_inicial;
  56. my $estado_final;
  57. my $posición_barca_orilla_izq;
  58.  
  59. ###############################################################################
  60. ### Proceso
  61. # El formato del viaje es un array de estados. Cada elemento es una fase del
  62. # viaje, compuesto de una cadena, con el formato siguiente:
  63. #
  64. #   M:3 C:3 \___/ ~~~~~~~~ M:0 C:0
  65. #     |   |   |              |   +- número de caníbales, a la der.
  66. #     |   |   |              +----- número de misioneros, a la der.
  67. #     |   |   +-------------------- posición de la barca
  68. #     |   +------------------------ número de caníbales, a la izq.
  69. #     +---------------------------- número de misioneros, a la izq.
  70. #
  71.  
  72. # Inicialización
  73. memoize('viajes_posibles');
  74. memoize('se_cumple_la_condición');
  75. memoize('define_estado');
  76.  
  77. # Leemos los posibles argumentos
  78. if (2 == @ARGV) {
  79.     $VIAJEROS     = shift @ARGV;
  80.     $LIMITE_BARCA = shift @ARGV;
  81. }
  82.  
  83. # Inicialización de los estados inicial, final
  84. $estado_inicial            = define_estado(IZQ, ($VIAJEROS, $VIAJEROS, 0, 0));
  85. $estado_final              = define_estado(DER, (0, 0, $VIAJEROS, $VIAJEROS));
  86. $posición_barca_orilla_izq = index($estado_inicial, $BARCA);
  87.  
  88. # Recorrido de todas las posibles combinaciones
  89. todos_los_viajes( $estado_inicial );
  90.  
  91. # Mostrar resultado
  92. if ($viaje_más_corto) {
  93.     say "Viajes posibles: $número_de_viajes_posibles";
  94.     say "Viaje más corto: $número_de_pasos pasos";
  95.     say $viaje_más_corto;
  96. }
  97. else {
  98.     say 'No se encontró solución.';
  99. }
  100.  
  101.  
  102. ###############################################################################
  103. ### Subrutinas
  104.  
  105. ### Regla lógica que siempre se debe cumplir en cada orilla
  106. sub se_cumple_la_condición {
  107.     my ($misioneros, $caníbales) = @_;
  108.  
  109.     # O no hay misioneros  o  hay más misioneros que caníbales
  110.     $misioneros == 0       or  $misioneros >= $caníbales;
  111. }
  112.  
  113. ### Crea la cadena que representa el estado
  114. sub define_estado {
  115.     my($orilla, @estado) = @_;
  116.     my $gráfico;
  117.  
  118.     $gráfico  = "M:$estado[0] C:$estado[1]";
  119.     $gráfico .= $orilla ? " $RÍO $BARCA " : " $BARCA $RÍO ";
  120.     $gráfico .= "M:$estado[2] C:$estado[3]";
  121. }
  122.  
  123. ### Realiza todos los posibles viajes, de forma recursiva
  124. sub todos_los_viajes {
  125.     my @ruta_actual   = @_;
  126.     my $estado_actual = $ruta_actual[-1];
  127.     my $orilla        = index($estado_actual, $BARCA) != $posición_barca_orilla_izq;
  128.  
  129.     my @estado_actual;                      # lo mismo en forma de matriz 2x2
  130.     push @estado_actual, [ $1, $2 ] while $estado_actual =~ /M:(\d+) C:(\d+)/g;
  131.  
  132.     # Los viajes posibles son un array de arrays,
  133.     # cada uno de los cuales indica cuántos viajeros metemos en la barca
  134.     for my $viaje_posible (viajes_posibles($orilla, @estado_actual)) {
  135.  
  136.         my ($m, $c) = @$viaje_posible;                  # viajeros
  137.  
  138.         if ($orilla) { $m = -$m; $c = -$c }             # que suman o restan según la orilla
  139.  
  140.         my $nuevo_posible_estado
  141.             = define_estado(
  142.                 1 - $orilla,                            # en la otra orilla
  143.                 $estado_actual[ IZQ ][ MISIONEROS ] - $m,
  144.                 $estado_actual[ IZQ ][ CANIBALES  ] - $c,
  145.                 $estado_actual[ DER ][ MISIONEROS ] + $m,
  146.                 $estado_actual[ DER ][ CANIBALES  ] + $c,
  147.             );
  148.  
  149.         # Comprobar si hemos llegado al final
  150.         if ($nuevo_posible_estado eq $estado_final) {
  151.             $número_de_viajes_posibles++;
  152.             my $viaje = join "\n", @ruta_actual, $nuevo_posible_estado;
  153.             if (length($viaje) < length($viaje_más_corto)  or  !$viaje_más_corto) {
  154.                 $viaje_más_corto = $viaje;
  155.                 $número_de_pasos = 1 + @ruta_actual;
  156.             }
  157.             #say "$viaje\n";
  158.             next;
  159.         }
  160.  
  161.         # Saltar si el estado estaba ya visitado
  162.         next if $nuevo_posible_estado ~~ @ruta_actual;
  163.  
  164.         # Recorremos cada viaje posible
  165.         todos_los_viajes( @ruta_actual, $nuevo_posible_estado );
  166.     }
  167. }
  168.  
  169. ### Calcular todas las combinaciones de viajes posibles
  170. sub viajes_posibles {
  171.     my ($esta_orilla, @estado_actual) = @_;
  172.  
  173.     my $otra_orilla = 1 - $esta_orilla;
  174.  
  175.     my @viajes_posibles;
  176.  
  177.     for my $m (reverse  0 .. $estado_actual[ $esta_orilla ][ MISIONEROS ]) {
  178.     for my $c (reverse  0 .. $estado_actual[ $esta_orilla ][ CANIBALES  ]) {
  179.  
  180.         # Límite de ocupación de la barca: no más del límite y al menos, uno
  181.         my $barca = $m + $c ;
  182.         next unless $barca <= $LIMITE_BARCA  and  $barca >= 1;
  183.  
  184.         # No permitir desigualdad en la orilla en que estamos
  185.         next if not se_cumple_la_condición(
  186.                 $estado_actual[ $esta_orilla ][ MISIONEROS ] - $m,
  187.                 $estado_actual[ $esta_orilla ][ CANIBALES  ] - $c,
  188.             );
  189.  
  190.         # No permitir desigualdad en la otra orilla
  191.         next if not se_cumple_la_condición(
  192.                 $estado_actual[ $otra_orilla ][ MISIONEROS ] + $m,
  193.                 $estado_actual[ $otra_orilla ][ CANIBALES  ] + $c,
  194.             );
  195.  
  196.         push @viajes_posibles, [$m, $c];
  197.     }}
  198.  
  199.     return @viajes_posibles;
  200. }
  201.  
  202. __END__
  203. Viajes posibles: 4
  204. Viaje más corto: 12 pasos
  205. M:3 C:3 \___/ ~~~~~~~~ M:0 C:0
  206. M:2 C:2 ~~~~~~~~ \___/ M:1 C:1
  207. M:3 C:2 \___/ ~~~~~~~~ M:0 C:1
  208. M:3 C:0 ~~~~~~~~ \___/ M:0 C:3
  209. M:3 C:1 \___/ ~~~~~~~~ M:0 C:2
  210. M:1 C:1 ~~~~~~~~ \___/ M:2 C:2
  211. M:2 C:2 \___/ ~~~~~~~~ M:1 C:1
  212. M:0 C:2 ~~~~~~~~ \___/ M:3 C:1
  213. M:0 C:3 \___/ ~~~~~~~~ M:3 C:0
  214. M:0 C:1 ~~~~~~~~ \___/ M:3 C:2
  215. M:1 C:1 \___/ ~~~~~~~~ M:2 C:2
  216. M:0 C:0 ~~~~~~~~ \___/ M:3 C:3
Coloreado en 0.006 segundos, usando GeSHi 1.0.8.4