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 ri and ci, 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:
- Model a Peg Board object, encapsulating a grid representing the existence/non-existence of pegs, and the slots between them
- 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.
1 year ago • 0 notes