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"...
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVALyOAB5JjUtgVgto84Ep56O2rozTO-OSS3yN3U21uj8syBzCNzTENCAeyGkJGsx-TxuZLm11T2cpov4pZxsVwKBBSnnSBC-GS-lhTp1eUw2H1B-2sxyn-GyloD1K59XbxfYQD9eAwxg/s400/pegGame1.png)
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,
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1kYnWwiFsemSLsQooIf4gdfLiPkPyzgC4xbP3Lmmz8qutgCu2sfmumiMVuEdWo3N7SsSfacnhI1iRWOikpNZPiGSxw1aXE3-N3fZfdzquH37BP6sqNW2RYYBcdBEd_MZWYVGJ2n6wz2c/s400/pegGame2.png)
where:
- blue arrows shows that ball goes forward to the bottom with the same probability as it has before.
Test case from problem description
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgqfLFxNlMlv8Kli8-xfn8i33T8B4cJVN2uh131oMwM2K2pcxFGXk8XqLfuRwnB5HIHTDNzxbUj2QRFmj-cs2XwniiWZ6ZH5aa1Q4K6eyYZ8i4OYn73kkqi5iapESh03M-nko2tiWJPGsw/s400/pegGame3.png)
1st test case from example input