Skip to content

Instantly share code, notes, and snippets.

@iconmaster5326

iconmaster5326/quintars.py

Last active April 28, 2022 00:26
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save iconmaster5326/b77d9878dcd91549ba053ba32ae81cbf to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save iconmaster5326/b77d9878dcd91549ba053ba32ae81cbf to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. iconmaster5326 revised this gist Apr 28, 2022. 1 changed file with 13 additions and 13 deletions.
    26 changes: 13 additions & 13 deletions solution.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -1,20 +1,20 @@
    Here is a solution for breeding a gold quintar with an initially empty stable:

    obtain DESERT BRUTISH from world
    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 TRUSTY with RED WOKE (making BLUE FANCY)
    breed DESERT BRUTISH with BLUE FANCY (making DESERT FANCY)
    breed RED WOKE with BLUE FANCY (making HIGHLAND BRUTISH)
    breed BLUE FANCY with RED WOKE (making HIGHLAND BRUTISH)
    breed BLUE FANCY with HIGHLAND BRUTISH (making HIGHLAND FANCY)
    obtain RIVER WOKE from world
    release DESERT BRUTISH
    breed DESERT FANCY with RIVER WOKE (making BLACK BRUTISH)
    breed RIVER WOKE with HIGHLAND FANCY (making AQUA BRUTISH)
    breed RIVER WOKE with AQUA BRUTISH (making AQUA WOKE)
    release BLUE TRUSTY
    breed BLACK BRUTISH with RED WOKE (making BLACK WOKE)
    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 HIGHLAND FANCY with RIVER WOKE (making AQUA BRUTISH)
    release RED WOKE
    breed AQUA BRUTISH with BLUE FANCY (making AQUA FANCY)
    release AQUA BRUTISH
    breed BLACK WOKE with AQUA FANCY (making GOLD BRUTISH)
    breed BLACK FANCY with AQUA WOKE (making GOLD BRUTISH)
  2. iconmaster5326 revised this gist Apr 27, 2022. 1 changed file with 9 additions and 7 deletions.
    16 changes: 9 additions & 7 deletions quintars.py
    View file
    Original file line number Diff line number Diff line change
    @@ -13,18 +13,17 @@
    pip install intbitset
    """


    import enum
    import multiprocessing
    import typing
    import intbitset


    class QuintarType(enum.Enum):
    RED = (
    1 # TODO: what is relative ordering of red and blue? not mentioned by any duck
    )
    RED = 1
    BLUE = 2
    DESERT = 3 # TODO: what is relative ordering of desert? not mentioned by any duck
    DESERT = 3
    HIGHLAND = 4
    RIVER = 5
    BLACK = 6
    @@ -151,9 +150,12 @@ def breed(q1: Quintar, q2: Quintar) -> Quintar:

    # default case: the least valuable type among the two
    else:
    new_type = min(
    q1.type, q2.type, key=(lambda x: x.value)
    ) # TODO: is this right? not mentioned by any duck
    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),
  3. iconmaster5326 revised this gist Apr 27, 2022. 1 changed file with 14 additions and 2 deletions.
    16 changes: 14 additions & 2 deletions quintars.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,17 @@
    # To run this script, you need some Python packages to be installed:
    # pip install intbitset
    """
    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
  4. iconmaster5326 revised this gist Apr 27, 2022. 1 changed file with 17 additions and 6 deletions.
    23 changes: 17 additions & 6 deletions quintars.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,10 @@
    # To run this script, you need some Python packages to be installed:
    # pip install intbitset

    import enum
    import multiprocessing
    import threading
    import typing
    import intbitset


    class QuintarType(enum.Enum):
    @@ -233,13 +236,17 @@ def possible_next_steps(slots: QuintarSlots) -> typing.Iterable[Action]:
    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: typing.Dict[typing.FrozenSet[Quintar], typing.Literal[True]] = {}
    visited: intbitset.intbitset = intbitset.intbitset()
    while True:
    steps = solutions.get(True)
    # print(
    @@ -248,18 +255,22 @@ def search_process(

    # cycle checking
    slots_after = quintar_slots_after(initial_slots, steps)
    slots_set = frozenset(q for q in slots_after if q is not None)
    if slots_set in visited:
    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[slots_set] = True
    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 (
    frozenset(q for q in next_step.act(slots_after) if q is not None)
    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,))
  5. iconmaster5326 revised this gist Apr 27, 2022. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion quintars.py
    View file
    Original file line number Diff line number Diff line change
    @@ -262,7 +262,7 @@ def search_process(
    frozenset(q for q in next_step.act(slots_after) if q is not None)
    not in visited
    ):
    solutions.put(steps + (next_step,), True)
    solutions.put_nowait(steps + (next_step,))


    def search(
  6. iconmaster5326 revised this gist Apr 27, 2022. 1 changed file with 75 additions and 39 deletions.
    114 changes: 75 additions & 39 deletions quintars.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,12 +1,16 @@
    import enum
    import multiprocessing
    import threading
    import typing


    class QuintarType(enum.Enum):
    RED = 1 # TODO: what is relative ordering of red and blue? not mentioned by any duck
    RED = (
    1 # TODO: what is relative ordering of red and blue? not mentioned by any duck
    )
    BLUE = 2
    HIGHLAND = 3
    DESERT = 4 # TODO: what is relative ordering of desert? not mentioned by any duck
    DESERT = 3 # TODO: what is relative ordering of desert? not mentioned by any duck
    HIGHLAND = 4
    RIVER = 5
    BLACK = 6
    AQUA = 7
    @@ -132,7 +136,9 @@ def breed(q1: Quintar, q2: Quintar) -> Quintar:

    # default case: the least valuable type among the two
    else:
    new_type = min(q1.type, q2.type, key=(lambda x: x.value)) # TODO: is this right? not mentioned by any duck
    new_type = min(
    q1.type, q2.type, key=(lambda x: x.value)
    ) # TODO: is this right? not mentioned by any duck
    return Quintar(
    new_type,
    combine_natures(q1.nature, q2.nature),
    @@ -150,6 +156,7 @@ def breed(q1: Quintar, q2: Quintar) -> Quintar:
    }
    MAX_QUINAR_SLOTS = 8
    EMPTY_SLOTS = (None,) * MAX_QUINAR_SLOTS
    NUMBER_THREADS = multiprocessing.cpu_count()
    QuintarSlots = typing.Tuple[typing.Optional[Quintar], ...]


    @@ -222,50 +229,79 @@ def possible_next_steps(slots: QuintarSlots) -> typing.Iterable[Action]:
    yield ActionObtainInWorld(quintar)
    if all(v is not None for v in slots):
    for q in slots:
    yield ActionRelease(q)

    if q is not None:
    yield ActionRelease(q)


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

    def search(
    slots: QuintarSlots = EMPTY_SLOTS,
    ) -> typing.Optional[typing.Tuple[Action, ...]]:
    solutions: typing.List[typing.Tuple[Action, ...]] = [()]
    visited: typing.Set[typing.FrozenSet[Quintar]] = set()
    while len(solutions) > 0:
    # cycle checking
    steps = solutions.pop(0)
    slots_after = quintar_slots_after(slots, steps)
    slots_after = quintar_slots_after(initial_slots, steps)
    slots_set = frozenset(q for q in slots_after if q is not None)
    if slots_set in visited:
    continue
    else:
    visited.add(slots_set)
    visited[slots_set] = True
    # success
    if any(q is not None and q.type == QuintarType.GOLD for q in slots_after):
    return steps
    result.put(steps)
    # recursion
    for next_step in possible_next_steps(slots_after):
    # print(f"[{len(steps)}] {next_step}")
    solutions.append(steps + (next_step,))
    # failure
    return None


    print(
    ", ".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,
    # )
    if (
    frozenset(q for q in next_step.act(slots_after) if q is not None)
    not in visited
    ):
    solutions.put(steps + (next_step,), True)


    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,
    # )
    )
    )
    or ("no solution found",)
    )
    )
  7. iconmaster5326 revised this gist Apr 27, 2022. 1 changed file with 7 additions and 6 deletions.
    13 changes: 7 additions & 6 deletions quintars.py
    View file
    Original file line number Diff line number Diff line change
    @@ -3,11 +3,11 @@


    class QuintarType(enum.Enum):
    RED = 1
    RED = 1 # TODO: what is relative ordering of red and blue? not mentioned by any duck
    BLUE = 2
    DESERT = 3
    RIVER = 4
    HIGHLAND = 5
    HIGHLAND = 3
    DESERT = 4 # TODO: what is relative ordering of desert? not mentioned by any duck
    RIVER = 5
    BLACK = 6
    AQUA = 7
    GOLD = 8
    @@ -130,10 +130,11 @@ def breed(q1: Quintar, q2: Quintar) -> Quintar:
    } and QuintarNature.FANCY in {q1.nature, q2.nature}:
    return Quintar(QuintarType.GOLD, combine_natures(q1.nature, q2.nature))

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

  8. iconmaster5326 revised this gist Apr 27, 2022. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion solution.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,6 @@
    obtain DESERT BRUTISH from world
    Here is a solution for breeding a gold quintar with an initially empty stable:

    obtain DESERT BRUTISH from world
    obtain BLUE TRUSTY from world
    obtain RED WOKE from world
    breed BLUE TRUSTY with RED WOKE (making BLUE FANCY)
  9. iconmaster5326 created this gist Apr 27, 2022.
    270 changes: 270 additions & 0 deletions quintars.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,270 @@
    import enum
    import typing


    class QuintarType(enum.Enum):
    RED = 1
    BLUE = 2
    DESERT = 3
    RIVER = 4
    HIGHLAND = 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 most valuable type among the two
    else:
    return Quintar(
    max(q1.type, q2.type, key=(lambda x: x.value)),
    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
    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:
    yield ActionRelease(q)


    def search(
    slots: QuintarSlots = EMPTY_SLOTS,
    ) -> typing.Optional[typing.Tuple[Action, ...]]:
    solutions: typing.List[typing.Tuple[Action, ...]] = [()]
    visited: typing.Set[typing.FrozenSet[Quintar]] = set()
    while len(solutions) > 0:
    # cycle checking
    steps = solutions.pop(0)
    slots_after = quintar_slots_after(slots, steps)
    slots_set = frozenset(q for q in slots_after if q is not None)
    if slots_set in visited:
    continue
    else:
    visited.add(slots_set)
    # success
    if any(q is not None and q.type == QuintarType.GOLD for q in slots_after):
    return steps
    # recursion
    for next_step in possible_next_steps(slots_after):
    # print(f"[{len(steps)}] {next_step}")
    solutions.append(steps + (next_step,))
    # failure
    return None


    print(
    ", ".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,
    # )
    )
    or ("no solution found",)
    )
    )
    20 changes: 20 additions & 0 deletions solution.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,20 @@
    obtain DESERT BRUTISH from world
    Here is a solution for breeding a gold quintar with an initially empty stable:

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