# python 3.x – Killing a Hydra – Overengineered

### Background

This question is inspired by the question: Killing a hydra, and my response therein. I will restate the problem at hand in full so that this question is fully self contained

You can only kill off a given number of heads at each hit and
corresponding number of heads grow back. The heads will not grow back
if the hydra is left with zero heads. For example:

``````heads = (135)
hits = (25,67,1,62)
growths = (15,25,15,34)
``````

Then you can kill off `hits(i)` heads but `growths(i)` heads grow back.

The important restriction here is that:

you have to leave the Hydra with exactly zero heads to win.

My own restriction in this post is that I want to try to minimize the number of hits necessary to kill

### Algorithm

After some consideration I came up with the following strategy. Note: this strategy is not part of my answer on the original question.

1. The difficult part is leaving the Hydra with exactly zero heads. So in order to accomplish this I wrote a short code that generates all optimal ways to leave the Hydra 1 hit from death. This is used as a lookup table for small number of heads.

• To create the lookup table fast, we create iterate over all possible `diffs` up to a certain magnitude. A `diff` is simply the change in heads after a hit and a regrow.
We then create a dict of these `diffs`
Each `diff` has multiple keys associated with them, which represents the number of heads reachable with 1 hit from that `diff`.

Example

``````hits = (1, 25, 62, 67)
growths = (15, 15, 34, 25)
diff = (1, 4, 0, 0)
``````

This corresponds to the number `1 * (1 - 15) + 4 * (25 - 15) = 26`. Which means that after applying `diff` to the Hydra, the Hydra has `26` fewer heads remaining. This also means that a Hydra with `88` heads is dead after `diff` heads have been removed. Why? Because `88 - 26 = 67` and `67` is in hits. In other words we create a dict which looks like

``````hydra_dict = {26+1: diff, 26+25: diff, 26+62: diff, 26+67: diff}
``````
2. If our number of heads is greater than the largest value in our lookup dict,
we remove
values by picking the greatest `diff` and applying it `x` times to heads until we are in range. We overshoot a bit to make sure we are not at the very edge of our lookup dict.

3. If the number of heads lies in our `hydra_dict` we simply return this value.

4. Else we run a breadth first recursive search to either find a value in our dict, or a valid configuration of hits to kill the hydra.

#### Questions

I think I barely managed to make my code presentable, typing hints, using a class etc. However, my main issues is with the implementation

• How do I decide how big my lookup table should be? At the moment I just hardcoded that every `diff` can at most be `7`. I tried with a few lower values and a few higher, but not sure how I can properly find the best limit. Do my diff limits have to be of same length?
• How do I decide how deep my recursive algorithm should go? At the moment it is hardcoded to be the same value as the size of my lookup table, which works. However, for smaller lookup tables I seem to need to use a bigger depth. `10` seems to always return something proper, again not sure how to find the proper value.
• Instead of using a recursive solution I can “fill in the missing gaps” in my lookup table. This can be done by switching the switch`COMPLETE_HYDRA_DICT = False`. The benefits are that we always arrive at a lookup value after shaving off the too large values. The downside, is that it is resource heavy to fill in the table. Any thoughts?
• My recursive function returns the solution with the minimal sum. I tried writing a recursive function that returns the first solution instead. Is this better? From some rudimentary testing it appears that these two (the return first recursive, and return minimal sum recursive) returns mostly the same values with a big enough lookup table.
• Any other suggestions on improving the recursive function is welcome. I am not sure if it is possible to include any more early exits to speed up the code.

### Code

``````import itertools
from typing import Union

Head, Hit, Growth = int, int, int
HitGrowthDiff = Union(Hit, Growth)
HitGrowthDiffs = list(HitGrowthDiff)

MAX_LOOKUP = 7
RECURSIVE_DEPTH = MAX_LOOKUP
COMPLETE_HYDRA_DICT = False

class Hydra:
"""
Simulates a tic tac toe board using a 32 bit integer as state:
"""

def __init__(self, hits: Hits, growths: Growths, hydra_heads=0):
self._hits = hits
self._growths = growths
self.update_variables()

@property
def hits(self) -> Hits:
return self._hits

@hits.setter
def hits(self, hits):
self._hits = hits
self.update_variables()

@property
def growths(self) -> Growths:
return self._growths

@growths.setter
def growths(self, growths):
self._growths = growths
self.update_variables()

@property
def diffs(self) -> HitGrowthDiffs:
return self._diffs

@diffs.setter
def diffs(self, diffs):
self._diffs = diffs
self.update_variables()

@property

