solutions for the google codejam qualifications 2013

Code Jam 2013 Qualification Round Answers to problems a-b-c

problem A : Tic-Tac-Toe

you can check the problem statement from codejam 2013 site:

https://code.google.com/codejam/contest/2270488/dashboard#s=p0

Answer

First loop on the diagonals , then loop on each row and column. While looping maintain two variable Xcount and Ycount , which you will increase whenever you counter a symbol (increase Xcount on finding 'X', increaseYcount on finding 'Y', increase Xcount and Ycount on finding 'T') , after each loop end check those variables, if one of them equals 5 (not 4 because I initialized them with 1) , the corresponding player is a winner, else you have two possibilities Draw or NotComplete, if there was a '.' in the input, the result is NoTcomleteGame else, Draw.

Coding

 import java.io.BufferedReader;  
 import java.io.BufferedWriter;  
 import java.io.File;  
 import java.io.FileNotFoundException;  
 import java.io.FileReader;  
 import java.io.FileWriter;  
 import java.io.IOException;  
 public class qual1 {  
      static BufferedWriter writer;  
      static BufferedReader reader;  
      public static void main(String args[]) throws IOException {  
           int newLineChar = 13;  
           File inFile = new File("input.txt"); // input file  
           File outFile = new File("output.out"); // outfile  
           FileWriter fwriter = new FileWriter(outFile);  
           writer = new BufferedWriter(fwriter);  
           FileReader freader = new FileReader(inFile);  
           reader = new BufferedReader(freader);  
        int numCases = Integer.parseInt(reader.readLine());  
           System.out.println("numcases = " + numCases);  
           for (int i = 0; i < numCases; ++i) {  
                System.out.println();  
                char[][] board = new char[4][4];  
                int curr;  
                char currC;  
                boolean notComplete = false;  
                for (int row = 0; row < 4; ++row) {  
                     String line = reader.readLine();// read thr row  
                     for (int col = 0; col < 4; ++col) {  
                          currC = line.charAt(col);  
                          board[row][col] = currC;  
                          System.out.print(currC);  
                          if (currC == '.') {  
                               notComplete = true;  
                          }  
                     }  
                     System.out.println();  
                }  
                checkScore(board, i, notComplete);  
                reader.readLine();  
           }  
           writer.close();  
      }  
      private static void checkScore(char[][] board, int caseNum,  
                boolean notComplete) throws IOException {  
           // TODO Auto-generated method stub  
           // check diagonals first  
           // first diagonal  
           int j = 0;  
           int xcount = 1;  
           int ycount = 1;  
           boolean tFound = false;  
           for (int i = 0; i < 4; ++i) {  
                if (board[i][j] == 'T') {  
                     ++xcount;  
                     ++ycount;  
                } else if (board[i][j] == 'X') {  
                     ++xcount;  
                } else if (board[i][j] == 'O') {  
                     ++ycount;  
                }  
                ++j;  
           }  
           if (xcount == 5) {  
                writer.write("Case #" + (caseNum + 1) + ": X won");  
                writer.newLine();  
                return;  
           }  
           if (ycount == 5) {  
                writer.write("Case #" + (caseNum + 1) + ": O won");  
                writer.newLine();  
                return;  
           }  
           // ///////////////////////////////////////////////////////////////////////  
           // second diagonal  
           j = 3;  
           xcount = 1;  
           ycount = 1;  
           tFound = false;  
           for (int i = 0; i < 4; ++i) {  
                if (board[i][j] == 'T') {  
                          ++xcount;  
                          ++ycount;  
                } else if (board[i][j] == 'X') {  
                          ++xcount;  
                } else if (board[i][j] == 'O') {  
                          ++ycount;  
                     }  
                --j;  
           }  
           if (xcount == 5) {  
                writer.write("Case #" + (caseNum + 1) + ": X won");  
                writer.newLine();  
                return;  
           }  
           if (ycount == 5) {  
                writer.write("Case #" + (caseNum + 1) + ": O won");  
                writer.newLine();  
                return;  
           }  
           // ////////////////////////////////////////////////////////////////////////  
           // checking rows and cols  
           for (int i = 0; i < 4; ++i) {  
                xcount = 1;  
                ycount = 1;  
                tFound = false;  
                for (int row = 0; row < 4; ++row) {  
                     if (board[row][i] == 'T') {  
                          ++xcount;  
                          ++ycount;  
                     } else if (board[row][i] == 'X') {  
                          ++xcount;  
                     } else if (board[row][i] == 'O') {  
                          ++ycount;  
                     }  
                }  
                if (xcount == 5) {  
                     writer.write("Case #" + (caseNum + 1) + ": X won");  
                     writer.newLine();  
                     return;  
                }  
                if (ycount == 5) {  
                     writer.write("Case #" + (caseNum + 1) + ": O won");  
                     writer.newLine();  
                     return;  
                }  
                xcount = 1;  
                ycount = 1;  
                tFound = false;  
                for (int col = 0; col < 4; ++col) {  
                     if (board[i][col] == 'T') {  
                          ++xcount;  
                          ++ycount;  
                     } else if (board[i][col] == 'X') {  
                          ++xcount;  
                     } else if (board[i][col] == 'O') {  
                          ++ycount;  
                     }  
                }  
                if (xcount == 5) {  
                     writer.write("Case #" + (caseNum + 1) + ": X won");  
                     writer.newLine();  
                     return;  
                }  
                if (ycount == 5) {  
                     writer.write("Case #" + (caseNum + 1) + ": O won");  
                     writer.newLine();  
                     return;  
                }  
           }  
           if (notComplete) {  
                writer.write("Case #" + (caseNum + 1) + ": Game has not completed");  
                writer.newLine();  
                return;  
           }  
           writer.write("Case #" + (caseNum + 1) + ": Draw");  
           writer.newLine();  
           return;  
      }  
 }  

