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
Raw
quintars.py
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
)
BLUE = 2
DESERT = 3 # TODO: what is relative ordering of desert? not mentioned by any duck
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:
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),
)
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 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}"
# )
# 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:
continue
else:
visited[slots_set] = True
# 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)
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,
# )
)
)
)
Raw
solution.txt
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)
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment