Twitcaps: Watching the World, in Real-Time

Hacker Cup - Problem #2 - Peg Game Solution

The brute force solution solved the sample inputs in a timely manner, which should not be a surprise given that the largest grid in the test set is only 5x4. After I constructed a test set with a 100x100 matrix, things took a predictable turn for the worse. I allowed it run for 30 minutes without result, and didn’t stick around to see the final outcome. Remember, we only have 6 minutes after downloading the input to submit an answer.

Brute force will not suffice.

Being a complete mathematical noob, I began searching for algorithms I could use to solve the problem in a timely and efficient manner. Two ideas in particular helped me out.

1. Pascal’s Triangle

The first thing I discovered was that, in terms of the data structure for probabilities, I’m dealing with something very similar to Pascal’s Triangle, only instead of each node being the sum of its two parents, each node’s probability to a specific coordinate is the sum of its children’s probabilities (divided by two) to that same coordinate.

This was my first clue toward optimization.

I can model a Slot object that contains a reference to each of its two child slots, unless there is an edge or missing peg to drop through. Then, I can calculate the probability from any given slot, to any other slot by recursively traversing the parent child relationships.

Previously, I had just been modelling slots as a two dimensional array of probabilities and crawling the peg grid every single time for, literally, every single path. Now I’ll have a self-referential data structure that I can create once and reuse for every path calculation.

Half way there.

2. Dynamic Programming

The problem still remains that I am going to be traversing the same paths, over-and-again, wasting time recalculating jumps I’ve already made in previous iterations.

Here’s where I’ll have to thank Facebook for the clue “Too hard for brute force switching to dp”.

We’ll switch to dp, then, or Dynamic Programming.

Dynamic programming refers not to the use of a dynamic programming language - Ruby, Python, Groovy, etc. - but rather to the mathematical concept that deals with breaking large problems up into groups of subproblems, particularly where the large problems consist of often overlapping subproblems.

This technique is frequently employed in situations where recursion would normally be used, but is too expensive for brute force algorithms. Genetic sequencing, or a Peg Game where you will be traversing the same paths repeatedly, for ridiculous example.

With the recent improvement to my data structure, and my existing recursion code, I’m well on my way to implementing a dp technique.

Really, all I need now is a way to store the pathing probabilities once they’ve been calculated, a technique called Memoization.

To do this, I’ll create a two dimensional array in each Slot that represents the probability for arriving at any other given slot from the current one. This way, once a path has been walked and its probability calculated, it is stored in memory and can be accessed directly the next time the path is overlapped by another one.

Each unique path will be walked a maximum of one time. That’s quite an improvement.

Of course, this drastically increases the memory footprint of our application as we are storing a double[][] array representation of the entire grid within every Slot of the grid.

Remember our worst case? 100x100 slots, and each one storing a 100x100 matrix inside itself? That’s 100,000,000 x size of a double in Java. There’s probably a better way to do this, but for now, I’ll just crank the JVM up with -Xmx1024m and forget about it.

After implementing dp, my program now executes in just under 2 seconds against the worst case data. 

I downloaded the official contest data from Facebook and it ran all 20 tests in 5.4 seconds. Not terrible at all.

I’m not going to post all of the code here for constructing the Slot objects according to the rules of the game, but I will offer up the meaty part of the Slot code, and the engine that powers my dp implementation.

Again, I’m sure there are better ways to do this, but this should be good-enough:

public class Slot {
    public Slot rightSlot;
// FYI, for consistency, I'm always storing the children of slots directly above a missing peg in the leftSlot
    public Slot leftSlot;
    public double[][] probabilities;
    public boolean[][] hasCalculated;
    int row;
    int column;

