Foro - Perl en Español

por **explorer** » 2010-04-01 19:52 @869

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.

#!/usr/bin/perl
#
# minisioneros_canibales.pl
#
# Autor
#   Joaquín Ferrero
#
# Descripción:
#   Tres misioneros junto con tres caníbales quieren pasar de una orilla a
#   otra de un río. Solo disponen de una canoa en la que pueden ir como máximo
#   dos personas. Y además, no pueden quedarse en ninguna de las dos orillas,
#   un número superior de caníbales que de misioneros.
#
# Entradas
#   Ninguna
#
# Parámetros
#   Ninguna.
#   Opcionalmente, dos números, primero el número de viajeros en una orilla, y
#   y segundo, la capacidad máxima de la barca.
#
# Salidas
#   El esquema de movimiento de las personas que cruzan el río.
#
# Historial
#    2010-05-16 : Versión inicial
#
 
 
###############################################################################
### Librerías
use common::sense;
use Memoize;
use open 'locale';
 
 
###############################################################################
### Constantes
use constant {MISIONEROS => 0, CANIBALES => 1};
use constant {IZQ        => 0, DER       => 1};
 
 
###############################################################################
### Variables
my $viaje_más_corto;
my $número_de_pasos;
my $número_de_viajes_posibles;
 
my $VIAJEROS     = 3;               # Valores por defecto
my $LIMITE_BARCA = 2;
 
my $BARCA = '\___/';                # Representación gráfica
my $RÍO   = '~~~~~~~~';
 
my $estado_inicial;
my $estado_final;
my $posición_barca_orilla_izq;
 
###############################################################################
### Proceso
# El formato del viaje es un array de estados. Cada elemento es una fase del
# viaje, compuesto de una cadena, con el formato siguiente:
#
#   M:3 C:3 \___/ ~~~~~~~~ M:0 C:0
#     |   |   |              |   +- número de caníbales, a la der.
#     |   |   |              +----- número de misioneros, a la der.
#     |   |   +-------------------- posición de la barca
#     |   +------------------------ número de caníbales, a la izq.
#     +---------------------------- número de misioneros, a la izq.
#
 
# Inicialización
memoize('viajes_posibles');
memoize('se_cumple_la_condición');
memoize('define_estado');
 
# Leemos los posibles argumentos
if (2 == @ARGV) {
    $VIAJEROS     = shift @ARGV;
    $LIMITE_BARCA = shift @ARGV;
}
 
# Inicialización de los estados inicial, final
$estado_inicial            = define_estado(IZQ, ($VIAJEROS, $VIAJEROS, 0, 0));
$estado_final              = define_estado(DER, (0, 0, $VIAJEROS, $VIAJEROS));
$posición_barca_orilla_izq = index($estado_inicial, $BARCA);
 
# Recorrido de todas las posibles combinaciones
todos_los_viajes( $estado_inicial );
 
# Mostrar resultado
if ($viaje_más_corto) {
    say "Viajes posibles: $número_de_viajes_posibles";
    say "Viaje más corto: $número_de_pasos pasos";
    say $viaje_más_corto;
}
else {
    say 'No se encontró solución.';
}
 
 
###############################################################################
### Subrutinas
 
### Regla lógica que siempre se debe cumplir en cada orilla
sub se_cumple_la_condición {
    my ($misioneros, $caníbales) = @_;
 
    # O no hay misioneros  o  hay más misioneros que caníbales
    $misioneros == 0       or  $misioneros >= $caníbales;
}
 
### Crea la cadena que representa el estado
sub define_estado {
    my($orilla, @estado) = @_;
    my $gráfico;
 
    $gráfico  = "M:$estado[0] C:$estado[1]";
    $gráfico .= $orilla ? " $RÍO $BARCA " : " $BARCA $RÍO ";
    $gráfico .= "M:$estado[2] C:$estado[3]";
}
 
