Sunday, April 6, 2014

Machine Graded Programming Tests

While doing my post-graduation in C-DAC (this was the 6 month full time PGDST course at E-city), we found that we'd pass the course only if we passed the minimum number of Machine Graded Programming Tests (MGPT's). These tests were similar to Google Code Jam, where you'd have to submit your program to a software program which will supply various inputs to your program and you pass the test only if each and every one of those inputs give the desired output.

It's a test that makes students very nervous, because lets' say you're writing a program to accept a string and print whether it's a palindrome or not, some programmers won't consider the possibility that the program might receive an empty string as an input. The software which supplies such boundary conditions to your program, was called the "Parikshak" program, in C-DAC. We'd be given our questions and had 45 minutes to write our program on paper. Then, we could go to the lab where we had 45 minutes to type our program, correct it and keep feeding it into Parikshak. We used to wait in trepidation each time we submitted the program to Parikshak, and Parikshak would evaluate the program by supplying inputs to it and we'd see if the outputs were correct, by (if I remember correctly), "X" symbols for every correct output and "-" for every wrong output. If we got even a single "-", we got zero marks for the question, and had to correct our program and re-submit.

The challenge eased:
I decided to put this nervousness to rest by requesting the course coordinator to allow us to create our own questions for Parikshak, so that our classmates could attempt solving it and thereby be prepared for the real MGPT's. Nobody had ever attempted to do this in C-DAC, and our generous course coordinator, Raman sir was happy to allow us (two other programmer enthusiast classmates of mine, joined in) to volunteer. We called ourselves the "Mock MGPT team" (play rock music now for some effect).

