-2
$\begingroup$

I saw this question here: The Hydra Game algorithm

I am also running into troubles with the same problem.

I also learned of the problem in this Numberphile video, and also tried to compute it myself.

The problem with my code is that it runs forever for n=4. It produces the correct results for n=1-3. I have had it running for about 3 hours now, and it is still running.

Here is my code:

class Node:
def __init__(self, parent):
    self.parent = parent
    self.children = []

def is_root(self):
    return self.parent == None

def add_child(self):
    self.children.append(Node(self))

def chop(self, n = 2):
    if not self.parent.is_root():
        for i in range(n):
            self.parent.parent.add_child()
    self.parent.children.remove(self)

def find_leftmost(self):
    if len(self.children) > 0:
        return self.children[-1].find_leftmost()
    return self

if __name__ == '__main__':
    root = Node(None)
    root.add_child()
    root.children[0].add_child()
    root.children[0].children[0].add_child()
    root.children[0].children[0].children[0].add_child()

    steps = 0
    while len(root.children) > 0:
        root.find_leftmost().chop(steps+1)
        steps += 1

    print(steps)
$\endgroup$
3
  • $\begingroup$ What makes you think it's running forever? If you periodically print steps, have you seen it pass 938038? $\endgroup$
    – Dan Doel
    Commented Apr 19 at 13:44
  • 1
    $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Commented Apr 19 at 13:51
  • 1
    $\begingroup$ Programming questions are off-topic here. $\endgroup$
    – Nathaniel
    Commented Apr 19 at 14:16

1 Answer 1

0
$\begingroup$

A nice little rule when having these types of problems: 'When in doubt, print it out'

But if it is hanging, it is because of while len(root.children) > 0: root.children may never actually be reaching a length of 0.

$\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.