Balance the eggs!
Problem
You just bought a full \$2 \times 5\$ carton of \$10\$ eggs:
For now on, we will depict cartons with ASCII art. The top-view of the above carton would look like:
+-----+
|ooooo|
|ooooo|
+-----+
To save on production costs, the egg factory has a master egg. Every egg produced is an identical clone of the master egg, so you may assume that all eggs are the same weight and volume.
Since these eggs are of pristine quality, they come with a hefty price. You decide that it would be better if you ordered them in bulk and stack them in a freezer so that you're stocked for the whole year. Managing all those eggs is tedious, so you also design and build a robot, to automatically pick random eggs every morning for you. They have to be random so that the robot's gears wear out evenly and don't jam.
As the robot takes out \$4\$ eggs out of the carton:
+-----+
|.oo.o|
|.ooo.|
+-----+
the carton becomes unbalanced. We have \$2\$ rows, an even number, so the \$X\$-axis passes between them and seperates the carton into two regions, \$X_{top}\$ and
\$X_{bottom}\$:
X_top
+-----+
|.oo.o|
X -------
|.ooo.|
+-----+
X_bottom
And we have \$5\$ "columns", an odd number, so the \$Y\$-axis passes ontop of the middle column of eggs. It ignores the middle column and seperates the carton into two regions again, \$Y_{left}\$ and \$Y_{right}\$. Thus, we end up with four regions:
X_top
Y
|
+--|--+
|.oo.o|
Y_left X ---+--- Y_right
|.ooo.|
+--|--+
|
X_bottom
While munching on eggs and admiring your creation, you realize a terrible mistake you've made. As more and more cartons become unbalanced, the stacks become unstable. Soon, egg cartons will start falling, and they might even land on other cartons! A cascading-chain-egg-carton-fall-apocalypse!
Randomly picking eggs uniformly should've already taken care of this, but the hardware RNG is bugged. Buying new hardware is very costly and it would arrive too late anyway. You don't have enough space in the freezer to unstack the cartons either and you certainly don't have enough time to unfreeze and eat so many eggs. You have only one option.
Goal
You have to update the robot's firmware to automatically balance a carton.
Balancing
To balance a carton, you realize that the following conditions suffice:
- The number of eggs in the \$X_{top}\$ region of the carton must be equal to the number of eggs in the \$X_{bottom}\$ region.
- Extending that condition, the two regions must be the reflection of each other, mirrored either through a single axis or both axes.
- Similarly for the \$Y_{left}\$ and \$Y_{right}\$ regions.
If you were to balance the previous carton, you'd get:
+-----+
|.ooo.|
|.ooo.|
+-----+
After some thinking, you realize a second solution is also possible:
+-----+
|o.o.o|
|o.o.o|
+-----+
But you don't really care, as long as the carton is balanced. You name these perfect cartons. A full carton would also qualify, as would a fully empty carton.
An invalid solution, however, would be this:
+-----+
|o.oo.|
|o.oo.|
+-----+
While condition 1 is satisfied, the regions \$Y_{left}\$ and \$Y_{right}\$ are not reflections of each other, so condition 2 is not satisfied.
Condition 2 (Mirror regions)
Examples of mirror regions through a single axis:
X regions Y regions X & Y regions
.o. o.|.o .o|o.
... .o|o. ..|..
----- o.|.o ---+---
... ..|..
.o. .o|o.
In some cases, reflections through both axes must be considered for a solution to count as valid. In the \$2 \times 5\$ carton, for example, this configuration is considered perfectly balanced:
+-----+
|oo..o|
|o..oo|
+-----+
and thus constitutes a third solution. Let's break it down:
X_top
Y
|
+--|--+
|oo..o|
Y_left X ---+--- Y_right
|o..oo|
+--|--+
|
X_bottom
In shorter form:
oo . .o
o. . oo
Ignoring the middle column, as it's already symmetric:
oo|.o
--+--
o.|oo
Reflecting \$X_{top}\$ through both axes:
Through X-axis first Then through Y-axis (but order doesn't matter)
oo|.o | | |
--+-- => --+-- --+-- => --+--
| oo|.o oo|.o o.|oo <- Same as X_bottom!
Reflecting \$Y_{left}\$ through both axes:
Through X-axis first Then through Y-axis (again, order doesn't matter)
oo| o.| o.| |.o
--+-- => --+-- --+-- => --+-- <- Same as Y_right!
o.| oo| oo| |oo
Respectively \$X_{bottom}\$, \$Y_{right}\$.
This allows for many more valid solutions:
+-----+ +-----+ +-----+ +-----+ +-----+
|o..oo| |.oo.o| |.oo.o| |.o.oo| |oo.o.|
|oo..o| |o.oo.| |o.oo.| |oo.o.| |.o.oo|
+-----+ +-----+ +-----+ +-----+ +-----+
All of the above are perfectly balanced; balanced on both the \$X\$ and \$Y\$ axes.
Edge cases
After skimming through your digital egg database, you realize that some cartons cannot be perfectly balanced. This carton:
+-----+
|..o..|
|..o.o|
+-----+
doesn't have enough eggs that you can move around to balance it! It would need atleast one more. Throwing eggs away just to balance a carton is overly wasteful and the robot's CPU is too slow to calculate whether it can borrow eggs from other cartons; it can only handle one carton at a time. Fortunately, not many of such cartons are actually in your freezer, so you believe that it's enough to balance on atleast one of the axes, either \$X\$ or \$Y\$. These are imperfect cartons.
Two example solutions of the above would be:
+-----+ +-----+
|..o..| |.....|
|o...o| |o.o.o|
+-----+ +-----+
The second solution might seem inferior to the first one, or that it should be outright rejected. But remember: the carton is imperfect, so it's enough to balance on a single axis. Here, specifically, the carton is balanced on the \$Y\$-axis in both solutions.
Non-cases
In a sudden moment of mathematical thinking, you discover that there are also some cartons that cannot be balanced at all. This carton:
+--+
|..|
|.o|
+--+
cannot be balanced on either axis, it's an unbalanceable carton. You query your database and... No such carton exists in your freezer! After some head-scratching, it becomes apparent that, to prevent future headaches, you should handle these cartons in one of the following ways:
- Leave them unchanged.
- Try to (unsuccessfully) balance them, but preserve their number of eggs and size.
Thus, for the carton above, any of these - and only these - following outputs is valid:
+--+ +--+ +--+ +--+
|..| |..| |o.| |.o|
|.o| |o.| |..| |..|
+--+ +--+ +--+ +--+
The robot must not crash on unbalanceable cartons under any circumstances!
Input
Since the robot can only handle one carton at a time, the firmware should accept a single carton as input. As you've had this egg setup for a while now, you've developed multiple formats for digitally storing your eggformation. Every carton is available in various formats, so you use the most convenient one for you. Example formats include:
ASCII art:
+-----+ +-----+
|.oo.o| or | oo o| or .oo.o
|.ooo.| | ooo | .ooo.
+-----+ +-----+
List of lists:
[[0,1,1,0,1], or negated [[1,0,0,1,0], or [[False, ...],
[0,1,1,1,0]] [1,0,0,0,1]] [False, True, ...]]
List:
Carton = list[int] # Or `list[bool]`.
def balanced_carton(rows: int, cols: int, carton: Carton) -> Carton:
...
output = balanced_carton(2, 5, [0,1,1,0,1, 0,1,1,1,0])
Binary blob, including bitmap images.
Combination of the above, as long as it's documented.
While the eggs are all identical, the cartons are not! Your freezer contains cartons of various sizes. Your formats reflect that and your new firmware must handle any size of carton.
Output
Your output must be a single carton, as well-balanced as possible, in whatever format you find most convenient. Given the first carton as an example, if you were to output in the "ASCII art" format, your output could be:
+-----+
|o.o.o|
|o.o.o|
+-----+
or any other valid solution.
To achieve consistent carton configurations, if the input carton is already balanced, the robot is allowed to rebalance it and arrive at a different - or the same - solution.
The firmware should not output whether the carton is perfect/imperfect/unbalanceable.
Constraints
- You don't want to go through this again, so you won't cut any corners (no loopholes)!
- The robot's onboard EEPROM is but a
few bytes. Your code must be as small as possible (code-golf)!
Examples
TODO
code-golf
.gif){kind=link}
