14
\$\begingroup\$

Background

Inspired by this video by Matt Parker

A Faro shuffle is a perfect riffle shuffle where the deck is exactly interleaved with its other half. This is how to perform one:

  • the deck of 52 cards is split into two piles of 26 cards each
  • the two piles are interleaved. In the case of an "in" shuffle, the bottom card of the top pile ends up on the bottom, and the top card of the bottom pile ends up on the top (the outer cards move inwards). In the case of an "out" shuffle, the top card of the top pile ends up on top and vice versa (the outer cards stay on the outside).

For example, with a demonstration deck of only 6 cards, the steps are as follows:

  • Start: [1, 2, 3, 4, 5, 6]
  • Split: [1, 2, 3] [4, 5, 6]
  • For an "in" shuffle, interleave like this: [4, 1, 5, 2, 6, 3] (zip the second half with the first half)
  • For an "out" shuffle, interleave like this: [1, 4, 2, 5, 3, 6] (zip the first half with the second half)

Challenge

Given a list of values representing "in" and "out" Faro Shuffles, determine the minimum number of times that list needs to repeat such that a deck of 52 distinct cards will return to its starting arrangement. Note that this is not the same value shown in Matt's video; it is divided by the length of the input.

If the deck returns to the starting arrangement part way through the list (for example, [0, 0, 0, 0, 0, 0] (6 out shuffles) would finish after 1 full set of 6 and then 2 more shuffles), it doesn't count as having finished the cycle because it wasn't completed at the end of the list (so the output for that example would be LCM(6, 8) / 6 = 4).

Example

Input: [0, 1, 1, 0, 1, 1, 1] (using 0 for "out" shuffles and 1 for "in" shuffles, and representing the starting deck is [0, 1, 2, 3, ... 48, 49, 50, 51])

  • First, we perform the shuffles as they are specified in the input: out, in, in, out, in, in, in. This gives the output:
[0, 26, 1, 27, 2, 28, 3, 29, 4, 30, 5, 31, 6, 32, 7, 33, 8, 34, 9, 35, 10, 36, 11, 37, 12, 38, 13, 39, 14, 40, 15, 41, 16, 42, 17, 43, 18, 44, 19, 45, 20, 46, 21, 47, 22, 48, 23, 49, 24, 50, 25, 51]
  • Now, we check if that has caused the list to return to its exact original arrangement
  • Repeat these steps, and output the number of times we've looped. In this case, it takes 1260 repetitions of [0, 1, 1, 0, 1, 1, 1], so our output is 1260

Test cases

Using 0 for "out" shuffles and 1 for "in" shuffles.

[0] 8
[1] 52
[0, 1] 252
[0, 0, 1] 20
[0, 1, 0] 20
[1, 0, 0] 20
[0, 1, 1, 0, 1, 1, 1] 1260
[0, 0, 0, 0, 0, 0, 0, 1] 2
[0, 0, 0, 0, 0, 0] 4
[0, 0, 0, 0, 0, 0, 0, 0, 0] 8
[0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1] 144
[1, 0, 1, 1, 1, 0, 1, 1, 1] 60
[0, 1, 1, 0] 44
[1, 1, 1, 1, 0, 1, 0, 1, 0] 306
[1, 1, 0, 1, 1, 0, 0, 1, 1, 0] 210
[1, 0, 0, 0, 0, 0, 0, 1] 2
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1] 168
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1] 228
[1, 0, 1, 0, 1] 60
[1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1] 66
[0, 0, 0, 0, 1, 0] 252

Rules

  • The values that represent "in" and "out" in the input list can be any two distinct values, within reason. For example, 0 and 1 is allowed, but code_to_do_an_in_shuffle() and code_to_do_an_out_shuffle() are not
  • Standard loopholes are forbidden
  • You may use any sensible I/O method
  • This is , so the shortest code in bytes wins
