Find solution to the Cannibals & Missioneries river crossing puzzle

cannibals-missioneries.py

# Cannibals & Missioneries solution finder
# https://archive.org/details/cannibals-missioneries

import sys
from enum import IntEnum
from typing import NamedTuple, Any
from collections.abc import Iterable, Iterator, Callable


class Side(IntEnum):
    LHS = -1
    RHS = +1


class Human(IntEnum):
    CANN = 1
    MISS = 2


class Map(NamedTuple):
    lhscann: int = 0
    lhsmiss: int = 0
    rhscann: int = 3
    rhsmiss: int = 3
    side: Side = Side.RHS


BEGIN_MAP = Map()
END_MAP = Map(3, 3, 0, 0, Side.LHS)


def trymove(miss: int, cann: int, map: Map = BEGIN_MAP) -> Map | None:
    side = map.side
    ohsnewcann = map[-side+Human.CANN] + cann
    ohsnewmiss = map[-side+Human.MISS] + miss
    chsnewcann = map[+side+Human.CANN] - cann
    chsnewmiss = map[+side+Human.MISS] - miss
    if (
        cann + miss <= 0 or cann + miss > 2
        or cann < 0 or cann > map[side+Human.CANN]
        or miss < 0 or miss > map[side+Human.MISS]
        or ohsnewcann > ohsnewmiss and ohsnewmiss != 0
        or chsnewcann > chsnewmiss and chsnewmiss != 0
    ):
        return None
    if side == Side.RHS:
        return Map(ohsnewcann, ohsnewmiss, chsnewcann, chsnewmiss, Side.LHS)
    return Map(chsnewcann, chsnewmiss, ohsnewcann, ohsnewmiss, Side.RHS)


MAYBE_VALID_MOVE = ((0, 1), (0, 2), (1, 0), (1, 1), (2, 0))


def main(steps: tuple[Map, ...] = (BEGIN_MAP,)) -> tuple[Map, ...] | None:
    last_step = steps[-1]
    if last_step == END_MAP:
        return steps
    for move in MAYBE_VALID_MOVE:
        trystep = trymove(*move, last_step)
        if trystep is None or trystep in steps:
            continue
        res = main(steps + (trystep,))
        if res is not None:
            return res
    return None


if __name__ == "__main__":
    steps = main()
    if steps is None:
        sys.exit(1)
    for i, (lhscann, lhsmiss, rhscann, rhsmiss, _) in enumerate(steps, 1):
        print(
            "[M]" * lhsmiss
            + "[ ]" * (3 - lhsmiss)
            + "\t"
            + "[ ]" * (3 - rhsmiss)
            + "[M]" * rhsmiss
        )
        print(
            "[C]" * lhscann
            + "[ ]" * (3 - lhscann)
            + "\t"
            + "[ ]" * (3 - rhscann)
            + "[C]" * rhscann
        )
        if i != len(steps):
            print()