1
$\begingroup$

I was recently introduced to the Hydra Game by the youtube channel Numberphile (https://www.youtube.com/watch?v=prURA1i8Qj4).

In this video, they discuss many variants of the Hydra Game - cut off one head (i.e. a leaf of a graph, more specifically a tree) and $n$ heads grow back. I am interested in the following variant, also detailed on the Wikipedia page (https://en.wikipedia.org/wiki/Hydra_game):

You start with the Hydra being a straight line of vertices and edges, with a single root and a single leaf. At each step, call it $k$, you always pick the right-most leaf/head and chop it off, whereafter $k$ leaves will regrow from the grandfather of the leaf, to the right of any existing children. If you chop off a leaf with no grandfather, i.e. one step from the root, no leaves regrow (which is also why this game always terminates).

The challenge is to determine how many chops you need to cut off all the heads of the hydra. Both the YouTube video and the Wikipedia article lists the following result, for the hydra starting with $n$ edges: $n=1: 1$, $n=2: 3$, $n=3: 11$ and $n=4: 938038$. They also both state that the result for $n=5$ is unknown.

My question is, does anyone know anyone know a reference for this variant of the game, OR can someone spot the mistake in my code/approach?

I feel that I am misunderstanding what "right-most" means. Since the grandfather of any leaf is always part of the original stem, i.e. one of the vertices that were there to begin with, and since no leaf can ever become a father, it would seem to me that the "right-most" leaf is just the newest leaf on the level with most leaves. I wrote the following simple Python code, which produces the correct results for $n=1,2,3$, but yields $327677$ for $n=4$ instead of $938038$. What am I doing wrong?

The code first sets up the hydra, with one vertex on each level (it forgets the root, since no heads can grow on this level). The first entry of hydra is the upper-most level. It then loops while the final level still has heads, keeps track of how many chops have already been done, and for each chop, adds heads to the level below, except if the level is the final one.

def hydrachop(n):
    hydra = [1 for i in range(n)]
    step = 0
    while hydra[n-1] > 0:
        i = hydra.index(max(hydra))
        hydra[i] -= 1
        step += 1
        if i < n-1:
            hydra[i+1] += step
    return step
$\endgroup$

4 Answers 4

0
$\begingroup$

The problem is in the line: i = hydra.index(max(hydra))

Running the code and printing: print(hydra, i, step) gives us this:

[0, 0, 13, 13] 3 37
[0, 0, 12, 13] 2 38
[0, 0, 12, 50] 3 39
[0, 0, 12, 49] 3 40

You'll see the the hydra at step 38 [0, 0, 12, 13] is resetting to [0, 0, 12, 50] before the 13 goes all the way down to 1. You'll need to track the index you're reducing until it goes down to 1.

Update: A lot of us are getting 1,114,111 as the answer.

def rightMostIndex(arr):
    index = next((i for i in range(len(arr) - 1, -1, -1) if arr[i] not in [0, 1]), None)
    return index`


def hydrachop(n):
    hydra = [1 for i in range(n)]
    step = 0
    printNext = False

    while hydra[n-1] > 0:
        if all(i == 1 or i == 0 for i in hydra):
            index = hydra.index(1)
            hydra[index] -= 1
            step += 1
            if index < n-1:
                hydra[index+1] += step

        else:    
            index = rightMostIndex(hydra);
            hydra[index] -= 1
            step += 1
            if index < n-1:
                hydra[index+1] += step
    return step
$\endgroup$
0
$\begingroup$

This is my mediocre attempt to write a program that solves the problem

#!/bin/python3

import sys
from typing_extensions import Self

class Node:
    children: list[Self]
    parent: Self

    def __init__(self, parent: Self, children: list[Self]):
        self.parent = parent
        self.children = children

class Hydra:
    root: Node

    def __init__(self, hight: int):
        self.root = Node(None, [])
        curr = self.root
        for i in range(hight):
            curr.children.append(Node(curr, []))
            curr = curr.children[0]

    def steps(self) -> int:
        return self._steps(0)

    def _steps(self, acc: int) -> int:
        while self.root.children != []:
            acc = acc + 1
            curr = self.root
            while curr.children != []:
                curr = curr.children[-1]
    
            if curr.parent.parent != None:
                for i in range(acc):
                    curr.parent.parent.children.append(Node(curr.parent.parent, []))
            
            del curr.parent.children[-1]

        return acc


print(Hydra(int(sys.argv[1])).steps())

I am also getting 1,114,111 for hight = 4

I don't quite understand what the "right-most leaf" means. And I feel like they skimmed over a lot of details on the video. If someone could describe an exact definition of the problem that would be awesome.

$\endgroup$
0
$\begingroup$

One thing I have noticed is that the question asker assumed "right-most" meant the "last" leaf on the level with the most leaves, and the other answers here have assumed "right-most" means "starting at the root, keep traversing to the rightmost child of the current vertex until you get to a leaf."

If the answering members have misinterpreted this, it would explain why they are getting a larger answer than expected. Removing heads closer to the root early causes the counter to increment more before returning to lower level roots, which cause more "exponential" growth. It also might explain why the original asker was getting a number lower than expected. When two layers both have the maximum number of vertices, hydra.index(max(hydra)) will return the smaller index, which corresponds to the lower-level. If "ties" go to the higher-level instead, the final answer should be larger.

Unfortunately, you have to be careful implementing this change because it is possible for two levels to have the same number of vertices, but for the higher level to not contain leaves, as is the case at the start when each level contains a single vertex.

$\endgroup$
0
$\begingroup$

Glad it's not just me facing the same problem. I also cannot reproduce the expected value of 938038.

The algorithm is definitely unclear. I have tried 4 variants of what I think the algorithm could be and none work.

Terminology

  • I will use "node" to mean one of the nodes in the original vertical tree. For any heads which get added to those nodes I will simply refer to those as leaves.
  • By "highest node" I mean the node furthest from the root. "Lowest" thus has the obvious meaning.

For all variants, in the event that none of the nodes have any leaves, I cut away the highest node.

Variant A Look for the node (in the original vertical tree) which has the most leaves and cut from there. In the event that two (or more) nodes have the same number of leaves, choose the highest node.

Result: 327677

Variant B Same as A but prefer the lowest node when two (or more) nodes have the same number of leaves.

Result: 720891

Variant C Always trim leaves from the lowest node with leaves.

Result: 1114111

Variant D Always trim leaves from the highest node with leaves.

Result: 495

Here's a gist with my code: https://gist.github.com/HormyAJP/c340a3ad9703582a6c74c56d460d9316

I checking in OEIS and neither the sequence expected by Numberphile nor any of my above answers (when added to the sequence) are listed.

Anyone any other ideas?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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