Вызов:

Входные данные: список различных положительных целых чисел в диапазоне $[1, \text{list-size}]$ .

Вывод: целое число: количество раз, когда список перемешивается . Для получения списка, это означает , что список делится на две половины, и эти половины чередуются (т.е. желобок-перетасовки списка [1,2,3,4,5,6,7,8,9,10]раз приведет [1,6,2,7,3,8,4,9,5,10], так что для этой задачи вход [1,6,2,7,3,8,4,9,5,10]приведет 1).

Правила соревнований:

• Вы можете предположить, что список будет содержать только положительные целые числа в диапазоне (или если вы решите иметь 0-индексированные входные списки ).$[1, \text{list-size}]$$[0, \text{list-size}-1]$
• Вы можете предположить, что все входные списки будут либо действительным списком с перемешиванием, либо отсортированным списком, который не перемешивается (в этом случае вывод 0).
• Можно предположить, что входной список будет содержать как минимум три значения.

Пошаговый пример:

Входные данные: [1,3,5,7,9,2,4,6,8]

Разбрасывание это однажды становится:, [1,5,9,4,8,3,7,2,6]потому что каждый четный 0-индексированный элемент идет первым [1, ,5, ,9, ,4, ,8], а затем все нечетные 0-индексированные элементы после этого [ ,3, ,7, ,2, ,6, ].
Список еще не упорядочен, поэтому мы продолжаем:

Перестановка списка снова становится: [1,9,8,7,6,5,4,3,2]
Снова становится: [1,8,6,4,2,9,7,5,3]
Тогда: [1,6,2,7,3,8,4,9,5]
И наконец:, [1,2,3,4,5,6,7,8,9]который является упорядоченным списком, так что мы закончили перестановку.

Мы перетасовали оригинал [1,3,5,7,9,2,4,6,8]пять раз, чтобы добраться до [1,2,3,4,5,6,7,8,9], так что вывод 5в этом случае.

Основные правила:

• Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.
  Не позволяйте языкам кода-гольфа отговаривать вас от публикации ответов на языках, не относящихся к кодексу. Попробуйте придумать как можно более короткий ответ для «любого» языка программирования.
• Стандартные правила применяются к вашему ответу с правилами ввода / вывода по умолчанию , поэтому вы можете использовать STDIN / STDOUT, функции / метод с правильными параметрами и типом возврата, полные программы. Ваш звонок.
• По умолчанию лазейки запрещены.
• Если возможно, добавьте ссылку с тестом для вашего кода (например, TIO ).
• Кроме того, добавление объяснения для вашего ответа настоятельно рекомендуется.

Тестовые случаи:

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

Желе , 8 байт

ŒœẎ$ƬiṢ’

Попробуйте онлайн!

Как?

ŒœẎ$Ƭ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 байта

Более короткая версия, предложенная @nwellnhof

Ожидается колода с 1-проиндексированными картами в качестве входных данных.

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

Попробуйте онлайн!

Для данной колоды $[c_0,\ldots,c_{L-1}]$ длины $L$ мы определяем:

И мы ищем $n$ такой, что $c_{x_n}=2$ .

JavaScript (ES6),  57 52  50 байт

Ожидается колода с 0-индексированными картами в качестве входных данных.

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

Попробуйте онлайн!

Как?

Поскольку в JS отсутствует встроенная поддержка извлечения фрагментов массива с помощью пользовательского пошагового выполнения, имитация всего перемешивания может быть довольно дорогостоящей (но, честно говоря, я даже не пробовал). Однако решение также можно найти, просто взглянув на 2-ю карту и общее количество карт в колоде.

Учитывая колоду длиной $L$ , этот код выглядит для $n$ такие , что:

где $c_2$ - вторая карта, а $k$ определяется как:

Python 2 , 39 байт

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

Попробуйте онлайн!

-4 спасибо Джонатану Аллану .

R , 58 55 45 байт

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

Попробуйте онлайн!

Имитирует процесс сортировки. Ввод 1 индексируется, возвращается FALSE0.

Perl 6 , 34 32 байта

-2 байта благодаря Джо Кингу

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

Попробуйте онлайн!

Похож на подход Арно . Индекс второй карты после n перемешиваний - 2**n % kс k, определенным как в ответе Арно.

APL (Dyalog Unicode) , 35 26 23 22 байта ^SBCS

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

Попробуйте онлайн!

Спасибо Adám за помощь, Эрик Outgolfer за -3 и ngn за -1.

Ссылка TIO содержит два теста.

Объяснение:

