21
\$\begingroup\$

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 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
\$\endgroup\$
2
  • \$\begingroup\$ 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] ?) \$\endgroup\$ – math junkie Apr 23 '20 at 4:15
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Bubbler Apr 23 '20 at 4:19

15 Answers 15

8
\$\begingroup\$

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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ η¹.sÀgmO for 9 bytes (or η¹.sÃöPO for 8, but it fails for p >= 10). \$\endgroup\$ – Grimmy Apr 23 '20 at 6:42
6
\$\begingroup\$

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!

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

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 17 bytes. \$\endgroup\$ – Bubbler Apr 23 '20 at 6:37
  • \$\begingroup\$ @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. \$\endgroup\$ – Jonah Apr 23 '20 at 12:31
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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)
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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... \$\endgroup\$ – user92069 Apr 23 '20 at 7:45
  • 1
    \$\begingroup\$ -2 bytes by getting rid of superscripts and parentheses. \$\endgroup\$ – Zgarb Apr 23 '20 at 10:42
  • \$\begingroup\$ @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. \$\endgroup\$ – Kevin Cruijssen Apr 23 '20 at 10:59
  • 1
    \$\begingroup\$ -1 byte by using M to get rid of the last superscript and swapping arguments. Unfortunately needs an explicit sum \$\endgroup\$ – Leo Apr 24 '20 at 2:53
  • \$\begingroup\$ @Leo Thanks! I tried M earlier, but didn't knew it needed the o Zgarb suggested in order to work here. \$\endgroup\$ – Kevin Cruijssen Apr 24 '20 at 6:30
3
\$\begingroup\$

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.

\$\endgroup\$
3
+150
\$\begingroup\$

APL (Dyalog Extended), 20 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

K (oK), 31 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 17 bytes

I×θ↨θEη⁼…η⁻Lηκ✂ηκ

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

     Eη              Map over elements of `S`
              ✂ηκ   `S` sliced starting at that element
       ⁼            Is equal to
        …η⁻Lηκ      Prefix of `S` with that length
   ↨θ               Convert from base `p`
 ×θ                 Multiply by `p`
I                   Cast to string for implicit print
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

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

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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