Penney-Conway odds

Question

Background

Penney's game is a two-player game about coin tossing. Player A announces a sequence of heads and tails of length \$n\$, then player B selects a different sequence of same length. The winner is the one whose sequence appears first as a substring (consecutive subsequence) in repeated coin toss.

Conway's algorithm describes how to calculate the odds of a single sequence of length \$n\$ in Penney's game:

For every integer \$1\le i \le n\$, add \$2^i\$ if its first \$i\$ items match the last \$i\$ items. The sum is the expected amount of tosses before you will see the exact pattern. For example (all examples being \$n=6\$),

• HHHHTT: Only matches at \$i=6\$, so the expected number of tosses is \$64\$.
• TTHHTT: Matches at \$i=1,2,6\$, so the expected number of tosses is \$2+4+64=70\$.
• HHHHHH: Matches everywhere, so \$2+4+8+16+32+64=126\$.

This generalizes easily to \$p\$-sided dice: for each match, add \$p^i\$ instead.

Task

Suppose we play Penney's game with \$p\$-sided dice, where \$p\ge 2\$. Given the value of \$p\$ and a sequence of outcomes \$S\$ as input, calculate the expected tosses before you get the exact pattern \$S\$.

The elements of \$S\$ can be \$1 \dots p\$ or \$0 \dots p-1\$.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

p  S                            ans
------------------------------------------
2  [0, 0, 0, 0, 1, 1]           64
2  [1, 1, 0, 0, 1, 1]           70
3  [1, 1, 1, 1, 1]              363
9  [0, 1, 2, 3, 4, 5, 6, 7, 8]  387420489

Answer 1

05AB1E, 16 9 bytes

Port of @Dingus's Ruby answer, so make sure to upvote him!

^{-7 bytes thanks to Grimmy.}

η¹.sÀgmO

Try it online!

Explanation

η          Find all prefixes of the input
 ¹         Re-take the first input
  .s       Find all suffixes of the input
    Ã      Find the two lists' intersection
     €g    Find the length of each
       m   Exponentiation by the second input
        O  Sum the output list

Answer 2

Python 3.8 (pre-release), 57 bytes

Modification of @math junkie's code making use of the walrus operator.

lambda p,S,i=0:sum(p**(i:=i+1)*(S[:i]==S[-i:])for _ in S)

Try it online!

---

An alternative 51-byte solution assuming that we may take an extra argument \$ l \$ denoting the length of the list.

Python 2, 51 bytes

f=lambda p,S,l:l and(S[:l]==S[-l:])*p**l+f(p,S,l-1)

Try it online!

Answer 3

J, ¹⁸ 15 bytes

#.0,~<\.=[:|.<\

Try it online!

