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.

The goal was to implement an algorithm to "play" a game, so that I could explore its properties for smaller numbers of beans, and generate test cases for verification of more optimized solutions.

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
• If we know number of bowls needed, in advance, we can imagine them being arranged in a large circle - so final solution (number of steps) should be invariant to whether beans start in first bowls or middle bowls or end bowls
• Based on the example, starting with N beans would require N+1 bowls. But that is only based on one example. Look deeper into this.

It seems like the line of bowls would have some kind of binary representation, but that's tricky because 0s and 1s don't cover how many beans are in each bowl.

The sole operation (taking two beans from a bowl and distributing them in the neighbor bowls) can be thought of as an array operation,

B[i]   = B[i] - 2
B[i+1] = B[i+1] + 1
B[i-1] = B[i-1] + 1