\$\endgroup\$
7
  • \$\begingroup\$ Sandbox, Related, Related, Related \$\endgroup\$ – pxeger May 3 at 13:21
  • \$\begingroup\$ What is the expected answer for [0, 0, 0, ... 9 times]? 0 or 8? Note that it returns to the starting arrangement before the first cycle finishes. \$\endgroup\$ – Manish Kundu May 3 at 13:50
  • \$\begingroup\$ @ManishKundu The way I interpret it is that it needs to complete the list. \$\endgroup\$ – EnderShadow8 May 3 at 13:51
  • 1
    \$\begingroup\$ @Jonah I'm going to say no, since it kind of defeats the background of the challenge, which is to simulate weird shuffling in card games \$\endgroup\$ – pxeger May 3 at 16:13
  • 2
    \$\begingroup\$ Random side note: the largest possible output is 180,180 (the largest order of a permutation of 52 objects) ... I wonder if there is an input that yields that. \$\endgroup\$ – Greg Martin May 4 at 1:21

15 Answers 15

4
\$\begingroup\$

Pyth, 63 53 bytes

J26AcU*J2JW=Y?@Q%ZlQ.iHG.iGH=+Z1AcYJI&qYSY!%ZlQB;/ZlQ

Try it online!

J26          # Set J to 26.
AcU*J2J      # Assign G and H to range(0, 26) and range(26, 52) respectively.
W            # While
?@Q%ZlK      # If the current element of Q (input list)
.iHG         # is 1, then interleave H and G
.iGH         # Otherwise, interleave G and H
=Y           # Assign that value to Y
=+Z1         # Increment Z by 1
AcYJ         # Now reassign G and H to the first and last 26 elements of Y respectively
I&qYSY!%ZlQB # If Y is already sorted and we are at the end of input list, then break
;/ZlQ        # Print Z divided by length of input list
\$\endgroup\$
4
\$\begingroup\$

J, 45 40 36 bytes

3 :'*./#&>C.{/|.y{(,:&,&|:|.)i.2 26'

Try it online!

-4 thanks to xash

Rather than use a while loop, the solution constructs the permutation, changes it to cyclic form C., and then takes the LCM *./ of the cycle lengths.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ (,:&,&|:|.)i.2 26 to save 4 \$\endgroup\$ – xash May 3 at 15:17
4
\$\begingroup\$

Python 3.8, 88 84 bytes

*r,=range(52)
f=lambda k,s=r:[s:=s[x::2]+s[1-x::2]for x in k[::-1]]!=s==r or-~f(k,s)

Try it online!

Uses @l4m2's neat idea (on @hyper-neutrino's answer) to reverse the shuffles instead of execute them forwards.

-4 bytes thanks to @dingledooper

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can use *r,=range(52)instead to save 4 bytes. \$\endgroup\$ – dingledooper May 3 at 17:56
  • \$\begingroup\$ Neat tip, thanks! \$\endgroup\$ – kops May 3 at 19:11
3
\$\begingroup\$

Python 2, 100 bytes

def f(k):
 s=t=range(52);q=1
 while 1:
	for x in k[::-1]:s=s[x::2]+s[1-x::2]
	if s==t:return q
	q+=1

Try it online!

-10 bytes thanks to pxeger
-4 bytes thanks to Neil
-11 bytes thanks to l4m2
-6 bytes thanks to dingledooper

\$\endgroup\$
10
  • \$\begingroup\$ This can be shorter by copying the initial range and comparing against that instead of sorting it: Try it online! \$\endgroup\$ – pxeger May 3 at 14:09
  • \$\begingroup\$ @pxeger Oh, good idea, thanks. (Got it to 123 bytes in py 2 using the same idea) \$\endgroup\$ – hyper-neutrino May 3 at 14:10
  • \$\begingroup\$ You can use range(52) instead of range(1,53): Try it online! \$\endgroup\$ – pxeger May 3 at 14:12
  • \$\begingroup\$ @pxeger oh oops, that was for testing lol. thanks \$\endgroup\$ – hyper-neutrino May 3 at 14:12
  • 1
    \$\begingroup\$ Reversed moves \$\endgroup\$ – l4m2 May 3 at 15:59
3
\$\begingroup\$

Charcoal, 47 35 bytes

W¬⁼ω⁺αβ«⊞υωF⮌θ≔⭆²Φ∨ω⁺αβ﹪⁺κ⁺λξ²ω»ILυ

Try it online! Link is to verbose version of code. Edit: Saved 12 bytes thanks to @l4m2 by performing in-sorts and out-sorts instead, but the input values are now 0 for an in-shuffle and 1 for an out-shuffle. Explanation:

