Facebook Hacker Cup Peg Game problem

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

We will be happy to hear your thoughts

Leave a reply

TechEggs
Logo