#!/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