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


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_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, 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()