 //...skipping down to interesting code...// 

// Row and Column parameters represent the ultimate TARGET coordinates to find
    public double getScore(int row,int column) {
           if(hasCalculated[row][column])
                return probabilities[row][column];

           double probability = 0.0;
           
           if(rightSlot!=null && leftSlot!=null) {
                double rightProb = rightSlot.getScore(row, column);
                double leftProb = leftSlot.getScore(row, column);
                probability = (rightProb+leftProb)*0.5;
           } else if(rightSlot!=null) {
                probability = rightSlot.getScore(row, column);
           } else if(leftSlot!=null) {
                probability = leftSlot.getScore(row, column);
           } else if(this.row==row && this.column == column) {
                probability = 1.0;
           }
            hasCalculated[row][column] = true;
            probabilities[row][column] = probability;
    return probability;
   }
}

—————

UPDATE 01/10/2011 

I optimized further by making the size of each Slot’s internal double[][] array’s first dimension scalable to the scope of its purview. For example, on a 100x100 board, a Slot that exists on the top level still stores a 100x100 array of probability results, but a slot that lives on the 99th row only stores a 2x100 array of results. (Yes, I am scaling only rows right now. One change at a time!)

Of course, I now need to account for the local row offset in my getScore() code, but that’s not a big deal.

With this small change, I’m now able to successfully pass the contest data in 1.8s.

Obviously, there are further optimizations to be gained.

1. Scale the columns the same as the rows.
2. Do not store a rectangle. The data structure of possibilities for any given path is a actually a triangle.
3. Compute from the bottom up. Start with the target coordinates and work your way up. You’ll need to change the way getScore() works and your Slot relationships, but it’d be worth it.

Both of these should be easy enough to implement, but the round is now over and I’m ready to think about new problems.

Hacker Cup - Problem #2 - Peg Game

I was saving this problem for last because I suspected it would give me the most trouble. Turns out that intuition was spot on. 

Part of the problem, is that the requirements aren’t 100% clear. Read on through the Facebook problem statement and then rejoin at the bottom for my commentary.

————————

Peg Game

At the arcade, you can play a simple game where a ball is dropped into the top of the game, from a position of your choosing. There are a number of pegs that the ball will bounce off of as it drops through the game. Whenever the ball hits a peg, it will bounce to the left with probability 0.5 and to the right with probability 0.5. The one exception to this is when it hits a peg on the far left or right side, in which case it always bounces towards the middle.

When the game was first made, the pegs where arranged in a regular grid. However, it’s an old game, and now some of the pegs are missing. Your goal in the game is to get the ball to fall out of the bottom of the game in a specific location. Your task is, given the arrangement of the game, to determine the optimal place to drop the ball, such that the probability of getting it to this specific location is maximized.

The image below shows an example of a game with five rows of five columns. Notice that the top row has five pegs, the next row has four pegs, the next five, and so on. With five columns, there are four choices to drop the ball into (indexed from 0). Note that in this example, there are three pegs missing. The top row is row 0, and the leftmost peg is column 0, so the coordinates of the missing pegs are (1,1), (2,1) and (3,2). In this example, the best place to drop the ball is on the far left, in column 0, which gives a 50% chance that it will end in the goal.

x.x.x.x.x
 x...x.x
x...x.x.x
 x.x...x
x.x.x.x.x
 G  

'x' indicates a peg, '.' indicates empty space.

Input

You should first read an integer N, the number of test cases. Each of the next N lines will then contain a single test case. Each test case will start with integers R and C, the number of rows and columns (R will be odd). Next, an integer K will specify the target column. Finally, an integer M will be followed by M pairs of integer r_i and c_i, giving the locations of the missing pegs.

Constraints

• 1 ≤ N ≤ 100
• 3 ≤ R,C ≤ 100
• The top and bottom rows will not have any missing pegs.
• Other parameters will all be valid, given R and C

Output

For each test case, you should output an integer, the location to drop the ball into, followed by the probability that the ball will end in columns K, formatted with exactly six digits after the decimal point (round the last digit, don’t truncate).

Notes

The input will be designed such that minor rounding errors will not impact the output (i.e. there will be no ties or near — up to 1E-9 — ties, and the direction of rounding for the output will not be impacted by small errors).