codejam 2013 prob a

problem B : Lawnmower

you can check the problem statement from  codejam 2013 site:

https://code.google.com/codejam/contest/2270488/dashboard#s=p1

Answer

First we map the desired pattern into a two dimensional array.

The idea is to find an element in the pattern which will make it an impossible pattern. Such element will be the one that you cant cut it vertically or horizontally, because if you do you will mess up another element.

                                           codejam 2013 prob b

Therefore, we start by calculating the max elements for each row and maximum element in each column, then we loop on the array elements, if we found an element that is not maximum in its row and not maximum in its column we mark the pattern as impossible.

Coding

 import java.io.BufferedReader;  
 import java.io.BufferedWriter;  
 import java.io.File;  
 import java.io.FileReader;  
 import java.io.FileWriter;  
 import java.io.IOException;  
 public class qua2 {  
      static BufferedWriter writer;  
      static BufferedReader reader;  
      /**  
       * @param args  
       * @throws IOException  
       */  
      public static void main(String[] args) throws IOException {  
           File inFile = new File("input2.txt"); // input file  
           File outFile = new File("output2.out"); // outfile  
           FileWriter fwriter = new FileWriter(outFile);  
           writer = new BufferedWriter(fwriter);  
           FileReader freader = new FileReader(inFile);  
           reader = new BufferedReader(freader);  
           int numCases = Integer.parseInt(reader.readLine());  
           System.out.println("numcases = " + numCases);  
           // looping on number of cases  
           for (int i = 0; i < numCases; ++i) {  
                boolean impossible = false;  
                String[] intalizingString = reader.readLine().split(" ");  
                String rows = intalizingString[0];  
                String cols = intalizingString[1];  
                int N = Integer.parseInt(rows);  
                int M = Integer.parseInt(cols); // M---->cols  
                System.out.println("N-->rows = " + N);  
                System.out.println("M-->cols = " + M);  
                // creating the int array representing the lawn  
                int[][] lawn = new int[N][M];  
                // reading the array  
                for (int j = 0; j < lawn.length; ++j) {  
                     String line = reader.readLine();// read the row  
                     int spointer = 0;  
                     String nums[]=line.split(" ");  
                     for (int k = 0; k < lawn[j].length; ++k) {  
                          lawn[j][k] = Integer.parseInt(nums[k]);  
                          System.out.print(lawn[j][k] + " ");  
                          spointer = spointer + 2;  
                     }  
                     System.out.println();  
                }  
                // ///starting the algorithm/////  
                int[] maxRows = new int[N];  
                int[] maxCols = new int[M];  
                // calculating the max of each row  
                for (int row = 0; row < N; ++row) {  
                     int max = -1;  
                     for (int col = 0; col < M; ++col) {  
                          if (lawn[row][col] > max)  
                               max = lawn[row][col];  
                     }  
                     maxRows[row] = max;  
                }  
                // calculating the max of each column  
                for (int col = 0; col < M; ++col) {  
                     int max = -1;  
                     for (int row = 0; row < N; ++row) {  
                          if (lawn[row][col] > max)  
                               max = lawn[row][col];  
                     }  
                     maxCols[col] = max;  
                }  
                // checking each element  
                for (int row = 0; row < N; ++row) {  
                     if (impossible)  
                          break;  
                     for (int col = 0; col < M; ++col) {  
                          if (lawn[row][col] < maxRows[row]  
                                    && lawn[row][col] < maxCols[col]) {  
                               // pattern is impossible  
                               impossible = true;  
                               break;  
                          }  
                     }  
                }  
                if (impossible) {  
                     System.out.println("NO");  
                     writer.write("Case #" + (i + 1) + ": NO");  
                     writer.newLine();  
                } else {  
                     System.out.println("YES");  
                     writer.write("Case #" + (i + 1) + ": YES");  
                     writer.newLine();  
                }  
           }  
           writer.close();  
      }  
 }  

