Killing a Hydra - Overengineered

Question

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 switchCOMPLETE_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


COUNT_ITERS = 0


class Hydra:
    """Tries to find the minimal required hits to kill the hydra"""

    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 + 1)
            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):
            final_diffs = [
                self.diffs_2_kill_recursive(
                    head - diff,
                    diff,
                    new_hits.copy(),
                    diff_index,
                    depth - 1,
                )
                for diff_index, diff in enumerate(self.diffs)
            ]
            return min(list(filter(None, final_diffs)), key=sum, default=[])
        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_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!"
                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, 4321, 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()

Answer 1

This was an interesting puzzle and your question was framed very well. I have a few code-review style comments. Those are followed by some discussion of, and corresponding code for, a different algorithmic approach -- one that seems easier to follow, at least to my eye.

The Hydra class has a complex implementation. Its own internal state requires fair bit of coordination, as evidenced primarily by the need to invoke self.update_variables() in various setters. Sometimes such dependencies are unavoidable, but one should generally view them as a potential warning sign. In this specific case, I think the warning is worth heeding. I don't think the complexity in the class is required.

A small symptom of the complexity. The Hydra class has bug. The API says you can pass the N of hydra_heads as an argument: Hydra(hits, growths, 2). But if you do, print(hydra) fails because _head has not been set. The culprit is this line in the initializer: self._heads = hydra_heads. Superficially, there is a typo (it should be self._head rather than self._heads). Of course, that mistake is natural because you have a plural thing (N of heads) but your code gives it a singular name (hence the confusion). But all of that is the surface layer. The deeper problem is that the initializer must use the setter, so that the object keeps its internal state aligned: self.head = hydra_heads.

The Hydra class is over-eager. A good guideline is to keep object initialization simple and lightweight: store the parameters and await further instruction. Your implementation solves the whole problem immediately. In my experience, lightweight initialization is usually better for testability, debuggability, and flexibility in the face of evolving requirements. But that's just a guideline, and there can be valid exceptions. But notice that if we decide to make Hydra eager during initialization, we could also decide to design the class to discourage mutation by users of the class. In other words, if the class solves the whole problem upon initialization, there's much less need for a bunch of setters that carefully align internal state. Eager can often be paired with a policy of treating the objects as non-modifiable, at least in spirit.

The Hydra class does not readily answer the primary question. Your stated goal is to minimize the number of hits necessary to kill the hydra. But the class does not appear to have a simple way to answer that question: how many hits were required? It also does not appear to have an easy way to see how many hits of each kind were required. Maybe there is a way and I overlooked it. In my case, I looked for a while and then just reverse-engineered the __str__() method to get the information I wanted. During my early experimentation, I added a few properties to your class to get what I needed.

Make debugging code data-oriented, not print-oriented. Your __str__() method is basically a debugging tool -- or at least that's the only use I can really see for it, and it's how I used it -- but a big string of narrative text is not a good debugging mechanism. Much better is data: one or more methods/properties to return the needed debugging facts. And even if you want the debugging information to be converted to text for reading (for example, to trace program logic), make the output data-oriented rather than textual. The precise format can vary depending on the problem, but the key is to emit the data in a way that is easy to scan and navigate visually. Sometimes tabular presentations work well (e.g., to see changes running down a column), sometimes hierarchy/indentation works well (e.g., to convey changes as state evolves through the program logic), and there are other possibilities. The main point is to be systematic and focus on the data. When experimenting with this problem I ended up writing a little debug function to print keyword-style data at various indentation levels mirroring the structure of my algorithm:

def debug(level, label, **kws):
    if False:
        msg = '  ' * level + label + ':'
        for k, v in kws.items():
            msg += f' {k}={v}'
        print(msg)

A simpler optimization. A fair bit of your code is oriented toward creating and managing optimizations like a lookup table. But one only needs optimization for large scale, which in this problem means a large number of heads. But when the N of heads is very large, the problem requires no optimization, because there is only one move to make: select the Hit with the largest positive difference between the N of heads removed vs regrown. Only when the numbers get smaller do we have to fuss over Hit selection so that we exactly kill the beast. To take advantage of those observations, we need a way to draw a line between very large N of heads and everything else. Least common multiples provide a convincing heuristic. In our case we have 4 Hit instances having the following removed/regrown differences: -14, 10, 28, and 42. We can ignore the negative value. The least common multiple of the other three differences is 420. If you need to remove significantly more than 420 heads, the most efficient way to do it is with the big-hits: use 10 of the 42-diff Hit rather than 15 of the 28-diff Hit, for example. I picked a conservative heuristic: any heads beyond 5x of that LCM were removed immediately by repeated applications of the 42-diff Hit. Since 5x the LCM is a tiny number, we don't really need to worry about any further optimization.

A Hit dataclass. You have list of hits (heads removed) and a parallel list of growths (heads regrown). I knew that I wanted to unify that data as a single list of Hit data objects. It was also handy to give that object a property for net head removal.

