Можете ли вы опередить Билла Гейтса?

13

Сортировка блинов - разговорный термин для математической задачи сортировки неупорядоченной стопки блинов в порядке их размера, когда шпатель можно вставить в любую точку стопки и использовать для переворачивания всех блинов над ней. Число блинов P (n) - это минимальное количество бросков, необходимое для n блинов. 1

В 1979 году молодой Билл Гейтс и Христос Пападимитриу написали статью, доказывающую верхнюю границу P (n) = (5n + 5) / 3 . 2

Я думаю, можно с уверенностью предположить, что Гейтс (и / или Пападимитриу) написал программу для сортировки блинов с использованием разработанного ими алгоритма (возможно, позже, чем в 1979 году). Поскольку Гейтс был опытным программистом, они, вероятно, пытались играть в этот код так хорошо, как могли, но размер исходного кода не является общедоступным (AFAIK).

Вызов:

Создайте функцию / программу, которая выполняет сортировку блинов, где максимальное количество бросков не превышает границы, найденной Гейтсом и Пападимитриу. 3 Вы можете выбрать, хотите ли вы, чтобы список рос по возрастанию или по убыванию, если он соответствует.

Вы можете предположить, что n <50 . Поэтому вы должны ограничить количество сальто (некоторыми случайно выбранными n-значениями ):

 n   P(n)
38   65
49   83
50   85

Выходными данными должно быть положение шпателя перед каждым щелчком. Выходные данные могут быть нулевыми или индексированными, и вы можете выбрать, будете ли вы считать сверху или снизу.

Дополнительные правила:

  • Время выполнения должно быть детерминированным
  • Не существует фиксированного ограничения по времени, но вы должны быть в состоянии предоставить вывод для списка из 50 элементов

Тестовые списки:

Я не могу предоставить самые сложные списки (если да, я бы написал статью, а не вызов), поэтому я приведу несколько случайных списков чисел, на которых вы можете проверить свои функции / программы. Я мог бы добавить других, если окажется, что эти списки «легки».

9, 63, 62, 75, 45, 78, 59, 75, 69, 3, 28, 94, 51, 10, 45, 93, 97, 80, 72, 36, 80, 88, 30, 93, 84, 80, 17, 31, 6, 80, 76, 91, 9, 76, 38, 33, 22, 15, 45, 46, 15, 98, 2, 56, 90, 27, 27, 26, 69, 25
...
74, 89, 57, 52, 70, 96, 16, 5, 77, 84, 54, 13, 90, 64, 31, 80, 3, 25, 13, 19, 13, 34, 1, 79, 35, 43, 4, 19, 82, 29, 48, 95, 97, 28, 45, 62, 64, 82, 70, 34, 38, 15, 51, 83, 21, 66, 4, 42, 74, 84
...
62, 73, 7, 90, 83, 18, 12, 35, 72, 71, 99, 67, 87, 62, 65, 70, 14, 72, 55, 92, 87, 3, 7, 4, 4, 95, 49, 25, 4, 18, 49, 39, 26, 1, 45, 64, 23, 66, 39, 17, 33, 24, 58, 72, 77, 46, 99, 71, 10, 21

Надеемся, что Билл Гейтс и Пападимитриу увидят эту проблему и предоставят их код, чтобы мы могли определить, действительно ли вы их превзошли.

3 Лучшие верхние границы были найдены, но вам не нужно заботиться о них.

code-golf number sorting optimization stack Стьюи Гриффин
источник
Связанный , но не дубликат. Здесь ответы не сработают.
Стьюи Гриффин
В то время я использовал BFS в своем решении, и он все еще должен работать (с небольшим обновлением), чтобы найти решение с минимальным количеством сальто.
миль
@miles тогда не стесняйтесь отправлять это. Я не подробно рассмотрел все ответы, но большинство из них просто использовали наивный подход.
Стьюи Гриффин

Ответы:

4

Python 2 (PyPy) , 238 235 222 байта

a=input();n=len(a);r=range(n);a=zip(a,r);a=map(sorted(a).index,a)+[n]
def s(u,m):
 if m<1:return[0]
 for k in r:
  v=u[k::-1]+u[k+1:]
  if sum(1<abs(v[i]-v[i+1])for i in r)<m:
   p=s(v,m-1)
   if p:return[k]+p
print s(a,5*n/3)

* (2 пробела = табуляция)

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

Сохранено 13 байтов, заимствуя метод ранжирования списка .

DFS с простой эвристикой, которая проверяет, разделяет ли флип пару «блинов», которые были бы смежными при сортировке. Сортирует по возрастанию. Вывод 0 индексируется слева, где 0 переворачивает первые 2 и так далее. Количество использованных ходов - это (5/3)*n+1 < 5/3*(n+1)где (18/11)*n < (5/3)*n+1 < 5/3*(n+1)и (18/11)*nболее жесткая верхняя граница, найденная в 2009 году .

миль
источник