quintars.py

"""
This script finds the minimal number of steps required to breed a golden
quintar, given an initial stable state.

Note that, due to its multi-threaded nature, there is a very small but finite
probability it does not return a minimal solution, but it will be at most one
step away from a minimal one. Also note that this script considers things like
releasing quintar or obtaining them from the game world steps; finding the
minimal number of breeding steps or the minimal number of quintar races required
would take considerably higher computing power.

To run this script, you need some Python packages to be installed:
    pip install intbitset
"""


import enum
import multiprocessing
import typing
import intbitset


class QuintarType(enum.Enum):
    RED = 1
    BLUE = 2
    DESERT = 3
    HIGHLAND = 4
    RIVER = 5
    BLACK = 6
    AQUA = 7
    GOLD = 8

    def __str__(self) -> str:
        return self.name


class QuintarNature(enum.Enum):
    FIENDISH = 1
    BRUTISH = 2
    WOKE = 3
    FANCY = 4
    TRUSTY = 5

    def __str__(self) -> str:
        return self.name


class Quintar(typing.NamedTuple):
    type: QuintarType
    nature: QuintarNature

    def __str__(self) -> str:
        return f"{self.type} {self.nature}"


def can_breed(q1: Quintar, q2: Quintar) -> bool:
    return q1.nature != q2.nature


def combine_natures(n1: QuintarNature, n2: QuintarNature) -> QuintarNature:
    if n1 == n2:
        return n1
    elif n1 == QuintarNature.FIENDISH or n1 == QuintarNature.BRUTISH:
        if n2 == QuintarNature.TRUSTY:
            return n1
        else:
            return n2
    elif n2 == QuintarNature.FIENDISH or n2 == QuintarNature.BRUTISH:
        if n1 == QuintarNature.TRUSTY:
            return n2
        else:
            return n1
    elif {n1, n2} == {QuintarNature.FANCY, QuintarNature.WOKE}:
        return QuintarNature.BRUTISH
    elif {n1, n2} == {QuintarNature.FANCY, QuintarNature.TRUSTY}:
        return QuintarNature.WOKE
    elif {n1, n2} == {QuintarNature.WOKE, QuintarNature.TRUSTY}:
        return QuintarNature.FANCY
    else:
        raise Exception(f"Unknown nature combination: {n1} and {n2}")


def breed(q1: Quintar, q2: Quintar) -> Quintar:
    # brutish takes own type and other's nature UNLESS they're Trusty
    # brutish takes priority over fiendish
    if q1.nature == QuintarNature.BRUTISH:
        if q2.nature == QuintarNature.TRUSTY:
            return Quintar(q1.type, q1.nature)
        else:
            return Quintar(q1.type, q2.nature)
    elif q2.nature == QuintarNature.BRUTISH:
        if q1.nature == QuintarNature.TRUSTY:
            return Quintar(q2.type, q2.nature)
        else:
            return Quintar(q2.type, q1.nature)

    # fiendish always clones the other parent UNLESS they're Trusty
    elif q1.nature == QuintarNature.FIENDISH:
        if q1.nature == QuintarNature.TRUSTY:
            return Quintar(q2.type, q1.nature)
        else:
            return Quintar(q2.type, q2.nature)
    elif q2.nature == QuintarNature.FIENDISH:
        if q1.nature == QuintarNature.TRUSTY:
            return Quintar(q1.type, q2.nature)
        else:
            return Quintar(q1.type, q1.nature)

    # red + blue = highland (if one parent is fancy)
    elif {q1.type, q2.type} == {
        QuintarType.RED,
        QuintarType.BLUE,
    } and QuintarNature.FANCY in {q1.nature, q2.nature}:
        return Quintar(QuintarType.HIGHLAND, combine_natures(q1.nature, q2.nature))

    # desert fancy + river X = black Y
    elif (
        q1.nature == QuintarNature.FANCY
        and q1.type == QuintarType.DESERT
        and q2.type == QuintarType.RIVER
    ):
        return Quintar(QuintarType.BLACK, combine_natures(q1.nature, q2.nature))
    elif (
        q2.nature == QuintarNature.FANCY
        and q2.type == QuintarType.DESERT
        and q1.type == QuintarType.RIVER
    ):
        return Quintar(QuintarType.BLACK, combine_natures(q1.nature, q2.nature))

    # highland fancy + river X = aqua Y
    elif (
        q1.nature == QuintarNature.FANCY
        and q1.type == QuintarType.HIGHLAND
        and q2.type == QuintarType.RIVER
    ):
        return Quintar(QuintarType.AQUA, combine_natures(q1.nature, q2.nature))
    elif (
        q2.nature == QuintarNature.FANCY
        and q2.type == QuintarType.HIGHLAND
        and q1.type == QuintarType.RIVER
    ):
        return Quintar(QuintarType.AQUA, combine_natures(q1.nature, q2.nature))

    # black + aqua = gold (if one parent is fancy)
    elif {q1.type, q2.type} == {
        QuintarType.BLACK,
        QuintarType.AQUA,
    } and QuintarNature.FANCY in {q1.nature, q2.nature}:
        return Quintar(QuintarType.GOLD, combine_natures(q1.nature, q2.nature))

    # default case: the least valuable type among the two
    else:
        if (
            q1.nature.value > q2.nature.value
        ):  # TODO: is this right? not mentioned by any duck
            new_type = q1.type
        else:
            new_type = q2.type
        return Quintar(
            new_type,
            combine_natures(q1.nature, q2.nature),
        )


