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:

000000010011000000
000001000100000000
000001001010001000
000001010000010000
000010000001010000
000010000010000001
000010001000001001
001000010000001001
001001000001001001

Nothing jumping out...

But we do have two invariants:

• total number of beans (0th moment)
• average location of beans (1st moment)

We could find the unique set of bean indices that (1) preserves total number of beans, (2) preserves average location of beans, and (3) minimizes sum of indices $\sum i^{2}$ (where i is the index of the bowl)

Map representation ideas

For a first-pass implementation, use a map instead of a bitwise vector. That avoids the need to allocate space for every bowl in advance, and just keep track of bowls that have/have seen beans.

(In Python, we can use a default dict, with the bowl index as the key and the number of beans (default 0) as the value.)

For N = 10 beans in one starting bowl, it takes 0.000132 seconds

For N = 100 beans in one starting bowl, it takes 0.061 seconds

For N = 1000 beans in one starting bowl, it takes 57.2 seconds

That kind of scale-up (nearly 1000x increase in computational cost for every 10x increase in beans) means this approach is totally unscalable. Not surprising, but at least we can get some insight from smaller cases.

Maximum bowls

Using the simulator we built, figuring out how the starting number of beans/positions affects the end range of indexes and layout

single bowl case

Single bowl case:

• Suppose we start with b beans in bowl k. No other bowls have any beans.
• The number of bowls needed to distribute b beans located in bowl k is b/2
• The bowls used will range from k - b/2 to k + b/2

• Example:
  • start with 100 beans in bowl 0
  • end with 1 bean in bowl -50, 1 bean in bowl -49, ..., 1 bean in bowl 49, 1 bean in bowl 50

• Example:
  • start with 100 beans in bowl 7
  • end with 1 bean in bowl -43, 1 bean in bowl -42, ..., 1 bean in bowl 57

two bowl case

Two bowl case:

• suppose we start with b1 beans in bowl k1, and b2 beans in k2. No other bowls have any beans.
• If k1 and k2 are very far apart, we can expect that neither bowl will interact, so reduces to single bowl case for each

• Example:
  • start with 10 beans in bowl 0, 10 beans in bowl 80
  • end with 1 bean in bowl -5, 1 bean in bowl -4, ..., 1 bean in bowl 4, 1 bean in bowl 5,
  • then 1 bean in bowl 75, 1 bean in bowl 76, ..., 1 bean in 84, 1 bean in bowl 85

• If k1 and k2 are close together, they will interact:

Initial State: {0: 10, 1: 10}
Final State: [-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Initial State: {0: 10, 2: 10}
Final State: [-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Initial State: {0: 10, 3: 10}
Final State: [-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Initial State: {0: 10, 4: 10}
Final State: [-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Initial State: {0: 10, 5: 10}
Final State: [-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Quadratic potential

Given that it is totally impossible to reach the final state by simulating every move, let's take an alternative approach, which is, to use the two invariants (0th moment, number of beans, and 1st moment, avg location of beans) and find a final state that satisfies those invariants while also minimizing number of moves

NOTE: we aren't using the definition of moment exactly correctly, b/c normally we would divide moment 1 by N, moment 2 by N^2, etc, but we can think of these as "non-normalized" moments

Game conserves two key quantities:

$M_{0}=\sum _{i}B_{i}$

$M_{1}=\sum _{i}i\cdot B_{i}$

where $B_{i}$ is the number of beans in bowl i

Denote the final state F as

$F=(F_{i})$

This final state must also satisfy the invariants:

$M_{0,F}=\sum _{i}F_{i}$

$M_{1,F}=\sum _{i}i\cdot F_{i}$

(This just says that number of beans must be preserved, and average location of beans must be preserved)

Now let's look at the second moment:

$M_{2,F}=\sum _{i}i^{2}\cdot F_{i}$

If we look at the way the second moment changes with each move, it increases by 2,

• Removing 2 beans from bowl i changes M2 by $-2\cdot i^{2}$
• Adding one bean to bowl i-1 changes M2 by $i^{2}-2i+1$
• Adding one bean to bowl i+1 changes M2 by $i^{2}+2i+1$
• Total change = 2

We want the value of M2 to be at a minimum, but while acknowledging that it must increase for each round

The stability condition corresponds to having the minimum possible value of the second moment amongst all possible configurations F satisfying our constraints:

• $F_{k}\in {0,1}$
• $\sum F_{k}=L$
• $\sum kF_{k}=M$

Unique final state is most "compact" arrangement of L beans (minimum sum of squared indices) producing the required moment

We can also determine the number of moves from the final state:

$N_{moves}={\dfrac {M_{2,F}-M_{2}}{2}}$

(Take the difference in the second moment from the start and end states, divide by 2, and that's your number of moves. Confirmed because each move changes Q by 2.)

Crux

Crux of the problem was, ironically, implementing the function for t_i in the problem statement:

The problem boiled down to how I was calculating t(i):

    tim1 = t(i - 1)
    if tim1 % 2 == 0:
        return tim1 // 2
    else:
        # return math.floor(tim1 / 2) ^ 926252 # <-- what I had originally
        return (tim1 // 2) ^ 926252            # <-- what actually worked