codejam 2013 prob b

problem C : Fair and Square

you can check the problem statement from  codejam 2013 site:

https://code.google.com/codejam/contest/2270488/dashboard#s=p2

Answer

Here we start form index zero, if the current index is palindrome  we check its square, if the square is outside the range, then we are done,else if the square is palindrome we increase the count, 

                                                               codejam 2013 prob c

Coding

 import java.io.BufferedReader;  
 import java.io.BufferedWriter;  
 import java.io.File;  
 import java.io.FileReader;  
 import java.io.FileWriter;  
 import java.io.IOException;  
 public class qual3 {  
      static BufferedWriter writer;  
      static BufferedReader reader;  
      public static void main(String[] args) throws IOException {  
           File inFile = new File("input3.txt"); // input file  
           File outFile = new File("output3.out"); // outfile  
           FileWriter fwriter = new FileWriter(outFile);  
           writer = new BufferedWriter(fwriter);  
           FileReader freader = new FileReader(inFile);  
           reader = new BufferedReader(freader);  
           int numCases = Integer.parseInt(reader.readLine());  
           System.out.println("numcases = " + numCases);  
           // looping on number of cases  
           double current = 0;  
           int count = 0;  
           for (int i = 0; i < numCases; ++i) {  
                String[] intalizingString = reader.readLine().split(" ");  
                String ss = intalizingString[0];  
                String es = intalizingString[1];  
                double start = Double.parseDouble(ss);  
                double end = Double.parseDouble(es);  
                System.out.println("start = " + start);  
                System.out.println("end = " + end);  
                count = 0;  
                for (double j = 0; j <= end; ++j) {  
                     String currS = getNumberFormated(j+"");  
                     //System.out.println(currS);  
                     double square = Math.pow(j, 2);  
                     if (square > end) {  
                          break;  
                     }  
                     if (square < start) {  
                          continue;  
                     }  
                     if (checkPalindrom(currS)) {  
                           square = Math.pow(j, 2);  
                          String sq = getNumberFormated(square+"");  
                          if (checkPalindrom(sq)) {  
                               ++count;  
                          }  
                     }  
                }  
                writer.write("Case #" + (i + 1) + ": " + count);  
                writer.newLine();  
           }  
           writer.close();  
      }  
      static boolean checkPalindrom(String num) {  
           int n = num.length();  
           for (int i = 0; i < n / 2; i++)  
                if (num.charAt(i) != num.charAt(n - i - 1))  
                     return false;  
           return true;  
      }  
      static String getNumberFormated(String number)  
      {  
           if(number.contains("E")){  
                String[] splited = number.split("E");  
                double zeros = Double.parseDouble(splited[1]);  
                String[] numParts = splited[0].split("\\.");  
                StringBuilder firstPart = new StringBuilder();  
                firstPart.append(numParts[0]+numParts[1]);  
                for (int i = 0; i < zeros; i++) {  
                firstPart.append("0");  
                }  
                return firstPart.toString();       
           }  
           return number.split("\\.")[0];  
      }  
 }  