Example Input

5
5 4 0 1 2 2
3 4 1 1 1 0
3 3 1 2 1 1 1 0
3 4 0 2 1 0 1 1
3 4 0 1 1 1

Example Output

0 0.375000
1 0.500000
1 1.000000
0 1.000000
0 0.500000

———————-

The idea is easy enough to grasp, and if you’ve ever watched The Price is Right gameshow, you’ll probably recognize this as the Plinko game. That was my first thought, so I preceded to design a solution based on my memory of it.

This turned out to be a bad idea as I conceived a Plinko board that was bounded by a rectangle, much like this:

In this layout, the odd rows have 1 more slot - the space between the pegs - in them than the even rows. The left-most and right-most slots of the odd rows bound against the wall and would then bounce the ball back toward the middle.

If I had more carefully read the problem statement (or looked at a picture of the actual Plinko game), I would’ve realized the peg board is supposed to look like this:

…which changes things quite a bit as you might imagine. 

Odd rows have 1 less slot - again, not the pegs, but the space between - than the even rows.

Now that that’s straightened out, the other tricky thing to note is the maximum constraint of the grid size. It will be no smaller than 3x3 and no larger than 100x100.

This fact may not seem significant right now, but if you start to think about your algorithm for solving the probabilities (most likely involving recursion), you’ll quickly realize that things can get out of control. Exponentially so.

And that, I would say has been theme for the qualification round of the Hacker Cup. Facebook even provides an explicit hint to this point. At the top of each puzzle page, is a line of text that reads:

Facebook Hacker Cup

Too hard for brute force, switching to dp

I’d probably do well to follow that advice out of the gate, but as usual I’m going to first attempt to solve this by brute force. I find that this approach tends to more readily illuminate the stumbling blocks and subtleties of the rules before I’ve had a chance to code myself into a corner. Like Knuth said: “Premature optimization is the root of all evil”.

I’ll report back after I finish writing my brute force solution. Briefly, here’s what I intend to do:

1. Model a Peg Board object, encapsulating a grid representing the existence/non-existence of pegs, and the slots between them
2. Write a recursive method that, given the coordinate of a starting slot, computes a probability matrix for arriving in all possible slots on the graph.

I have every expectation that this will be insufficient for the worst-case.

Hacker Cup - Double Squares - Solution

At the end of my last post, I mentioned I was going to run my code against the sample set to see if it works and then try out the worst-case dataset.

Well, it worked well against the sample and simply would not complete in the worst case because of my crappy non-algorithm. Let’s think about what I was doing wrong.

My approach was to try and sum the squares of every combination of numbers less than the input number. 

And ya know what? It works perfectly well for a low order input like 25, but it IS a very dumb, brute-force sort of algorithm.

Now try this approach on a number like 2147483647, which just so happens to be the upper constraint specified by Facebook.

You can’t do it.

That’s 2147483647! or 2147483647 factorial. 

In order to compute a solution for this, we’d need the lifespan of many more universes than the one we have. Such a task would require a far, far greater number of universes than even the total number of atoms in this universe! Yeah.

Fortunately, there are a number of tricks we can use to lower the difficulty. 

We know right away that many of those numbers in our combinations list aren’t even necessary because their sum will be greater than the input.

So, we can set a limit on which numbers we’ll square and sum by dividing the input in half, and taking the square root:

limit = sqrt(input/2)

Already, this reduces our 2147483647! to 32768!, which is still an incomputably large number if we’re calculating for every possible combination of integers in this smaller set. 

Stop it. We don’t need to do that.

Instead, we’ll just iterate through the list, and for each number n, we’ll do this:

sqrt(input - (n * n))

If the resultant square root evaluates to an integer (i.e., not a decimal), then we know that we have a match.

This vastly improved algorithm runs the worst case (2147483647 x 100) in 108 milliseconds under Java.

No further optimization necessary and problem solved. Here’s a peek at the actual code that does the work:

int[] sumArr = app.readSumsFromFile(args[0]);
List<Integer> resultsList = new ArrayList<Integer>();

for(int sum : sumArr) {
  int matches = 0;

  double theLimit = Math.sqrt(sum/2);

// This next check handles the sum^2 + 0^2 case 
  if(Math.sqrt(sum)%1==0) {
    matches++;
  }
  for(int i=1;i<=theLimit;i++) {
    if(Math.sqrt((sum-(i*i)))%1==0) 
       matches++; 
  }
  resultsList.add(new      Integer(matches));
  }
}

Hacker Cup - Problem #1 - Double Squares

Into the next one. I’m going to save the second one for last because after a brief glance it seems to be the most difficult from a logic context.

Again, straight from the FB:

———————-

Double Squares

A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3^2 + 1^2. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 3^2 + 1^2 (we don’t count 1^2 + 3^2 as being different). On the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2.

Input

You should first read an integer N, the number of test cases. The next N lines will contain N values of X.

Constraints

0 ≤ X ≤ 2147483647

1 ≤ N ≤ 100

Output

For each value of X, you should output the number of ways to write X as the sum of two squares.

Example Input

5
10
25
3
0
1

Example Output

1
2
0
1
1

————————

My gut tells me the solution is pretty easy, you just need to make sure and read the invisible emphases on the constraints line. 

X may equal 0.

AND

X may be as large as 2147483647

The first part of the constraint means that every integer input that is itself a square will have AT LEAST its square root + 0^2 as a sum. 

They explicitly point this out to you in the problem statement:

“On the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2.”

The second part of the constraint implies that we could be squaring an awful lot of numbers to brute force this thing through to completion. 

I’m going to start by accounting for the first constraint and solving the sample data set, which should be fast and easy.

Just take every combination of numbers less than the one provided in a given line of input. Now, multiply each of the two per set by themselves and sum the products. If it equals the value from the input, then that counts as a match. Do your book keeping.

Don’t forget to account for zeroes and ones. 

That’s it.

Now, mock up some test data to match the worst case scenario and see how fast it performs. I’m about to do the same, myself.

Hacker Cup - Studious Student Submitted

I implemented a two-core Concurrent Sort in Java and cut the time in half to 38 seconds for the worst-case scenario. Proof positive that this is a viable avenue for tackling future sort algorithms depending on how it scales.

Soon I would like to refactor this code to use an arbitrary number of cores and allow for threshold configuration so that I wouldn’t have to spin up 8 threads just to sort a list of < 100, for example.

For now, though, I thought this should be sufficient to solve the problem. I downloaded my official data set from Facebook:

20

9 eavcqvv wyuh mkfq not evhlpur eidqnartht pesgphnnlq t ztvu

9 iccrmcrm mwp sil iccrmcrm ic odo iccrm crm odocrm

9 wjxwgm qdhmzkmpzv uhibo gcikegpzv ceqiwekdx rxegvkc ujjvbv kfit peiawyk

9 nnozzwtf ahkjj wtp t sj htawm ihw egzinwju vn

9 nl jtdmdxu ux nlmnyzdxu mnyz jtdm nlmnyz dxu uxdxu

9 z dvqgfh wqx vnajabkqvs sdwkc dlhcnc ezrcvsc teje gzwwj

9 fujv mzr kgukjmokvz schpxugnef p rjojpzbsro wpobp wl od

9 i hsmh hsmheh xgi eh xg xgeh xnfc ihsmh

9 myrzwdyhv pojiires fbjbkcbtq pzdfuxfh rq ukbom ypkffomyl tdko zbwqkbuu

9 qxwd bejf wfaua rvkorigcm psdflr utgcsj iaolpoazv hmzczeg hqktnql

5 uiuy hopji li j dcyi

9 rgh woqg dmabatgbt qrvpcrx eluunoi sy w wnthqxgkg aimallazuc

6 facebook hacker cup for studious students

5 k duz q rc lvraw

