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

Observations that need more exploration:

• 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.
• Based on the example, the entire process seems to be abelian (same result regardless of what order the steps are performed in)

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

Bitvector representation ideas

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. However, it's possible that we could find a shortcut that lets us jump straight from the input (starting state of the game) to a final representation (which, because it is only 0s and 1s, is conducive to a bitvector representation).

The invariant properties of both the number of beans (zeroth moment) and the average location (first moment) could help. I imagine some kind of process where we take the binary representations of neighboring numbers, and "add" (xor?) them together such that we get the final outcome.

Examine the example:

• Start with 2 and 3 next to each other, which in binary is 10 and 11
• 0 0 10 11 0 0
• 0 1 0 100 0 0
• 0 1 1 10 1 0
• 0 1 10 1 10 0
• 0 10 1 10 0 0

(The starting numbers are not the largest the numbers will get - they can and will get larger, esp. as number of starting piles grows - so we can't, say, initialize every slot as a binary number with 3 or 4 digits, b/c can't know in advance what the maximum sum will be - unless we sum up all the beans and use that as the maximum size of number that will ever be in any given bowl)

This might just work...

• starting configuration has 1500 bowls filled
• assume worst case happens, and all of those beans end up in one bowl at some point during our solution
• total number of beans in initial configuration (for the final problem we're trying to solve) is about a million: 1124250
• log2(1124250) = 20.1, so we could initialize each bowl as a 21-element bitwise vector (a modest 3.9KB to store the entire game)

Revisiting the example, using this approach, we get

• Start with 2 and 3 next to each other, total beans is 5, binary representation is 101 (only 3 digits)
• Representing every slot with a 3-digit bitwise vector:
• 000 000 010 011 000 000 (start)
• 000 001 000 100 000 000 (round 1)
• 000 001 001 010 001 000
• 000 001 010 000 010 000
• 000 010 000 001 010 000 (round 4)
• 000 010 000 010 000 001
• 000 010 001 000 001 001
• 001 000 010 000 001 001
• 001 001 000 001 001 001 (round 8)

short form:

000 000 010 011 000 000
000 001 000 100 000 000
000 001 001 010 001 000
000 001 010 000 010 000
000 010 000 001 010 000
000 010 000 010 000 001
000 010 001 000 001 001
001 000 010 000 001 001
001 001 000 001 001 001