Google Code Jam 2012 Underway – Qualifications Round Live Blog

The 2012 Google Code Jam is underway!

As a participant in this year’s event, I’ll be live blogging throughout the entire competition (or as far as I make it, anyways). If you’ve read this much, and still have no idea what we’re talking about, check out Zach’s article about the Google Code Jam events. Otherwise, let’s dig in.

1:15AM EST – Problem 3 Solved – sort of.

So I locked up the points for the Problem 3 short data set. Also made sure to submit the proper source file! However, the large data set was a way too much for my code. I failed to make it very efficient, choosing iterative over mathematical. Also I stuck w/ my core language of PHP for a highly iterative string comparison script. If was going to do something like that on a large scale, I could have at least used Perl. My 8 minute window to submit my answers expired before the script even got done with the first case. *sadface*

Even if I had forked these cases across the sixteen cores available to me on this machine, I still wouldn’t have gotten it done in time! Oh well. There’s no time based criteria in this round, so I’m going to crash for the night. I’ll wrap up Problem 2 tomorrow AM/afternoon to solidify my 20 points. I’ll also go ahead and prep my code so it will publish here immediately after the round expires.

For all of those still coding, good luck!

12:05AM EST – Oops on Problem 1 and Problem 3 kicking my butt

So I realized while working on Problem 3 that I uploaded the wrong source file for my Problem 1 set. Whoops. I’ll need to make sure I get another 20 points, as I don’t want to risk being disqualified for failing to submit the proper source for my Problem 1 answer.

As for Problem 3, I’m so close to solving it. The example input file given I’m getting 3/4 cases correct. Trying to find that last missing piece, and hopefully I can pick up a full twenty points between both the small and large sets here.

I was looking for some fancy math to do this work for me, but settled w/ some iteration that’s working great. Also helps to have some monster computing power to leverage for these calculations, so I don’t have to seek to be too efficient on this. As eluded above, however, something is slightly off. I’m still missing a few recycled sets, and once I pinpoint what they are, I can figure out why I’m missing them and hopefully lock this up!

10:15 EST – Solved Problem 1

This took me about 30 minutes to knock out. Most of that time was spent trying to look for some sort of trick. I assume there’s not, and it is as simple as it looks. I’ll post my source after the round is over.

Oh, Google. Here’s a couple of my translated lines from my data set:

Case #15: translating text is not goros strength
Case #16: strength is goros strength

(See Zach’s article on Google Code Jam for the goro reference.)

Case #20: oh my god lets make out
Case #27: now that you know googlerese please do not use it to hack into our systems

~ 9:00pm EST – First looks

The contest opened up two hours ago, and I’m finally getting my first look at the problems. This is the qualification round, and only 20 points are needed to advance to the next round. There are four questions in total. The questions give a scenario and you submit your code to answer either a small, large, or both set of inputs. Large sets sometimes will award more points than the smaller sets, as a large data set will expose more variability and problems that a smaller, limited data set will not.

Problem 1: Speaking in Tongues

We have come up with the best possible language here at Google, called Googlerese. To translate text into Googlerese, we take any message and replace each English letter with another English letter. This mapping is one-to-one and onto, which means that the same input letter always gets replaced with the same output letter, and different input letters always get replaced with different output letters. A letter may be replaced by itself. Spaces are left as-is.

For example (and here is a hint!), our awesome translation algorithm includes the following three mappings: ‘a’ -> ‘y’, ‘o’ -> ‘e’, and ‘z’ -> ‘q’. This means that “a zoo” will become “y qee”.

Googlerese is based on the best possible replacement mapping, and we will never change it. It will always be the same. In every test case. We will not tell you the rest of our mapping because that would make the problem too easy, but there are a few examples below that may help.

Given some text in Googlerese, can you translate it to back to normal text?

This problem looks relatively simply, and only offers a small input worth 15 points. This is probably the first one I’ll attempt to tackle.

Problem 2: Dancing with the Googlers

