JANUARY 10, 2011
Peg Game is the 2nd (and the hardest) of the 3 problems posted in the qualification round for the 2011 Facebook Hacker Cup. It basically consists of dropping a ball through a series of pegs from the top and calculating the optimal drop position and the probability of success for making it fall on a particular slot on the bottom. Here are some thoughts on it…
First though, here’s a copy of the problem description:
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
I initially had some difficulty understanding the problem as I was going through the example input cases manually and was not getting the expected results. It turns out that the first and last pegs on the odd rows (counting from 0, obviously) counted as being on the far left or far right side which is not what I intuitively thought.
With that cleared, I designed an algorithm to solve the problem and proceeded to code and then test the application. Some bugs did come out during the process, among them, I was initially using a Linked List to queue the order in which the pegs were to be “explored”, while this worked on the limited example cases, I discovered that there were other cases where this caused a conflict due to the fact that missing pegs cause the ball to keep dropping and I was passing this probability 2 rows below. This caused the pegs on that level to be inserted onto the queue before they were supposed to and was giving incorrect results. I fixed this by changing the Linked List to a Priority Queue with a custom comparator.
In the end, I solved the problem but did not upload the result for it on time because Opera 11.00 (build 1156), which is what I used to open the input, has a 65536 byte limit on the amount of data it will display when opening a text file. As the browser stopped opening any more data, I thought it had finished and proceeded to copy and paste the data onto my program (which uses standard console input) and believed (correctly) that my implementation was fast enough to process the input with plenty of time to spare, however the seconds passed and I kept on waiting for my program to finish computing a result.
I though I had come across a very tough test case and kept on waiting completely unaware that what was actually happening is that my program was waiting for more input!. By this point I only had a bit over 2 minutes left (out of the 6 minute period you get) when I noticed that my CPU utilization was actually pretty low, this gave me an indication that my program was idle and noticed that Opera was not showing the reload icon on its toolbar but the stop icon. I began to suspect that something was awry and opened Internet Explorer to download the input there.
This time I decided to open the file directly and load it in Notepad++, this would guarantee that it would be opened correctly as I had previously seen that the files are using the UNIX EOL format and regular Notepad would screw that up. I did that and as I initially expected, the input was processed in around 40 seconds.
Unfortunately by that point I was watching the timer and it ran out before the program finished. A big bummer, given that I had put in a couple of hours into this problem.
EDIT – After Facebook decided to allow problem re-submission, I sent this in again (now downloading the file correctly) and my solution was accepted.
Anyway, here’s the source code I made:
import java.text.DecimalFormat;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
/**
* @author Luis Edgardo Argote Bolio
*
*/
public class PegGame {
public static Scanner in = new Scanner(System.in);
/**
* This is the main method, it reads the input and handles the program flow
*
* @param args
*/
public static void main(String[] args) {
int games = in.nextInt();
for (int game = 0; game < games; game++) {
// Read input
int rows = in.nextInt();
int columns = in.nextInt();
/*
* Generates a Matrix with the game board, it contains Peg elements
* I made it larger for simplicity, it could be about half as "wide"
* but that would have complicated coding.
*
* For example, this will be ultimately generated for
* 5 4 0 3 1 1 2 1 3 2
*
* R X X X L
* R M X L
* R M X X L
* R X M L
* X X X X X
* *G*******
*
* Note that:
* X is a regular peg
* R means the peg is on the left edge (always bounces right)
* L means the peg is on the right edge (always bounces left)
* M means the peg is missing
* G is the Goal position (where we want the ball to fall)
* '*' and ' ' are just fillers
*
*/
Peg[][] pegGame = new Peg[rows + 1][(columns * 2) - 1];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < (columns * 2) - 1; j++) {
pegGame[i][j] = new Peg();
if (i % 2 == 0) { // Even rows
if (j % 2 == 0) { // Even columns
if (j <= 1) {
// If it's on the left edge (always bounces
// right)
pegGame[i][j].setType('R');
} else if (j >= (columns * 2) - 3) {
// If it's on the right edge (always bounces
// left)
pegGame[i][j].setType('L');
} else {
pegGame[i][j].setType('X');
}
}
} else { // Odd rows
if (j % 2 != 0) { // Even columns
if (j <= 1) {
// If it's on the left edge (always bounces
// right)
pegGame[i][j].setType('R');
} else if (j >= (columns * 2) - 3) {
// If it's on the right edge (always bounces
// left)
pegGame[i][j].setType('L');
} else {
// If it is a regular peg (50% chance to bounce
// left, 50% chance to bounce right)
pegGame[i][j].setType('X');
}
}
}
}
}
// This basically creates the pegs for the bottom row
// (where the goal will be set)
for (int j = 0; j < (columns * 2) - 1; j++) {
pegGame[rows][j] = new Peg('*', 0.0);
}
// Gets the goal peg and sets it in the Matrix
int goal = in.nextInt();
pegGame[rows][1 + (goal * 2)].setType('G');
// Gets the missing pegs and sets them in the Matrix
int missing = in.nextInt();
for (int j = 0; j < missing; j++) {
int missingRow = in.nextInt();
int missingCol = in.nextInt();
missingCol *= 2;
missingCol += (missingRow % 2 == 0 ? 0 : 1);
pegGame[missingRow][missingCol].setType('M');
}
// Calculates the initial result which is dropped in the same
// slot as where we want it to land, this is quite likely to
// be the highest
int bestDropPoint = goal;
double bestResult = determineDropProbability(pegGame, goal);
// Calculates the results for dropping the ball on all other
// slots, this is probably unnecessary as the best slot tends to
// be the goal slot or very close to it
for (int dropPoint = 0; dropPoint < columns - 1; dropPoint++) {
// Prevent recalculation of the initial slot
if (dropPoint == bestDropPoint) {
continue;
}
double result = determineDropProbability(pegGame, dropPoint);
if (result > bestResult) {
bestResult = result;
bestDropPoint = dropPoint;
}
}
// Formats and prints the output
DecimalFormat df = new DecimalFormat("0.000000");
System.out.println(bestDropPoint + " " + df.format(bestResult));
}
}
/**
* This method calculates the probability of the ball landing on the slot
* we want given a drop point for the ball
* @param board the matrix containing the board description
* @param dropPoint the point where the ball will be dropped
* @return
*/
public static double determineDropProbability(Peg[][] board, int dropPoint) {
// Displace the drop point to correspond to a board matrix column
dropPoint = (dropPoint * 2) + 1;
// Instantiate the comparator and the priority queue that will use it
Comparator comparator = new CoordinateStringComparator();
PriorityQueue pegsToCheck = new PriorityQueue(20,
comparator);
// These variables will let us know where to retrieve the final result
int targetRow = 0;
int targetCol = 0;
// Insert the initial drop point into the prioritized queue
String coordinate = (1) + "," + dropPoint;
pegsToCheck.add(coordinate);
// Set the probability for the initial point to 100% (1.0)
board[1][dropPoint].setProbability(1.0);
// While there are pegs that have a probability of being hit, this will
// check then and pass the probabilities on "downwards"
while (!pegsToCheck.isEmpty()) {
// Obtain the position on the matrix that the peg corresponds to
String[] coo = pegsToCheck.poll().split(",");
int row = Integer.parseInt(coo[0]);
int col = Integer.parseInt(coo[1]);
if (board[row][col].isType('X')) {
// Standard peg, add half the probability of this peg to each
// of the pegs the ball would fall on to
board[row + 1][col - 1].addProbability(board[row][col]
.getProbability() / 2.0);
board[row + 1][col + 1].addProbability(board[row][col]
.getProbability() / 2.0);
// Add those two pegs to the queue if they're not already there
String co2 = (row + 1) + "," + (col - 1);
if (!pegsToCheck.contains(co2)) {
pegsToCheck.add(co2);
}
String co3 = (row + 1) + "," + (col + 1);
if (!pegsToCheck.contains(co3)) {
pegsToCheck.add(co3);
}
} else if (board[row][col].isType('R')) {
// Left edge peg, add its complete probability of this peg to
// the right peg where the ball would fall on to
board[row + 1][col + 1].addProbability(board[row][col]
.getProbability());
// Add the peg to the queue if it's not already there
String co3 = (row + 1) + "," + (col + 1);
if (!pegsToCheck.contains(co3)) {
pegsToCheck.add(co3);
}
} else if (board[row][col].isType('L')) {
// Right edge peg, add its complete probability of this peg to
// the left peg where the ball would fall on to
board[row + 1][col - 1].addProbability(board[row][col]
.getProbability());
// Add the peg to the queue if it's not already there
String co2 = (row + 1) + "," + (col - 1);
if (!pegsToCheck.contains(co2)) {
pegsToCheck.add(co2);
}
} else if (board[row][col].isType('M')) {
// Missing peg, the ball will fall on to the next peg below it,
// it is the peg 2 rows below
board[row + 2][col].addProbability(board[row][col]
.getProbability());
// Add the peg to the queue if it's not already there
String co4 = (row + 2) + "," + (col);
if (!pegsToCheck.contains(co4)) {
pegsToCheck.add(co4);
}
} else if (board[row][col].isType('G')) {
// If the queue gets to the goal peg, obtain its position on the
// Matrix and continue (its probability is not reset to 0 yet)
targetRow = row;
targetCol = col;
continue;
}
// Resets the Peg's probability to 0 so that another drop point can
// be calculated without having to have made a copy of the matrix
board[row][col].setProbability(0.0);
}
// Stores the result before reseting the goal slot to 0 as well, then
// returns it
double result = board[targetRow][targetCol].getProbability();
board[targetRow][targetCol].setProbability(0.0);
return result;
}
}
/**
* This is a simple data structure for each peg that includes its type and the
* probability it'll be hit The methods on it are very basic and, thus, not
* commented
*
* @author Luis Edgardo Argote Bolio
*/
class Peg {
private char type;
private double probability;
Peg() {
this.type = ' ';
this.probability = 0.0;
}
Peg(char type, double probability) {
this.type = type;
this.probability = probability;
}
public char getType() {
return type;
}
public void setType(char type) {
this.type = type;
}
public double getProbability() {
return probability;
}
public void setProbability(double probability) {
this.probability = probability;
}
public boolean isType(char typeToCheck) {
return (this.type == typeToCheck);
}
public void addProbability(double probabilityToAdd) {
this.probability += probabilityToAdd;
}
}
/**
* This is the comparator I use for the Prioritized Queue for peg analysis The
* Queue contains a String in the format "Row,Column" with the position of the
* next peg to analyze, it is prioritized by level, that way the probability
* accumulator value for each peg is guaranteed to contain ALL possible routes
* that could fall onto it as all of them will be analyzed before.
*
* @author Luis Edgardo Argote Bolio
*/
class CoordinateStringComparator implements Comparator {
@Override
public int compare(String o1, String o2) {
// Basically, split the string and parse the part we want, then subtract
// to get which is larger.
String[] coords1 = o1.split(",");
String[] coords2 = o2.split(",");
return Integer.parseInt(coords1[0]) - Integer.parseInt(coords2[0]);
}
}