Google Code Jam 2013 – Update: Passed Qualifying!

Well… I started code jam for the first time on Friday night and got a bit of a shock. My preparation was nowhere near enough! I thought I could hit the qualification points a lot easier than I did. The plan was to start with what looked like the easiest problem, complete the small and large data sets and then carry on. However, I was over tired and wasn’t thinking clearly so things didn’t go to plan. I had spent an hour late at night getting nowhere so decided to go to bed. I was pissed off with myself as I was psyched up for this.

A. Tic-Tac-Toe-Tomek
This puzzle gave you grids of 4×4 tic tac toe games which were in a particular game state. You had to write something which would return the state of the board for each case. There were 4 different possible states which were, X won, O won, Draw, Not yet completed.

Example input is:

XXXT
. . . .
OO. .
. . . .

Example output is:
Case #n: X won the game

The way I tackled this problem was to check each row first for a winning game, then column and then finally diagonals. If no win and there were no empty squares (.) then it was a draw, otherwise the game was not completed. Having looked at the sample python code from Google, my C# version was long winded!

B. Lawnmower
We are asked to check patterns for grass cutting as the input. We need to confirm if the pattern is achievable by cutting at a set height for a whole row or column of the lawn.

Example Input:

2 1 2
1 1 1
2 1 2

2 2 2 2 2
2 1 1 1 2
2 1 2 1 2
2 1 1 1 2
2 2 2 2 2

Example Output:
Case #1: YES
Case #2: NO

You can see from the first input we can cut this lawn to the desired pattern as we need 2 runs with the lawnmower across the middle row and middle column cutting to height 1.

However, with the second one you can see there is a square of height 1 in the centre of the lawn. This is impossible because we need to cut from edge to edge and cannot start in the middle. We also cannot grow grass back. So this would be impossible.

For my solution to this, I had 2 versions of the lawn. The starting version which I would cut to then match the desired version. This would give me something to aim for and compare against. Firstly, I decided to cut the whole lawn to the maximum grass height found in the whole lawn. This would trim it down all over and allow me to start cutting individual rows and columns next. Then I would check rows to see if all of the squares in the row were the same height. If they were I would cut them, if not move to the next row. Then I’d do the same for the columns. This would hopefully end me up with either the desired pattern or something different. I could work out my output per test case this way.

I realised my mistake with this after the competition. I had checked the max grass height all over when I should have done this check per row and column.

C. Fair and Square
For this problem we are asked to find all of the “fair” and square numbers within a given range. To quote Google on this the definition of a fair and square number is:

“it is a number that is a palindrome and the square of a palindrome at the same time. For instance, 1, 9 and 121 are fair and square (being palindromes and squares, respectively, of 1, 3 and 11)”

So my method for solving this one was to loop through numbers from 1 to the upper limit (probably should have been the lower limit) and first of all check if that is a palindrome. If it is one, I then get the square of it by multiplying it by itself. If this square number is within the range given to me, I then check again if this square is a palindrome. Again if so, it will be added to my count of fair and square numbers!

I’ll post the code soon so keep an eye out!

D. Treasure
I didn’t attempt this question so I won’t have a valuable discussion about it. I will update this part if I decide to give it a shot!

Summary
I enjoyed my first taste of competitive programming. However, based on this attempt and how long it took me to finish the problems I attempted, there is no way I will make it past the next round. But I need to remember I have done what I set out to achieve and qualified! Bring on the next round.

Leave a Reply