9 r wwwr ndtc ndtclp lpb b wwwb www lp

9 rnnabb ldk ndhn rnnaldk zeabbbb zeabb zea rnna bb

9 m xmnz mlk vlk lk iwkf lkiwkf vm v

9 krqeokrq weo usau krqeo eo zltg krq w zltgkrq

9 o zt da wv brorejctww fu phnej ynrdkylwys ekggrmehcl

9 k itqsgpwze ma yhpncg xtf w m kahula zgbo

I generated the following output:

eavcqvveidqnarthtevhlpurmkfqnotpesgphnnlqtwyuhztvu

crmiccrmcrmiccrmcrmiccrmicmwpodocrmodosil

ceqiwekdxgcikegpzvkfitpeiawykqdhmzkmpzvrxegvkcuhiboujjvbvwjxwgm

ahkjjegzinwjuhtawmihwnnozzwtfsjtvnwtp

dxujtdmdxujtdmmnyznlmnyzdxunlmnyznluxdxuux

dlhcncdvqgfhezrcvscgzwwjsdwkctejevnajabkqvswqxz

fujvkgukjmokvzmzrodprjojpzbsroschpxugnefwlwpobp

ehhsmhehhsmhihsmhixgehxgixgxnfc

fbjbkcbtqmyrzwdyhvpojiirespzdfuxfhrqtdkoukbomypkffomylzbwqkbuu

bejfhmzczeghqktnqliaolpoazvpsdflrqxwdrvkorigcmutgcsjwfaua

dcyihopjijliuiuy

aimallazucdmabatgbteluunoiqrvpcrxrghsywnthqxgkgwoqgw

cupfacebookforhackerstudentsstudious

duzklvrawqrc

blpblpndtclpndtcrwwwbwwwrwww

bbldkndhnrnnabbrnnaldkrnnazeabbbbzeabbzea

iwkflkiwkflkmlkmvlkvmvxmnz

eokrqeokrqeokrqkrqusauweowzltgkrqzltg

brorejctwwdaekggrmehclfuophnejwvynrdkylwyszt

itqsgpwzekahulakmamwxtfyhpncgzgbo

5 seconds. Excellent, I’m happy with that.

Seems there is significant lag between solution submittal and receiving your score for the problem. I could whine on the FB discussion board or…

…move on to the next problem. #1 sounds fun…

————-

UPDATE: 01/10/2011

After completing the other two problems in this round, I’m fairly confident there’s a much better algorithm for solving this one and that Facebook expects you to be using it.

Still, getting my little brute force multi-core proggie to solve this problem in 5 seconds is indeed a hack in every sense.

Hacker Cup - Studious Student Optimization

The way this round works is that once you’ve chosen to download the Facebook-provided data, you have 6 minutes from the time of download to paste the output from your program into the Hack Cup web form.

As I mentioned in my previous post, I’m able to execute the worst-case scenario - 100 rows of 9 words of 10 characters in length - in 78 seconds. That may be fast enough for the qualification round, but it is almost assuredly suboptimal.

Since I have 72 hours to solve 1 of the 3 presented problems, and I think I may functionally have this one licked, I’m going to spend some time optimizing as a practice exercise for the upcoming rounds. 

I’ve written my initial, suboptimal solution in Java and I’m thinking of two approaches to tighten things up:

1. Multi-core Java: Let’s say I have for a single word set (1 line in the input file), a list of 400,000 permutations. I have 8 cores on my CPU, therefore I will split the sorting work among 8 different threads (1 per core) giving each one 50k to work on. The performance gain isn’t quite linear due to the overhead of recombining the lists afterwards and having to wait for all threads to complete, but I’d still expect to be able to finish in - ballpark - 25% of my original execution time. 
2. Erlang: Considering I’ve never written a line of Erlang, I don’t expect this to be a big success, however high-concurrency, multi-processor friendliness is inherent in its design and maybe it’ll just be stupid easy. This is as good an excuse as any to dive head-first into a language I’ve always wanted to check out. And Facebook has a big old throbbing erection for Erlang, which can’t hurt if I make it to the later rounds :)