You’re watching a show where Googlers (employees of Google) dance, and then each dancer is given a triplet of scores by three judges. Each triplet of scores consists of three integer scores from 0 to 10 inclusive. The judges have very similar standards, so it’s surprising if a triplet of scores contains two scores that are 2 apart. No triplet of scores contains scores that are more than 2 apart.

For example: ( 8, 8, 8 ) and ( 7, 8, 7) are not surprising. ( 6, 7, 8 ) and (6, 8, 8 ) are surprising. ( 7, 6, 9 ) will never happen.

The total points for a Googler is the sum of the three scores in that Googler’s triplet of scores. The best result for a Googler is the maximum of the three scores in that Googler’s triplet of scores. Given the total points for each Googler, as well as the number of surprising triplets of scores, what is the maximum number of Googlers that could have had a best result of at least p?

For example, suppose there were 6 Googlers, and they had the following total points: 29, 20, 8, 18, 18, 21. You remember that there were 2 surprising triplets of scores, and you want to know how many Googlers could have gotten a best result of 8 or better.

I have a faint idea on how I might solve this, but still prefer to solve Problem 1. If I can get Problem 1 solved, I’ll try to tackle the smaller set here, which is worth 10 points.

Problem 3: Recycled Numbers

Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don’t care about television, but I do sometimes feel that way about numbers.

Let’s say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits (excluding leading zeros) in order to be a recycled pair.

Given integers A and B with the same number of digits, how many distinct recycled pairs (n, m) are there with A ≤ n < m ≤ B?

Also have a good idea on how to do this. Will actually jump to this one before Problem 2. Still like Problem 1 the most so far.

Problem 4: Hall of Mirrors

You live in a 2-dimensional plane, and one of your favourite places to visit is the Hall of Mirrors. The Hall of Mirrors is a room (a 2-dimensional room, of course) that is laid out in a grid. Every square on the grid contains either a square mirror, empty space, or you. You have width 0 and height 0, and you are located in the exact centre of your grid square.

Despite being very small, you can see your reflection when it is reflected back to you exactly. For example, consider the following layout, where ‘#’ indicates a square mirror that completely fills its square, ‘.’ indicates empty space, and the capital letter ‘X’ indicates you are in the center of that square:

######
#..X.#
#.#..#
#...##
######

f you look straight up or straight to the right, you will be able to see your reflection.
Unfortunately in the Hall of Mirrors it is very foggy, so you can’t see further than D units away. Suppose D=3. If you look up, your reflection will be 1 unit away (0.5 to the mirror, and 0.5 back). If you look right, your reflection will be 3 units away (1.5 to the mirror, and 1.5 back), and you will be able to see it. If you look down, your reflection will be 5 units away and you won’t be able to see it.

It’s important to understand how light travels in the Hall of Mirrors. Light travels in a straight line until it hits a mirror. If light hits any part of a mirror but its corner, it will be reflected in the normal way: it will bounce off with an angle of reflection equal to the angle of incidence. If, on the other hand, the light would touch the corner of a mirror, the situation is more complicated. The following diagrams explain the cases:

In the following cases, light approaches a corner and is reflected, changing its direction:

In the first two cases, light approached two adjacent mirrors at the point where they met. Light was reflected in the same way as if it had hit the middle of a long mirror. In the third case, light approached the corners of three adjacent mirrors, and returned in exactly the direction it came from.

In the following cases, light approaches the corners of one or more mirrors, but does not bounce, and instead continues in the same direction:

This happens when light reaches distance 0 from the corner of a mirror, but would not have to pass through the mirror in order to continue in the same direction. In this way, a ray of light can pass between two mirrors that are diagonally adjacent to each other — effectively going through a space of size 0. Good thing it’s of size 0 too, so it fits!

In the final case, light approaches the corner of one mirror and is destroyed:

The mirror was in the path of the light, and the ray of light didn’t approach the corners of any other mirrors.

Note that light stops when it hits you, but it has to hit the exact centre of your grid square.

How many images of yourself can you see?

I’m easily distracted by pretty pictures, and this is definitely a tl;dr scenario. I’ll pass for now and focus on Problem 1.