codejam 2013 prob c

Creating C++ templates

C++ Templates

C++ templates is a way to make your code generic, ie: you can call a function with any data type,

C++ uses this technique in its Abstract Data types such as vectors and lists,

to create a list of integers : list<int> intlist,

to create a list of strings: list<string> stringlist.

How to define functions using templates

Templates are implemented in C++ as Macro expansions, as they are not resolved in run time but actually in compile time,

consider the following function definition :

template <class myType>
myType GetMax (myType a, myType b) {
 return (a>b?a:b);
}
and to call the function:

int x,y;

GetMax<int>(x,y);

here template <class myType> is a parameter to the compiler to change “mytype” any where in the function with the word you define in the function call (here it is “int”)

How to define classes using Templates

template <class myType>
call MyClass{
 public: Myclass();
}
template <class myType>

 MyClass::Myclass<myType>(){                                               
}

Note: we must always notify the compiler that we are using templates using template keyword template<class mytype>

Implementing disjoint sets in C++

Implementing disjoint sets in C++ using path compression and union by rank

introduction

Disjoint sets are very useful data structures that are used in many famous Algorithms, and you might consider using them in designing algorithms that include some sort of union behavior.
In this post i will show you how to implement a Disjoint List efficiently using C++, and i consider that you already know what a Disjoint List is.
the source code is attached.

overview

the implementation is as follows,
a disjoint list is a list of disjoint nodes objects, each node is holding a generic node of data_type defined by the user.
Each Disjoint Node has a list of all its childrens.

mian functions are :

• list.unionlist(x), unions the list with list x
• list.find(DisjointNode n), finds the representative (root) of the list holding node n 

The Disjoint Node

the node of our Disjoint list is called DisJointNode and it has the following structure,
CoreNode, a generic object
ParentPointer , pointer to the node's parent in the disjoint list
Childs, a list of node's children which we will use to iterate n the whole list

Here is the DisJointNode.h

 #ifndef DISJOINTNODE_H  
 #define DISJOINTNODE_H  
 #include<list>  
 #include<vector>  
 #include <string>  
 using namespace std;  
 template<class a_type> class DisJointNode {  
 public:  
      a_type coreNode; //input by user contains core info  
      DisJointNode<a_type> *parent; //linking structure  
      std::list<DisJointNode<a_type> *> *childs; //we need this list for iteration and deletion perposes  
      int rank;  
 public:  
      string setName;  
      DisJointNode();  
      DisJointNode(a_type node);  
      void setParent(DisJointNode<a_type>*paren);  
      virtual ~DisJointNode();  
 protected:  
 };  
 ///////////////////////////////////////////////////////////////////////////////////////////  
 template<class a_type> DisJointNode<a_type>::DisJointNode(){  
 }  
 template<class a_type> DisJointNode<a_type>::DisJointNode(a_type node) {  
      this->setName="NONAME";  
      this->coreNode = node;  
      this->parent = NULL;  
      this->rank = 0;  
      this->childs = new std::list<DisJointNode<a_type> *>();  
 }  
 template<class a_type> void DisJointNode<a_type>::setParent(  
           DisJointNode<a_type>*paren) {  
      this->parent = paren;  
 }  
 template<class a_type> DisJointNode<a_type>::~DisJointNode() {    
      delete (childs);  
 }  
 #endif // DISJOINTNODE_H  

Note:
when a Node is created, its initial parent is the node it self.

The DisjointList

A Disjoint list will include pointer to a DisJointNode (root), all the nodes of a given list will be linked to the list's root such that parent of a node is another node in the list or the root of the node,

