Czy możesz przestać tasować talię i już grać?

31

Wyzwanie:

Dane wejściowe: lista różnych dodatnich liczb całkowitych z zakresu .[1,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,list-size][0,list-size1]
  • 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 , 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
Kevin Cruijssen
źródło
Przydałby się jeden lub dwa przypadki testowe o nieparzystej długości i wyjściu większym niż 0. W takich przypadkach łatwo jest zepsuć riffle, jeśli musisz napisać kod riffle sam, zamiast polegać na wbudowanych funkcjach.
Olivier Grégoire
@ OlivierGrégoire The [1,3,5,7,9,2,4,6,8]ma długość 9, ale dodam jeszcze kilka dla długości 7 i 11. EDYCJA: Dodano przypadki testowe [1,3,5,7,2,4,6] = 2(długość 7) i [1,6,11,5,10,4,9,3,8,2,7] = 6(długość 11). Mam nadzieję, że to pomaga.
Kevin Cruijssen
Mój zły: byłem pewien, że wspomniany przypadek testowy ma rozmiar 8. Ale dziękuję za dodatkowe przypadki testowe.
Olivier Grégoire
1
Obecnie formułowane pytanie wydaje się „błędne” ... pojedyncze przetasowanie karabinów powinno skutkować zmianą pierwszej i ostatniej karty, chyba że wykonasz jakąś sztuczkę! tj. [6,1,7,2,8,3,3,4,4,10,5] po pojedynczym przetasowaniu 10 kart.
Steve
2
@ Steve Chyba masz rację. Generalnie tasowanie karabinów po prostu przeplata dwie połowy, więc obie [1,6,2,7,3,8,4,9,5,10]lub [6,1,7,2,8,3,9,4,10,5]są możliwe. W moim wyzwaniu oznacza to, że najwyższa karta zawsze pozostanie górną kartą, więc jest to naprawdę sztuczka. Nigdy nie widziałem, żeby ktoś używał tylko tasowania riffle do tasowania talii kart. Zwykle używają również innego rodzaju przetasowań pomiędzy nimi. W każdym razie jest już za późno na zmianę wyzwania, więc ze względu na to wyzwanie najlepsza karta zawsze pozostanie górną kartą po przetasowaniu.
Kevin Cruijssen

Odpowiedzi:

6

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
Jonathan Allan
źródło
25

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 [c0,,cL1] o długości L , definiujemy:

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

I szukamy n takich, że doxn=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:

do2)(k+12))n(modk)

gdzie do2) jest drugą kartą, a k jest zdefiniowane jako:

k={L.Jeśli L. to jest dziwneL.-1Jeśli L. jest parzysty

Arnauld
źródło
12

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 .

Erik the Outgolfer
źródło
Zaoszczędź cztery bajty zf=lambda x:2!=x[1]and-~f(x[::2]+x[1::2])
Jonathan Allan
@JonathanAllan Oh, oczywiście! Cóż ... !=może być -. ;-)
Erik the Outgolfer
Ach, tak, zastrzeżenie emptor: D (lub tylko x[1]>2tak sądzę)
Jonathan Allan
5

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.

Kirill L.
źródło
Bardzo dobrze! Pracowałem nad podobnym podejściem, ale korzystałem z funkcji rekurencyjnej, która nie działała jak gra w golfa.
user2390246
5

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.

nwellnhof
źródło
5

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

{⍵≡⍳≢⍵:01+∇⍵[⍒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:

{⍵≡⍳≢⍵: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
źródło
1
Policz głębokość rekurencji dla -3.
Erik the Outgolfer
@EriktheOutgolfer O wiele lepiej, dziękuję!
Ven
1
∧/2≤/⍵->⍵≡⍳≢⍵
ngn
@ngn nie zdawał sobie sprawy, że tablica nie ma dziur. Dzięki!
Ven
4

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
Jo King
źródło
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
źródło
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: Interesujące. Nie wiedziałem, że był tasowanie. W tym przypadku jest taka sama jak moja wersja, ale funkcja odtasowania zachowuje wymiary w tablicach 2D.
Emigna
3

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

Olivier Grégoire
źródło
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! Mój nowy algorytm jest w rzeczywistości taki sam jak twój ... I spędziłem pół godziny, zastanawiając się nad tym sam ...
Olivier Grégoire
Mówiąc dokładniej, jest to odpowiednik ulepszenia w stosunku do mojego oryginalnego algorytmu znalezionego przez @nwellnhof.
Arnauld
3

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!

Galen Iwanow
źródło
zbiegają-iteracji , następnie spadek jednego i zliczono - prowadzi to do skrócenia kodu
NGN
@ngn. Podobnie jak w moim rozwiązaniu J - spróbuję później, dzięki!
Galen Iwanow
1
1#@}.(\:2|#\)^:(2<1{])^:a:na 26 bajtów
Jonasz
@Jonah Dziękuję!
Galen Iwanow
2

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
RosLuP
źródło
Po raz pierwszy widziałem, jak ktoś odróżnia znaki od bajtów 👍. Zawsze mnie denerwuje, kiedy widzę znaki Unicode i twierdzą, że jest to jeden bajt na znak. To nie jest jeden bajt!
Kerndog73
@ Kerndog73 Wszystko jest liczbą, ale w APL znaki nie są liczbami ... (wydają się elementem tablicy AV)
RosLuP
2

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.

GB
źródło
2

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.

Nick Kennedy
źródło
1
@ user2390246 fair point. Dostosowano odpowiednio
Nick Kennedy
2

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
    }
}
rtpax
źródło
2

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!

Volare
źródło
Pozwoliłem sobie na poprawienie twojego tytułu i dodanie linku TIO do przypadków testowych (w oparciu o drugą odpowiedź R ), a także zweryfikowałem, że twoja odpowiedź działa zgodnie z przeznaczeniem, więc daj mi +1 i witaj w PPCG! :)
Kevin Cruijssen
1

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!

Galen Iwanow
źródło
1

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

¹

Ven
źródło
1

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!

mazzy
źródło
1

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
Kudłaty
źródło
1
Ten tłumacz wygląda super.
rekurencyjny
0

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ę =)

Alex
źródło