# Killing a hydra

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. My approach is to randomise the index of hits each time and it works but I don't think this is too efficient. Of course the time taken varies for every different array of hits, growths. We have to determine if the hydra is killable for a given limit on iterations.

from timeit import default_timer as timer

start = timer()

import random
import time

hits = [25,67,1,62]
growths = [15,25,15,34]

def hydra_killing():

iter_limit = 1000

iters = 0           #Resets iters at every new 'hydra'
iters += 1

if iters == iter_limit:
print("NO")
break
else:
i = random.randint(0,3)         #Randomly choose a hit value

print(f'''
YES...............................................{iters}

''')
else:

else:
iters -= 1 #if the heads remaining are greater than
#hits[i], then this iteration is not counted

hydra_killing()

end = timer()
print(end - start, " seconds")


• Can you overkill a hydra? If the hydra has 20 heads can you cut off 26? Jun 25, 2021 at 5:43
• imo no you can't
– sato
Jun 25, 2021 at 5:58
• if the heads remaining are greater than hits[i], then we regenerate an i and that 'try' is not counted
– sato
Jun 25, 2021 at 6:00
• Try Lee algorithm. Imagine you're in a snakes-and-ladders labyrinth, with hydra head count is a cell number and possible moves are growth[i]-hits[i]. en.m.wikipedia.org/wiki/Lee_algorithm Jun 25, 2021 at 6:14
• 'It always gives an optimal solution, if one exists, but <<is slow and requires considerable memory>>'
– sato
Jun 25, 2021 at 6:15

### Code feedback

• Use a linter! You have many inconsistencies in your code that suggests you are not using any type of autoformater for your code. This is strongly suggested. I like to use black, but there are many other variants.
• Structure your code using functions
• Remove unused imports using imports.
• Time only the relevant parts.
• Split the print from the hits

Using the bullet points above a starting point for improving your code looks like this

from timeit import default_timer as timer
import random

growths_ = dict(zip(hits, growths))

iters = 0
while (iters := iters + 1) < iter_limit:
hit = random.choice(hits)
continue
return True, iters

return False, iter_limit

if __name__ == "__main__":

heads = [88, 135, 192, 152]
hits = [25, 67, 1, 62]
growths = [15, 25, 15, 34]

start = timer()
end = timer()
print(end - start, " seconds")


Alternatively we could try a smaller hit value instead of calling continue. This would look like this

def hydra_killing(head, hits, growths, iter_limit=1000):
growths_ = dict(zip(hits, growths))

iters = 0
while (iters := iters + 1) < iter_limit:
hit = random.choice(hits)
if small_hits := [hit for hit in hits if hit < head]:
hit = random.choice(small_hits)
else:
return False, iters
return True, iters

return False, iter_limit


It will reduce the number of iterations quite a bit, but if this is something you want to implement is up to you. The return statement in the code above is added if for instance the hydra has 2 heads left, and we can only kill 3 or more heads. Then the hydra is not killable, and we return.

### Suggestion 1 [We only want to know if the Hydra can be killed!]

So you have a very good starting point! Randomly picking a number of heads to kill is not a bad idea! However, to improve upon the code we need to introduce a few early exits.

• If head is in hits we return. This one is simple enough, if the hydra can be killed on the next turn, we return.

• What if hit - growth is in hits? Concretely if heads = 72, diff := hit - growth = 25 - 15 = 10 then we _know the hydra is killable on the next turn. Because heads - diff = 62 and 62 is in hits.

• Similarly we can remove diff over and over again until we reach hit. So any multiple of 72 can be removed since. 92 - 10 - 10 = 62 for instance. And we know that the change in heads after adding and removing is 10. Python has a clever way of checking this with the % operator (modulo) So we simply check if head % diff lies in hits.

• If we are smart we check if a particular hit leaves us in the state above. Meaning we check if head - hit % diff lies in hits, and if it do, we return.