OBTAINABLE_IN_WORLD = {
    Quintar(QuintarType.BLUE, QuintarNature.FIENDISH),
    Quintar(QuintarType.RED, QuintarNature.TRUSTY),
    Quintar(QuintarType.RIVER, QuintarNature.WOKE),
    Quintar(QuintarType.BLUE, QuintarNature.TRUSTY),
    Quintar(QuintarType.RED, QuintarNature.WOKE),
    Quintar(QuintarType.DESERT, QuintarNature.BRUTISH),
    Quintar(QuintarType.DESERT, QuintarNature.FIENDISH),
}
MAX_QUINAR_SLOTS = 8
EMPTY_SLOTS = (None,) * MAX_QUINAR_SLOTS
NUMBER_THREADS = multiprocessing.cpu_count()
QuintarSlots = typing.Tuple[typing.Optional[Quintar], ...]


class ActionObtainInWorld(typing.NamedTuple):
    quintar: Quintar

    def act(self, slots: QuintarSlots) -> QuintarSlots:
        free_index = slots.index(None)
        assert free_index >= 0
        return tuple(
            (self.quintar if i == free_index else v) for i, v in enumerate(slots)
        )

    def __str__(self) -> str:
        return f"obtain {self.quintar} from world"


class ActionRelease(typing.NamedTuple):
    quintar: Quintar

    def act(self, slots: QuintarSlots) -> QuintarSlots:
        full_index = slots.index(self.quintar)
        assert full_index >= 0
        return tuple((None if i == full_index else v) for i, v in enumerate(slots))

    def __str__(self) -> str:
        return f"release {self.quintar}"


class ActionBreed(typing.NamedTuple):
    quintar1: Quintar
    quintar2: Quintar

    def act(self, slots: QuintarSlots) -> QuintarSlots:
        free_index = slots.index(None)
        assert free_index >= 0
        return tuple(
            (breed(self.quintar1, self.quintar2) if i == free_index else v)
            for i, v in enumerate(slots)
        )

    def __str__(self) -> str:
        return f"breed {self.quintar1} with {self.quintar2} (making {breed(self.quintar1, self.quintar2)})"


Action = typing.Union[ActionObtainInWorld, ActionRelease, ActionBreed]


def quintar_slots_after(
    slots: QuintarSlots, actions: typing.Iterable[Action]
) -> QuintarSlots:
    for action in actions:
        slots = action.act(slots)
    return slots