{⍵≡⍳≢⍵: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 байта

-2 байта благодаря nwellnhof

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

Попробуйте онлайн!

Обратный риффл тасует путем сортировки по индексу по модулю 2, пока список не будет отсортирован, а затем возвращает длину последовательности.

Забавно, я обычно не пробую рекурсивный подход к Perl 6, но на этот раз он оказался короче оригинала.

Объяснение:

$!={.[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 байтов

[DāQ#ι˜]N

Попробуйте онлайн!

объяснение

[   #  ]     # 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 байт

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

Попробуйте онлайн!

Надежно работает только для массивов с размером менее 31 или решений с менее чем 31 итерацией. Для более общего решения см. Следующее решение с 63 байтами:

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

Попробуйте онлайн!

объяснение

В риффе следующая позиция - это предыдущая единица, умноженная на два, либо по длине, если она нечетная, либо по длине - 1, если она четная.

Поэтому я перебираю все индексы, используя эту формулу, пока не найду значение 2 в массиве.

кредиты

• -8 байт благодаря Кевину Круйссену . (Предыдущий алгоритм с использованием массива)
• -5 байт благодаря Арно .

J , 28 26 байт

-2 байта благодаря Ионе!

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

Попробуйте онлайн!

Вдохновлен решением AP AP от Ven.

Объяснение:

               ^:       ^: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)     

К (нгн / к) , 25 байтов

Спасибо ngn за совет и за его переводчик K!

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

Попробуйте онлайн!

APL (NARS), символы 49, байты 98

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

зачем использовать в самом глубоком цикле один алгоритм, который должен быть nlog (n), когда мы можем использовать один линейный n? только на несколько байт больше? [⍵≡⍵ [⍋⍵] O (nlog n) и сопоставление каждого элемента для просмотра в порядке, используя тест ∧ / ¯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

Рубин , 42 байта

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

Попробуйте онлайн!

Как:

Найдите номер 2 внутри массива: если он находится на второй позиции, колода не была перетасована, в противном случае проверьте позиции, в которые ее поместили бы последующие тасовки.

р , 70 72 байта

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

Попробуйте онлайн!

Теперь обрабатывает случай нулевого шаффла.

C (GCC) 64 63 байта

-1 байт от nwellnhof

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

Это значительно более короткий ответ, основанный на ответах Арно и Оливье Грегуара. Я оставлю свое старое решение ниже, так как оно решает немного более общую проблему колод с картами, которые не являются смежными.

Попробуйте онлайн

C (GCC) 162 байта

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

Попробуйте онлайн

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 байт

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

Попробуйте онлайн.

объяснение

Глупый (грубая сила) метод, гораздо менее элегантный, чем следование карточке №2.

Вместо того, чтобы переставлять ввод, sмы начинаем с отсортированного вектора, uкоторый мы постепенно перемешиваем, пока он не будет идентиченs . Это дает предупреждения (но количество случайных чисел все еще корректно) для нечетных длин ввода из-за складывания вектора нечетной длины в матрицу из 2 столбцов; в этом случае в R пропущенная точка данных заполняется повторным использованием первого элемента ввода.

Цикл никогда не завершится, если мы предоставим вектор, который не может быть перемешан.

Приложение: вы сохраняете один байт, если не переставляете. В отличие от ответа выше, нет необходимости перемещать с t(), однако, упорядочение - byrow=TRUEвот почему Tпоявляется в matrix().

R , 84 байта

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

Попробуйте онлайн!

PowerShell , 116 114 108 84 78 байт

-24 байта благодаря Эрик Outgolfer «s решение .

-6 байт благодаря маззи .

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

Попробуйте онлайн!

Wolfram Language (Mathematica) , 62 байта

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

Попробуйте онлайн!

объяснение

Список ввода есть a. Он не разбирается и сравнивается с отсортированным списком, пока не совпадет.

Красный , 87 79 78 байт

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

Попробуйте онлайн!

Perl 5 -pa , 77 байт

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

Попробуйте онлайн!

Pyth , 18 байт

L?SIb0hys%L2>Bb1
y

Попробуйте онлайн!

-2 благодаря @ Эрику Аутгольферу.

Сценарий имеет две строки: первая определяет функцию y, вторая вызывается yс неявным Q(оцененным stdin) аргументом.

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 байт

+9 байт при тестировании с добавлением четного числа элементов.

-1 байт с брызгами.

-4 байта: перенести выражение с $i, $jв новую область.

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

Попробуйте онлайн!

Japt , 13 11 10 байт

Взяв моего блестящего, нового , очень работающего переводчика для тест-драйва.

ÅÎÍ©ÒßUñÏu

Попробуйте или запустите все тесты

ÅÎÍ©Òß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 байт

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

Попробуйте онлайн!

Мне нужно обновлять страницу чаще: пропустил редактирование Эрика Outgolfer, делающего подобный трюк =)