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.