Resolução de Problemas - Canibais e Missionários

Afluentes: Inteligência Artificial

Estrutura de Dados

Estrutura de Dados do problema dos Canibais e Missionários

LadoEsquerdo (
	Canibais = inteiro
	Missionarios = inteiro
	Canoa = booleano
)

Na forma de Vetor:

(C, M, J)
(3, 3, T)

Observações:

• C = Canibais
• M = Missinários
• J = Jangada (não deu pra colocar C de Canoa)
  • T (ou True), a canoa está do lado esquerdo, se do lado direito, então F (False)
• Para saber como está do lado direito, basta calcular:
  • C2 = 3 - C
  • M2 = 3 - M
  • e J = F

Restrições

• Max2 - Máximo de passageiros na canoa é 2 pessoas
• !C>M - Nao pode ter mais canibais que missionários
• 1P - Mínimo de passageiros numa canoa é 1 pessoa

Regras / Métodos

• 1MD - Transportar 1 Missionário para a direita
• 2MD - Transportar 2 Missionários para a direita
• 1CD - Transportar 1 Canibal para a direita
• 2CD - Transportar 2 Canibais para a direita
• CMD - Transportar 1 Canibal e 1 Missionário para a direita
• 1ME - Transportar 1 Missionário para a esquerda
• 2ME - Transportar 2 Missionários para a esquerda
• 1CE - Transportar 1 Canibal para a esquerda
• 2CE - Transportar 2 Canibais para a esquerda
• CME - Transportar 1 Canibal e 1 Missionário para a esquerda

Teste de Mesa e Estados

0. (3, 3, 1, 0, 0, 0) - CMD
1. (2, 2, 0, 1, 1, 1) - 1ME
2. (2, 3, 1, 1, 0, 0) - 2CD
3. (0, 3, 0, 3, 0, 1) - 1CE
4. (1, 3, 1, 2, 0, 0) - 2MD
5. (1, 1, 0, 2, 2, 1) - CME
6. (2, 2, 1, 1, 1, 0) - 2MD
7. (2, 0, 0, 1, 3, 1) - 1CE
8. (3, 0, 1, 0, 3, 0) - 2CD
9. (1, 0, 0, 2, 3, 1) - 1CE
10.(2, 0, 1, 1, 3, 0) - 2CD
11.(0, 0, 0, 3, 3, 1)

Algoritmo

Principal

Inicio
	Enquanto Não TERMINOU Fazer
		Operação = LerDoTeclado
		Se VALIDA(Operacao) Entao
			Se Operacao == 1M-AB Então
				LadoA.Missionario--
				LadoB.Missionario++
				LadoA.Canoa = Falso
				LadoB.Canoa = Verdadeiro
			Senão
				... // Demais operações
			Fim Se
		Fim Se
	Fim Enquanto
Fim

TERMINOU

Inicio
	Se (LadoB.Canibais == 3) e (LadoB.Missionarios == 3) Então
		Retorna Verdadeiro
	Senão
		Retorna Falso
	Fim Se
Fim

VALIDA

Inicio (operação)
	Se (operacao == 1M-AB) Então
		Se LadoA.Missionarios == 0 Então
			Retorna Falso
		Fim Se
		Se (LadoA.Missionarios - 1 < LadoA.Canibais) Então
			Retorna Falso
		Fim Se
	Senão
		... // Demais Operações
	Fim Se
	Retorna Verdadeiro
Fim

Programa

Programa em Python com base na Estrutura de Dados definida e algoritmos apresentados.

passo = 0
estado = (3, 3, True)


def mover(estado_atual, canibais, missionarios):
    global passo
    C, M, L = estado_atual

    # Direção da travessia:
    # -1 se for da esquerda para a direita,
    # +1 se da direita para a esquerda
    direcao = -1 if L else 1

    # Atualiza canibais e missionários do lado esquerdo
    C += direcao * canibais
    M += direcao * missionarios

    # Inverte lado da canoa
    L = not L

    passo += 1
    imprimir_estado((C, M, L))

    return C, M, L


def estado_valido(estado):
    C, M, _ = estado
    C2 = 3 - C
    M2 = 3 - M

    # Nenhum número pode ser negativo ou maior que 3
    if not (0 <= C <= 3 and 0 <= M <= 3):
        return False, False
    if not (0 <= C2 <= 3 and 0 <= M2 <= 3):
        return False, False

    # Missionários nunca podem ser menos que canibais,
    # nos dois lados (se tiver missionários)
    if M > 0 and C > M:
        return False, False
    if M2 > 0 and C2 > M2:
        return False, False

    if C == 0 and M == 0:
        return True, True

    return True, False


def imprimir_estado(estado_atual):
    global passo
    C, M, L = estado_atual
    lado = r"\___/          " if L else r"          \___/"
    print(f"{passo:2}. Esquerda: {C}C, {M}M", end=" ")
    print(f"| {lado}", end=" ")
    print(f"| Direita: {3 - C}C, {3 - M}M", end=" ")
    valido, objetivo = estado_valido(estado_atual)
    print("|", "valido" if valido else "invalido", end="")
    print(", Objetivo Alcançado..." if objetivo else "")


imprimir_estado(estado)
estado = mover(estado, 1, 1)
estado = mover(estado, 0, 1)
estado = mover(estado, 2, 0)
estado = mover(estado, 1, 0)
estado = mover(estado, 0, 2)
estado = mover(estado, 1, 1)
estado = mover(estado, 0, 2)
estado = mover(estado, 1, 0)
estado = mover(estado, 2, 0)
estado = mover(estado, 1, 0)
estado = mover(estado, 2, 0)

Saída:

 0. Esquerda: 3C, 3M | \___/           | Direita: 0C, 0M | valido
 1. Esquerda: 2C, 2M |           \___/ | Direita: 1C, 1M | valido
 2. Esquerda: 2C, 3M | \___/           | Direita: 1C, 0M | valido
 3. Esquerda: 0C, 3M |           \___/ | Direita: 3C, 0M | valido
 4. Esquerda: 1C, 3M | \___/           | Direita: 2C, 0M | valido
 5. Esquerda: 1C, 1M |           \___/ | Direita: 2C, 2M | valido
 6. Esquerda: 2C, 2M | \___/           | Direita: 1C, 1M | valido
 7. Esquerda: 2C, 0M |           \___/ | Direita: 1C, 3M | valido
 8. Esquerda: 3C, 0M | \___/           | Direita: 0C, 3M | valido
 9. Esquerda: 1C, 0M |           \___/ | Direita: 2C, 3M | valido
10. Esquerda: 2C, 0M | \___/           | Direita: 1C, 3M | valido
11. Esquerda: 0C, 0M |           \___/ | Direita: 3C, 3M | valido, Objetivo Alcançado...