def possible_next_steps(slots: QuintarSlots) -> typing.Iterable[Action]:
    if any(v is None for v in slots):
        for q1 in slots:
            for q2 in slots:
                if (
                    q1 is not None
                    and q2 is not None
                    and can_breed(q1, q2)
                    and breed(q1, q2) not in slots
                ):
                    yield ActionBreed(q1, q2)
        for quintar in OBTAINABLE_IN_WORLD:
            if quintar not in slots:
                yield ActionObtainInWorld(quintar)
    if all(v is not None for v in slots):
        for q in slots:
            if q is not None:
                yield ActionRelease(q)


def intbitset_hash(value: typing.Hashable):
    return hash(value) % intbitset.__maxelem__


def search_process(
    process_no: int,
    initial_slots: QuintarSlots,
    solutions: "multiprocessing.Queue[typing.Tuple[Action, ...]]",
    result: "multiprocessing.Queue[typing.Tuple[Action, ...]]",
):
    visited: intbitset.intbitset = intbitset.intbitset()
    while True:
        steps = solutions.get(True)
        # print(
        #     f"[{process_no}] got {len(steps)} steps ending in: {steps[-1] if len(steps) > 0 else None}"
        # )

        # cycle checking
        slots_after = quintar_slots_after(initial_slots, steps)
        slots_set_hash = intbitset_hash(
            frozenset(q for q in slots_after if q is not None)
        )
        if slots_set_hash in visited:
            continue
        else:
            visited.add(slots_set_hash)
        # success
        if any(q is not None and q.type == QuintarType.GOLD for q in slots_after):
            result.put(steps)
        # recursion
        for next_step in possible_next_steps(slots_after):
            if (
                intbitset_hash(
                    frozenset(q for q in next_step.act(slots_after) if q is not None)
                )
                not in visited
            ):
                solutions.put_nowait(steps + (next_step,))


def search(
    slots: QuintarSlots = EMPTY_SLOTS,
) -> typing.Tuple[Action, ...]:

    with multiprocessing.Manager() as manager:
        solutions = manager.Queue()
        solutions.put((), True)
        result = manager.Queue(1)

        processes = [
            multiprocessing.Process(
                target=search_process, args=(i, slots, solutions, result)
            )
            for i in range(NUMBER_THREADS)
        ]
        for process in processes:
            process.start()
        return result.get(True)


if __name__ == "__main__":
    multiprocessing.freeze_support()
    print(
        "\n".join(
            str(step)
            for step in search(
                # if you already have some quintars, fill them in below and uncomment the following lines:
                # (
                #     Quintar(QuintarType.EXAMPLE, QuintarNature.EXAMPLE), # slot filled with Quintar
                #     None, # slot not filled with Quintar
                #     None,
                #     None,
                #     None,
                #     None,
                #     None,
                #     None,
                # )
            )
        )
    )

solution.txt

Here is a solution for breeding a gold quintar with an initially empty stable:

obtain RIVER WOKE from world
obtain BLUE TRUSTY from world
breed RIVER WOKE with BLUE TRUSTY (making BLUE FANCY)
obtain RED WOKE from world
breed BLUE FANCY with RED WOKE (making HIGHLAND BRUTISH)
breed BLUE FANCY with HIGHLAND BRUTISH (making HIGHLAND FANCY)
breed RIVER WOKE with HIGHLAND FANCY (making AQUA BRUTISH)
breed RIVER WOKE with AQUA BRUTISH (making AQUA WOKE)
release BLUE TRUSTY
obtain DESERT BRUTISH from world
release BLUE FANCY
breed DESERT BRUTISH with HIGHLAND FANCY (making DESERT FANCY)
release DESERT BRUTISH
breed RIVER WOKE with DESERT FANCY (making BLACK BRUTISH)
release RIVER WOKE
breed BLACK BRUTISH with DESERT FANCY (making BLACK FANCY)
release BLACK BRUTISH
breed BLACK FANCY with AQUA WOKE (making GOLD BRUTISH)