by Michael Stern
The Infinite House of Pancakes seems to be rather easy to solve at first glance. I did pick this puzzle right after solving Standing Ovation, thinking it should be only slightly harder, given it has only 9pts compared to the 7pts from Standing Ovation.
I was wrong.
My idea on how to solve this was simple, too simple. I did put all plate sizes in an array, located the highest plate(s) and took half of the pancakes off. I compared the number of steps needed before and after, and if it was better or equal after, I repeated the process until it did not get better. Voila.
No, “incorrect”. And it kept saying incorrect to me until I had to depart, leaving the puzzle behind but still taking it along in the head, trying to figure out what was wrong.
Let’s check with an example.
9 3 1 -> 5 4 3 1 -> 3 2 4 3 1 -> 3 2 2 2 3 1 -> 2 1 2 2 2 2 1 1
9 turns on the starting number of steps if we just let it be. I use 1 move to split the 9 into 5 and 4 and get to 6 steps (1 move + 5 eats). Better, so we keept that. Use another move (2 now) to split the 5 which gets to 6 (2+4) which is equal, lets still keep that. Now split the 4 (3rd move) giving us 6 again (3+3). Oh well, now split the 3s (needs 2 moves) giving us 7 (5+2) which is worse. So our answer is 6 steps.
I was missing the cruical point: it might be better to split a stack in multiple stacks, not just take half of it off. Splitting the 9 into three 3s and not into 5 and 4 is the move that makes the difference.
9 3 1 -> 3 3 3 3 1
Which is 2 moves and 3 eats. Giving you a 5 (2+3), which is better than the 6 we got with our previous algorithm.
Even though the puzzle crossed my mind a couple times after the qualification round, I did have to wait and check the solutions page to get that idea, which makes me feel a bit ashamed. I do only find comfort in the fact, that during the round less than half of the contestants solved this correctly.
After being given that hint, the implementation was done rather quickly with less code than I did write for the first algorithm.
Try ever plate size from one to max and see how many steps it would take.
-> on github
public void solve() {
private int checkPlates(List plates) {
int max = Integer.MAX_VALUE;
int fullestPlate = plates.stream().max(Integer::compare).get();
for (int i = 1; i <= fullestPlate; i++) {
int moves = 0;
for (int p : plates) {
if (p > i) {
moves += p / i;
if (p % i == 0) {
moves--; // if it divides evenly we actually took all pancakes off the plate, which is one move more than we need
}
}
}
if (moves + i < max) {
max = moves + i;
}
}
return max;
}
The code jam solutions page is even more elaborate with some more optimizations, so head over there and check it out.
Nico Heid
Latest posts by Nico Heid (see all)
- Raspberry Pi Supply Switch, start and shut down your Pi like your PC - August 24, 2015
- Infinite House of Pancakes – code jam 2015 - July 13, 2015
- google code jam 2014 – magic trick - April 18, 2014