MagicalTux in Japan

After talking about Double Squares and Peg Game, here is the last of the serie: Studious Student.

At first it may look like the easiest problem, however there is a trap here. Reading the problem quickly may let you think “oh, I just do alphabetical order and stick the words together”, but no. If you think that you’re doomed. I say that because I saw an example code on internet (in Java) which does exactly that while claiming to provide the right answer for this Facebook puzzle.

Facebook helped you a lot by putting this special case in the examples provided in the page (if it was me, I wouldn’t give it out that easily). Let’s have a look at this example:

5 jibw ji jp bw jibw

If you just order this in alphabetical order, you get “bw ji jibw jibw jp”, but this is not the right answer. The right answer would be “bw jibw jibw ji jp”. That’s because alphabetical order will count a word which is equal to the beginning of the next word as having precedence. This rule is irrelevant here since all the words are concatenated into a single string.

At this third problem I was still feeling brutal, so I wrote another bruteforcing code. I noticed the maximum of word count was rather low (9 words) which makes bruteforcing a viable solution again. Going through all the possible permutations for a given set is easy (with some recursive function calls) and with only 9 elements to play with, the maximum number of values I would have to test was 362880. Of course it’ll take some time, but not that much (actually it took 30 seconds to run in PHP).

I just generate every single possible permutation, and I compare it with my “current lowest”. If the new one is lower I replace the “current lowest”, then continue to the next value. Simple. And provides the expected result.

~

As I said my only regret here is having Facebook include the trap in the example values given on the page. But still, it must have cleared a lot of the “I never read exercice texts” guys.

So, that’s all for now. I’ll be doing this again next week after the first round!

Tags: Bruteforce, FaceBook, Hacker Cup, Hacker Cup 2011

Continuing my previous post, let me explain the second game now: Peg Game.

The concept is simple: there is a board with pegs, and a ball falls from the top. Each time it hits a peg, it has 50% chances of going to the left, and 50% chances going to the right, except if one of the directions is not available (the peg is on the side of the board). Sometimes pegs are missing (the board is old) and in this case the ball has nothing to hit, and has 100% chances of falling (gravity helping). The first and last lines of pegs are guaranteed intact. Also the board size is variable (but the first and last lines will always be wide lines).
The goal is to find the entry point with the most chances of arriving to a given exit.

Since I’m still in my “let’s be brutal” mood, I’ll be using a brutal way of solving this problem. I’ll be tracking chances from each entry point (holes between pegs on the first line), processing line after line until I reach the end, then I’ll check probability at goal point for each entry point and take the best one.

By checking the examples provided by Facebook I noticed that if two entry point have the same highest probability of win, the left-most one is to be taken.

For example a 5×5 board looks likes this:

 | | | |
x x x x x
>x x x x<
x x x x x
>x x x x<
x x x x x
 | | | |

On this 5×5 board, we have 4 entry points, and 4 exit points, indexed starting at zero. Missing peg coordinates ignore empty space.

For this exercices too I decided to go with PHP, and have some fun bruteforcing every possible outcome for all the entry points, in order to then select the outcome most fitting for our need (best chances of reaching goal).

The first step is to create a in-memory representation of the board (including missing pegs). I decided to use two dimentional arrays, and use the value to know what I have in a given place: nothing (false), a peg (true) or the board limits (NULL). A 5×5 board will be represented as a 9×5 array (I take empty spaces into account).
I then initialize my “probability” array for the first line, in which the probability of my ball being in column 1 when dropped in column 1 is 100%, etc. (probability of ball being in column 0 is 0 anyway, I coded that to avoid doing a special case for those).

I then iterate each line of my peg board through a function that will generate the new ball position probability for each initial position based on the line being analyzed. By default previous probability is inherited. If I hit a false (nothing) then nothing happens. If I hit a true (peg) in middle of board, half of the value is added to left and right cells, and current cell is set to zero, and if the peg is on the side of the board, probability is moved in the opposite direction. I shouldn’t hit NULL with a non-zero probability, but I coded it anyway (moves probability one or two cells toward the middle based on the existance of a peg or not in the next cell).

This proved to run quite fast despite using PHP (~60 seconds to run on facebook’s input file, which is less than the alloted 6 minutes) and gave the right results, which is good.

Tags: Bruteforce, FaceBook, Hacker Cup, Hacker Cup 2011

The “2011 Facebook Hacker Cup” is currently happening, and the qualification stage has just finished as I write those lines.

Since I like solving fun problems I took part and solved all 3 problems and will  be progressing to next stage. The goal here is speed (code won’t be reviewed by Facebook staff, but you need to produce results fast) so I decided to trade CPU cycles for development time. It took less time to write the code, but the CPU usage will be a bit more intensive than what it could be if I took time to optimize the code and fine more elegant ways to produce the required output.

So, let me explain the first one, called “Double Squares”. The problem here is quite simple, and revolves around the following equation:

x² + y² = a

Only a is known. x and y are both integer values between 0 and 2147483647 (0x7fffffff, the maximal value for a signed integer). The goal is not to find x or y, but to determine how many values of x and y can yield to the equation being true. And reversing values for x and y do not count as an extra solution.

First, let’s make this equation a bit easier to handle, shall we? What if we write our equation this way:

y = sqrt(a – x²)

We could then cycle through the possible values of x, compute y each time and see if it is integer. The problem makes things even easier:

• We know the minimal value of y is 0, which means the maximal value for x would be sqrt(a). Since the maximal value for a is 2147483647, this means x will never be over 46340.
• To avoid duplicate values of x and y we can stop as soon as y goes below x. This also means that in the worst case, we’ll have to test half of all the possibilities (23170 iterations in worst case is viable)

Looks like bruteforce is a viable solution.

My implementation in PHP needed about 200ms with the values from Facebook’s input. I was a bit disappointed it ran this fast (can’t really call it bruteforce) but at least the result is good.

Tags: Bruteforce, FaceBook, Hacker Cup, Hacker Cup 2011