• Even this code has problems when the number of heads grows large the final trick is that we remove chunks instead of single hits. You can think of this as we do n hits, and then the hydra regrows n times.

        chunk = max(1, head // chunk_size)
head += (growths_[hit] - hit) * chunk

##### code 1
from timeit import default_timer as timer
import random

def hydra_killing(head, hits, growths, iter_limit=10 ** 6):

growths_ = dict(zip(hits, growths))
positive_hits, differences = zip(
*[(hit, hit - growth) for hit, growth in zip(hits, growths) if hit > growth]
)
chunk_size = 1000
iters = 0
while (iters := iters + 1) < iter_limit:

return True, iters
for diff in differences:
if head % diff in positive_hits:
return True, iters
for h in positive_hits:
if (head - (h + growths_[h])) % diff in positive_hits:
return True, iters

hit = random.choice(hits)

if small_hits := [hit for hit in hits if hit < head]:
hit = random.choice(small_hits)
else:
return False, iters
chunk = max(1, head // chunk_size)
head += (growths_[hit] - hit) * chunk

return False, iter_limit

if __name__ == "__main__":

heads = [88, 135, 192, 98767892]
hits = [25, 67, 1, 62]
growths = [15, 25, 15, 34]

start = timer()
end = timer()
print(end - start, " seconds")


### Suggestion 2 [We want the optimal]

Unless you have a ton of heads I would recommend simply using itertools. Notice that until the very last hit, the hit and growth can occur at the same time. Meaning we can just hit the hydra down, and check if it can be killed in one hit.

The hydra can be killed in one hit, if its heads is in hits

Then we just have to iterate over all possible hit values and return the first one that matches.

#### Code 2

import itertools

"""Checks if Hydra is 1 hit away from death after n hits"""
(hit - growth) * number
for hit, number, growth in zip(hits, number_of_hits, growths)
)

"""Iterates over all possible number of hits, returns first '1 hit from death'"""
for hydra_hits in itertools.product(*[range(head // 10) for _ in hits]):
return hydra_hits
return ()

if __name__ == "__main__":

heads = [88, 135, 152, 1002]
hits = [25, 67, 1, 62]
growths = [15, 25, 15, 34]

# Sorts hits and growths in ascending number of hydra heads killed
# which speeds up the iteration somewhat
hits, growths = zip(
*sorted(zip(hits, growths), key=lambda sub: sub[1] - sub[0], reverse=True)
)

if hits_2_almost_kill := kill_hydra_itertools(head, hits, growths):
print(hits_2_almost_kill)


### Example

For instance for 152 the code returns (2, 0, 1, 3) we can check that this is correct by doing

print(152 - (25 - 15) * 2 - (1 - 15) * 1 - (62 - 34) * 3)


Indeed, this returns 62 which is a number of heads we can strike of in the next turn. Notice that this already takes into consideration the growing back of heads.

### Suggestion 3 [Mathematics]

We could also have used mathematics to obtain the results, this is somewhat fast for very large inputs. I would recommend going for one of the two other suggestions first though!

We know that every time we hit the hydra the change in heads is equal to

change_in_heads = [25-15, 67-25, 1-15, 62-34] = [10, 42, -14, 28]


This means in principle we are looking for the solution to the equation

10 r + 42 s - 14 t + 28 u = heads


This is known as a Diophantine equation which sympy knows how to solve.

Note that this returns the general solution, meaning for instance that the solution to

10 r + 42 s - 14 t + 28 u = 88


is written as

t_0, -35 t_0 + 7 t_1 + 132, t_0 + t_1 + t_2, -20 t_0 + 8 t_1 + 3 t_2 + 88


Where t_0, t_1 and t_2 are integers which we can change to generate as many solutions as we want. (Amongst the nerds we say that the solution can be written as aparametric equation.) So all we have do to is use sympy to solve the equation, and then check if we can find a particular solution with integer coefficients.

Noe 0: The explanation above is not quite right. Due to how you choose to calculate the hits and regrowth (hits before regrowth). We really need to hit the Hydra until it is one hit away from death. Meaning the Hydra's healthbar has to be in hits This is done by instead by checking if

10 x + 42 y - 14 z + 28 w = 88 - hit


has a solution for each hit in hits.

Note 1: that the switch minimize in the code below attempts to find the shortest or fastest way to kill the Hydra. If you only any solution set this boolean to false.

Note: 2: the code below is merely a suggestion. There are several improvements that could (and should be made to the code below). Such as, but not limited to

#### Work still to be done

• Instead of using nested for loops to find the positive solution either:

• Use a recursive solution or use itertools as seen before.

• The recurse solution would also benefit from adding restrictions from the general solution. As an example we have

t_0, -35 t_0 + 7 t_1 + 132, t_0 + t_1 + t_2, -20 t_0 + 8 t_1 + 3 t_2 + 88


For the first hydra. This means that t_0>0, t_1 > (35 t_0 - 132)/7, and for instance t_2 > t_1 + t_2. This could make the looping faster.

#### Code 3

from sympy.solvers.diophantine import diophantine
from sympy import symbols, solve

r, s, t, u = symbols("r, s, t, u", integer=True)

change_in_heads = [hit - growth for hit, growth in zip(hits, growths)]
equation = sum(d * var for d, var in zip(change_in_heads, [r, s, t, u]))

min_hits_2_kill = [float("Inf")] * len(hits)
for index, hit in enumerate(hits):
try:
[solution] = diophantine(equation - (heads - hit))
except ValueError:
continue
hits_2_kill = hydra_hits_required(solution, minimize_solution)
if sum(hits_2_kill) < float("Inf"):
if minimize_solution:
if sum(min_hits_2_kill) > sum(hits_2_kill):
min_hits_2_kill = hits_2_kill
else:
return True, hits
return sum(min_hits_2_kill) < float("Inf"), min_hits_2_kill

def hydra_hits_required(solution, minimize_solution=False, max_range=10):
t_1, t_0, t_2 = solution[3].free_symbols

length_solution = float("Inf")
shortest = [float("Inf"), float("Inf"), float("Inf")]
t0_start = int(nsolve(solution[0], 0) + 1)
for t0 in range(t0_start, max_range + t0_start):
sol1 = [expr.subs({t_0: t0}) for expr in solution]
t1_start = int(nsolve(sol1[1], 0) + 1)
for t1 in range(t1_start, max_range + t1_start):
sol2 = [expr.subs({t_1: t1}) for expr in sol1]
t2_start = max(int(nsolve(sol2[2], 0) + 1), int(nsolve(sol2[3], 0) + 1))
for t2 in range(t2_start, t2_start + max_range):
sol3 = [expr.subs({t_2: t2}) for expr in sol2]
if min(sol3) > 0 and sum(sol3) < length_solution:
shortest = sol3
length_solution = sum(sol3)
if not minimize_solution:
return shortest
return shortest

"""Checks if Hydra is 1 hit away from death after n hits"""
for hit, number, growth in zip(hits, number_of_hits, growths):

if __name__ == "__main__":

heads = [88, 135, 192, 98765672]
hits = [25, 67, 1, 62]
growths = [15, 25, 15, 34]

minimize = True