Project Euler/334
From charlesreid1
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.
Flags
