Author Archives: Nico Heid

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.

image by Steven Depolo

Even though I could not participate in this years google code jam qualification round, I want to provide you my solution for magic trick.

I actually failed to implement it correctly on the first try. My idea was that after the volunteer chose the row in the first grid, all the cards of this row needed to be in different rows on the second grid. Which is probably how you’d set up the trick too, if you’d perform it.

The thing is, you can still be lucky by placing only the correct card in the row the volunteer actually picks into it’s own new row. The other three can be either in the same row, or wherever. It doesn’t matter.

Let’s assume we start with this as our first grid

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

If you think of your pattern as a matrix it becomes clear, that by laying down the transponse (read the columns and write them as rows) of your matrix, you can always solve what the volunteer picked.

1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

This would be the logical thing to do, but you can also just depend on your good luck and try something like this:

1 2 3 5
4 5 6 7
9 10 11 12
13 14 15 16

If the user actually picked the 4, it is still solveable. But if he picked 1, 2 or 3 you’d have no chance to determin which card it was because you failed to spread them into different rows.

And this was the mistake, I forgot that the magician can be lucky even if he did not lay out the cards as transponse of his first grid.

So here’s my solution (or go to github)

public void solve() {

        int cases = in.nextInt();

        for (int j = 1; j <= cases; j++) {
            out.print("Case #" + j + ": ");

            // first card
            int rowWithCard = in.nextInt();
            in.nextLine();
            List row1 = getRow(rowWithCard);

            //second card
            rowWithCard = in.nextInt();
            in.nextLine();
            List row2 = getRow(rowWithCard);

            if (!isWizardWithoutFailure(row1, row2)) {
                out.println("Bad Magician!");
                continue;
            }

            String result = findCard(row1, row2);
            if (result == null) {
                out.println("Volunteer cheated!");
                continue;
            } else {
                out.println(result);
            }
        }
    }


    // get the card from the chosen row, every other row is not interesting
    private List getRow(int chosenRow) {
        List cardRow = new ArrayList();
        for (int row = 1; row <= 4; row++) {
            if (chosenRow == row) {
                cardRow.addAll(Arrays.asList(in.nextLine().split(" ")));
            } else {
                in.nextLine();
            }
        }
        return cardRow;
    }

    // check if the wizard did lay down less than two cards from the previous row picked by the volunteer
    private boolean isWizardWithoutFailure(List row1, List row2) {
        int matchingCards = 0;

        for (String card : row1) {
            if (row2.contains(card)) {
                matchingCards++;
            }
        }
        if (matchingCards > 1) {
            return false;
        }

        return true;
    }

    // find the duplicate card, if there is none, volunteer cheated
    private String findCard(List row1, List row2) {
        for (String card : row1) {
            if (row2.contains(card)) {
                return card;
            }
        }

        return null;
    }