Эта проблема связана с Flipping Pancakes .
Возможно, вы слышали о сортировке блинов , когда стопка блинов сортируется по размеру, вставляя шпатель в стопку и переворачивая все блины над лопаточкой, пока блины не будут отсортированы наименьшим по величине на тарелке. Проблема сгоревшего блина немного другая. У всех блинов теперь есть одна сожженная сторона, и сожженная сторона каждого блина должна быть обращена к тарелке после завершения сортировки.
Например, с учетом следующего стека (размер блина слева. 0
Означает сгоревшую сторону внизу и 1
означает сгоревшую сторону справа):
1 0
3 1
2 1
Вы можете перевернуть всю стопку, чтобы получить 20 30 11
, перевернуть две верхние, чтобы получить, 31 21 11
и перевернуть всю стопку, чтобы получить 10 20 30
сортированную стопку сожженных блинов. Эта последовательность ходов, flip 3, flip 2, flip 3, может быть представлена как 3 2 3
.
Соревнование
- Учитывая массив размеров блинов (не обязательно уникальных) и их ориентации, выведите любую действительную последовательность сортировки сожженных блинов, то есть последовательность переворотов, которая приводит к сортировке стопки блинов от наименьшего к наибольшему с обожженными сторонами вниз.
- Ввод и вывод может быть любым нормальным форматом с разделителями, но, пожалуйста, укажите, какие форматы вы используете, и укажите, какой конец вашего формата ввода является вершиной стека (TOS).
- Блин с нуля допускается.
- Смешивание разделителей на входе / выходе разрешено.
Контрольные примеры
Для всех следующих тестовых случаев input представляет собой список, а output - разделенную пробелами строку, а TOS находится слева.
[[1, 0], [3, 1], [2, 1]]
"3 2 3"
[[5, 1], [3, 0], [4, 1], [2, 1], [1, 0]]
"5 3 4 1 3 2 1"
[[5, 1], [3, 0], [3, 0], [1, 1]]
"4 3 2 3"
Как всегда, если что-то неясно или неправильно, пожалуйста, дайте мне знать в комментариях. Удачи и хорошего гольфа!
0
Разрешено ли в списке вывода?CJam (37 байт)
Ввод - это массив в формате CJam на stdin; output - это разделенный новой строкой список длин флипов на stdout. Вершина стека находится в индексе
0
;0
указывает на обожженную сторону вверх и1
указывает на обожженную сторону вниз.Онлайн демо
рассечение
Выход всегда
3n
переворачивается, гдеn
количество блинов. Сначала мы переворачиваем самый большой оставшийся блин наверх; затем, если он сгорел стороной вниз, мы переворачиваем один блин; и затем мы переворачиваем это на дно и повторяем, как будто стопка блинов была на одну короче.источник
Рубин,
1019593 байтаНе очень в гольфе, я просто хотел сделать бого-вариант. Это анонимная функция, которая принимает массив массивов и печатает случайные сальто в стандартный вывод до сортировки блинов.
Вы можете, например, назначить его
f
и сказатьf.call [[1, 0], [3, 1], [2, 1]]
-5 байтов от @Jordan с блестящим использованием
rassoc
-2 байтов от @ Sherlock9
источник
a.all?{...}
на!a.rassoc(1)
.r
)assoc
раньше, но, подумав об этом, это, вероятно, полезно при большом количестве проблем на этом сайте - я чувствую, что это должно быть в посте с советами по игре в гольф на Ruby. В любом случае, спасибо :) Я также смог убить еще один байт, хотя применение закона deMorgans и заменитьuntil
наwhile
.b
как только когда-либо0
или1
,1-b
также будет работать и сохранит два байта.