ROSECODE 372
Slaying the hydra
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(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:
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
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
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 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