Wyzwanie:
Dane wejściowe: lista różnych dodatnich liczb całkowitych z zakresu .
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 ).
- 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 5
w 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
źródło
[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.[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.Odpowiedzi:
Galaretka , 8 bajtów
Wypróbuj online!
W jaki sposób?
źródło
JavaScript (ES6), 44 bajty
Krótsza wersja sugerowana przez @nwellnhof
Oczekuje talii z kartami o indeksie 1 jako wejście.
Wypróbuj online!
Biorąc pod uwagę pokład[c0,…,cL−1] o długości L , definiujemy:
I szukamyn takich, że doxn= 2 .
JavaScript (ES6),
57 5250 bajtówOczekuje talii z kartami z indeksowaniem 0 jako wejściem.
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ściL. , ten kod szuka n takich, że:
gdziedo2) jest drugą kartą, a k jest zdefiniowane jako:
źródło
Python 2 , 39 bajtów
Wypróbuj online!
-4 dzięki Jonathanowi Allanowi .
źródło
f=lambda x:2!=x[1]and-~f(x[::2]+x[1::2])
!=
może być-
. ;-)x[1]>2
tak sądzę)R ,
585545 bajtówWypróbuj online!
Symuluje proces sortowania. Dane wejściowe są indeksowane 1, zwraca
FALSE
0.źródło
Perl 6 ,
3432 bajty-2 bajty dzięki Jo King
Wypróbuj online!
Podobne do podejścia Arnaulda . Indeks drugiej karty po n przetasowaniach ma wartość
2**n % k
k zdefiniowaną jak w odpowiedzi Arnaulda.źródło
APL (Dyalog Unicode) ,
35262322 bajtów SBCSWypró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:
¹
źródło
∧/2≤/⍵
->⍵≡⍳≢⍵
Perl 6,
36 3432 bytes-2 bajty dzięki nwellnhof
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:
źródło
05AB1E (legacy), 9 bytes
Try it online!
Explanation
źródło
Å≠
that inspired this challenge. :)Java (JDK) , 59 bajtów
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:
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
źródło
x.clone()
instead ofA.copyOf(x,l)
.J ,
2826 bajtów-2 bajty dzięki Jonaszowi!
Wypróbuj online!
Zainspiruj się rozwiązaniem APL firmy Ven.
Wyjaśnienie:
K (ngn / k) , 25 bajtów
Dzięki ngn za radę i jego tłumacza K.
Wypróbuj online!
źródło
1#@}.(\:2|#\)^:(2<1{])^:a:
na 26 bajtówAPL (NARS), znaki 49, bajty 98
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)]:
źródło
Rubin , 42 bajty
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ódło
R ,
7072 bajtówWypróbuj online!
Teraz obsługuje przypadek zerowania losowego.
źródło
C (GCC)
6463 bajty-1 bajt z nwellnhof
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
Wypróbuj online
źródło
R, 85 bajtów
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 wektorau
, który stopniowo tasujemy, aż będzie identycznys
. 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 jestbyrow=TRUE
, dlategoT
pojawia się wmatrix()
.R , 84 bajtów
Wypróbuj online!
źródło
PowerShell ,
116 114 108 8478 bajtów-24 bajty dzięki Outgolfer Erik „s rozwiązania .
-6 bajtów dzięki mazzy .
Wypróbuj online!
źródło
Wolfram Language (Mathematica) , 62 bajty
Wypróbuj online!
Wyjaśnienie
Lista wejściowa to
a
. Jest niezafałszowany i porównywany z posortowaną listą, dopóki się nie dopasuje.źródło
Czerwony ,
877978 bajtówWypróbuj online!
źródło
Perl 5
-pa
, 77 bajtówWypróbuj online!
źródło
Pyth , 18 bajtów
Wypróbuj online!
-2 dzięki @Erik the Outgolfer.
Skrypt ma dwie linie: pierwsza definiuje funkcję
y
, druga linia wywołujey
z niejawnymQ
(ocenionym standardowym) argumentem.¹
źródło
PowerShell ,
62717066 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
,$j
do nowego zakresu.Wypróbuj online!
źródło
Japt ,
131110 bajtówBiorąc mój błyszczący, nowy
, bardzo pracującyinterpreter na jazdę próbną.Wypróbuj lub uruchom wszystkie przypadki testowe
źródło
Python 3, 40 bajtów
Wypróbuj online!
Muszę częściej odświeżać stronę: przegapiłem edycję Outgolfera Erika, wykonując podobną sztuczkę =)
źródło