Os Missionários e os Canibais

[thoga31]

Os Missionários e os Canibais

Este é um desafio pertencente à categoria clássica dos problemas dos rios.

A história

Temos 3 missionários e 3 canibais numa margem do rio. O barco apenas aguenta com 2 pessoas de cada vez. Deve-se ter em atenção que, se os canibais estiverem em maior número, mas não igual, aos missionários, eles tornam-se refeição...

O objectivo, claro, é passar todos os 6 elementos da história sem que os missionários sejam transformados em refeição dos canibais.

Objectivo

Construir um programa/script na vossa linguagem de eleição que resolva este problema.

Restrições

O programa/script deve estar preparado para receber por input um número qualquer de canibais e missionários, ou seja, deve estar preparado para resolver este problema qualquer que seja a condição inicial.

Deve haver um controlo do input, ou seja, o nº de missionários nunca deve ser inferior ao de canibais.

Cada passo de resolução deve ter uma parte "Vão" e outra "Voltam" - ou seja, cada passo corresponde a uma ida e volta do barco margem-a-margem.

E lembrem-se: o barco não anda sozinho - pelo menos uma pessoa, missionário ou canibal, deverá ir a bordo para o barco andar.

Exemplo de input/output

Canibais? 3
Missionários? 4
ERRO: Missionários > Canibais
Missionários? 3

SOLUÇÃO:
01) Vão: 2 canibais + 0 missionários. Voltam: 1 canibais + 0 missionários.
02) Vão: 2 canibais + 0 missionários. Voltam: 1 canibais + 0 missionários.
03) Vão: 0 canibais + 2 missionários. Voltam: 1 canibais + 1 missionários.
04) Vão: 0 canibais + 2 missionários. Voltam: 1 canibais + 0 missionários.
05) Vão: 2 canibais + 0 missionários. Voltam: 1 canibais + 0 missionários.
06) Vão: 2 canibais + 0 missionários. Voltam: <FIM!>

Material de apoio

Jogo online para testar o problema

Edited July 4, 2012 at 05:11 PM by thoga31

[HappyHippyHippo]

acho que falta um restrição : uma viagem (ida ou volta) deverá sempre levar alguém "o barco não anda sozinho"

[thoga31]

acho que falta um restrição : uma viagem (ida ou volta) deverá sempre levar alguém "o barco não anda sozinho"

Pensei que isso era óbvio, mas eu coloco lá na mesma, não vá alguém ter na solução 3 passos com "Voltam: 0 + 0" 😛

[Flinger]

Até porque se assim não for a solução é ainda mais simples 😛

Levam-se 2 canibais,volta sozinho, levam-se 2 missionários, volta sozinho, leva os 2 que faltam.

[HappyHippyHippo]

ora bem : aqui vai a minha solução em D com um algoritmo de breadth-first search

import tango.io.Console;
import tango.stdc.stdlib;
import Integer = tango.text.convert.Integer;

// Enumeracao que dita para que lado do rio o barco se movimentou na acao
enum Dir {
   Para_Direita,
   Para_Esquerda
}

// um estado/acao da solução
struct Estado {
   Dir  dir;      // Direcao do barco
   byte eCanibal; // Numero de canibais do lado esquerdo da margem
   byte eMission; // Numero de missionarios do lado esquerdo da margem
   byte dCanibal; // Numero de canibais do lado direito da margem
   byte dMission; // Numero de missionarios do lado direito da margem
   byte action;   // Numero identificativo da acao realizada no estado
}

// Lista de funcoes que actualizam um estado quando o barco se movimenta para a mergem direita do rio
//
// para a direita / acao 1 / 2 canibal e 0 missionarios
// para a direita / acao 2 / 1 canibal e 0 missionarios
// para a direita / acao 3 / 1 canibal e 1 missionarios
// para a direita / acao 4 / 0 canibal e 1 missionarios
// para a direita / acao 5 / 0 canibal e 2 missionarios
Estado c2m0_e_d(Estado e) { e.action = 1; e.dir = Dir.Para_Direita; e.eCanibal -= 2; e.dCanibal += 2; return e; }
Estado c1m0_e_d(Estado e) { e.action = 2; e.dir = Dir.Para_Direita; e.eCanibal -= 1; e.dCanibal += 1; return e; }
Estado c1m1_e_d(Estado e) { e.action = 3; e.dir = Dir.Para_Direita; e.eCanibal -= 1; e.dCanibal += 1; e.eMission -= 1; e.dMission += 1; return e; }
Estado c0m1_e_d(Estado e) { e.action = 4; e.dir = Dir.Para_Direita; e.eMission -= 1; e.dMission += 1; return e; }
Estado c0m2_e_d(Estado e) { e.action = 5; e.dir = Dir.Para_Direita; e.eMission -= 2; e.dMission += 2; return e; }

