Simple single-player board game, expected score distribution

Question

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
  

Answer 1

Stax, 56 55 bytes^CP437

ü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

                

Answer 2

Perl 5, -a0 111 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!