Facebook Hacker Cup Peg Game problem


Lately I’ve been playing around Facebook’s Hacker Cup, while ignoring the problems with input files and time expired, it provides a lot of fun. I also noticed a lot of people are getting stuck at the Peg Game problem, and not quite understanding how the first example input, 5 4 0 1 2 2 is suppose to generate 0 0.375. So, here’s the explanation I’ve been trying to explain lately:

0 x.x.x.x
1  x.x.x
2 x.X…x
3  x.x.x
4 x.x.x.x
ignore the first line, start straight from second one.
so starting at slot 0, row 1 we hit a peg. since it’s a side one, we don’t have a choice where to go, and go to row 2 peg slot 1 (marked with a big X)
there we have a choice of either row3 peg slot 0, or row3 peg slot 1.
we have to sum the probability of this two options.
option1 (row3 peg slot 0):
again no choice. we go to row4 peg1, and then have a 0.5 probability of going to slot 0 (the goal).
so total for this option to hit the goal: 0.5*0.5 = 0.25.
option2 (row3 peg slot 1):
again a crossroad. (0.5 chance to go either)
option2.1 (row4 peg slot 1):
0.5 of hitting the goal.
option2.2 (row4 peg slot 2):
0 of hitting the goal.
so total for this option to hit the goal: 0.5*0.5*0.5 = 0.125.
sum of both options: 0.25 + 0.125 = 0.375

Hope this helps anyone. I have a lot more to write about this contest from my observation point, but I’ll hold with it until the round is over. 0 x.x.x.x1  x.x.x2 x.X…x3  x.x.x4 x.x.x.xignore the first line, start straight from second one.so starting at slot 0, row 1 we hit a peg. since it’s a side one, we don’t have a choice where to go, and go to row 2 peg slot 1 (marked with a big X)there we have a choice of either row3 peg slot 0, or row3 peg slot 1.we have to sum the probability of this two options.option1 (row3 peg slot 0):again no choice. we go to row4 peg1, and then have a 0.5 probability of going to slot 0 (the goal).so total for this option to hit the goal: 0.5*0.5 = 0.25.option2 (row3 peg slot 1):again a crossroad. (0.5 chance to go either)option2.1 (row4 peg slot 1):0.5 of hitting the goal.option2.2 (row4 peg slot 2):0 of hitting the goal.so total for this option to hit the goal: 0.5*0.5*0.5 = 0.125.sum of both options: 0.25 + 0.125 = 0.375


Leave a Reply

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