Project Euler/334

Link: https://projecteuler.net/problem=334

Beans Game

In Plato's heaven, there exist an infinite number of bowls in a straight line.

Each bowl either contains some or none of a finite number of beans.

A child plays a game, which allows only one kind of move: removing two

beans from any bowl, and putting one in each of the two adjacent bowls.

The game ends when each bowl contains either one or no beans.

For example, consider two adjacent bowls containing

and beans respectively, all other bowls being empty. The following eight moves will finish the game:

0 0 2 3 0 0

0 1 0 4 0 0

0 1 1 2 1 0

0 1 2 0 2 0

0 2 0 1 2 0

0 2 0 2 0 1

0 2 1 0 1 1

1 0 2 0 1 1

1 1 0 1 1 1

Approach

Before trying to tackle the full problem, I started by thinking about the game, and how it could be efficiently represented.

Key insights:

• The total number of beans (sum of all bean piles) is invariant
• The line of bean bowls is infinite, but the number of beans is finite, so a program implementing the game only needs a finite number of bowls to simulate a game
• Based on the example, starting with N beans would require N+1 bowls. But that is only based on one example, need to check.