// Lista de funcoes que actualizam um estado quando o barco se movimenta para a mergem esquerda do rio
//
// para a esquerda / acao 1 / 2 canibal e 0 missionarios
// para a esquerda / acao 2 / 1 canibal e 0 missionarios
// para a esquerda / acao 3 / 1 canibal e 1 missionarios
// para a esquerda / acao 4 / 0 canibal e 1 missionarios
// para a esquerda / acao 5 / 0 canibal e 2 missionarios
Estado c2m0_d_e(Estado e) { e.action = 1; e.dir = Dir.Para_Esquerda; e.dCanibal -= 2; e.eCanibal += 2; return e; }
Estado c1m0_d_e(Estado e) { e.action = 2; e.dir = Dir.Para_Esquerda; e.dCanibal -= 1; e.eCanibal += 1; return e; }
Estado c1m1_d_e(Estado e) { e.action = 3; e.dir = Dir.Para_Esquerda; e.dCanibal -= 1; e.eCanibal += 1; e.dMission -= 1; e.eMission += 1; return e; }
Estado c0m1_d_e(Estado e) { e.action = 4; e.dir = Dir.Para_Esquerda; e.dMission -= 1; e.eMission += 1; return e; }
Estado c0m2_d_e(Estado e) { e.action = 5; e.dir = Dir.Para_Esquerda; e.dMission -= 2; e.eMission += 2; return e; }

// Funcao usada para validar a actualizacao do estado
bool validar(Estado[] solucao) {
   // elemento actualizado a ser verificado
   Estado e = solucao[$-1];

   bool ok = (e.eCanibal <= e.eMission || e.eMission == 0) && // verificar racio de canibais/missionarios do lado esquerdo
             (e.dCanibal <= e.dMission || e.dMission == 0) && // verificar racio de canibais/missionarios do lado direito
             (e.eCanibal >= 0) && (e.dCanibal >= 0) && (e.eMission >= 0) && (e.dMission >= 0) && // validar movimentos invalido que levem a numeros negativos
             (e.dCanibal + e.dMission > 0); // invalidar movimentos que levem ao estado inicial

   // verificar na solucao por um estado igual = ciclo
   for (int index = solucao.length - 2; index >= 0 && ok; index--) {
       if ((solucao[index].dCanibal == solucao[$-1].dCanibal) &&
           (solucao[index].eCanibal == solucao[$-1].eCanibal) &&
           (solucao[index].dMission == solucao[$-1].dMission) &&
           (solucao[index].eMission == solucao[$-1].eMission) &&
           (solucao[index].dir      == solucao[$-1].dir))
               ok = false;
   }

   return ok;
}

// funcao para verificar se a solucao chegou ao fim
bool solucao(Estado e) {
   return (e.eCanibal == 0) &&
          (e.eMission == 0);
}

// funcao recursiva de resolucao do problema
bool calcular(Estado[][] matrix, Dir dir, ref Estado[] res, int iteracao) {
   // matrix auxiliar
   Estado[][] aux;

   // limitar o numero de iteracoes, nao queremos que o programa fique para sempre a correr
   if (iteracao >= 50)
       return false;

   // calculo de novos valores para a matrix
   int n_solucoes = matrix.length * 5;
   int n_passos = matrix[0].length + 1;

   // alocacao de memoria para a matrix dinamica auxiliar
   aux.length = n_solucoes;
   for(int index = 0; index < aux.length; index++)
       aux[index].length = n_passos;

   // ciclo de copia da matrix original para a matrix auxiliar com a concatenacao do nova estado
   for(int index = 0; index < matrix.length; index++) {
       if (dir == Dir.Para_Direita) {
           // movimento do barco da direita para a esquerda
           aux[index*5    ][0 .. n_passos] = matrix[index] ~ c2m0_e_d(matrix[index][n_passos - 2]);
           aux[index*5 + 1][0 .. n_passos] = matrix[index] ~ c1m0_e_d(matrix[index][n_passos - 2]);
           aux[index*5 + 2][0 .. n_passos] = matrix[index] ~ c1m1_e_d(matrix[index][n_passos - 2]);
           aux[index*5 + 3][0 .. n_passos] = matrix[index] ~ c0m1_e_d(matrix[index][n_passos - 2]);
           aux[index*5 + 4][0 .. n_passos] = matrix[index] ~ c0m2_e_d(matrix[index][n_passos - 2]);
       } else {
           // movimento do barco da esquerda para a direita
           aux[index*5    ][0 .. n_passos] = matrix[index] ~ c2m0_d_e(matrix[index][n_passos - 2]);
           aux[index*5 + 1][0 .. n_passos] = matrix[index] ~ c1m0_d_e(matrix[index][n_passos - 2]);
           aux[index*5 + 2][0 .. n_passos] = matrix[index] ~ c1m1_d_e(matrix[index][n_passos - 2]);
           aux[index*5 + 3][0 .. n_passos] = matrix[index] ~ c0m1_d_e(matrix[index][n_passos - 2]);
           aux[index*5 + 4][0 .. n_passos] = matrix[index] ~ c0m2_d_e(matrix[index][n_passos - 2]);
       }
   }

   /* "limpar" a matrix original para ser recriada so com as novas solucoes viaveis */
   matrix.length = 0;
   for (int index = 0; index < n_solucoes; index++) {
       // verifica se o estado calculado e solucao
       if (solucao(aux[index][n_passos - 1])) {
           res = aux[index];
           return true;
       }

       // valida o estado calculado
       if (validar(aux[index])) {
           // adiciona a solucao a matrix de solucoes parciais
           matrix.length = matrix.length + 1;
           matrix[$-1] = aux[index];
       }
   }

   // chamada recursiva de pesquisa da solucao
   if (dir == Dir.Para_Direita)
       return calcular(matrix, Dir.Para_Esquerda, res, iteracao++);
   return calcular(matrix, Dir.Para_Direita, res, iteracao + 1);
}