DisJointList.h

 #ifndef DISJOINLIST_H  
 #define DISJOINLIST_H  
 #include "DisJointNode.h"  
 #include<list>  
 #include <iostream>  
 #include <string>  
 using namespace std;  
 /**  
  we must include the implementation in the header file  
  why? because...what ever iam too lazy to know  
  **/  
 template<class a_type> //indicate a template type to the compiler  
 class DisjoinList {  
 protected:  
 public:  
      string name;  
      DisJointNode<a_type> *root;  
      void getList(std::list<DisJointNode<a_type>*> *input);  
      DisjoinList(DisJointNode<a_type> *root); //make set  
      DisjoinList(); //make set  
      DisJointNode<a_type>* find(DisJointNode<a_type> *x); //find set  
      void unionSets(DisjoinList<a_type> *x); //Union set  
      void Link(DisJointNode<a_type> *x, DisJointNode<a_type> *y,  
                DisjoinList<a_type> *list);  
      virtual ~DisjoinList();  
 private:  
      void getListRecursive(std::list<DisJointNode<a_type>*> *input,  
                DisJointNode<a_type> *root);  
 };  
 ///////////////////////////////////////////////////////////////////////////////////////// cpp  
 template<class a_type>  
 DisjoinList<a_type>::DisjoinList()  
 {  
 }  
 template<class a_type>  
 void DisjoinList<a_type>::getList(std::list<DisJointNode<a_type>*> *input) {  
      //in order traversal  
      getListRecursive(input, this->root);  
 }  
 template<class a_type>  
 void DisjoinList<a_type>::getListRecursive(  
           std::list<DisJointNode<a_type>*> *input, DisJointNode<a_type> *root) {  
      //in order traversal   
      typename std::list<DisJointNode<a_type> *>::iterator it =  
                root->childs->begin();  
      input->push_front(root);  
      for (int i = 0; it != root->childs->end(); ++it) {  
           getListRecursive(input, *it);  
      }  
      return;  
 }  
 /**  
  * constructor, root node is input  
  */  
 template<class a_type>  
 DisjoinList<a_type>::DisjoinList(DisJointNode<a_type> *root)  
 {  
      this->root = root;  
      this->root->parent = this->root;  
 }  
 template<class a_type>  
 void DisjoinList<a_type>::unionSets(DisjoinList<a_type> *x) {  
      Link(this->root, x->root, x);  
 }  
 template<class a_type>  
 DisJointNode<a_type>* DisjoinList<a_type>::find(DisJointNode<a_type> *x) {  
      if (x->parent != x) {  
           x->parent = find(x->parent);  
      }  
      return x->parent;  
 }  
 /**  
  * links two lists by adjusting their roots  
  */  
 template<class a_type>  
 void DisjoinList<a_type>::Link(DisJointNode<a_type> *x, DisJointNode<a_type> *y,  
           DisjoinList<a_type> *list) {  
      if (x->rank > y->rank) {  
           y->parent = x;  
           x->childs->push_front(y); // adding y to x's childs  
           list->root = x;  
      } else {  
           x->parent = y;  
           y->childs->push_front(x); // adding y to x's childs  
           this->root = y;  
      }  
      if (x->rank == y->rank) {  
           (y->rank)++;  
      }  
 }  
 template<class a_type>  
 DisjoinList<a_type>::~DisjoinList() {  
      if (root == NULL)  
                return;  
           std::list<DisJointNode<a_type> *> *nodes;  
           getList(nodes);  
           delete (nodes);  
 }  
 #endif // DISJOINLIST_H  

Note:

• when unioning two lists we must adjust their roots childs and parents 
• getList() makes an inorder traversal on the list's nodes
• Since we are using pass compression the method Find() sets x->parent = find(x->parent) until we reach the root node, this means that when find() is called again on the same node find() will return in O(1).
• when the destructor ~DisjoinList() is called this means that the list is being deleted, at this point we must delete all the nodes of the list 

What is a device driver

What is a device driver

 initial understanding:

device driver is a software that the OS use to communicate with the device, ie using its functionality, ex: the driver of a mouse device, the OS needs an interface to communicate with the mouse, when you connect the mouse to the machine, a stream of data is transferred from the mouse to the device, HOW THE OS MANAGES THIS STREAM?!