W¬⁼ω⁺αβ«

Repeat until the shuffle reaches the initial pack, represented here by the concatenation of the upper and lower case letters.

⊞υω

Keep track of the number of cycles.

F⮌θ

Loop over each type of shuffle in reverse, since we're performing inverse shuffles.

≔⭆²Φ∨ω⁺αβ﹪⁺κ⁺λξ²ω

Take alternating cards from the pack (initialising it on the first pass). Whether odd or even cards are taken first depends on the type of shuffle. The remaining cards are then concatenated, completing the in-sort or out-sort.

»ILυ

Output the number of shuffles needed.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 86 80 77 bytes

->s{r=k=[*0..51];1.step.find{s.map{|c|r=k.map{|v|r[(v/2+26*v+=c)%52]}};r==k}}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 83 bytes by copying the initial range and comparing against that instead of the sorted array \$\endgroup\$ – pxeger May 3 at 13:59
  • \$\begingroup\$ You need to include the assignment f= as part of the code because you recurse using it, by the way \$\endgroup\$ – pxeger May 3 at 14:01
2
\$\begingroup\$

JavaScript (Node.js), 102 99 98 95 bytes

f=s=>s.map(v=>L=L.map((_,i)=>L[i+52*(i%2^v)>>1]))|L+[]==G||1+f(s);L=G=[...Array(52)].map(Array)

Try it online!

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

Wolfram Language, 97 bytes

