Hydra game n=steps from the end of https://youtu.be/prURA1i8Qj4

hydragame.cpp

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <math.h>

uint64_t hydraSlow(uint32_t height)
{
	if (height == 0)
	{
		return 0;
	}
	if (height > 4)
	{
		printf("This will take too long\n");
		return 0;
	}

	uint64_t *nodes      = new uint64_t[height];
	uint64_t  steps      = 0;
	uint32_t  heightOrig = height;

	// Init
	for (uint32_t i = 0; i < height; i++)
	{
		nodes[i] = 1;
	}

	while (height > 0)
	{
		// Find right most head (lowest node with a head (leaving 1 which is not a head yet), node at the current height is all heads)
		for (uint32_t i = 0; i < height; i++)
		{
			if (nodes[i] > 1 || i + 1 == height)
			{
				// Cut head off
				nodes[i]--;
				steps++;

				// That was the last head at the height
				if (nodes[i] == 0)
				{
					height--;
				}

				// Regrow heads below
				if (i > 0)
				{
					nodes[i - 1] += steps;
				}
				break;
			}
		}
	}

	delete [] nodes;
	return steps;
}

uint64_t hydraFast(uint32_t height, bool printInfo = false)
{
	if (height == 0)
	{
		return 0;
	}

	uint64_t *nodes      = new uint64_t[height];
	uint64_t  steps      = 0;
	uint32_t  heightOrig = height;

	// Init
	for (uint32_t i = 0; i < height; i++)
	{
		nodes[i] = 1;
	}

	while (height > 2)
	{
		if (printInfo)
		{
			printf("%" PRIu64, nodes[0]);
			for (uint32_t i = 1; i < heightOrig; i++)
			{
				printf(" -> %" PRIu64, nodes[i]);
			}
			printf("\tsteps: %" PRIu64 "\n", steps);
		}

		// Remove level 2 heads and the new level 1 heads
		// Slow version
		//   while (nodes[1] > 1)
		//   {
		//     nodes[1]--;
		//     steps += steps + 2;
		//   }
		// Fast version
		if (nodes[1] > 1)
		{
			uint64_t n = nodes[1] - 1;

			// Stop when ((steps + 2) << n) will overflow
			if (log2((double) steps + 2.0) + (double) n >= 64.0)
			{
				if (!printInfo)
				{
					printf("%" PRIu64, nodes[0]);
					for (uint32_t i = 1; i < heightOrig; i++)
					{
						printf(" -> %" PRIu64, nodes[i]);
					}
					printf("\tsteps: %" PRIu64 "\n", steps);
				}
				printf("Stopping because (%" PRIu64 " << %" PRIu64 ") will overflow\n\n", steps + 2, n);
				return 0;
			}

			steps = ((steps + 2) << n) - 2;
			nodes[1] = 1;
		}

		// Find right most head (lowest node with a head (leaving 1 which is not a head yet), node at the current height is all heads)
		for (uint32_t i = 2; i < height; i++)
		{
			if (nodes[i] > 1 || i + 1 == height)
			{
				// Cut head off
				nodes[i]--;
				steps++;

				// That was the last head at the height
				if (nodes[i] == 0)
				{
					height--;
				}

				// Regrow heads below
				nodes[i - 1] += steps;
				break;
			}
		}
	}

	// Remove level 2 heads and the new level 1 heads
	if (height > 1)
	{
		// Slow version
		//   while (nodes[1] > 0)
		//   {
		//     nodes[1]--;
		//     steps += steps + 2;
		//   }
		// Fast version
		uint64_t n = nodes[1];
		steps = (steps << n) + ((2 << n) - 2);
		nodes[1] = 0;
	}

	delete [] nodes;
	return steps + 1; // nodes[0] == 1
}

int main()
{
	for (uint32_t i = 1; i < 8; i++)
	{
		if (i < 5)
		{
			printf("%u: %" PRIu64 " (slow version)\n", i, hydraSlow(i));
			printf("%u: %" PRIu64 " (fast version)\n\n", i, hydraFast(i));
		}
		else
		{
			printf("%u:\n", i);
			hydraFast(i, true);
		}
	}

	return 0;
}