formal definition:

in computing, a device driver is a computer program that operates or controls a particular type of device that is attached to a computer. A driver typically communicates with the device through the computer bus or communications subsystem to which the hardware connects. When a calling program invokes a routine in the driver, the driver issues commands to the device. Once the device sends data back to the driver, the driver may invoke routines in the original calling program. Drivers are hardware-dependent and operating-system-specific. They usually provide the interrupt handling required for any necessary asynchronous time-dependent hardware interface

http://en.wikipedia.org/wiki/Device_driver

Main Function:

A device driver simplifies programming by acting as translator between a hardware device and the applications or operating systems that use it.[1] Programmers can write the higher-level application code independently of whatever specific hardware the end-user is using. Physical layers communicate with specific device instances. For example, a serial port needs to handle standard communication protocols such as XON/XOFF that are common for all serial port hardware. This would be managed by a serial port logical layer. However, the physical layer needs to communicate with a particular serial port chip. 16550 UART hardware differs from PL-011. The physical layer addresses these chip-specific variations. Conventionally, OS requests go to the logical layer first. In turn, the logical layer calls upon the physical layer to implement OS requests in terms understandable by the hardware. Conversely, when a hardware device needs to respond to the OS, it uses the physical layer to speak to the logical layer.
http://en.wikipedia.org/wiki/Device_driver

Windows and Linux Device Drivers:
In Linux environments, programmers can build device drivers either as parts of the kernel or separately as loadable modules. Makedev includes a list of the devices in Linux: ttyS (terminal), lp (parallel port), hd (disk), loop (loopback disk device), sound (these include mixer, sequencer, dsp, and audio)...[3]
The Microsoft Windows .sys files and Linux .ko modules contain loadable device drivers. The advantage of loadable device drivers is that they can be loaded only when necessary and then unloaded, thus saving kernel memory.
http://en.wikipedia.org/wiki/Device_driver

Device drivers are dangerous!!

since device drivers mostly run in Kernel Mode, the can cause system unstability and falier,normal user mode programs are safe beacause the OS can kill their process if they made a fault or unprevilage instruction, for this who develop a device driver must be very familliar with the underline hardware, usually hardware vendors implement their device drivers.

Logical Device Drivers (LDD) VS Physical Device Drivers (PDD)

LDD is a layer above the PDD, LDD is implemented typically by the OS vendor, while the PDD by the hardware Vendor.
programms communicate with the LDD to request a certain task from the hardware in a logical way what ever the underlining hardware is, for example, a serial port needs to handle standard communication protocols such as XON/XOFF that are common for all serial port hardware. This would be managed by a serial port logical layer. However, the physical layer needs to communicate with a particular serial port chip. 16550 UART hardware differs from PL-011. The physical layer addresses these chip-specific variations. Conventionally, OS requests go to the logical layer first. In turn, the logical layer calls upon the physical layer to implement OS requests in terms understandable by the hardware. Conversely, when a hardware device needs to respond to the OS, it uses the physical layer to speak to the logical layer.

in the above figure, the Operating System Abstract Layer is the Logical Device Driver (LDD), while the drivers in the next level are the Physical Device Drivers(PDD).



what is the Board Support Package (BSP) ??

the board support package is the soft ware that wrape all the device derivers for all devices on your board, The board support package has many drivers and it installs the necessary drivers permanently on your computer and it does the following,
 initializes the whole board, brings it up getting all peripherals initaialised, and most importantly jumps to present boot loader, and of course also provides primitive set of drivers support such as disk drive etc.
it also:

•     Initialize the processor.
•     Initialize the bus.
•     Initialize the interrupt controller.
•     Initialize the clock.
•     Initialize the RAM (random access memory) settings.
•     Configure the segments (if applicable).
•     Run the boot loader.

note: Windows Embedded Compact 7 includes a set of standard device drivers for each board support package (BSP) that it supports.
http://www.linuxforums.org/forum/kernel/89588-difference-between-board-support-package-device-driver.html
http://whatis.techtarget.com/definition/board-support-package