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 butgrowths(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.

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. Adiff
is simply the change in heads after a hit and a regrow.
We then create a dict of thesediffs
Eachdiff
has multiple keys associated with them, which represents the number of heads reachable with 1 hit from thatdiff
.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 applyingdiff
to the Hydra, the Hydra has26
fewer heads remaining. This also means that a Hydra with88
heads is dead afterdiff
heads have been removed. Why? Because88  26 = 67
and67
is in hits. In other words we create a dict which looks likehydra_dict = {26+1: diff, 26+25: diff, 26+62: diff, 26+67: diff}


If our number of heads is greater than the largest value in our lookup dict,
we remove
values by picking the greatestdiff
and applying itx
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. 
If the number of heads lies in our
hydra_dict
we simply return this value. 
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 be7
. 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
Heads, Hits, Growths = list(Head), list(Hit), list(Growth)
HitGrowthDiff = Union(Hit, Growth)
HitGrowthDiffs = list(HitGrowthDiff)
HydraDict = dict(Head, HitGrowthDiffs)
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()
if hydra_heads > 0:
self._heads = hydra_heads
@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 head(self) > Head:
return self._head
@head.setter
def head(self, head):
self._head = head
self.diffs_2_kill(head)
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)
for head, next_head in zip(unreachable(:1), unreachable(1:)):
if next_head  head > reachable_len(1)  reachable_len(0):
reachable_len = (head, next_head)
print(reachable_len)
for head in range(1, reachable_len(0)):
if head in self.diffs_2_kill_:
continue
self.diffs_2_kill_(head) = self.diffs_2_kill_iterative(head)
self.diffs_2_kill_ = dict(
(
(head, kill)
for head, kill in self.diffs_2_kill_.items()
if head < reachable_len(1)
)
)
def heads_removed(self, number_of_hits: list(int)) > Head:
return sum(diff * number for diff, number in zip(self.diffs, number_of_hits))
def is_hydra_one_hit_from_death(self, total_heads: Head, number_of_hits) > bool:
"""Checks if Hydra is 1 hit away from death after n hits"""
heads_left = total_heads  self.heads_removed(number_of_hits)
return heads_left in self.hits
def diffs_2_kill_iterative(
self,
head: Head,
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)):
if self.is_hydra_one_hit_from_death(head, list(hydra_hits)):
return list(hydra_hits)
return ()
def diffs_2_kill(
self,
head: Head,
) > 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
if head > self.max_hydra:
times = int((head  self.max_hydra) / self.max_diff + 2)
head = times * self.max_diff
extra_hits(self.max_diff_index) += times
if head in self.diffs_2_kill_:
final_hits = self.diffs_2_kill_(head)
else:
final_hits = self.diffs_2_kill_recursive(head)
heads = list(hits + extra for hits, extra in zip(final_hits, extra_hits))
self.final_hit = self.head  self.heads_removed(heads)
self.number_of_diffs_2_kill = heads
self.kill_hits = dict(zip(self.hits, self.number_of_diffs_2_kill))
def diffs_2_kill_recursive(
self,
head: Head,
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
if head == 0:
return new_hits
elif head in self.diffs_2_kill_:
heads_ = (
hit + extra for hit, extra in zip(self.diffs_2_kill_(head), new_hits)
)
return heads_
elif depth == 0:
return ()
elif (diff is None) or (diff < head):
return min(
(
final_diffs
for final_diffs in (
self.diffs_2_kill_recursive(
head  diff,
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 += f"Hydra heads: {self.head}".center(width)
string += "n" + "=" * width
head = self.head
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!"
head = hit  growth
string += f"n {head} heads remain!"
else:
string += f"nWe kill {hit} heads of the hydra!"
string += f"nOh no! {growth} heads regrew!"
head = hit  growth
string += f"n {head} heads remain!"
string += "n ." * 3
string += f"nThis is repeated {number_of_hits2} 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!"
head = hit  growth
string += f"n {head} heads remain!"
string += "n"
string += f"nWe kill {self.final_hit} heads of the hydra!"
head = self.final_hit
if head == 0:
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)
for head in heads:
hydra.head = head
print(hydra)
if __name__ == "__main__":
main()