Code jam

Google Code Jam is an international programming competition hosted and administered by Google. The competition began in 2003 as a means to identify top engineering talent for potential employment at Google. The competition consists of a set of algorithmic problems which must be solved in a fixed amount of time. Competitors may use any programming language and development environment to obtain their solutions. From 2003 to 2007, Google Code Jam was deployed on Topcoder’s platform and had quite different rule, since 2008 Google has developed their own dedicated infrastructure for the contest. For more information one can refer this link. Participating in such a competition helps you to increase your programming capabilities. It also enhances your logical thinking. So I decided to solve Google code Jam as practice, starting from 2017 qualification round and there by sharing my solution in this blog.

Oversized Pancake Flipper

This is the first problem in code jam qualification round 2017. The summery of the problem is as below. There are few number of pancakes which has one side made of chocolate chips (called as “happy side” )and a blank side. They are arranged in a single row in a random sides facing up. You have one pancakes flipper which flips exactly K consecutive pancakes.(NOT less than that or more than that) You need to find out the minimum number of times you need to use the flipper to leave all the pancakes happy side up or state there is no way to do it. For detailed version of this problem, one can refer this link. This contest is open for practice. I encourage you to solve it first before reading this solution.

Solution

Consider the below example given. —+-++- 3

The capacity of Pancake Flipper is 3. Your ultimate goal is to keep all the pancakes facing upside. i.e, (++++++++) with minimum number of attempts. If not possible then state, IMPOSSIBLE. One solution to this is,

  1. Start from the first pancake.
  2. Check if it facing black side upwards. i.e, Check if it is ‘-’.
  3. If yes, then flip 3 consecutive pancakes. (3 because it is the capacity of pancake flipper)
  4. Then check the next (has to increase by one )pancake.
  5. Then go step 2 and repeat it for total number of pancakes. Also make sure it is not less than that of capacity of pancake flipper.
  6. Once the step 5 is done, check whether all the pancakes remain happy side upwards. If yes print the number times you flipped as solution. If no, then we have no way to do it. So state IMPOSSIBLE.

Below are few sample solutions based on above steps.

Case 1:

—+-++- 3

Step 1 : +++ +-++-

Step 2 : ++++ +–-

Step 3 : +++++ +++

After final stage, it is ++++++++. And bolded text indicates the state, after being flipped. So here all the cakes are facing happy sides upwards. And we have used flipper for 3 times. So the solution is 3.

Case 2 :

-+-+- 4

Step 1 : +-+-

Step 2 is not possible. Now the second cake remains blank side upwards. ( + - + -). But we have left with only 3 cakes which is less than 4. (the capacity of pancake flipper). Now we are at the end. When we checked if all the cakes are facing happy side upwards, we get NO as answer. So the solution is IMPOSSIBLE.

The implementation of this solution in C++ is as below.

#include<iostream>
#include<string.h>
#include <bits/stdc++.h>
using namespace std;

main()
{
    int No_Of_Trial; 
    cin >> No_Of_Trial;
    for(int Trial= 1;Trial<=No_Of_Trial;Trial++)
    {
      //Get the pancake positions
      string pancake;
      cin>>pancake;

      // Number of pancakes in current trial
      int n = pancake.size(); 

      //Get the Pancake Flipper's capacity
      int k; 
      cin>>k;

      //Final solution 
      int Number_Of_Flips = 0;

      for(int i=0;i+k <= n;i++)
      {
 if(pancake[i] == '-')
 {
 
   for(int j=i;j< i+k;j++)
   {
      pancake[j] = (pancake[j] == '+') ? '-' : '+'; //Flip the pancake 
   }
      Number_Of_Flips++;

 }
      }
      //Now we have flipped pancakes. Check which trials are full of happy faces;
      //if all are happy faces, then print the number of flips as solution
      //otherwise print "IMPOSSIBLE"

      bool All_Happyside = true;
      for (int i = 0; i < n; i++)
      {
 All_Happyside = (pancake[i] == '+');
 if(All_Happyside == false) 
   break;
      }
      printf("Case #%d: ", Trial);
      if (All_Happyside)
 printf("%d\n", Number_Of_Flips);
      else
  printf("IMPOSSIBLE\n");
      
    }
   
    return 0;
}

You can download the complete solution from below github link.

https://github.com/s-gopinath/Codejam_2017

I am nearly about to complete the next post “Tidy Number”. I will post it soon as my next post.