This is the first problem I've posted here; please post criticisms in comments.
Summary
A game board consists of a starting space, an ending space, and between them are N
spaces, each with an instruction. You begin on the starting space with 0
points to your credit. Flip a coin or roll a die to choose the number 1
or 2
. Move forward that many spaces. Now look at the instruction on the space you landed on. The possible instructions consist of "Do nothing", "Score x
points", and "Move forward y
spaces and obey the instruction there". x
and y
are positive. After obeying the instruction, go back to the coin flip. When you land on or pass the ending square, the game is over.
Given a description of a game board (number of squares, instruction on each space) your code should calculate the probability distribution of possible ending scores. It's irrelevant how many turns are taken before the end.
Input
- An unambiguous representation (in whatever format you desire, though numbers should be human-readable) of the instruction on each space. Numbers should be human-readable.
Output
- A list of pairs of each possible score and the probability of obtaining that score (either an exact fraction or a real number accurate to at least four decimal places). Can be returned or output. It's optional to include scores that have 0 probability of occurring.
Scoring the entries
- They must be correct to be considered; wrong answers don't count.
- Code size. If you golf it please also post an ungolfed version; if you use a golfing language please post a good explanation.
Examples
Easy
Input
3 1 F2 1
Output
0 0.5 // rolled a 2 on first turn, game over 1 0.25 // rolled a 1 then a 1 2 0.25 // rolled a 1 then a 2
Complex
Input
16 2 1 0 5 10 F3 5 15 1 0 3 F3 5 0 0 5
Output
7 0.0234375 8 0.0078125 9 0.01171875 10 0.03515625 11 0.01171875 12 0.048828125 13 0.015625 14 0.015625 15 0.0732421875 16 0.0322265625 17 0.06005859375 18 0.015625 19 0.01171875 20 0.087890625 21 0.046875 22 0.0654296875 23 0.009765625 24 0.0107421875 25 0.064453125 26 0.0380859375 27 0.0380859375 28 0.001953125 29 0.0029296875 30 0.044677734375 31 0.023681640625 32 0.0281982421875 33 0.00390625 34 0.0029296875 35 0.015869140625 36 0.017333984375 37 0.0177001953125 38 0.0078125 39 0.0087890625 40 0.013916015625 41 0.015625 42 0.0096435546875 43 0.00390625 44 0.009033203125 45 0.0155029296875 46 0.010009765625 47 0.00567626953125 49 0.003662109375 50 0.0067138671875 51 0.003662109375 52 0.00274658203125
0.983215334
, not the expected1.0
. Would you mind double-checking this, please? \$\endgroup\$