void main() {
   // matrix inicial de pesquisa de solucao
   Estado[][] matrix;
   // array com a solucao encontrada
   Estado[] resultado;

   // inicializacao da matrix de pesqusia
   matrix.length = 1;
   matrix[0].length = 1;

   // perguntar pelo numero de canibais
   int quantidade = 0;
   while (quantidade < 3 || quantidade > 100) {
       try {
           Cout("Qual o número de canibais? (min = 3 | max = 100)")
               .newline();
           if ((quantidade = Integer.toInt(Cin.get())) < 3)
               Cout("O valor inserido não pode ser inferior a 3")
                   .newline();
       } catch (Object o) {
           Cout("O valor inserido não é um número válido").newline();
       }
   }
   matrix[0][0].eCanibal = quantidade;
   matrix[0][0].dCanibal = 0;

   // perguntar pelo numero de missionarios
   quantidade = 0;
   while (quantidade < matrix[0][0].eCanibal || quantidade > 100) {
       try {
           Cout("Qual o número de missionários? (min = ")
               .append(Integer.toString(matrix[0][0].eCanibal))
               .append(" | max = 100)")
               .newline();
           if ((quantidade = Integer.toInt(Cin.get())) < 3)
               Cout("O valor inserido não pode ser inferior a 3")
                   .newline();
       } catch (Object o) {
           Cout("O valor inserido não é um número válido").newline();
       }
   }
   matrix[0][0].eMission = quantidade;
   matrix[0][0].dMission = 0;

   // chamar a funcao recursiva de pesquisa da solucao
   if (calcular(matrix, Dir.Para_Direita, resultado, 0)) {
       Cout("Solução:").newline();

       // ciclo de apresentacao dos passos da solucao
       for(int index = 1; index < resultado.length; index++) {
           if (index % 2 == 1) {
               Cout(Integer.toString(index / 2));
               Cout(") Vão : ");
               switch (resultado[index].action) {
                   case 1: Cout("2 canibais + 0 missionários. "); break;
                   case 2: Cout("1 canibais + 0 missionários. "); break;
                   case 3: Cout("1 canibais + 1 missionários. "); break;
                   case 4: Cout("0 canibais + 1 missionários. "); break;
                   case 5: Cout("0 canibais + 2 missionários. "); break;
               }
           } else {
               Cout("Voltam : ");
               switch (resultado[index].action) {
                   case 1: Cout("2 canibais + 0 missionários. "); break;
                   case 2: Cout("1 canibais + 0 missionários. "); break;
                   case 3: Cout("1 canibais + 1 missionários. "); break;
                   case 4: Cout("0 canibais + 1 missionários. "); break;
                   case 5: Cout("0 canibais + 2 missionários. "); break;
               }
               Cout.newline();
           }
       }
   } else
       Cout("Não foi possível encontrar nenhuma solução").newline();

   Cout().newline();
   system("PAUSE"); // infelizmente fiz isto no Windows 
}

espero com este post ter apresentado uma "nova" linguagem de programação a muita gente 😄

Edited July 5, 2012 at 09:47 AM by HappyHippyHippo