Simple single-player board game, expected score distribution

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

1. They must be correct to be considered; wrong answers don't count.
2. 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

• While not exactly the same, this is similar to the recent Snakes and Ladders. Jul 21, 2015 at 15:30
• Indeed, but there are key differences: this game is single-player, and the final score is what matters, not the number of turns. Also, all motion is forward, which makes calculating an exact solution feasible. Jul 21, 2015 at 15:41
• I tried adding together all the probabilities in your output for the "Complex" example, and I got 0.983215334, not the expected 1.0. Would you mind double-checking this, please? Aug 10, 2015 at 23:24
• @mathmandan thanks...looks like something is wrong with my reference program! I'll get it fixed. Aug 13, 2015 at 14:24

Stax, 56 55 bytesCP437

üZÄ^3Γ╥£X╜T∩L╖á↨→╘Oïë╢Δ╥∙Eü╦5├jC╩XpN◘╘♥«╟╝☻y╞╘wé↔Ioÿ≈⌐─


Run and debug online!

Warning: Takes a long time (around 5 minutes in my box) to run the large example.

Credits to the almighty rubber duck for -1 byte.

Input is a list of numbers. Scoring x points is represented by -x, and Move y steps forward and follow the instruction there is represented by y. So for example the small test case will be represented as [-1,2,-1].

Outputs in rational number, the output for the large case is like this:

7 3/128
8 1/128
9 3/256
10 9/256
11 3/256
12 25/512
13 1/64
14 1/64
15 75/1024
16 33/1024
17 123/2048
18 1/64
19 3/256
20 45/512
21 3/64
22 67/1024
23 5/512
24 11/1024
25 33/512
26 39/1024
27 39/1024
28 1/512
29 3/1024
30 183/4096
31 97/4096
32 231/8192
33 1/256
34 3/1024
35 65/4096
36 71/4096
37 145/8192
38 1/128
39 9/1024
40 57/4096
41 1/64
42 79/8192
43 1/256
44 37/4096
45 127/8192
46 41/4096
47 93/16384
49 15/4096
50 55/8192
51 15/4096
52 45/16384


Alternative version

Calculates the probability recursively instead of enumerating every possibility. Much faster. Not really golfed.

00\sn+~]]01\]]+Yd;%{;%=zi^]?i]+ys@iXd{{dx2<;x|i-v@1<+!C_E2u*s;x@0|m-s\mm:f;i({i+|i=!Ci2+mys@{{B;x@0|m-+rm+F{o{h}/{hh0_{H+F\m]ys+YdFUUv\ys@:fo{h}/mhh0_{H+F\J

Try and debug online!

The two different algorithms give the same result.

Explanation

Uses the unpacked version to explain. The size of the game board is stored in register x. The current position on the board is stored in register y. There is an extra flag (boolean) denoted bFlip that is stored on the stack, used to indicate the type of last instruction.

The complete unpacked version is 66 bytes.

X|2{v:Bx)0Y1~s{^,*y+Ycx>{d1~}{v;@c1<c~{-}{y+Yd}?}?F,dmo|RmNx|2u*+J


I will explain it part by part.

X|2{v:Bx)0Y1~s{     F,dm
X|2                        2^x
{v                  m    For [0..2^x-1] do the following
:Bx)                   Binary representation of the current loop index
Padded with zeros to make the length l.
Each binary represents a sequence of coin flip outcomes
0Y1~s              Initialize y and current score to 0, and bFlip to true
{     F       Play the game as indicated by the sequence of coin flip outcomes
,d     Clean up: remove bFlip from the stack.


The block that plays the game:

{^,*y+Ycx>{d1~}{v;@c1<c~{-}{y+Yd}?}?F
{                                   F    The loop as stated above
^                                       Increment current flip result
Map the original [0,1] to [1,2], denote this as n.
,*                                     If last instruction is of the type Score k points (k may be 0)
y+Y                                      Move forward n steps and save the new current position to register y.
cx>{   }{                  }?     If already moved past the end
d1~                               Mark this instruction as Score 0 points (or Do nothing)
Else
v;@                          Get current instruction
c1<c~                     Get the type of current instruction and remember it
{ }{    }?           If the current instruction is Score k points
-                       Score k points
Else
y+Yd                 Move forward as the instruction indicates


After executing this, we have a list with 2^x elements containing the scores of all possible coin flips, with equal probabilities. The rest of the program is just converting them to the output.

o|RmNx|2u*+J
o|R             Convert to a list of pairs of [element, count of appearance]
m            Map the array elements with the rest of the program, output the results on separate lines
Nx|2u*+     Divide the count of appearance by 2^x to get probability
J    Join the two elements with a space



Perl 5, -a0111 108 bytes

Input format: Give the instructions separated by white-space (newline works) on STDIN including the starting cell represented by 0. The jump is indicated by an F after the number. So the example input becomes:

0
1
2F
1


With correct output

0 0.5
1 0.25
2 0.25

#!/usr/bin/perl -a0
@1=1;$n++,map{$i=0;for$a(@$n){${$n+$_>@F?z:$n+$_}[$i+++$']+=$a/2}}/F/?($)x2:(/|/,2)for@F;say$z++," \$_"for@z
`

Try it online!