### Realiza todos los posibles viajes, de forma recursiva
sub todos_los_viajes {
    my @ruta_actual   = @_;
    my $estado_actual = $ruta_actual[-1];
    my $orilla        = index($estado_actual, $BARCA) != $posición_barca_orilla_izq;
 
    my @estado_actual;                      # lo mismo en forma de matriz 2x2
    push @estado_actual, [ $1, $2 ] while $estado_actual =~ /M:(\d+) C:(\d+)/g;
 
    # Los viajes posibles son un array de arrays,
    # cada uno de los cuales indica cuántos viajeros metemos en la barca
    for my $viaje_posible (viajes_posibles($orilla, @estado_actual)) {
 
        my ($m, $c) = @$viaje_posible;                  # viajeros
 
        if ($orilla) { $m = -$m; $c = -$c }             # que suman o restan según la orilla
 
        my $nuevo_posible_estado
            = define_estado(
                1 - $orilla,                            # en la otra orilla
                $estado_actual[ IZQ ][ MISIONEROS ] - $m,
                $estado_actual[ IZQ ][ CANIBALES  ] - $c,
                $estado_actual[ DER ][ MISIONEROS ] + $m,
                $estado_actual[ DER ][ CANIBALES  ] + $c,
            );
 
        # Comprobar si hemos llegado al final
        if ($nuevo_posible_estado eq $estado_final) {
            $número_de_viajes_posibles++;
            my $viaje = join "\n", @ruta_actual, $nuevo_posible_estado;
            if (length($viaje) < length($viaje_más_corto)  or  !$viaje_más_corto) {
                $viaje_más_corto = $viaje;
                $número_de_pasos = 1 + @ruta_actual;
            }
            #say "$viaje\n";
            next;
        }
 
        # Saltar si el estado estaba ya visitado
        next if $nuevo_posible_estado ~~ @ruta_actual;
 
        # Recorremos cada viaje posible
        todos_los_viajes( @ruta_actual, $nuevo_posible_estado );
    }
}
 
### Calcular todas las combinaciones de viajes posibles
sub viajes_posibles {
    my ($esta_orilla, @estado_actual) = @_;
 
    my $otra_orilla = 1 - $esta_orilla;
 
    my @viajes_posibles;
 
    for my $m (reverse  0 .. $estado_actual[ $esta_orilla ][ MISIONEROS ]) {
    for my $c (reverse  0 .. $estado_actual[ $esta_orilla ][ CANIBALES  ]) {
 
        # Límite de ocupación de la barca: no más del límite y al menos, uno
        my $barca = $m + $c ;
        next unless $barca <= $LIMITE_BARCA  and  $barca >= 1;
 
        # No permitir desigualdad en la orilla en que estamos
        next if not se_cumple_la_condición(
                $estado_actual[ $esta_orilla ][ MISIONEROS ] - $m,
                $estado_actual[ $esta_orilla ][ CANIBALES  ] - $c,
            );
 
        # No permitir desigualdad en la otra orilla
        next if not se_cumple_la_condición(
                $estado_actual[ $otra_orilla ][ MISIONEROS ] + $m,
                $estado_actual[ $otra_orilla ][ CANIBALES  ] + $c,
            );
 
        push @viajes_posibles, [$m, $c];
    }}
 
    return @viajes_posibles;
}
 
__END__
Viajes posibles: 4
Viaje más corto: 12 pasos
M:3 C:3 \___/ ~~~~~~~~ M:0 C:0
M:2 C:2 ~~~~~~~~ \___/ M:1 C:1
M:3 C:2 \___/ ~~~~~~~~ M:0 C:1
M:3 C:0 ~~~~~~~~ \___/ M:0 C:3
M:3 C:1 \___/ ~~~~~~~~ M:0 C:2
M:1 C:1 ~~~~~~~~ \___/ M:2 C:2
M:2 C:2 \___/ ~~~~~~~~ M:1 C:1
M:0 C:2 ~~~~~~~~ \___/ M:3 C:1
M:0 C:3 \___/ ~~~~~~~~ M:3 C:0
M:0 C:1 ~~~~~~~~ \___/ M:3 C:2
M:1 C:1 \___/ ~~~~~~~~ M:2 C:2
M:0 C:0 ~~~~~~~~ \___/ M:3 C:3
Coloreado en 0.007 segundos,  usando GeSHi 1.0.8.4

Foro - Perl en Español

Reto: misioneros y caníbales

Reto: misioneros y caníbales

Publicidad

Re: Reto: misioneros y caníbales

¿Quién está conectado?