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:
. . . . . .
. . . . . .
. . . . . .
. . . . . .

Since the eggs are grabbed one handed on the edge of the container the ideal balance is some sort of minimized moment of inertia from a rotational axis on the edge?

Or maybe a good scoring algo is just to add up the deviations from the impossible ideal of each row and column. The lower that score, the better balanced the container?

12 eggs: ideal is 3 eggs per row, 2 eggs per column.

2 0 2 2 0 2
O O . . O O   1
O . . . . O   1
O . . . . O   1
O O . . O O   1
score: 12

0 0 0 0 0 0
. O . O . O   0
O . O . O .   0
. O . O . O   0
O . O . O .   0
score: 0 (winner)

9 eggs: ideal is 1.5 eggs per row, 2.25 eggs per column.

1.25 .25 1.25 .25 .25 1.25
. O . O . .   .5
O . . . O .   .5
. O . O . O   1.5
. . O . O .   .5
score: 7.5

1.25 .25 1.25 1.25 .25 .25
O . . . O .   .5
. O . O . O   1.5
. . O . O .   .5
. O . . . O   .5
score: 7.5 (tied)

Sum up the distance of each egg from the center (assuming uniform mass), the closest to 0 wins?

Here's an option for 6x4. Simple selection strategy of picking the most-balanced next move with no look-ahead.

 .  O  O  O  O  O 
 O  O  .  O  O  O 
 O  O  O  O  O  O 
 O  O  O  O  O  . 
balance: 0.707107

 .  O  O  O  O  O 
 O  O  .  O  O  . 
 O  .  .  O  O  O 
 O  O  O  O  O  . 
balance: 0.000000

 .  .  O  O  O  O 
 O  O  .  .  O  . 
 O  .  .  O  O  O 
 O  O  O  .  O  . 
balance: 0.707107

 .  .  O  O  O  O 
 O  O  .  .  .  . 
 .  .  .  O  .  O 
 O  O  O  .  O  . 
balance: 0.000000

 .  .  .  O  O  O 
 O  .  .  .  .  . 
 .  .  .  O  .  O 
 O  O  O  .  .  . 
balance: 0.707107

 .  .  .  O  O  O 
 .  .  .  .  .  . 
 .  .  .  .  .  . 
 O  O  O  .  .  . 
balance: 0.000000

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

 .  .  .  .  .  . 
 .  .  .  .  .  . 
 .  .  .  .  .  . 
 .  .  .  .  .  . 
balance: 0.000000

@davidknaack how are you calculating your balance values?

@drforr so I'm pretty sure "center of mass" is insufficient. Copy/pasting from the Slack discussion:

Trying to figure out how to explain my preference for

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

over

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

in terms of physics... is this a moment of inertia thing? I assure you, those feel very different in my hand (or maybe its just in my head somehow ... I need a double-blind test).
cause I'm grabbing it on one end -- I'm pretty sure that's a real effect while lifting those two different distributions
ya, this is a torque thing in my hand, I think
yup https://en.wikipedia.org/wiki/Moment_of_inertia#/media/File:Rolling_Racers_-_Moment_of_inertia.gif
solid sphere wins cause it's equally distributed
So ... since I'm grabbing it on the end and lifting it with torque (not lifting with two hands from opposite corners or lifting it from the center somehow) is it not something about the moment of inertia from a rotational axis on one end that makes unequal distribution feel too light / heavy?
too light = eggs splattered on my ceiling
too heavy = eggs slammed down onto the floor

( 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