Wyzwanie:

Dane wejściowe: lista różnych dodatnich liczb całkowitych z zakresu .$[1, \text{list-size}]$

Dane wyjściowe: liczba całkowita: liczba potasowań listy . W przypadku listy oznacza to, że lista jest podzielona na dwie połowy, a te połówki są przeplatane (tj. Jednorazowe przetasowanie listy [1,2,3,4,5,6,7,8,9,10]raz [1,6,2,7,3,8,4,9,5,10], więc w przypadku tego wyzwania dane wejściowe [1,6,2,7,3,8,4,9,5,10]byłyby wynikiem 1).

Zasady konkursu:

• Możesz założyć, że lista będzie zawierała dodatnie liczby całkowite z zakresu (lub jeśli wybierzesz opcję 0-indeksowanych list wejściowych ).$[1, \text{list-size}]$$[0, \text{list-size}-1]$
• Możesz założyć, że wszystkie listy wejściowe będą albo prawidłową listą wymieszaną z karabinem, albo listą posortowaną, która nie jest tasowana (w takim przypadku dane wyjściowe są 0).
• Możesz założyć, że lista wejściowa będzie zawierać co najmniej trzy wartości.

Przykład krok po kroku:

Wkład: [1,3,5,7,9,2,4,6,8]

Odznaczanie go raz staje się: [1,5,9,4,8,3,7,2,6]ponieważ każdy parzysty element o indeksie 0 jest pierwszy [1, ,5, ,9, ,4, ,8], a następnie wszystkie nieparzyste elementy o indeksie 0 potem [ ,3, ,7, ,2, ,6, ].
Lista nie jest jeszcze uporządkowana, dlatego kontynuujemy:

Ponowne przetasowanie listy staje się ponownie: [1,9,8,7,6,5,4,3,2]
Ponownie staje się: [1,8,6,4,2,9,7,5,3]
Następnie: [1,6,2,7,3,8,4,9,5]
I w końcu [1,2,3,4,5,6,7,8,9]:, która jest uporządkowaną listą, więc skończymy tasowanie.

[1,3,5,7,9,2,4,6,8]Pięć razy przetasowaliśmy oryginał, aby do niego dotrzeć [1,2,3,4,5,6,7,8,9], więc 5w tym przypadku wynik jest taki.

Główne zasady:

• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
  Nie pozwól, aby języki gry w golfa zniechęcały Cię do publikowania odpowiedzi w językach niekodujących golfa. Spróbuj znaleźć możliwie najkrótszą odpowiedź na „dowolny” język programowania.
• Do odpowiedzi mają zastosowanie standardowe reguły z domyślnymi regułami We / Wy , więc możesz używać STDIN / STDOUT, funkcji / metody z odpowiednimi parametrami i typem zwracanych, pełnych programów. Twoja decyzja.
• Domyślne luki są zabronione.
• Jeśli to możliwe, dodaj link z testem kodu (tj. TIO ).
• Zalecane jest również dodanie wyjaśnienia do odpowiedzi.

Przypadki testowe:

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

Galaretka , 8 bajtów

ŒœẎ$ƬiṢ’

Wypróbuj online!

W jaki sposób?

ŒœẎ$Ƭ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

JavaScript (ES6), 44 bajty

Krótsza wersja sugerowana przez @nwellnhof

Oczekuje talii z kartami o indeksie 1 jako wejście.

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

Wypróbuj online!

Biorąc pod uwagę pokład $[c_0,\ldots,c_{L-1}]$ o długości $L$ , definiujemy:

I szukamy $n$ takich, że $c_{x_n}=2$ .

JavaScript (ES6),  57 52  50 bajtów

Oczekuje talii z kartami z indeksowaniem 0 jako wejściem.

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

Wypróbuj online!

W jaki sposób?

Ponieważ JS nie ma natywnej obsługi wyodrębniania wycinków tablicy z niestandardowym krokiem, symulacja całego ruffle-shuffle byłaby prawdopodobnie dość kosztowna (ale szczerze mówiąc, nawet nie próbowałem). Rozwiązanie można jednak znaleźć, patrząc tylko na drugą kartę i całkowitą liczbę kart w talii.

Biorąc pod uwagę pokład o długości $L$ , ten kod szuka $n$ takich, że:

gdzie $c_2$ jest drugą kartą, a $k$ jest zdefiniowane jako:

Python 2 , 39 bajtów

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

Wypróbuj online!

-4 dzięki Jonathanowi Allanowi .

R , 58 55 45 bajtów

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

Wypróbuj online!

Symuluje proces sortowania. Dane wejściowe są indeksowane 1, zwraca FALSE0.

Perl 6 , 34 32 bajty

-2 bajty dzięki Jo King

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

Wypróbuj online!

Podobne do podejścia Arnaulda . Indeks drugiej karty po n przetasowaniach ma wartość 2**n % kk zdefiniowaną jak w odpowiedzi Arnaulda.

APL (Dyalog Unicode) , 35 26 23 22 bajtów ^SBCS

{⍵≡⍳≢⍵:0⋄1+∇⍵[⍒2|⍳⍴⍵]}

Wypróbuj online!

Dzięki Adámowi za pomoc Erik the Outgolfer za -3 i ngn za -1.

Łącze TIO zawiera dwa przypadki testowe.

Wyjaśnienie:

