Google Code Jam Problem B.

Currently Listening to:
KOAN Sound - Sly Fox
Funkanomics - The Goonies Island

CSCI 462 has no more required blog posts. Now it is time to start blogging about specific problems I have been having as well as observations that I have.

Last weekend I participated in the Google Code Jam. This online programming competition is open to students and professionals alike. Out of the 4 problems I solved 2 of them with small and large datasets, and one of them with just a small dataset bringing my score for the competition to 80 (you only need 35 to qualify for the next round). My favorite problem to solve from a critical thinking standpoint was problem B, the lawnmower problem. 

The problem stated that if you have a patch of grass and a lawnmower that can only cut in straight (horizontal and vertical) lines, would it be possible to create the given pattern. Originally I was going to solve the problem by just checking to see if the rows and columns had a valid line, but this misses test cases. 

Eventually I got to the point where I figured that if you remove the smallest valid line that the lawnmower made (i.e. the last pass chronologically that the lawnmower made) and remove that line, you can work your way back in time until you have the original lawn. For the sake of simplicity I just removed the line out of my list completely and if I had a list of nothing it at the end of the loop was a valid lawn, otherwise if I still had stuff in the list something went wrong and it wasn't a valid cut. The method for checking is to find the smallest value in the list and checking to see if either the horizontal or vertical line was filled with the same values. So this is what a lawn looked like as it ran through the code:

2 1 2

1 1 1

2 1 2

(bold and underline is the smallest)

changed to:

2 2

1 1

2 2

which changed to:

2 2

2 2

which eventually turned into an empty list. That meant that it was a valid lawn. If at any point both the horizontal and the vertical check failed it would break out of the loop, which caused the "isEmpty" to be called and a judgement of the lawn set. My problem B solution can be found here.