def update_variables(self) -> None:
hits = (0) * len(self.hits)
growths, diffs = hits.copy(), hits.copy()
for index, (hit, growth) in enumerate(
sorted(
zip(self.hits, self.growths),
key=lambda sub: sub(1) - sub(0),
reverse=True,
)
):
hits(index), growths(index), diffs(index) = hit, growth, hit - growth

self._hits, self._growths, self._diffs = hits, growths, diffs

self.generate_diffs_2_kill_hydra_lookup()
self.max_hydra = max(self.diffs_2_kill_)
self.max_diff = max(self.diffs)
self.max_diff_index = self.diffs.index(self.max_diff)

def generate_diffs_2_kill_hydra_lookup(
self,
limit: int = MAX_LOOKUP,
complete: bool = COMPLETE_HYDRA_DICT,
) -> None:
"""Generates a dictionary of optimal hit values for a large sample of heads"""
self.diffs_2_kill_ = dict()
for diffs_count in itertools.product(*(range(limit) for _ in self.diffs)):
hits = sum(d * count for d, count in zip(self.diffs, diffs_count))
if hits < 0:
continue
for final_hit in self.hits:
total_hits = hits + final_hit
if total_hits not in self.diffs_2_kill_:
self.diffs_2_kill_(total_hits) = list(diffs_count)
elif sum(self.diffs_2_kill_(total_hits)) > sum(diffs_count):
self.diffs_2_kill_(total_hits) = list(diffs_count)

if complete:
self.complete_diffs_2_kill_hydra_lookup()

def complete_diffs_2_kill_hydra_lookup(self) -> None:
"""Finds the missing head values in hydra_dict and fills them in manually"""
unreachable = sorted(
set(range(max(self.diffs_2_kill_) + 1)) - set(self.diffs_2_kill_.keys())
)
reachable_len = (0, 0)
print(reachable_len)

continue
self.diffs_2_kill_ = dict(
(
)
)

return sum(diff * number for diff, number in zip(self.diffs, number_of_hits))

"""Checks if Hydra is 1 hit away from death after n hits"""

def diffs_2_kill_iterative(
self,
nums: int = MAX_LOOKUP,
) -> HitGrowthDiffs:
"""Iterates over all possible number of hits, returns first 1 hit from death"""
for hydra_hits in itertools.product(*(range(nums) for _ in self.hits)):
return list(hydra_hits)
return ()

def diffs_2_kill(
self,
) -> None:
"""Low level function to check if a head is killable"""
extra_hits = (0) * len(self.diffs)
# Removes heads until we are in lookup range
times = int((head - self.max_hydra) / self.max_diff + 2)
extra_hits(self.max_diff_index) += times

else:
heads = list(hits + extra for hits, extra in zip(final_hits, extra_hits))
self.kill_hits = dict(zip(self.hits, self.number_of_diffs_2_kill))

def diffs_2_kill_recursive(
self,
diff: HitGrowthDiff = None,
new_hits: Hits = None,
diff_index: int = None,
depth: int = RECURSIVE_DEPTH,
) -> HitGrowthDiffs:
if new_hits is None:
new_hits = (0) * len(self.diffs)
if diff_index is not None:
new_hits(diff_index) += 1
return new_hits
hit + extra for hit, extra in zip(self.diffs_2_kill_(head), new_hits)
)
elif depth == 0:
return ()
elif (diff is None) or (diff < head):
return min(
(
final_diffs
for final_diffs in (
self.diffs_2_kill_recursive(
diff,
new_hits.copy(),
diff_index,
depth - 1,
)
for diff_index, diff in enumerate(self.diffs)
)
if final_diffs
),
key=sum,
)
return ()

def __str__(self):
width = 60
string = "=" * width + "n"
string += "n" + "=" * width

for index, number_of_hits in enumerate(self.number_of_diffs_2_kill):
hit, growth = self.hits(index), self.growths(index)

if number_of_hits < 6:
for _ in range(number_of_hits):
string += f"nWe kill {hit} heads of the hydra!"
string += f"nOh no! {growth} heads regrew!"
else:
string += f"nWe kill {hit} heads of the hydra!"
string += f"nOh no! {growth} heads regrew!"
string += "n      ." * 3
string += f"nThis is repeated {number_of_hits-2} times"
string += "n      ." * 3
head -= (hit - growth) * (number_of_hits - 2)
string += f"nWe kill {hit} heads of the hydra!"
string += f"nOh no! {growth} heads regrew!"

string += "n"
string += f"nWe kill {self.final_hit} heads of the hydra!"
string += "n The Hydra is dead!"
string += "n" + "~" * width + "n"
return string

def main():

heads = (88, 135, 192, 781, 98767893)
hits = (25, 67, 1, 62)
growths = (15, 25, 15, 34)

hydra = Hydra(hits, growths)