# Penney-Conway odds

## 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.

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 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

• Does the pattern of the last i elements need to be in the same order as the first i elements? (eg. what would the output be for 3 [0, 1, 2, 1, 0] ?) – math junkie Apr 23 '20 at 4:15
• @mathjunkie Yes. In your case, only i=1 and i=5 match. You can see it in the second test case, where [1, 1, 0] != [0, 1, 1] so 3 is not counted. – Bubbler Apr 23 '20 at 4:19

# 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

• η¹.sÃ€gmO for 9 bytes (or η¹.sÃöPO for 8, but it fails for p >= 10). – Grimmy Apr 23 '20 at 6:42

# 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!

• Alternative non-recursive 60-bytes: Try it online! – math junkie Apr 23 '20 at 4:23
• Python 3.8 is released now :) – Gavin S. Yancey Apr 23 '20 at 18:35

# J, 18 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
• – Bubbler Apr 23 '20 at 6:37
• @Bubbler Thanks (nice p. use) but I actually realized my original solution could be 3 bytes shorter by just using = instead of -:&>, because = on boxes automatically checks their contents. – Jonah Apr 23 '20 at 12:31

# 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!

# Husk, 1210 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)

• The Husk answer is a port of my answer, mine is a port of the Ruby answer, the Ruby answer is a port of the Python answer... – user92069 Apr 23 '20 at 7:45
• -2 bytes by getting rid of superscripts and parentheses. – Zgarb Apr 23 '20 at 10:42
• @Zgarb Thanks! Only my third Husk answer, so I still have to get used to it a bit.. Didn't even knew about § nor o. – Kevin Cruijssen Apr 23 '20 at 10:59
• -1 byte by using M to get rid of the last superscript and swapping arguments. Unfortunately needs an explicit sum – Leo Apr 24 '20 at 2:53
• @Leo Thanks! I tried M earlier, but didn't knew it needed the o Zgarb suggested in order to work here. – Kevin Cruijssen Apr 24 '20 at 6:30

# 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.

# APL (Dyalog Extended), 20 bytes

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

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


Try it online!

# 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!

# K (oK), 31 bytes

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


Try it online!

$- 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  # 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. # 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  # 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.

# 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).

• Another 16-byter: Try it online!. There's probably a way to golf this – math junkie May 29 '20 at 18:01

# 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.