7
\$\begingroup\$

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
    
\$\endgroup\$
  • \$\begingroup\$ While not exactly the same, this is similar to the recent Snakes and Ladders. \$\endgroup\$ – Geobits Jul 21 '15 at 15:30
  • \$\begingroup\$ 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. \$\endgroup\$ – Snowbody Jul 21 '15 at 15:41
  • 4
    \$\begingroup\$ 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? \$\endgroup\$ – mathmandan Aug 10 '15 at 23:24
  • \$\begingroup\$ @mathmandan thanks...looks like something is wrong with my reference program! I'll get it fixed. \$\endgroup\$ – Snowbody Aug 13 '15 at 14:24
3
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.