How to Tackle Programming Problems (Google Code Jam 2017 Qualification Round, Problem A)

Jessica YungProgramming, UncategorizedLeave a Comment

giphy

This is a walkthrough of how one might start thinking about Problem A (small input) of Google Code Jam’s 2017 Qualification Round (April 8-9).

Google posts excellent solutions to their problems, so the focus here will be that of the idea generation process or how one might begin to tackle such problems. Full problem statements can be found here.

Problem A (Oversized Pancake Flipper)

Problem: We have a row of pancakes, some ‘happy side’ up and some blank side up. We can flip precisely k consecutive pancakes at a time. Print the minimum number of flips needed to make all the pancakes ‘happy side’ up. If it is not possible, print ‘IMPOSSIBLE’.

The first thing to do is to understand the problem.

1. Understand the problem: Draw a Picture

We can do this by drawing a picture.

Each pancake can either be happy side up or blank side up. That is, it has two states. It can be good to represent this in binary in case there are binary-related tricks we can use. So let’s represent happy-side-up pancakes by ‘0’ and blank side up pancakes using ‘1’. Our goal is to reduce our binary number to 0.

samplecases_repr.jpg

2. Understand the problem: Solve small cases manually

Let’s first solve small cases manually and see if our solutions use the minimum number of flips.

Why do this? 

  • Solving the problem gives you part of the answer (an upper bound to the number of flips / whether or not it is possible to flip all pancakes happy side up), gives you a feel for the problem and gives you a framework for working out the optimal solution.
  • Psychologically it’s much better if you know you can solve it than if you’re just sitting there worrying about edge cases and are not writing anything down.

Case 1: 11101001, k = 3.

samplecase_1.png

11101001 -> 00001001 -> 00000111 -> 00000000. 3 flips required.

  • We can’t do it it fewer than three flips: It is not possible to flip the 1s in the first, fifth and eighth positions in two flips. This is because you can only flip one of those at a time when k = 3, and we need to flip all three of those 1s to be finished.

Case 1 is useful for identifying patterns used to solve the problem. We can say we saw the ‘111’ on the far left and then thought it was obvious to flip all of those, then moved on to the next ‘1’ to the right. So we’ve identified two possible patterns here:

  • Flip the blocks of k 1s (or the most consecutive 1s).
  • Go from left to right. This has the effect of ‘herding’ the 1s to the right and ensuring we do not flip the same block twice.

We’ll come back to these later.

Case 2: 00000. We don’t need to do anything. 0 flips required.

Case 3: 10101, k = 4.

k4

It is impossible. Any flip that flips the 0 in the second position also flips the 1 in the third position, so we can’t flip the pancakes such that both the second and the third will be zeroes (happy side up).

Case 3 is interesting because it’s an example of there being no solution, but this case seems contrived because you can immediately tell there is no solution. Can we come up with examples where there is no solution?

fe8d69b51835b240d51001ef914e86bc_kid-drawing-on-wall-cartoon-clipart-of-cartoon-people-that-kids-can-draw_345-321

3. Come up with your own cases and find patterns or apply your strategy

Let’s try 10101 with k = 3.

Let’s use the strategy we came up with before: going from left to right. At each step, we flip starting at the leftmost position where there is a 1. By doing so we guarantee that there will be no ‘1’s from that position onwards at the next step.

k3_owncase

 

It took us three flips and was possible.

4. Is your strategy optimal?

Now we have to answer two questions: (1) can we show that this always produces the minimum number of flips required? (2) If we can’t solve the problem this way, does it mean it definitely can’t be solved, or might we have missed something?

(1) Can we show that this always produces the minimum number of flips required?

  • Does the order of flips matter?
    • No. Each flip reverses the state of each digit (pancake) within the flip. This does not depend on when the flip occurred.
      • In some problems it would matter, e.g. if each pancake had to be flipped before a certain time was up.
  • Now that we know the order doesn’t matter, we only have to show that the flips we use were all necessary.
    • We definitely had to flip all the 1s. We started with the leftmost 1.

(2) If we can’t solve the problem this way, does it mean it definitely can’t be solved, or might we have missed something?

  • Observe that two patterns are ‘the same’ in terms of solvability if you push all the ‘1’s to one end and you end up with the same ‘k’ digits.
    • e.g. in our last example, 10101, 01001 and 00111 with k = 3 are the same because if you push all the 1s to the end you get 00111. (Or 00000 if you include the last flip.)
  • So now we have to show that, after pushing all the 1s to one end, if the last ‘k’ digits are not all 1s or 0s, there is no solution.
    • (Or we could be wrong, in which case we wouldn’t be able to show this.)
    • We will prove this by contradiction. Warning: The following section is a bit abstract and messy.
      • Suppose there was some solution that involved re-flipping pancakes that weren’t in the last ‘k’ positions.
      • Consider the first not-just-last-k-positions flip. Each of these flips would increase the number of 1s in the currently all-0 region.
        • e.g. suppose we had 00000101, k=3.
        • proof_by_contradiction
        • Flip 5th-7th positions -> 00001011.
      • Let the total number of digits be n. Then we have (n-k) + k digits. We know that the last k digits are not soluble on their own. Neither are the first (n-k) digits, because there are a cluster of fewer than k ‘1’s at its end. Thus any solution would involve flips on the boundary of the first (n-k) and the final k digits. But then we’re back to where we started.
        • I’m aware the last sentence is not rigorous – will try to phrase this better and update this soon.
    • This might seem a bit long-winded – in a contest you might just say to yourself that it seems likely that this would work and just hope you were right. 😛

5. Key takeaways

the_gift_of_yaks_509955

  • Understand the problem by drawing a picture.
    • It may be useful to represent problems in binary.
  • Solve small cases manually to get a feel for the problem.
  • If applicable, when is there no solution?
  • Ideas:
    • Does the ordering matter? If not, were the moves all necessary?
    • Can we show that two inputs are essentially the same e.g. when it comes to solvability?

Hopefully this gives you an idea of the thought process behind tackling a programming problem. Happy programming!

Further reading

 

Leave a Reply