{⍵≡⍳≢⍵:0⋄1+∇⍵[⍒2|⍳⍴⍵]}
{⍵≡⍳≢⍵:0⋄1+∇⍵[⍒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.

¹

Perl 6, 36 34 32 bytes

-2 bajty dzięki 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.

Wyjaśnienie:

$!={.[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

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

Java (JDK) , 59 bajtów

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

Wypróbuj online!

Działa niezawodnie tylko w przypadku tablic o rozmiarze mniejszym niż 31 lub rozwiązań z mniej niż 31 iteracjami. Aby uzyskać bardziej ogólne rozwiązanie, zobacz następujące rozwiązanie z 63 bajtami:

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

Wypróbuj online!

Wyjaśnienie

W riffle następną pozycją jest poprzedni raz dwa razy moduł albo długość, jeśli jest nieparzysta, albo długość - 1, jeśli jest parzysta.

I tak iteruję wszystkie indeksy za pomocą tej formuły, dopóki nie znajdę wartości 2 w tablicy.

Kredyty

• -8 bajtów dzięki Kevin Cruijssen . (Poprzedni algorytm przy użyciu tablicy)
• -5 bytes thanks to Arnauld.

J , 28 26 bajtów

-2 bajty dzięki Jonaszowi!

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

Wypróbuj online!

Zainspiruj się rozwiązaniem APL firmy Ven.

Wyjaśnienie:

               ^:       ^: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 bajtów

Dzięki ngn za radę i jego tłumacza K.

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

Wypróbuj online!

APL (NARS), znaki 49, bajty 98

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

po co używać w najgłębszej pętli jednego algo, który powinien być nlog (n), skoro możemy użyć jednego liniowego n? tylko o kilka bajtów więcej? [⍵≡⍵ [⍋⍵] O (nlog n) i konfrontacja każdego elementu dla zobacz są w kolejności przy użyciu testu ∧ / ¯1 ↓ ⍵≤1⌽⍵ O (n)]:

  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

Rubin , 42 bajty

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

Wypróbuj online!

W jaki sposób:

Wyszukaj numer 2 w tablicy: jeśli jest na drugiej pozycji, talia nie została przetasowana, w przeciwnym razie sprawdź pozycje, w których byłyby umieszczane kolejne losowania.

R , 70 72 bajtów

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

Wypróbuj online!

Teraz obsługuje przypadek zerowania losowego.

C (GCC) 64 63 bajty

-1 bajt z nwellnhof

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

To drastycznie krótsza odpowiedź oparta na odpowiedziach Arnaulda i Oliviera Grégoire'a. Zostawię moje stare rozwiązanie poniżej, ponieważ rozwiązuje nieco bardziej ogólny problem talii z kartami, które nie są ciągłe.

Wypróbuj online

C (GCC) 162 bajty

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];}}

Wypróbuj 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
    }
}

R, 85 bajtów

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

Wypróbuj online.

Wyjaśnienie

Głupia metoda (brutalna siła), znacznie mniej elegancka niż podążanie za kartą nr 2.

Zamiast odtasowywać dane wejściowe s, zaczynamy od posortowanego wektora u, który stopniowo tasujemy, aż będzie identyczny s. Daje to ostrzeżenia (ale liczby losowe są nadal poprawne) dla nieparzystych długości danych wejściowych ze względu na złożenie wektora o nieparzystej długości do macierzy 2-kolumnowej; w takim przypadku w punkcie R brakujący punkt danych jest wypełniany przez recykling pierwszego elementu danych wejściowych.

Pętla nigdy się nie zakończy, jeśli zapewnimy wektor, którego nie można przetasować.

Dodatek: zapisujesz jeden bajt, jeśli zamiast tego tasujesz. W przeciwieństwie do odpowiedzi powyżej, nie ma potrzeby, aby przenieść się t()jednak, zamawiania jest byrow=TRUE, dlatego Tpojawia się w matrix().

R , 84 bajtów

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

Wypróbuj online!

PowerShell , 116 114 108 84 78 bajtów

-24 bajty dzięki Outgolfer Erik „s rozwiązania .

-6 bajtów dzięki mazzy .

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

Wypróbuj online!

Wolfram Language (Mathematica) , 62 bajty

c=0;While[Sort[a]!=a,a=a[[1;;-1;;2]]~Join~a[[2;;-1;;2]];c++];c

Wypróbuj online!

Wyjaśnienie

Lista wejściowa to a. Jest niezafałszowany i porównywany z posortowaną listą, dopóki się nie dopasuje.

Czerwony , 87 79 78 bajtów

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

Wypróbuj online!

Perl 5 -pa , 77 bajtów

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

Wypróbuj online!

Pyth , 18 bajtów

L?SIb0hys%L2>Bb1
y

Wypróbuj online!

-2 dzięki @Erik the Outgolfer.

Skrypt ma dwie linie: pierwsza definiuje funkcję y, druga linia wywołuje yz niejawnym Q(ocenionym standardowym) argumentem.

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

¹

PowerShell , 62 71 70 66 bajtów

+9 bajtów, gdy testowane są przypadki z dodaną parzystą liczbą elementów.

-1 bajt z rozpryskiwaniem.

-4 bajtów: owinąć ekspresji z $i, $jdo nowego zakresu.

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

Wypróbuj online!

Japt , 13 11 10 bajtów

Biorąc mój błyszczący, nowy , bardzo pracujący interpreter na jazdę próbną.

ÅÎÍ©ÒßUñÏu

Wypróbuj lub uruchom wszystkie przypadki testowe

ÅÎÍ©Òß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

Python 3, 40 bajtów

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

Wypróbuj online!

Muszę częściej odświeżać stronę: przegapiłem edycję Outgolfera Erika, wykonując podobną sztuczkę =)