← RoseCode

ROSECODE 372

Slaying the hydra

Philippe_57721 · Programming ·

An hydra is a rooted tree.

Hercules' task is to slay the hydra by choping all its heads.
But the hydra's heads grow again with the following rules. At the step n :
- if Hercules cuts a head growing from the root, the hydra doesn't grow any head.
- if Hercules cuts a head attached to a given node, this head is deleted.
The node at which the head was attached is copied n times on the node just below.




Here is the evolution of a small hydra:



We define the size of an hydra as the number of its heads and nodes.
The hydra in the above picture as a size of 4 at step 1.

We can represent an hydra as a string as follow:
  • n A leaf
  • n(..) A node, inside the parenthesis its children
For instance, in the above picture the first 3 hydras are :
n(n(nn))
n(n(n)n(n))
n(nnnn(n))

We always cut the left most heads.
If we consider all the hydras of size 5, after 100 steps, the maximum sizes reached are the following:
  • n(n(n(n(n)))) - 5686
  • n(n(n(nn))) - 341
  • n(n(n(n)n)) - 288
  • n(n(n(n))n) - 21
  • n(n(nn(n))) - 70
  • n(n(nnn)) - 156
  • n(n(nn)n) - 9
  • n(n(n)n(n)) - 6
  • n(n(n)nn) - 5
  • n(nn(n(n))) - 67
  • n(nn(nn)) - 20
  • n(nn(n)n) - 5
  • n(nnn(n)) - 5
  • n(nnnn) - 4
(The initial size before steps is not counted)
The 5 largest sizes are (in descending order): 5686,341,288,156,70

What are the 5 largest sizes reached among all the 6-size hydras after 100 steps?

Answer format: comma delimited list in descending order

[My timing: 55 sec]
Credit to Andrej Bauer for the images