So we set out on this new journey with the blessings of both our teachers and our classmates. For me, it was a creative journey too. These are some of the questions I created (just came across them today in an old email and thought I'd post it online):

Question 1:

PROBLEM STATEMENT:
A software error in a data entry software caused the string "MGPT" to get added to some institution names in a list of instutitions in Bangalore. When word got out, the principals of those institutions thought it a pretty good idea to introduce MGPT in their colleges. The students however, are worried, and have pleaded with you to remove MGPT from the list before the principals return from their tea break and take a final decision on the matter.

Your job is to write a program which will locate the "MGPT" string in the institution names and remove the string from the institution name.
If an institution name is CDAC (upper case, lower case or both), you are to leave the MGPT string in that institution name intact.
If the "MGPT" string occurs in any institution name, it will not occur more than once.
All institution names will begin with an alphabet.
Institution names may contain only alphabets, spaces and/or full stops.
The list of institution names have to be sorted alphabetically before being output.
The default priority for alphabetical sorting is: 1.Spaces, 2.Full stops, 3.Upper case letters 4.Lower case letters. (This is the same priority followed by the Java string handling functions)
The "MGPT" string may either consist of upper case or lower case letters.

INPUT:
The first input will be a number N, indicating the number of institution names that will follow.
N number of institution names will be provided, each on a new line.

OUTPUT:
The list of institution names, sorted alphabetically. Each on a new line.


SAMPLE INPUT:

7
Ammgptbc Institute of Technology
Z P College of EngineeringmGpt and Technology
Ghost ColMGptlege of Engineering
MGPTJanaloka Education Institute
JSM College of EngineeringmgpT
cmgPtDac
M. R. College of Engineering

SAMPLE OUTPUT:

Ambc Institute of Technology
Ghost College of Engineering
JSM College of Engineering
Janaloka Education Institute
M. R. College of Engineering
Z P College of Engineering and Technology
cmgPtDac


PROGRAM:
import ncst.pgdst.*;

class m
{

 public static void main(String[] args)throws IOException
 {
  SimpleInput s=new SimpleInput();
  int n=Integer.parseInt(s.readLine());
  String[] word=new String[n];//stores the original strings
  String[] big=new String[n];//strings converted to upper case
  String[] removed=new String[n];//strings with 'mgpt' removed
  for(int i=0;i  {
   word[i]=s.readLine();
   big[i]=word[i].toUpperCase();//convert it to upper case for ease of use
   removed[i]="";
  }//for

  for(int i=0;i  {
   int start=0,end=0;
   String w="";
   start=big[i].indexOf("MGPT");
   if (start>=0)//found the mgpt string
   {
    end=start+4;
    w=word[i].substring(0,start)+word[i].substring(end,word[i].length());
    String temp=w.toUpperCase();
    if (temp.compareTo("CDAC")==0) {w=word[i];}
   }//if
   else w=word[i];
   removed[i]=w;
  }//for

  //sort alphabetically
  for(int i=0;i  {
   for(int j=0;j   {
    if (removed[j].compareTo(removed[j+1])>0)
    {
     String temp=removed[j+1];
     removed[j+1]=removed[j];removed[j]=temp;
    }
   }//for
  }//for

  for(int i=0;i  {
   System.out.println(removed[i]);
  }
 }//main
}//class


-----------------------

Question 2 for Mock MGPT (classmates found this one very amusing)

When Tarzan came swinging to the CDAC campus, he heard of forests and trees being discussed in the classes. The CDAC'ians offered Tarzan three binary search trees to start swinging on, but Tarzan was afraid that if he tried to swing on a leaf node, he'd fall down.
A bunch of monkeys decided to help him with this. The monkeys would climb up onto the trees, according to their ages, in the same way that numbers are inserted into a binary search tree.
Any node which is not null is a node containing a monkey.

Tarzan doesn't like crash-landing on monkeys and he can't swing on the leaf of a tree, so he will swing only on VALID branches of the trees.
He differentiates between VALID branches and leaves (ie:leaf's) this way (this is a little different from conventional terminology)
A VALID branch is a node which is null and has a sibling node which contains a monkey.
A node is a leaf node if it is null and its sibling node is also null.

We will specify a swinging height for Tarzan (one swinging height will apply for all trees) so that he doesn't crash into the CDAC building. The swinging height is always greater than zero. Even if there is a single VALID branch at the specified height on a tree, Tarzan can swing on that tree.
Tarzan will be jumping from the CDAC building, onto the first tree, then to the second tree and then to the third tree, in that order. He doesn't jump after he reaches the third tree. Each time he jumps, he yells "OOOEEOOOYEEEOOOHH". If a tree doesn't have any VALID branches at the specified height, Tarzan falls down and yells "OOH AAH OUCH". Once he falls down, he doesn't attempt to jump onto any more trees.

You have to write a program to create three binary search trees and insert monkeys (age of the monkeys) into the trees. You should output the words that Tarzan yells when he attempts to jump onto the first tree, the second tree and the third tree. Assume the root node to be at a height of zero.


INPUT SPECIFICATION:
Three lines of numbers, each on a new line. The first number N of each line specifies that N numbers (these are the ages of the monkeys) follow it on the same line. The first line of monkey ages are for insertion into the first binary tree, the second line for the second tree and so on.
One number on a new line, specifying the swinging height.

OUTPUT SPECIFICATION:
"OOOEEOOOYEEEOOOHH" (without quotes) if Tarzan can jump onto a tree with VALID nodes.
"OOH AAH OUCH" (without quotes) if he cannot land on a tree because it doesn't have VALID nodes at the specified height.

SAMPLE INPUT/OUTPUT:

Input1:
3 4 2 3
6 10 9 60 5 11 61
6 8 6 21 4 7 30
1

Output1:

OOOEEOOOYEEEOOOHH
OOH AAH OUCH

Input2:
3 4 2 3
6 10 9 60 5 11 61
6 8 6 21 4 7 30
2

Output2:
OOOEEOOOYEEEOOOHH
OOOEEOOOYEEEOOOHH
OOOEEOOOYEEEOOOHH

Input3:
4 4 2 3 5
6 10 9 60 5 11 61
6 8 6 21 4 7 30
1

Output3:
OOH AAH OUCH


PROGRAM:

import ncst.pgdst.*;

class t
{
 public static void main(String[] args)throws IOException
 {
  SimpleInput s=new SimpleInput();

  Node r1=new Node();
  int t=Integer.parseInt(s.readWord());
  for(int i=0;i
  Node r2=new Node();
  t=Integer.parseInt(s.readWord());
  for(int i=0;i
  Node r3=new Node();
  t=Integer.parseInt(s.readWord());
  for(int i=0;i
  int sHeight=Integer.parseInt(s.readWord());
  boolean fell=false;
      //check if first tree has VALID nodes
  if (r1.search(sHeight))
     System.out.println("OOOEEOOOYEEEOOOHH");
  else {System.out.println("OOH AAH OUCH");fell=true;}

  if (!fell)
     {//check if second tree has VALID nodes
      if (r2.search(sHeight))
         System.out.println("OOOEEOOOYEEEOOOHH");
      else {System.out.println("OOH AAH OUCH");fell=true;}
     }
  if (!fell)
     {//check if third tree has VALID nodes
      if (r3.search(sHeight))
         System.out.println("OOOEEOOOYEEEOOOHH");
      else {System.out.println("OOH AAH OUCH");fell=true;}
     }
 }//main
}//class

class Node
{
 Node left,right;
 int value;
 int height;

 Node() {left=null;right=null;value=0;height=0;}
 Node(int v, int h) {left=null;right=null;value=v;height=h;}

 public boolean search(int searchHeight)
 {
  boolean b=false,bv=false;
  if (height==searchHeight-1)
  {
   if ((right!=null && left==null) || (right==null && left!=null)) bv=true;
  }
  else
  {
   if (right!=null) {b=right.search(searchHeight);if (b) bv=true;}
   if (left!=null) {b=left.search(searchHeight);if (b) bv=true;}
  }
  return bv;
 }//search

 public void insert(int v)
 {
  if (value==0) value=v;
  else
  {
   if (v>value)
      {
       if (right==null) {Node n=new Node(v,height+1);right=n;} else right.insert(v);
      }
   else
      {
       if (left==null) {Node n=new Node(v,height+1);left=n;} else left.insert(v);
      }
  }//else
 }//insert

}//Node


--------------------

Question 3:

Students complained that bugs, which accidentally entered the Brinjal curry in the canteen food which they ate, were turning up as bugs in their software programs, which highly inconvenienced them while writing bug-free code during MGPT's.
Following these complaints, the canteen decided to install a device, capable of detecting and driving out bugs from the food with a K.N machine that emits special, patented Keeda-Naashak rays.

The food on a plate consists of many layers of food. Each layer is uniform in constitution, and is represented here with 5 characters. The character representation meaning is given below:
'P' is for a layer of Paapad. 'C' is for a layer of curry. 'R' is for a layer of rice.
'K' is a bug that can be present in any layer of food.
When a bug is present in a layer of food, the layer of food is represented with 4 food characters and one bug character.

The K.N machine emits rays laterally into a plate of food for 2 seconds. This irritates the bug, which immediately crawls up the layers of food and flies away when it reaches the surface.
The bug takes one second to crawl through a layer of food. The exception to this rule is that the bug takes 2 seconds to crawl through the curry layer.
If in the beginning the bug is in a layer of curry or if the bug passes through a layer of curry while crawling up, the bug always takes 2 seconds to crawl through ANY layer of food. Curry layers are not additive. ie: if a bug passes through two layers of curry, it won't take 2+(2+2) seconds to cross the layer. The time taken to cross the two layers of curry will be 2+2=4 seconds.

At the end of the 2 seconds for which the machine scans the food, if the bug is still in the food, the machine displays "KEEDA ALERT" (without quotes) on its screen. If there is no bug or if the bug has managed to reach the surface within the two seconds, the machine displays "CLEAN" (without quotes) on its screen.
You have to write a program to find out if at the end of the 2 seconds of scanning, would the food be bug-free or not. Your output will be the same as what is displayed on the screen of the K.N machine.

Assumptions:
1. The bug always crawls upward perpendicularly.
2. Assume that the number of layers of food will always be: number of layers >= 3 and number of layers <= 5
3. All inputs will be in upper-case characters
4. Assume that there can be only one or no bugs in a plate of food

INPUT:

One integer M, representing the number of plates to be scanned
M number of plate inputs will follow.
A plate input consists of:
One integer N on a new line, representing the number of layers of food in a plate.

N layers of food will follow, each on a new line.

OUTPUT:
"KEEDA ALERT" (without quotes) is displayed for a plate if it has a bug at the end of the two second scan.
"CLEAN" (without quotes) is displayed for a plate if it has no bug in it at the end of the two second scan.


SAMPLE INPUT:
5
4
PPPPP
PPPPP
CCCKC
RRRRR
3
PPPPP
CCCCC
KRRRR
3
PPPPP
RRRRR
KRRRR
5
PPPPP
PPPPP
RRRRR
RRRRK
CCCCC
3
CCCCC
PPPPP
RRRRR

SAMPLE OUTPUT:
KEEDA ALERT
KEEDA ALERT
CLEAN
KEEDA ALERT
CLEAN


CODE:

import ncst.pgdst.*;
class m
{
 public static void main(String[] args)throws IOException
 {
  SimpleInput s=new SimpleInput();
  int plates=Integer.parseInt(s.readWord());
  for(int j=0;j  {
   int n=Integer.parseInt(s.readWord()),foundInLayer=999;
   boolean alert=false,curry=false;
   for(int i=0;i   {
    String layer=s.readWord();
    if (layer.indexOf("K")!=-1 && i>1) {foundInLayer=i;alert=true;}
    if (i<3 amp="" curry="true;<br" layer.indexof="">    if (foundInLayer==2) alert=curry;
   }//for i
   if (alert) System.out.println("KEEDA ALERT"); else System.out.println("CLEAN");
  }//for j
 }//main
}//class


Few interested classmates regularly attempted the mock MGPT's. Some of them were the only ones to crack the real MGPT's too. The sessions were helpful in taking a bit of the tension away from our minds. If I may humbly mention, I was the first one in my class to crack the real MGPT's and eventually was the only one to pass my PGDST course in the first attempt, because I was the only one in a class of 38 (comprising of CS engineers and MCA grads), to clear the necessary number of MGPT's.

The FPGDST (one year course) students had it easy. Their MGPT's were extremely simple. We PGDST (half year course) students had it very tough. Clearing it was not only a challenge, it was satisfying to have given my best shot at something and winning!

2 comments:

varun naidu said...

Good one Naveen. Reminded me of my ordeal with MGPTs. It was a real scare initially, but finally a happy ending :-)

Navin Ipe said...

Hey, nice to see your comment here Varun. You were one of the top programmers in C-DAC. Yeah, my first MGPT was a scare too :) and be a bit careful with the "happy ending" phrase :-D