Google Code Jam Qualification Round
Today was the qualification round for the 2013 Google Code Jam... always my favorite programming contest. I decided to make an attempt at the first three problems, and didn't attack the last problem, given the points I figured a depth first search was too naive to work.
The first problem was a 4x4 tic tac toe game, with wildcard squares. The goal was just to determine if there was a winner, or if it was a draw, or if the game is not done yet. I've done many chess games based on bitmasks, so I decided to use that approach here. I created the masks by hand, they are easy enough to figure out. The problem is then solved with 10 bitwise checks per side, and an additional draw check.
The second problem was about figuring out if a given lawnmower pattern could be achieved given certain rules... first, the lawnmower could only make straight line cuts perpendicular to one of the edges. Second, the height of the blade could only be set at the start of an edge. The lawnmower had to be driven all the way across the grass, at which point you could drive the lawnmower across from another edge starting point. The key insight was that for any given patch of grass, the height had to be greater than or equal to the max height in the row, or the max height in the column. Finding the max for each row and each column has to be done only once, and then once through each patch to do the check, leads to O(n*m) time.
The third problem was sneaky .. but I've been messing around with palindromes for fun with some coworkers, so we had figured out how to get them efficiently as a sequence. The problem asks us to find all numeric palindromes which are also squares of numeric palindromes. So for instance, 121 is a palindrome, which is 11^2, where 11 is also a palindrome. The hard part about this problem is the interval bounds. The small set is only squares less than a thousand, but the middle set could be all such numbers from 0 to 10^14, and the large set was numbers from 0 to 10^100. I gave up on the large data set immediately, figuring that it would take some mathy trick to get it to pass. The key insight for the other two data sets is first recognizing that instead of looking for numbers to be taking the square root of, you start with smaller palindromes, and check to see that the squares are also palindromes. This means we really are only searching for numbers less than 10^7, which is much more tractable. In fact, there are only 10999 palindromes less than 10^7, so I went with the approach of just finding all of the requested numbers in the full range up front. Then, for each interval, just test how many in the list fall within the bounds.
I didn't attempt the last problem, but I did notice a couple of things that could have helped improve the performance of a solution. This problem was described as having a set of locked chests, each which may contain some keys, and each chest can only be unlocked by certain classes of keys. You start with at least one key, and need to check if you can unlock all the chests.
If you go with a depth first search approach, don't include the empty boxes in the initial search. They are outside the critical path, and could be added back in to the critical sequence after the fact, maintaining the "lexigraphical order". Second, at each node of the search, you should probably check if there are enough reachable keys left to unlock any given box... this is a more directed search, and could cut off much more quickly. Third, it may be possible to identify if the graph of chests is fully connected graph up front, and immediately fail without searching for an unlock order if it isn't connected. Other than that, I didn't take a crack at this one.
I hope everyone is enjoying the code jam so far, and am interested in hearing other approaches.
The first problem was a 4x4 tic tac toe game, with wildcard squares. The goal was just to determine if there was a winner, or if it was a draw, or if the game is not done yet. I've done many chess games based on bitmasks, so I decided to use that approach here. I created the masks by hand, they are easy enough to figure out. The problem is then solved with 10 bitwise checks per side, and an additional draw check.
The second problem was about figuring out if a given lawnmower pattern could be achieved given certain rules... first, the lawnmower could only make straight line cuts perpendicular to one of the edges. Second, the height of the blade could only be set at the start of an edge. The lawnmower had to be driven all the way across the grass, at which point you could drive the lawnmower across from another edge starting point. The key insight was that for any given patch of grass, the height had to be greater than or equal to the max height in the row, or the max height in the column. Finding the max for each row and each column has to be done only once, and then once through each patch to do the check, leads to O(n*m) time.
The third problem was sneaky .. but I've been messing around with palindromes for fun with some coworkers, so we had figured out how to get them efficiently as a sequence. The problem asks us to find all numeric palindromes which are also squares of numeric palindromes. So for instance, 121 is a palindrome, which is 11^2, where 11 is also a palindrome. The hard part about this problem is the interval bounds. The small set is only squares less than a thousand, but the middle set could be all such numbers from 0 to 10^14, and the large set was numbers from 0 to 10^100. I gave up on the large data set immediately, figuring that it would take some mathy trick to get it to pass. The key insight for the other two data sets is first recognizing that instead of looking for numbers to be taking the square root of, you start with smaller palindromes, and check to see that the squares are also palindromes. This means we really are only searching for numbers less than 10^7, which is much more tractable. In fact, there are only 10999 palindromes less than 10^7, so I went with the approach of just finding all of the requested numbers in the full range up front. Then, for each interval, just test how many in the list fall within the bounds.
I didn't attempt the last problem, but I did notice a couple of things that could have helped improve the performance of a solution. This problem was described as having a set of locked chests, each which may contain some keys, and each chest can only be unlocked by certain classes of keys. You start with at least one key, and need to check if you can unlock all the chests.
If you go with a depth first search approach, don't include the empty boxes in the initial search. They are outside the critical path, and could be added back in to the critical sequence after the fact, maintaining the "lexigraphical order". Second, at each node of the search, you should probably check if there are enough reachable keys left to unlock any given box... this is a more directed search, and could cut off much more quickly. Third, it may be possible to identify if the graph of chests is fully connected graph up front, and immediately fail without searching for an unlock order if it isn't connected. Other than that, I didn't take a crack at this one.
I hope everyone is enjoying the code jam so far, and am interested in hearing other approaches.
Comments
Post a Comment