Bisakah Anda berhenti mengocok geladak dan sudah bermain?

31

Tantangan:

Input: Daftar bilangan bulat positif yang berbeda dalam kisaran [1,list-size] .

Keluaran: Bilangan bulat: berapa kali daftar diacak-acak . Untuk daftar, ini berarti daftar ini dibagi menjadi dua bagian, dan bagian ini saling terkait (yaitu mengacak-acak daftar yang [1,2,3,4,5,6,7,8,9,10]akan dihasilkan sekali [1,6,2,7,3,8,4,9,5,10], jadi untuk tantangan ini input [1,6,2,7,3,8,4,9,5,10]akan menghasilkan 1).

Aturan tantangan:

  • Anda dapat mengasumsikan bahwa daftar hanya akan berisi bilangan bulat positif dalam kisaran [1,list-size] (atau [0,list-size1] jika Anda memilih untuk membuat daftar input yang diindeks 0).
  • Anda dapat mengasumsikan semua daftar input akan menjadi daftar acak-acak, atau daftar diurutkan yang tidak dikocok (dalam hal ini hasilnya adalah 0 ).
  • Anda dapat mengasumsikan bahwa daftar input akan mengandung setidaknya tiga nilai.

Contoh langkah demi langkah:

Memasukkan: [1,3,5,7,9,2,4,6,8]

Unshuffling sekali menjadi:, [1,5,9,4,8,3,7,2,6]karena setiap item bahkan diindeks 0 datang terlebih dahulu [1, ,5, ,9, ,4, ,8], dan kemudian semua item 0-diindeks aneh setelah itu [ ,3, ,7, ,2, ,6, ].
Daftar ini belum dipesan, jadi kami melanjutkan:

Membatalkan daftar lagi menjadi: [1,9,8,7,6,5,4,3,2]
Sekali lagi menjadi: [1,8,6,4,2,9,7,5,3]
Lalu: [1,6,2,7,3,8,4,9,5]
Dan akhirnya:[1,2,3,4,5,6,7,8,9] :, yang merupakan daftar yang diurutkan, jadi kita selesai mengacak.

Kami melepas paket aslinya [1,3,5,7,9,2,4,6,8]lima kali [1,2,3,4,5,6,7,8,9], jadi hasilnya adalah5 dalam kasus ini.

Aturan umum:

  • Ini adalah , jadi jawaban tersingkat dalam byte menang.
    Jangan biarkan bahasa kode-golf mencegah Anda memposting jawaban dengan bahasa non-codegolf. Cobalah untuk memberikan jawaban sesingkat mungkin untuk bahasa pemrograman 'apa saja'.
  • Aturan standar berlaku untuk jawaban Anda dengan aturan I / O default , sehingga Anda diizinkan untuk menggunakan STDIN / STDOUT, fungsi / metode dengan parameter yang tepat dan tipe pengembalian, program penuh. Panggilanmu.
  • Celah Default tidak diperbolehkan.
  • Jika memungkinkan, silakan tambahkan tautan dengan tes untuk kode Anda (yaitu TIO ).
  • Juga, menambahkan penjelasan untuk jawaban Anda sangat dianjurkan.

Kasus uji:

Input                                                   Output

