Peg Game Problem Analysis

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).

Here is my problem analysis for Facebook Hacker Cup Qualification Round: Peg Game.

Peg Game Problem Analysis:
This is the most confusing problem of the three problems due to the problem description being unnecessary long and ambiguous. You can see how many people are asking clarifications for this problem in the wall posts compared to the other problems (I really think Facebook should create a clarification section to answer people’s questions). Besides, the example they used to illustrate the problem is not included in the sample input, which doesn’t help at all.


A Galton box (also known as the bean machine) is a machine consists of a vertical board with interleaved rows of pins. Balls are dropped from the top, and bounce left and right as they hit the pins. Eventually, they are collected into one-ball-wide bins at the bottom. The height of ball columns in the bins approximates a bell curve.

It definitely takes me more than few times re-reading the problem description to finally “guess” what they really mean. Anyway, after understanding the problem, it is not that difficult to code the solution using a direct simulation.

However, there are a few places where you need to be careful, and I found that most people fall into this fallacy below:

Count the total number of ways to reach the goal, then divide it by the total number of ways to reach the bottom.

Why the above approach is incorrect? This is simply because one necessary condition for the above statement to be true is that ways that reaches the bottom must all be equally likely. Unfortunately, this is not necessarily true.

The correct method is to multiply the probabilities as the ball falls in a step-wise fashion. You would also need to determine if the ball is at an edge peg. If it is at an edge peg, then the ball always fall toward the opposite direction of the edge peg with 100% chance. On the other hand, if it is not at an edge peg, then it will fall in either direction with 50-50 chance.

Below is the coded solution for Peg Game.

VN:F [1.9.22_1171]
Rating: 2.3/5 (3 votes cast)
Peg Game Problem Analysis, 2.3 out of 5 based on 3 ratings

7 thoughts on “Peg Game Problem Analysis

  1. Cygwin98

    I was using recursion in my solution that worked for the test suites, but failed to scale up for the input file.

    VA:F [1.9.22_1171]
    0
  2. Anonymous

    Thanks for posting your code. But can you please also upload the code which can be readily used to generate an output file.

    VA:F [1.9.22_1171]
    0
  3. Shuxian Jin

    what about from bottom to up?

    If the ball is to fall into the spot K, then find the upper position from which it is possible for the ball to fall into K. Go up from layer to layer. The position on the top with max possibility is the one.

    Use a queue, first put {2, 1} into queue, where 1 describe the possibility.
    x.x.x.x.x
    x…x.x
    x…x.x.x
    x.x…x
    x.x.x.x.x
    Then pop out (2,1}, add{2,1} on level 5;
    Pop out (2,1}, add{3,0.5} on level 4;
    Pop out {3,1} , add{2,1/8} {3,1/4},{4,1/8} on level 3;
    Pop out all, and add {3,1/4}{4,1/4}{5,1/16} on level 2;
    Pop out all, and add {2,1/8} {4, 1/4} {6, 1/32}

    So the answer is 4.
    Is this idea right?

    VN:F [1.9.22_1171]
    0
  4. Max

    actually I think you don’t have to initialize the “game”. I use back tracking to solve this problem. And it can be optimized by remembering previous probability of (r, c), so the final running time will be o(n), here n is the input size.

    VN:F [1.9.22_1171]
    0
    1. Max

      VN:F [1.9.22_1171]
      0
      1. Max

        I don’t know why I cannot put complete code. Last try:

        typedef struct misspair{
        int r;
        int c;
        }M_PAIR;

        M_PAIR mpair[3] = {{1,3}, {2, 2}, {3,5}};

        bool isMissing(int r, int c){
        for(int i=0; ipr ? pl : pr; //and store its probability
        }
        }
        }

        double solvePegGame(int R, int C, int K){
        double maxP = 0;
        for(int i=0; ipr ? pl : pr;
        }
        if(maxP < p)
        maxP = p;
        }
        return maxP;
        }

        VN:F [1.9.22_1171]
        0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*