• Create the boxed suffixes <\. and reversed prefixes [:|.<\...
• and check where they match elementwise =...
• This will be a boolean mask representing the number we seek in base p, but shifted right one.
• 0,~ shifts it back how we want...
• #. converts it using base p

Answer 4

Python 2, 55 bytes

f=lambda p,l,i=0:l==l[:i]or(l[:i]==l[-i:])+p*f(p,l,i+1)

Try it online!

Answer 5

Husk, 12 10 9 bytes

ΣMo^L§nṫḣ

Port of @petStorm's 05AB1E answer, so make sure to upvote him!
-2 bytes thanks to @Zgarb.
-1 byte thanks to @Leo.

Try it online.

Explanation:

     §     # Using the first argument-list twice:
        ḣ  #  Take its prefixes
       ṫ   #  And its suffices
      n    #  List intersection; keep only the sublists which are present in both
 M         # Map over each remaining sublist as left argument,
  o        # using the following two commands:
    L      #  Take the length of the sublist
   ^       #  take the power of the two: input^length
Σ          # And then sum the integers in the mapped list
           # (after which the result is output implicitly)

Answer 6

Ruby, ^{55 53} 49 bytes

->p,s{(1..s.size).sum{|i|s[0,i]==s[-i,i]?p**i:0}}

Try it online!

Similar to the non-recursive Python answer.

Answer 7

APL (Dyalog Extended), 20 bytes

{⍺+.*≢¨(⌽¨,\⌽⍵)∩,\⍵}

{⍺+.*≢¨(⌽¨,\⌽⍵)∩,\⍵}
,\⍵         prefixes
∩           intersect
(⌽¨,\⌽⍵)   suffixes
≢¨          length of each
⍺+.*        exponentiation and sum

Try it online!

Answer 8

Red, 87 bytes

func[p s][o: 0
repeat n d: length? s[if(at s d + 1 - n)=
copy/part s n[o: p ** n + o]]]

Try it online!

Answer 9

K (oK), 31 bytes

{x/|0,{(y#x)~|y#|x}/:[y;1+!#y]}

Try it online!

Answer 10

Jelly, 9 bytes

eÐƤ¹Ƥ$;0ḅ

A dyadic Link accepting a list on the left and an integer on the right which yields an integer.

Try it online!

How?

eÐƤ¹Ƥ$;0ḅ - Link: list, S; integer, p           e.g.  [2,3,1,2,3]; 4
     $    - last two links as a monad:
    Ƥ     -   for prefixes (of S):                    [2] [2,3] [2,3,1] [2,3,1,2] [2,3,1,2,3]
   ¹      -     identity                              [2] [2,3] [2,3,1] [2,3,1,2] [2,3,1,2,3]
          -   }                                      =[[2],[2,3],[2,3,1],[2,3,1,2],[2,3,1,2,3]]
 ÐƤ       -   for post-fixes (of S):                  [2,3,1,2,3] [3,1,2,3] [1,2,3] [2,3] [3]
e         -     exists in (the collected prefixes)?   1           0         0       1     0
          -   }                                      =[1,   0,   0,   1,   0]
       0  - literal zero                              0
      ;   - concatenate                               [1,   0,   0,   1,   0,   0]
        ḅ - convert from base (p)                      1×4⁵+0×4⁴+0×4³+1×4²+0×4¹+0×4°
                                                      =1024+16
                                                      =1040

Answer 11

Retina, 55 bytes

~[".+¶$.("|'_Lv$`((,\d+)+)$(?<=^(\d+)\1\b.*)
$#2*$($3$*

Try it online! Link includes test suite. Takes input as a comma-separated list, but the test suite removes spaces and brackets for ease of use. Explanation:

Lv$`((,\d+)+)$(?<=^(\d+)\1\b.*)

Match all (necessarily overlapping) suffixes of the input starting with a comma that also match immediately after the base.

$#2*$($3$*

For each match, output a string of the form 2*2* where 2 is the input base and the number of 2s is the number of matched integers. (The trailing ) is implied.)

[".+¶$.("|'_

Join the matches with a _ and prefix the whole output with the following:

.+
$.(

For the second example, this results in the following:

.+
$.(2*2*2*2*2*2*_2*2*_2*

Note that the _) at the end of the program is implied.

~

Evaluate the generated Retina program, thus computing the desired result.

Answer 12

Charcoal, 17 bytes

Ｉ×θ↨θＥη⁼…η⁻Ｌηκ✂ηκ

Try it online! Link is to verbose version of code. Explanation:

     Ｅη              Map over elements of `S`
              ✂ηκ   `S` sliced starting at that element
       ⁼            Is equal to
        …η⁻Ｌηκ      Prefix of `S` with that length
   ↨θ               Convert from base `p`
 ×θ                 Multiply by `p`
Ｉ                   Cast to string for implicit print

Answer 13

Pure Bash, 70 bytes

for((i=$#;--i;)){ [ "${*:2:$i}" = "${*: -$i}" ]&&$[s+=$1**i];};echo $s

Try it online!

The input is passed in the arguments: first p, then the items (each as a separate argument).

Output is on stdout.

Answer 14

Pyth, 16 bytes

sm*q<Qd>dQ^vzdSl

Try it online!

Map (m) over the 1-indexed range of the sequence (Sl(Q)). If the first d elements of the sequence (<Qd) equals the last d elements (>dQ), map to "p to the power of d" (^vzd). Sum the result (s).

Answer 15

Brachylog, 16 bytes

{{a₀.&a₁}ᵗlᵗ^}ᶠ+

Try it online!

               +    The output is the sum of
{            }ᶠ     every possible output from:
  a₀.               find a prefix
     &a₁            which is also a suffix
 {      }ᵗ          of the last item of the input,
          lᵗ        take its length,
            ^       and take the first element to the power of that length.