[1,2,3]                                                 0
[1,2,3,4,5]                                             0
[1,3,2]                                                 1
[1,6,2,7,3,8,4,9,5,10]                                  1
[1,3,5,7,2,4,6]                                         2
[1,8,6,4,2,9,7,5,3,10]                                  2
[1,9,8,7,6,5,4,3,2,10]                                  3
[1,5,9,4,8,3,7,2,6,10]                                  4
[1,3,5,7,9,2,4,6,8]                                     5
[1,6,11,5,10,4,9,3,8,2,7]                               6
[1,10,19,9,18,8,17,7,16,6,15,5,14,4,13,3,12,2,11,20]    10
[1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20]    17
[1,141,32,172,63,203,94,234,125,16,156,47,187,78,218,109,249,140,31,171,62,202,93,233,124,15,155,46,186,77,217,108,248,139,30,170,61,201,92,232,123,14,154,45,185,76,216,107,247,138,29,169,60,200,91,231,122,13,153,44,184,75,215,106,246,137,28,168,59,199,90,230,121,12,152,43,183,74,214,105,245,136,27,167,58,198,89,229,120,11,151,42,182,73,213,104,244,135,26,166,57,197,88,228,119,10,150,41,181,72,212,103,243,134,25,165,56,196,87,227,118,9,149,40,180,71,211,102,242,133,24,164,55,195,86,226,117,8,148,39,179,70,210,101,241,132,23,163,54,194,85,225,116,7,147,38,178,69,209,100,240,131,22,162,53,193,84,224,115,6,146,37,177,68,208,99,239,130,21,161,52,192,83,223,114,5,145,36,176,67,207,98,238,129,20,160,51,191,82,222,113,4,144,35,175,66,206,97,237,128,19,159,50,190,81,221,112,3,143,34,174,65,205,96,236,127,18,158,49,189,80,220,111,2,142,33,173,64,204,95,235,126,17,157,48,188,79,219,110,250]
                                                        45
Kevin Cruijssen
sumber
Satu atau dua test case dengan panjang ganjil dan output lebih besar dari 0 akan lebih baik. Sangat mudah untuk mengacaukan riffle dalam kasus-kasus seperti itu jika Anda harus menulis kode riffle sendiri daripada mengandalkan builtin.
Olivier Grégoire
@ OlivierGrégoire [1,3,5,7,9,2,4,6,8]Panjangnya 9, tapi saya akan menambahkan beberapa lagi untuk panjang 7 dan 11 mungkin. EDIT: Menambahkan kasus uji [1,3,5,7,2,4,6] = 2(panjang 7) dan [1,6,11,5,10,4,9,3,8,2,7] = 6(panjang 11). Semoga itu bisa membantu.
Kevin Cruijssen
Buruk saya: Saya yakin test case yang Anda sebutkan adalah ukuran 8. Tapi terima kasih untuk test case tambahan.
Olivier Grégoire
1
Pertanyaan seperti yang dirumuskan saat ini sepertinya "salah" ... satu riffle shuffle akan menghasilkan kartu pertama dan terakhir berubah, kecuali Anda menarik trik tipuan! yaitu [6,1,7,2,8,3,9,4,10,5] setelah satu pengocokan 10 kartu.
Steve
2
@ Sveve saya kira Anda agak benar. Mengacak-acak secara umum hanya menyisipkan dua bagian, sehingga keduanya [1,6,2,7,3,8,4,9,5,10]atau [6,1,7,2,8,3,9,4,10,5]mungkin. Dalam tantangan saya itu tidak berarti bahwa kartu teratas akan selalu tetap menjadi kartu teratas, jadi itu memang sedikit trik. Saya belum pernah melihat seseorang atau hanya menggunakan riffle-shuffles untuk mengocok setumpuk kartu. Biasanya mereka juga menggunakan jenis shuffle lain di antaranya. Bagaimanapun, sudah terlambat untuk mengubah tantangan sekarang, jadi demi tantangan ini kartu teratas akan selalu tetap menjadi kartu teratas setelah mengacak-acak.
Kevin Cruijssen

Jawaban:

6

Jelly , 8 byte

ŒœẎ$ƬiṢ’

Cobalah online!

Bagaimana?

ŒœẎ$ƬiṢ’ - Link: list of integers A
    Ƭ    - collect up until results are no longer unique...
   $     -   last two links as a monad:
Œœ       -     odds & evens i.e. [a,b,c,d,...] -> [[a,c,...],[b,d,...]]
  Ẏ      -     tighten                         -> [a,c,...,b,d,...]
     Ṣ   - sort A
    i    - first (1-indexed) index of sorted A in collected shuffles
      ’  - decrement