Facebook Hacker Cup - Problem #3 - Studious Student

I’ve decided to start working problem #3 first…
Here is the problem statement Copy & Pasted directly from the site:

Studious Student

You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string. 

Input

As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters. 

Output

Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order. 

Constraints

1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10

Example input:

5

6 facebook hacker cup for studious students

5 k duz q rc lvraw

5 mybea zdr yubx xe dyroiy

5 jibw ji jp bw jibw

5 uiuy hopji li j dcyi

Example output:

cupfacebookforhackerstudentsstudious

duzklvrawqrc

dyroiymybeaxeyubxzdr

bwjibwjibwjijp

dcyihopjijliuiuy

—————————————————————————

This seems to be a pretty easy problem, until you look closely at the 4th result in the sample input:

jibw ji jp bw jibw

The given sample output for this line is:

bwjibwjibwjijp

After following the requirements of the problem statement, you may think that all you need to do is order sequentially by alphabetical value, every string in the list. If you’re writing your solution in Java, this is a trivial task as the String class already has the necessary alphabetical comparators built-in.

In fact, this approach gives a correct answer for everything in the sample except….uh oh….the fourth one from YOUR result set:

bwjijibwjibwjp

Look closely and you’ll notice that the Facebook approved answer has the ji token positioned BEFORE the two jibw tokens. The implication is that you cannot actually compare the values of the individual tokens and just concatenate them ascendingly.

So, how to compute the Answer, then? 

You must combine every possible permutation of the words in the list, and THEN do the alphabetical value comparison on the combined results which should solve for any case that Facebook will throw at you.

This is of course computationally non-trivial, and orders of magnitude more difficult. I’ve got a working solution that I’m currently trying to optimize from my best of 78sec on a dataset that meets the maximum constraints specified by the problem.

Deployed Twitcaps v1.1 (Search RSS & Usability Enhancements)

This deployment marks the first non-beta release of Twitcaps. Very much a non-event from a user perspective, though stability and performance have been significantly improved.

• Added the ability to subscribe to RSS Feeds for a particular search. Hackable URLs for the feeds at http://twitcaps.com/rss/%QUERY_STRING%
• Many little usability improvements: Twitcaps remembers your auto-refresh preference, live image stream auto-pauses upon mouse-over, retweet-count works on searches again, other enhancements.
• Back-end stability enhancements related to Twitter API timeouts (and lack thereof)
• Performance tuning related to JVM options and use of Hibernate Second-Level Cache

Deployed TwitCaps v1.01b (Search Refactor)

Big release. Nothing short of a wholesale refactor of the search functionality.

• Implemented robust search caching. Twitcaps should now be more resilient during times of heavy load and through variations in Twitter Search API response times. The app will now even gracefully handle and still serve results during total outages for trending and otherwise popular / recent / frequent searches.
• Removed search pagination. The same ajax calls are now accomplished on scroll.
• Searches now poll the server for new results at an interval of 10 seconds. This is just auto-refresh from the home page applied to searches.
• Made many, many cross-browser layout fixes. Now enforcing DTD //W3C//DTD XHTML 1.0 Strict
• Fixed bug with Image Detail Pane not showing correctly in IE7/8 when the page is scrolled
• Fixed a pretty significant bug with displaying image times (dunno when I buggered that one)
• Small refactor of TwitterSlurper. Realized that the volume of Twitpic images is now large enough that some were slipping through the cracks during the few seconds between poll calls. This fix alleviates the issue and also greatly increases speed of the slurpers.
• Wrote a testing framework specifically for testing the highly volatile, highly concurrent caching code. Hoping it is robust enough to catch most of my concurrency risks.
• No longer a need to choose between OptimisticLocking OR Pessimistic Locking. Don’t care about locking any longer.
• A couple of URLMapping enhancements
• Many tiny fixes that are too numerous to list.