s|->Length@NestWhileList[Fold[Riffle@@#~TakeDrop~26~RotateLeft~#2&,#,s]&,Range[52],UnsameQ,All]-1

Try it online! (uses \[Function] rather than |->, as TIO doesn't have the most recent version of the language)

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

R, 80 bytes

o=scan();e=d=0:51;while({for(s in o)d=t(matrix(d,26,3)[,1:2+s]);sd(d-e)})T=T+1;T

Try it online!

Implements riffle shuffle by re-arranging the deck into a matrix with 26 rows, and transposing.
An 'in' shuffle first reverses the columns, which is achieved in R by making a 3-column matrix (which gets filled by recycling elements), and then selecting columns 2,3.

e=d=0:51                # set e,d to the initial order of the deck
while({                 # while loop: 
  for(s in o)           #  first cycle through the shuffle-types in o
    d=                  #  reordering d each time
      t(                #  as the transpose of
        matrix(d,26,    #  a matrix with 26 rows
        3)              #  and 3 columns (so the third column is the first one again)
          [,1:2+s])     #  selecting columns 1:2 if o==0, 
                        #  or columns 2:3 (same as 2:1) if o==1;
  sd(d-e)}              #  then repeat until standard deviation of d-e is non-zero
                        #  (d & e are both permutations of the deck,
                        #  so sum(d-e) must be zero, and sd(d-e) can only
  )                     #  be zero if d==e)
  T=T+1                 # increment T (from initial value of 1) each loop
T                       # and finally output the value of T
\$\endgroup\$
2
\$\begingroup\$

PowerShell 7, 87 84 bytes

for(;"$c"-ne0..51;$x++){$args|%{$s=$_
$c=$c ??0..51|%{(2*$_+($s,!$s)[$_/51])%52}}}$x

Try it online! (Link is to a TIO-compatible version with 4 additional bytes; PowerShell 6 and below do not support the null-coalescing operator ??)

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

Husk, 13 bytes

Γ€GFöΣT*½ḣ52∞

Try it online! or Verify all tests

15 bytes, 16 bytes, 16 bytes

input taken as 1 instead of 0 and -1 instead of 1.

-2 bytes from Leo.

This could be another 15 bytes, but times out.

Explanation

Γ€GFöΣT*½ḣ52∞
            ∞ infinite list of repetitions of the input
  G           scan from left with:
         ḣ52  1..52 as the start value
   Fö          fold the repeated list with
               the current value as start
               and do the following:
        ½       split in two halves
       *        multiply by the list number
      T         transpose
     Σ          flatten
Γ              take first element and:
 €             find its index in the remaining list
\$\endgroup\$
1
\$\begingroup\$

Python 3, 136 bytes

-5 thanks to OP

Can definitely be golfed more, but I'm too tired.

def f(s):
 o=l=[*range(52)];c=0
 while 1:
  for i in s:l=[(l[:26],l[26:])[j%2-i][j//2]for j in range(52)]
  c+=1
  if l==o:return c

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ The list comprehension part instead of zip is really smart! You don't need o=l[:] since you never mutate l (only reassign) - it can just be o=l=[*range(52)]. This allows you to replace the second range(52) with just o Also, in Python 2 you could drop the [*] because range returns a list already, change // to /, and save some with tab indentation: Try it online! \$\endgroup\$ – pxeger May 3 at 14:18
  • \$\begingroup\$ Ohh, I was thinking about the horrors of how pointers to the same object cause headaches so I think I did that by habit. I'll fix it. \$\endgroup\$ – EnderShadow8 May 3 at 14:24
  • \$\begingroup\$ There's no room for best practices in code golf! :-) \$\endgroup\$ – pxeger May 3 at 14:26
  • 1
    \$\begingroup\$ I remember the days of onelinerizer.com before I discovered code golf \$\endgroup\$ – EnderShadow8 May 3 at 14:28
  • \$\begingroup\$ There are still a few low-hanging fruit here; not sure if you missed them in my previous comment \$\endgroup\$ – pxeger May 3 at 14:30
1
\$\begingroup\$

Haskell, 91 bytes

f l=[r|r<-[1..],and[foldl(\x i->mod(2*x+mod(div x 26+i)2)52)y([1..r]>>l)==y|y<-[0..51]]]!!0

Try it online!

f takes l as a list of 0s and 1s, with the format described in the statement.

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

Jelly, 15 bytes

ØẠŒHṚ⁹¡ż/Fʋƒ@ƬL

A monadic Link accepting a list of 1s (in) and 0s (outs) which yields a positive integer (number of repetitions of the described procedure required to reset the deck of 52 cards).

Try it online!

How?

Just repeatedly executes the instructions list until reset has occured...

ØẠŒHṚ⁹¡ż/Fʋƒ@ƬL - Link: list, shuffles
ØẠ              - "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" ...26*2=52 :)
             Ƭ  - collect up starting with that "deck" until a repetition occurs using:
            @   -   with reversed arguments - f(shuffles,deck)
           ƒ    -     reduce using (X) as the initial value with:
          ʋ     -       last four links as a dyad - f(current_deck, current_shuffle):
  ŒH            -         split (current_deck) into two halves
      ¡         -         repeat...
     ⁹          -           ...number of times: right argument = current_shuffle
    Ṛ           -           ...action: reverse
        /       -         reduce using:
       ż        -           zip together
         F      -         flatten
              L - length
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 194 \$\cdots\$ 180 174 bytes

Saved 6 bytes thanks to ceilingcat!!!

w=52;n;c;i;j;a[156];f(s,l)int*s;{for(c=i=0;i<w*3;)a[n=i++]=i%w;for(;n;++c)for(j=0;j<l;++j)for(i=!wmemcpy(a+w,a,w);i<w;n=wmemcmp(a,a+2*w,w))a[i++]=a[w+(s[j]+i&1)*26+i/2];n=c;}

Try it online!

Inputs a pointer to the shuffle array and its length (since pointers in C carry no length info).

Explanation (before some golfs)

w=52;n;c;i;j;                              // declare needed vars   
f(s,l)int*s;{                              // main function
    char a[w],b[w],e[w];                   // declare arrays for shuffling  
    for(c=i=0;i<w;)a[i++]=e[i]=i;          // init a and e to 0..51
    for(n=1;n;++c)                         // loop until array a is back 
                                           // to its original order (n == 0)
                                           // c counts iterations
        for(j=0;j<l;++j)                   // loop over shuffle array  
            for(i=!memcpy(b,a,w);          // copy a over to b (returns !0)  
                                 i<w;      // loop over a and b   
                          n=memcmp(a,e,w)) // here's a good place to calc n 
              a[i++]=                      // set each element in a to
                     b[                   ]// an element in b depending on
                       ((s[j]+i)%2)*26+i/2 // our current shuffle and i   
    n=c;                                   // return count  
}  
\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat Nice - thanks! :D \$\endgroup\$ – Noodle9 May 9 at 21:00

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.