6x4 grid of eggs. Remove 3 eggs at a time, maximizing balance of entire container at each step.

gistfile1.txt

midwestdevchat.com (Slack) #nondevshitineedhelpwith 2019-10-11

starting position:
O O O O O O
O O O O O O
O O O O O O
O O O O O O

---------------------------------------
caramiki's progression #1

O O O O O O
O O . O O O
O . O O . O
O O O O O O

O O O O O O
O . . O . O
O . O . . O
O O O O O O

O O O . O O
O . . . . O
O . . . . O
O O O O O O

O O . . O O
O . . . . O
O . . . . O
O O . . O O

O O . . . O
. . . . . O
O . . . . O
O . . . O O

O . . . . O
. . . . . O
O . . . . .
O . . . . O

. . . . . O
. . . . . .
O . . . . .
. . . . . O

---------------------------------------
caramiki's progression #2

. O O O O O
O O O O O O
O O O O O O
O . O O O .

. O . O . O
O O O O O O
O O O O O O
O . O . O .

. O . O . O
O O O . O .
. O O O O O
O . O . O .

. O . O . O
O . O . O .
. O . O . O
O . O . O .

. O . O . .
O . . . O .
. O . O . O
. . O . O .

. O . O . .
. . . . O .
. O . . . .
. . O . O .

. O . . . .
. . . . O .
. . . . . .
. . O . . .

---------------------------------------
jhannah's progression

O O O O O O
O O . O O O
O . O O O O
O O O O . O

O O O . O O
O O . O O O
O . O . O O
. O O O . O

O . O . O O
. O . O . O
O . O . O O
. O O O . O

O . O . O .
. O . O . O
O . O . O .
. O . O . O

O . . . O .
. O . O . O
. . O . O .
. O . . . O

O . . . O .
. O . . . .
. . . . O .
. O . . . O

O . . . . .
. . . . . .
. . . . . .
. O . . . O

---------------------------------------
final position:
. . . . . .
. . . . . .
. . . . . .
. . . . . .

( sort of related, totally awesome "The Bizarre Behavior of Rotating Bodies, Explained" )

how are you calculating your balance values?

@jhannah

The puzzle doesn't specify precisely what is meant by 'balance', but it is stated in physical terms, so I've chosen to interpret 'balance' in the physical sense of minimizing the distance between the assembly's center of gravity and point of suspension. I'm assuming the carton is a uniform symmetric rectangular grid (as illustrated in your 'starting position' ASCII art) suspended on its centroid (inferred from the assumption that the given starting point meets the definition of 'balanced'). I'm modeling the eggs as unit-force dimensionless points. This makes them difficult to scramble, but easy to compute. Dimensional asymmetric eggs would balance slightly differently, but that's a slippery slope into a swamp of finite element analysis, and I was just trying to kill a Friday evening, not 2020.

Other interpretations of 'balance' are possible. As you note, different distributions of eggs that are static balanced about the center point may have different rotational moments of inertia, which will make them feel different when handling them. Since the puzzle did not specify static balance vs dynamic balance, I've chosen static balance, partly because dynamic balance seems more likely to lead to boring symmetric solutions.

Consider a simple balance apparatus consisting of a beam supported by a fulcrum. An egg placed some distance d from the fulcrum will apply a force F, creating a moment, or torque, M=Fd. Force F is generated by the acceleration of gravity on the mass of the egg, and I've chosen to use eggs with a mass that generates a force of exactly 1, so we can simplify to M=d.

If we place two eggs on the balance we can sum their associated moments to combine them into a net moment. Two eggs at distance d from from the fulcrum create a moment of M = d + d, 2d. Eggs at distances d and -d create a moment of M = d + (-d), 0.

The eggs in the puzzle are arranged in two orthogonal dimensions, so Euclidean vectors are a convenient method of handling the separate moments in each of the two dimensions. The magnitude and direction of the moment vector for an egg represents the moment of the egg in the plane. Summing the vectors for multiple eggs calculates the moment vector of the system of eggs. The magnitude of the vector of the system of eggs represents the balance of the system. Perfect balance is represented by a magnitude of zero.

So, finally, to answer your question, I calculate the balance value by first creating a moment vector for each egg, summing the vectors, then calculating the magnitude of the result. The moment vector for an egg is created by calculating the egg's distance (because M=d) in each dimension from the suspension point of the carton.

As an example, consider the arrangement:

 O  . 
 .  .

The moment vector for this egg is (-0.5, 0.5), which has a magnitude of √(x²+y²), 0.7071.

The worst balance in the game (I'm using game/board/move vocabulary in the program) I posted above is from the arrangement:

 .  .  .  .  .  O 
 .  .  .  .  .  . 
 .  .  .  .  .  . 
 .  O  O  .  .  . 
balance: 1.581139

Which has moment vectors (2.5,1.5),(-1.5,-1.5),(-0.5,-1.5), which sum to (0.5, -1.5), with a magnitude of 1.581139.

The solution path from that game is generated by following the instructions in the puzzle to 'maximize balance of entire container at each step', selecting the first minimum-imbalance move with no look-ahead to try to avoid paths with poor balances in later moves. The next iteration for my solver is to add look-ahead to see if I can avoid solution paths with larger imbalances to find solutions with lower worst-balance values.

I added a new move selection strategy for choosing a random best next move (order the set of possible next moves by board balance and pick a random move from the top options), and after playing around a little it's clear that with the way I've set up the balance evaluation there are a lot of options that solve the puzzle with the minimum possible imbalance even without any lookahead. These games all look a bit like the example below, with board balance alternating between 0 and 0.7071.

I'm thinking that since there are a lot of well-balanced solutions maybe the next step is to add a selection strategy that inserts a symmetry sort before the random pick so that it will prefer various types of symmetry.

Fun puzzle, thanks for posting it!

 O  O  O  O  O  . 
 O  O  O  O  O  O 
 O  O  .  O  O  O 
 O  .  O  O  O  O 
 balance: 0.707

 O  .  O  O  O  . 
 O  O  O  .  O  O 
 O  O  .  O  O  O 
 O  .  O  .  O  O 
 balance: 0.000

 .  .  O  O  O  . 
 O  O  O  .  O  . 
 O  O  .  O  O  O 
 O  .  .  .  O  O 
 balance: 0.707

 .  .  O  O  .  . 
 O  O  O  .  O  . 
 O  O  .  O  .  O 
 .  .  .  .  O  O 
 balance: 0.000

 .  .  O  .  .  . 
 O  O  O  .  O  . 
 .  O  .  O  .  . 
 .  .  .  .  O  O 
 balance: 0.707

 .  .  O  .  .  . 
 O  .  .  .  O  . 
 .  O  .  O  .  . 
 .  .  .  .  .  O 
 balance: 0.000

 .  .  O  .  .  . 
 O  .  .  .  .  . 
 .  .  .  .  .  . 
 .  .  .  .  .  O 
 balance: 0.707

 .  .  .  .  .  . 
 .  .  .  .  .  . 
 .  .  .  .  .  . 
 .  .  .  .  .  . 
 balance: 0.000

Max balance: 0.707
Min balance: 0.000
Avg balance: 0.354
  Play time: 47.43ms