Sunday, January 9, 2011

Peg Game explanation

A lot of people had a lot of question while solving Peg Game problem @ Qualification Round of Facebook Hacker Cup. Here is my understanding of this puzzle. I hope I'm right and my solution will be accepted.

Imagine a game board and try to get "boundary condition"...

where:
  • blue arrows shows "far left" and "far right" cases;
  • red arrows shows situation that will never happend (probability 0).

Also imagine "missing of a peg" situation,
where:
  • blue arrows shows that ball goes forward to the bottom with the same probability as it has before.


Test case from problem description


1st test case from example input

15 comments:

Евгений said...

Thanks ! This is the only correct interpretation of the problem ! in my opinion =)

Toast said...

This is my interpretation of the problem as well. I dislike the angled boundaries, but given the math provided plus sample problems/solutions, it's the only thing that makes sense.

Hopefully the next round will be more clear.

Nabeel Mukhtar said...
This comment has been removed by the author.
상상할 수 있는 힘이 모자라다. said...

Dear Illya Havsiyevych,

What about the second test case in the given example? I think I coded based on same strategy with yours, but, in my case, the probability is 0.5 when starting point is 1 and 2.

According to the problem, there is no ties or near. I did it several time on paper also, but I got same result.

Could you kindly explain what I might be missing?

shane said...

I didn't exactly get that result. Instead of doing it your method I took out the peg at (2,2). I did manage to get the problem correct but it required doing a perfect grid ie:

x.x.x.x

x.x.x.x

x.x...x

x.x.x.x

x.x.x.x

#1pos: (0,0)
#2pos: (1,1) 1.0 probability
#3pos: (2,0).5prob (2,2).5prob
#4pos: (3,1).75prob (3,3).25prob
#5pos: (4,0).375prob (4,2).3125prob

leaving the ball in the first column (0) at .375000 probability. The reason at position 3 the ball goes to 2,2 then to 3,3 is because the peg is missing.

shane said...

I would like to introduce the following pseudo-code to present my findings:

for(rows)
#1(0,0) = 1.0
//if(col = 0) then increment and keep probability
#2(1,1) = 1.0/2 //column not 0
//peg splits and col +- 1
#3(2,0) = .5 and (2,2) = .5
#4(3,1) = .5/2 and (3,2) = .5/2 //peg missing
#5(4,0) = .25 and (4,1) = .25/2 and (4,3) = .25/2
//if(col0 and col1 exists)
#6(END) = .25+.125=.375

Illya Havsiyevych said...

FYI, my output for input file
-----------------------------
48 0.112857
0 0.375000
0 0.500000
16 0.089765
24 0.100113
8 0.175087
2 0.250000
35 0.230835
0 1.000000
25 0.089105
9 0.124782
8 0.167464
52 0.101299
30 0.100734
17 0.214032
44 0.266663
85 0.511620
11 0.072748
5 0.359375
2 1.000000

SITZ said...

Can you give your input file... Just for testing purpose...

Rok Kralj said...

I am not sure your output is right... I got a different one...

Rok Kralj said...

Be careful, he is trying to decieve you! His solution is nowhere right, because 15th test case is 4 3 0 0, and his output is 17 column which does not even exist!

Mayerwin said...
This comment has been removed by the author.
Mayerwin said...
This comment has been removed by the author.
Mayerwin said...
This comment has been removed by the author.
Mayerwin said...
This comment has been removed by the author.
Illya Havsiyevych said...

Please ignore my output because it looks like it has no sense without input. So some cases from my input:

2nd:
5 4 0 1 2 2

3rd:
3 4 0 0

7th:
5 4 2 6 1 1 3 0 2 0 2 3 3 1 1 0

9th:
3 3 0 1 1 0

15th:
71 35 17 1191 ....