5
\$\begingroup\$

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

heads = [88,135,192,152]

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



def hydra_killing():
    
    iter_limit = 1000

    for head in heads:
        iters = 0           #Resets iters at every new 'hydra'
        while head != 0:
            iters += 1

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

                    if head == 0:
                        print(f'''
YES...............................................{iters}


''')
                    else:
                        head += growths[i]
                        #print(head, hits[i], growths[i], iters)
                        
                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")


            
        
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Can you overkill a hydra? If the hydra has 20 heads can you cut off 26? \$\endgroup\$ Jun 25, 2021 at 5:43
  • \$\begingroup\$ imo no you can't \$\endgroup\$
    – sato
    Jun 25, 2021 at 5:58
  • \$\begingroup\$ if the heads remaining are greater than hits[i], then we regenerate an i and that 'try' is not counted \$\endgroup\$
    – sato
    Jun 25, 2021 at 6:00
  • \$\begingroup\$ 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 \$\endgroup\$ Jun 25, 2021 at 6:14
  • \$\begingroup\$ 'It always gives an optimal solution, if one exists, but <<is slow and requires considerable memory>>' \$\endgroup\$
    – sato
    Jun 25, 2021 at 6:15

1 Answer 1

2
\$\begingroup\$

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


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 head < hit:
            continue
        head -= hit
        if head == 0:
            return True, iters
        head += growths_[hit]

    return False, iter_limit


if __name__ == "__main__":

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

    for head in heads:
        start = timer()
        is_hydra_dead, iters = hydra_killing(head, hits, growths)
        end = timer()
        print(end - start, " seconds")
        print(is_hydra_dead, iters)

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 head < hit:
            if small_hits := [hit for hit in hits if hit < head]:
                hit = random.choice(small_hits)
            else:
                return False, iters
        head -= hit
        if head == 0:
            return True, iters
        head += growths_[hit]

    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:

        if head in hits:
            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 head < hit:
            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]
    # heads = [4321]
    hits = [25, 67, 1, 62]
    growths = [15, 25, 15, 34]

    for head in heads:
        start = timer()
        is_hydra_dead, iters = hydra_killing(head, hits, growths)
        end = timer()
        print(end - start, " seconds")
        print(is_hydra_dead, iters)

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

def is_hydra_one_hit_from_death(total_heads, hits, number_of_hits, growths):
    """Checks if Hydra is 1 hit away from death after n hits"""
    heads_removed = sum(
        (hit - growth) * number
        for hit, number, growth in zip(hits, number_of_hits, growths)
    )
    return (total_heads - heads_removed) in hits


def kill_hydra_itertools(head, 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]):
        if is_hydra_one_hit_from_death(head, hits, hydra_hits, growths):
            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)
    )

    for head in heads:
        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

  • Adding PEP484 typing hints

  • 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)


def is_hydra_killable(heads, hits, growths, minimize_solution=False):
    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


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


if __name__ == "__main__":

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

    minimize = True

    for head in heads:
        is_dead, hits_2_kill = is_hydra_killable(head, hits, growths, minimize)
        print(hits_2_kill)
        print(is_hydra_one_hit_from_death(head, hits, hits_2_kill, growths))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.