[Question]
  [
## Background
[**Penney's game**](https://en.wikipedia.org/wiki/Penney%27s_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**](https://mathoverflow.net/a/357282) 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](/questions/tagged/code-golf "show questions tagged '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]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~16~~ 9 bytes
Port of [@*Dingus*'s Ruby answer](https://codegolf.stackexchange.com/a/203788/92069), so make sure to upvote him!
-7 bytes thanks to Grimmy.
```
η¹.sÃ€gmO
```
[Try it online!](https://tio.run/##yy9OTMpM/f//3PZDO/WKDzc/alqTnuv//3@0oY4CEBmAEYgdy2UEAA "05AB1E – 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]
# [Python 3.8 (pre-release)](https://docs.python.org/3.8/), 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!](https://tio.run/##bYzLCsIwEEX3fsUskzhCY33UQL4iyxikIsEBmw6xLvz6GBSKoHBW91wOP6frmNqOc4n2WG79cL70wOiQbGPuj0GwUoKMpaWWSjhvKFjr/IpMkHHMcAJK4GThTGkSUawRfIMwoytBysW31@/5v29nr3/l4ROvc83U5wZhi7BD2CN09Vhe "Python 3.8 (pre-release) – 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](https://docs.python.org/2/), 51 bytes
```
f=lambda p,S,l:l and(S[:l]==S[-l:])*p**l+f(p,S,l-1)
```
[Try it online!](https://tio.run/##dc3NCsMgDMDx@54iR3Up1O6zgk/hUTw4imyQWRm97Olt6MDtMsjt/0tS3st9zkOtyVJ83qYIBR2SIYh5Es4bCtY635EJUhWlaJ/EJjota3k98gJJDAi@R2ijeQLCWe5@hd7CP3FoQrd8@ubx84IDn2J75Mr7CBeEK9NR1hU "Python 2 – Try It Online")
[Answer]
# [J](http://jsoftware.com/), 18 15 bytes
```
#.0,~<\.=[:|.<\
```
[Try it online!](https://tio.run/##Xc29CsJAEATg3qcYtAjCuuz9eHc5cpVgZWVrOjEEG19A8uqXxYiiMNvMtzD3uuZmQMloQBBkvR3jcD4d64aFpq7ncslP7vq6Xd2u4wPBo8BigNA3RrNwlDebV/vPLjh193Hzgyl6Kz61@tIuC4qW4AiesCcEQiSkOgM "J – 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]
# [Python 2](https://docs.python.org/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!](https://tio.run/##K6gsycjPM/r/P802JzE3KSVRoUAnRyfT1sAqx9Y2J9oqMza/SANMg7i6mVaxmtoFWmkaYFXahpr/C4oy80oU0jSMdBSiDXQU4MgQiGI1uZClDcGiWKWN4dKGGHKWEJOBokBDgApNdBRMdRTMdBTMdRQsYjX/AwA "Python 2 – Try It Online")
[Answer]
# [Husk](https://github.com/barbuz/Husk/wiki/Commands), ~~12~~ ~~10~~ 9 [bytes](https://github.com/barbuz/Husk/wiki/Codepage)
```
ΣMo^L§nṫḣ
```
Port of [*@petStorm*'s 05AB1E answer](https://codegolf.stackexchange.com/a/203789/52210), so make sure to upvote him!  
-2 bytes thanks to *@Zgarb*.  
-1 byte thanks to *@Leo*.
[Try it online.](https://tio.run/##yygtzv7//9xi3/w4n0PL8x7uXP1wx@L///9HG@oY6hgAIZCO/W8EAA)
**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]
# [Ruby](https://www.ruby-lang.org/), ~~55~~ ~~53~~ 49 bytes
```
->p,s{(1..s.size).sum{|i|s[0,i]==s[-i,i]?p**i:0}}
```
[Try it online!](https://tio.run/##ZYvNCsIwEITvfYo5atmGxn@F6IOEPai0mEOhuOlBkz57DBYKIgzDMt@3z@H2Sq1J1bknCQutlChx72apZOhCdFFsTY6NEVu5fFz6snSnehyTb8QLDGwB2BVlDXN0DjNNBFZ/lz@0npH@2Y@Ua1Lzd7Y2hC1hR9gTDswFq@Z6fyAg@ogerS09Y0wf "Ruby – Try It Online")
Similar to the non-recursive [Python answer](https://codegolf.stackexchange.com/a/203785/92901).
[Answer]
# [APL (Dyalog Extended)](https://github.com/abrudz/dyalog-apl-extended), 20 bytes
```
{⍺+.*≢¨(⌽¨,\⌽⍵)∩,\⍵}
```
```
{⍺+.*≢¨(⌽¨,\⌽⍵)∩,\⍵}
,\⍵         prefixes
∩           intersect
(⌽¨,\⌽⍵)   suffixes
≢¨          length of each
⍺+.*        exponentiation and sum
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNrShJzUtJTfn/v/pR7y5tPa1HnYsOrdB41LP30AqdGCD1qHer5qOOlUB279ba/2mP2iY86u171NX8qHfNo94th9YbP2qb@KhvanCQM5AM8fAM/m@kkKZgAIWGCoZcID6QhvONoXww5LIEqzZUMFIwVjBRMFUwUzBXsAAA "APL (Dyalog Extended) – Try It Online")
[Answer]
# [Red](http://www.red-lang.org), 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!](https://tio.run/##Zcy9CsIwFIbhPVfxjdoiNtbfgHgPruEMpUm0UJKQxMGrjwldFDnT98B7glb5rpUkZkQ2LztKj0jSCXQsaK@HBAslMGv7SM8bopzMqmCEQguODez6ykbn31s/hOq2xh5NU8IWjoiyD5NNMNhBdliOgxP78rL/vV@c/@qlfuEl6rHHAUeccKb8AQ "Red – Try It Online")
[Answer]
# [K (oK)](https://github.com/JohnEarnest/ok), 31 bytes
```
{x/|0,{(y#x)~|y#|x}/:[y;1+!#y]}
```
[Try it online!](https://tio.run/##y9bNz/7/P82qukK/xkCnWqNSuUKzrqZSuaaiVt8qutLaUFtRuTK29n@aQrSltYGCoYKRgrGCiYKpgpmCuYJF7H8A "K (oK) – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 9 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
eÐƤ¹Ƥ$;0ḅ
```
A dyadic Link accepting a list on the left and an integer on the right which yields an integer.
**[Try it online!](https://tio.run/##y0rNyan8/z/18IRjSw7tPLZExdrg4Y7W////RxvqKACRARiB2LH/jQA "Jelly – 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]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 55 bytes
```
~[".+¶$.("|'_Lv$`((,\d+)+)$(?<=^(\d+)\1\b.*)
$#2*$($3$*
```
[Try it online!](https://tio.run/##K0otycxLNPyvqpEQHasQHcv1vy5aSU/70DYVPQ2lGvV4nzKVBA0NnZgUbU1tTRUNexvbOA0QJ8YwJklPS5NLRdlIS0VDxVhF6/9/Ix0FhWgDHQU4MgSiWC6wsCGYhyxsjBA2hIlZQk0A8oC6gCpMdBRMdRTMdBTMdRQsYgE "Retina – 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 `2`s 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]
# [Charcoal](https://github.com/somebody1234/Charcoal), 17 bytes
```
Ｉ×θ↨θＥη⁼…η⁻Ｌηκ✂ηκ
```
[Try it online!](https://tio.run/##HUnLCsIwEPyVPW5hBfXam8GbBUFvpYclBBNcU9ukQr9@TTIM87SeVzuzqN7XEDMaThmf4eMSLgQXTq76wF/0BNdlY0lodivO@LltQ4hbwpuLr@zRdwTvrshDgnX1Lq2hVx3PBDCeCAqPjTVPkx5@8gc "Charcoal – 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]
# Pure [Bash](https://www.gnu.org/software/bash/), 70 bytes
```
for((i=$#;--i;)){ [ "${*:2:$i}" = "${*: -$i}" ]&&$[s+=$1**i];};echo $s
```
[Try it online!](https://tio.run/##S0oszvifnFiiYKdQUJSfXpSYq2Bjo@Tq76b0Py2/SEMj01ZF2VpXN9NaU7NaIVpBSaVay8rISiWzVknBFsJT0AXzYtXUVKKLtW1VDLW0MmOta61TkzPyFVSK/wPN4krOyM1PUSjVroBZwsWlpw@zz0jBAAoNFQxRxIF8LOLGYHFDNFFLsDojoKyJgqmCmYK5gsV/AA "Bash – 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]
# [Pyth](https://github.com/isaacg1/pyth), 16 bytes
```
sm*q<Qd>dQ^vzdSl
```
[Try it online!](https://tio.run/##K6gsyfj/vzhXq9AmMMUuJTCurColOOf//2hDHQUEiuUyBgA "Pyth – 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]
# [Brachylog](https://github.com/JCumin/Brachylog), 16 bytes
```
{{a₀.&a₁}ᵗlᵗ^}ᶠ+
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/pfXa6koGunoFRu/6htw6Ompoe7Omsfbp3wv7o68VFTg54akGwECkzPAeK42ofbFmj//x@tEG2kE22gA4GGOoaxsTogESALWcQYImII41uC9BjqGOkY65jomOqY6ZjrWMTGKsQCAA "Brachylog – 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.
```
]