from dataclasses import dataclass

@dataclass(frozen = True)
class Hit:
    removed: int
    regrown: int

    @property
    def net_removed(self):
        return self.removed - self.regrown

A stack-based DFS algorithm, with guiding restrictions. I also expected that my no-need-for-optimization algorithm could be a stack-based DFS search -- but one arranged to find the optimal solution first. That is achieved through the interplay between two features of the algorithm. First, it tries bigger Hit instances before smaller, because we want the most efficient kill. Second, and pulling in the opposite direction, it requires that the Hit instances be selected in a monotonically increasing fashion. In other words, we might prefer to use bigger hits, but selecting bigger hits comes with a cost: smaller hits are disallowed on all subsequent selections. On a "representative" DFS traversal, the algorithm naively starts with big selections, but those reach a dead end if the solution requires some smaller hits too. The pathways involving smaller hits are put into the stack, so we will eventually explore them and find a solution. But, again, on any specific selection, the algorithm prefers the biggest allowed hit, which ensures that we will choose the fewest small hits possible when reaching the solution. That's an intuitive explanation for the logic. I think one could make a formal proof that these two features produce a correct solution, but I basically convinced myself that they worked through old-fashioned experimentation. As always, I might be wrong.

A State dataclass. To simplify information management within stack or queue based algorithms, it often helps to use a data object to represent program state. Here's what I ended up with:

@dataclass
class State:
    n_heads: int     # N heads remaining.
    counts: list     # Counts of Hits delivered so far.
    rng: range       # Indexes of remaining candidate Hits.

    def __post_init__(self):
        # Ensure that each State gets an independent list of counts.
        self.counts = list(self.counts)

Orchestration code. My own code evolved as I experimented toward a solution, but here's a simplified setup:

import sys

def main(args):
    hits = [Hit(25, 15), Hit(67, 25), Hit(1, 15), Hit(62, 34)]
    n_heads = int(args[0])
    counts = hits_to_kill_hydra(n_heads, hits)
    print(n_heads, counts)

if __name__ == "__main__":
    main(sys.argv[1:])

Algorithm. And the algorithm ended up in one main function with two small helpers. If one were feeling object-oriented, this code could be wrapped in a HydraKiller class or something, but I'm not convinced that would help too much with clarity. It might help if one had other goals or reporting needs in mind. I got interested in the puzzle mainly from the perspective of trying to write a solution that was as simple and intuitive as possible.

import math

def hits_to_kill_hydra(n_heads, hits):
    # Sort hits from small to large.
    hits = sorted(hits, key = lambda h: h.net_removed)

    # Set up initial n_heads and counts after quickly
    # removing any heads beyond the LCM-based threshold.
    n_heads, counts = rapid_head_removal(n_heads, hits)

    # Initialize stack with the starting State.
    limit = len(hits)
    s = State(n_heads, counts, range(0, limit))
    stack = [s]

    while stack:

        # Get current State.
        s = stack.pop()

        # Return a dict mapping hits to counts if we
        # can kill the hydra on the next Hit.
        i = immediate_kill(s.n_heads, hits)
        if i is not None:
            s.counts[i] += 1
            return dict(zip(hits, s.counts))

        # Otherwise, select the largest legal hit among those
        # specified by the current range of indexes.
        for i in reversed(s.rng):
            h = hits[i]
            if h.removed < s.n_heads:
                # In case hits[i] leads to a dead end, we need to put the
                # not-yet-considered alternatives (ie, Hits smaller than the
                # selected one) into the stack for later backtracking.
                if i > s.rng.start:
                    s2 = State(s.n_heads, s.counts, range(s.rng.start, i))
                    stack.append(s2)

                # Adjust state information based on selecting hits[i]. The
                # adjustments for n_heads and counts are straightforward. The
                # key part is the next State.rng: it ensures the the Hits will
                # be selected in a monotonically increasing fashion.
                s.counts[i] += 1
                n2 = s.n_heads - h.net_removed
                s2 = State(n2, s.counts, range(i, limit))
                stack.append(s2)
                break

    return None

def rapid_head_removal(n_heads, hits):
    # Compute N of heads beyond the 5x LCM threshold.
    net_removals = [h.net_removed for h in hits if h.net_removed > 0]
    surplus = n_heads - 5 * math.lcm(*net_removals)

    # Compute N of the biggest Hit to apply.
    big_hit = hits[-1]
    n_big = surplus // big_hit.net_removed

    # Use n_big to return the adjusted n_heads and counts.
    counts = [0 for _ in hits]
    if n_big > 0:
        counts[-1] += n_big
        n_heads -= n_big * big_hit.net_removed
    return (n_heads, counts)

def immediate_kill(n_heads, hits):
    # Return index of Hit that would immediately kill the hydra.
    for i, h in enumerate(hits):
        if n_heads == h.removed:
            return i
    return None