Jonathan Allan
sumber
25

JavaScript (ES6), 44 byte

Versi lebih pendek disarankan oleh @nwellnhof

Mengharapkan dek dengan kartu 1-diindeks sebagai input.

f=(a,x=1)=>a[x]-2&&1+f(a,x*2%(a.length-1|1))

Cobalah online!

Diberi setumpuk [c0,,cL1] dengan panjang L , kami mendefinisikan:

xn={2nmodLif L is odd2nmod(L1)if L is even

Dan kami mencari n sedemikian rupa sehingga cxn=2 .


JavaScript (ES6),  57 52  50 byte

Mengharapkan dek dengan kartu 0-diindeks sebagai input.

f=(a,x=1,k=a.length-1|1)=>a[1]-x%k&&1+f(a,x*-~k/2)

Cobalah online!

Bagaimana?

Karena JS kurang memiliki dukungan asli untuk mengekstraksi irisan array dengan loncatan kustom, mensimulasikan seluruh riffle-shuffle mungkin akan agak mahal (tapi jujur, saya bahkan tidak mencoba). Namun, solusinya juga dapat ditemukan dengan hanya melihat kartu ke-2 dan jumlah total kartu di dek.

Diberi setumpuk panjang L , kode ini mencari n sedemikian rupa sehingga:

c2(k+12)n(modk)

di mana c2 adalah kartu kedua dan k didefinisikan sebagai:

k={Lif L is oddL1if L is even

Arnauld
sumber
12

Python 2 , 39 byte

f=lambda x:x[1]-2and-~f(x[::2]+x[1::2])

Cobalah online!

-4 Terima kasih kepada Jonathan Allan .

Erik the Outgolfer
sumber
Simpan empat byte denganf=lambda x:2!=x[1]and-~f(x[::2]+x[1::2])
Jonathan Allan
@ Jonathan Allan Oh, tentu saja! Yah ... !=bisa saja -. ;-)
Erik the Outgolfer
Ah, ya, pengarang peringatan: D (atau hanya x[1]>2saya kira)
Jonathan Allan
5

R , 58 55 45 byte

a=scan();while(a[2]>2)a=matrix(a,,2,F<-F+1);F

Cobalah online!

Mensimulasikan proses penyortiran. Input diindeks 1, pengembalian FALSEuntuk 0.

Kirill L.
sumber
Sangat bagus! Saya sedang mengerjakan pendekatan yang sama tetapi menggunakan fungsi rekursif, yang tidak berfungsi sebagai golf.
user2390246
5

Perl 6 , 34 32 byte

-2 byte terima kasih kepada Jo King

{(.[(2 X**^$_)X%$_-1+|1]...2)-1}

Cobalah online!

Mirip dengan pendekatan Arnauld . Indeks kartu kedua setelah n mengocok adalah 2**n % kdengan k didefinisikan seperti dalam jawaban Arnauld.

nwellnhof
sumber
5

APL (Dyalog Unicode) , 35 26 23 22 byte SBCS

{⍵≡⍳≢⍵:01+∇⍵[⍒2|⍳⍴⍵]}

Cobalah online!

Thanks to Adám for the help, Erik the Outgolfer for -3 and ngn for -1.

The TIO link contains two test cases.

Explanation:

{⍵≡⍳≢⍵:01+∇⍵[⍒2|⍳⍴⍵]}
{⍵≡⍳≢⍵:01+∇⍵[⍒2|⍳⍴⍵]}  function takes one argument: ⍵, the array
 ⍵≡⍳≢⍵                  if the array is sorted:
 ⍵≡⍳≢⍵                  array = 1..length(array)
      :0                then return 0
                       otherwise
         1+             increment
                       the value of the recursive call with this argument:
            ⍵[      ]   index into the argument with these indexes:
                 ⍳⍴⍵    - generate a range from 1 up to the size of 
               2|       - %2: generate a binary mask like [1 0 1 0 1 0]
                       - grade (sorts but returns indexes instead of values), so we have the indexes of all the 1s first, then the 0s.

¹

Ven
sumber
1
Count the recursion depth for -3.
Erik the Outgolfer
@EriktheOutgolfer Much better, thanks!
Ven
1
∧/2≤/⍵ -> ⍵≡⍳≢⍵
ngn
@ngn didn't realize the array had no holes. Thanks!
Ven
4

Perl 6, 36 34 32 bytes

-2 bytes thanks to nwellnhof

$!={.[1]-2&&$!(.sort:{$++%2})+1}

Try it online!

Reverse riffle shuffles by sorting by the index modulo 2 until the list is sorted, then returns the length of the sequence.

It's funny, I don't usually try the recursive approach for Perl 6, but this time it ended up shorter than the original.

Explanation:

$!={.[1]-2&&$!(.sort:{$++%2})+1}
$!={                           }   # Assign the anonymous code block to $!
    .[1]-2&&                       # While the list is not sorted
            $!(             )      # Recursively call the function on
               .sort:{$++%2}       # It sorted by the parity of each index
                             +1    # And return the number of shuffles
Jo King
sumber
3

05AB1E (legacy), 9 bytes

[DāQ#ι˜]N

Try it online!

Explanation

[   #  ]     # loop until
  ā          # the 1-indexed enumeration of the current list
 D Q         # equals a copy of the current list
     ι˜      # while false, uninterleave the current list and flatten
        N    # push the iteration index N as output
Emigna
sumber
I didn't even knew it was possible to output the index outside the loop in the legacy. I thought it would be 0 again at that point, just like in the new 05AB1E version. Nice answer! Shorter than my 10-byter using the unshuffle-builtin Å≠ that inspired this challenge. :)
Kevin Cruijssen
@KevinCruijssen: Interesting. I didn't know there was an unshuffle. In this instance it's the same as my version, but unshuffle maintains dimensions on 2D arrays.
Emigna
3

Java (JDK), 59 bytes

a->{int c=0;for(;a[(1<<c)%(a.length-1|1)]>2;)c++;return c;}

Try it online!

Works reliably only for arrays with a size less than 31 or solutions with less than 31 iterations. For a more general solution, see the following solution with 63 bytes:

a->{int i=1,c=0;for(;a[i]>2;c++)i=i*2%(a.length-1|1);return c;}

Try it online!

Explanation

In a riffle, the next position is the previous one times two modulo either length if it's odd or length - 1 if it's even.

So I'm iterating over all indices using this formula until I find the value 2 in the array.

Credits

Olivier Grégoire
sumber
163 bytes by using two times x.clone() instead of A.copyOf(x,l).
Kevin Cruijssen
2
64 bytes
Arnauld
@Arnauld Thanks! I had a hard time figuring how to simplify that "length if odd else length - 1"
Olivier Grégoire
@Arnauld Oh! My new algorithm is actually the same as yours... And I spent half an hour figuring it out by myself...
Olivier Grégoire
More precisely, it's equivalent to an improvement over my original algorithm found by @nwellnhof.
Arnauld
3

J, 28 26 bytes

-2 bytes thanks to Jonah!

 1#@}.(\:2|#\)^:(2<1{])^:a:

Try it online!

Inspired be Ven's APL solution.

Explanation:

               ^:       ^:a:   while 
                 (2<1{])       the 1-st (zero-indexed) element is greater than 2   
     (        )                do the following and keep the intermediate results
          i.@#                 make a list form 0 to len-1
        2|                     find modulo 2 of each element
      /:                       sort the argument according the list of 0's and 1's
1  }.                          drop the first row of the result
 #@                            and take the length (how many rows -> steps)     

K (ngn/k), 25 bytes

Thanks to ngn for the advice and for his K interpreter!

{#1_{~2=x@1}{x@<2!!#x}\x}

Try it online!

Galen Ivanov
sumber
converge-iterate, then drop one, and count - this leads to shorter code
ngn
@ngn. So, similar to my J solution - I'll try it later, thanks!
Galen Ivanov
1
1#@}.(\:2|#\)^:(2<1{])^:a: for 26 bytes
Jonah
@Jonah Thank you!
Galen Ivanov
2

APL(NARS), chars 49, bytes 98

{0{∧/¯1↓⍵≤1⌽⍵:⍺⋄(⍺+1)∇⍵[d],⍵[i∼d←↑¨i⊂⍨2∣i←⍳≢⍵]}⍵}

why use in the deepest loop, one algo that should be nlog(n), when we can use one linear n? just for few bytes more? [⍵≡⍵[⍋⍵] O(nlog n) and the confront each element for see are in order using ∧/¯1↓⍵≤1⌽⍵ O(n)]test:

  f←{0{∧/¯1↓⍵≤1⌽⍵:⍺⋄(⍺+1)∇⍵[d],⍵[i∼d←↑¨i⊂⍨2∣i←⍳≢⍵]}⍵}
  f ,1
0
  f 1 2 3
0
  f 1,9,8,7,6,5,4,3,2,10
3
  f 1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20
17
RosLuP
sumber
That’s the first time I’ve seen someone differentiate between characters and bytes 👍. It always bugs me when I see Unicode characters and they claim that it’s one byte per character. This 😠 is not one byte!
Kerndog73
@Kerndog73 All is number, but in APL think characters are not numbers... (they seems element in AV array)
RosLuP
2

Ruby, 42 bytes

f=->d,r=1{d[r]<3?0:1+f[d,r*2%(1|~-d.max)]}

Try it online!

How:

Search for number 2 inside the array: if it's in second position, the deck hasn't been shuffled, otherwise check the positions where successive shuffles would put it.

G B
sumber
2

R, 70 72 bytes

x=scan();i=0;while(any(x>sort(x))){x=c(x[y<-seq(x)%%2>0],x[!y]);i=i+1};i

Try it online!

Now handles the zero shuffle case.

Nick Kennedy
sumber
1
@user2390246 fair point. Adjusted accordingly
Nick Kennedy
2

C (GCC) 64 63 bytes

-1 byte from nwellnhof

i,r;f(c,v)int*v;{for(i=r=1;v[i]>2;++r)i=i*2%(c-1|1);return~-r;}

This is a drastically shorter answer based on Arnauld's and Olivier Grégoire's answers. I'll leave my old solution below since it solves the slightly more general problem of decks with cards that are not contiguous.

Try it online


C (GCC) 162 bytes

a[999],b[999],i,r,o;f(c,v)int*v;{for(r=0;o=1;++r){for(i=c;i--;(i&1?b:a)[i/2]=v[i])o=(v[i]>v[i-1]|!i)&o;if(o)return r;for(i+=o=c+1;i--;)v[i]=i<o/2?a[i]:b[i-o/2];}}

Try it online

a[999],b[999],i,r,o; //pre-declare variables
f(c,v)int*v;{ //argument list
    for(r=0;o=1;++r){ //major loop, reset o (ordered) to true at beginning, increment number of shuffles at end
        for(i=c;i--;(i&1?b:a)[i/2]=v[i]) //loop through v, split into halves a/b as we go
            o=(v[i]>v[i-1]|!i)&o; //if out of order set o (ordered) to false
        if(o) //if ordered
            return r; //return number of shuffles
        //note that i==-1 at this point
        for(i+=o=c+1;i--;)//set i=c and o=c+1, loop through v
            v[i]=i<o/2?a[i]:b[i-o/2];//set first half of v to a, second half to b
    }
}
rtpax
sumber
2

R, 85 bytes

s=scan();u=sort(s);k=0;while(any(u[seq(s)]!=s)){k=k+1;u=as.vector(t(matrix(u,,2)))};k

Try it online.

Explanation

Stupid (brute force) method, much less elegant than following the card #2.

Instead of unshuffling the input s we start with a sorted vector u that we progressively shuffle until it is identical with s. This gives warnings (but shuffle counts are still correct) for odd lengths of input due to folding an odd-length vector into a 2-column matrix; in that case, in R, missing data point is filled by recycling of the first element of input.

The loop will never terminate if we provide a vector that cannot be unshuffled.

Addendum: you save one byte if unshuffling instead. Unlike the answer above, there is no need to transpose with t(), however, ordering is byrow=TRUE which is why T appears in matrix().

R, 84 bytes

s=scan();u=sort(s);k=0;while(any(s[seq(u)]!=u)){k=k+1;s=as.vector(matrix(s,,2,T))};k

Try it online!

Volare
sumber
I took the liberty of fixing your title and adding a TIO-link for the test cases (based on the other R answer), and also verified your answer works as intended, so +1 from me and welcome to PPCG! :)
Kevin Cruijssen
2

PowerShell, 116 114 108 84 78 bytes

-24 bytes thanks to Erik the Outgolfer's solution.

-6 bytes thanks to mazzy.

param($a)for(;$a[1]-2){$n++;$t=@{};$a|%{$t[$j++%2]+=,$_};$a=$t.0+$t.1;$j=0}+$n

Try it online!

Andrei Odegov
sumber
you can save a bit more: Try it online!
mazzy
@muzzy, you're right again :) thanks
Andrei Odegov
1

Red, 87 79 78 bytes

func[b][c: 0 while[b/2 > 2][c: c + 1 b: append extract b 2 extract next b 2]c]

Try it online!

Galen Ivanov
sumber
1

Perl 5 -pa, 77 bytes

map{push@{$_%2},$_}0..$#F;$_=0;++$_,@s=sort{$a-$b}@F=@F[@0,@1]while"@F"ne"@s"

Try it online!

Xcali
sumber
1

Pyth, 18 bytes

L?SIb0hys%L2>Bb1
y

Try it online!

-2 thanks to @Erik the Outgolfer.

The script has two line: the first one defines a function y, the second line calls y with the implicit Q (evaluated stdin) argument.

L?SIb0hys%L2>Bb1
L                function y(b)
 ?               if...
  SIb            the Invariant b == sort(b) holds
     0           return 0
      h          otherwise increment...
       y         ...the return of a recursive call with:
             B   the current argument "bifurcated", an array of:
              b   - the original argument
            >  1  - same with the head popped off
          L      map...
         % 2     ...take only every 2nd value in each array
        s         and concat them back together

¹

Ven
sumber
1

PowerShell, 62 71 70 66 bytes

+9 bytes when Test cases with an even number of elements added.

-1 byte with splatting.

-4 bytes: wrap the expression with $i,$j to a new scope.

for($a=$args;$a[1]-2;$a=&{($a|?{++$j%2})+($a|?{$i++%2})}){$n++}+$n

Try it online!

mazzy
sumber
1

Japt, 13 11 10 bytes

Taking my shiny, new, very-work-in-progress interpreter for a test drive.

ÅÎÍ©ÒßUñÏu

Try it or run all test cases

ÅÎÍ©ÒßUñÏu     :Implicit input of integer array U
Å              :Slice the first element off U
 Î             :Get the first element
  Í            :Subtract from 2
   ©           :Logical AND with
    Ò          :  Negation of bitwise NOT of
     ß         :  A recursive call to the programme with input
      Uñ       :    U sorted
        Ï      :    By 0-based indices
         u     :    Modulo 2
Shaggy
sumber
1
This interpreter looks super cool.
recursive
0

Python 3, 40 bytes

f=lambda x:x[1]-2and 1+f(x[::2]+x[1::2])  # 1-based
f=lambda x:x[1]-1and 1+f(x[::2]+x[1::2])  # 0-based

Try it online!

I need to refresh the page more frequently: missed Erik the Outgolfer's edit doing a similar trick =)

Alex
sumber