Для заданной строки длиной N знаков «меньше» и «больше чем» ( <
, >
) вставьте целые числа от 0 до N в начале и в конце каждой пары знаков так, чтобы все неравенства были выполнены. Выведите полученную строку. Если имеется несколько допустимых выходов, выведите любой (и только один) из них.
Например
<<><><<
имеет 7 символов, поэтому необходимо вставить все цифры от 0 до 7 включительно. Действительный вывод
2<3<4>1<5>0<6<7
потому что все неравенства приняты по одному
2<3
3<4
4>1
1<5
5>0
0<6
6<7
это правда.
При желании на выходе могут быть пробелы вокруг знаков, например 2 < 3 < 4 > 1 < 5 > 0 < 6 < 7
.
Самый короткий код в байтах побеждает.
Тестовые случаи
Первая строка после пустой строки - это входные данные, а каждая следующая строка - допустимые примеры вывода.
[empty string]
0
<
0<1
>
1>0
<<
0<1<2
<>
1<2>0
><
1>0<2
2>0<1
>>
2>1>0
<<<
0<1<2<3
><>
1>0<3>2
>><
3>2>0<1
3>1>0<2
2>1>0<3
>>>
3>2>1>0
>>><<<
3>2>1>0<4<5<6
6>3>1>0<2<4<5
4>2>1>0<3<5<6
4>3>1>0<2<5<6
<<><><<
2<3<4>1<5>0<6<7
>><><>>
7>6>0<5>1<4>3>2
<<<<<<<<<<<<<<
0<1<2<3<4<5<6<7<8<9<10<11<12<13<14
>><<<<><>><><<
6>5>4<7<8<9<10>3<11>2>1<12>0<13<14
14>5>4<7<8<9<10>3<11>2>1<12>0<13<6
code-golf
math
arithmetic
permutations
integer
Кальвин Хобби
источник
источник
Ответы:
Сетчатка , 20 байт
Число байтов предполагает кодировку ISO 8859-1.
Попробуйте онлайн! (Первая строка включает набор тестов, разделенных переводом строки.)
объяснение
Простой способ , чтобы найти действительную перестановку, чтобы начать путем вставки цифры от
0
доN
в порядке, а затем в обратном число , окружающее каждую подстроку>
с. Возьмите<><<>>><<
в качестве примера:Обе эти задачи довольно просты в Retina, хотя все, с чем мы действительно можем работать, это строки. Мы можем сохранить дополнительный байт, вставив числа
N
снизу0
и перевернув окружающие секции<
, но принцип тот же.Этап 1: Замена
Мы начинаем с вставки длины
$'
(суффикса, то есть всего после совпадения) в каждую возможную позицию на входе. Это вставит цифры отN
вниз до0
.Этап 2: Сплит
Мы разбиваем входные данные
>
на отдельные строки, поэтому каждая строка представляет собой либо отдельный номер, либо список чисел, с которыми соединяются<
.Этап 3: сортировка
Внутри каждой строки (
%
) мы сортируем (O
) числа (\d#
) по их числовому значению (#
). Так как мы вставили число в обратном числовом порядке, это переворачивает их.Этап 4: Замена
Мы
>
снова превращаем перевод строки, чтобы объединить все обратно в одну строку. Вот и все.В качестве примечания я хотел добавить способ применения
%
к другим разделителям, кроме перевода строки. Если бы я уже сделал это, это представление было бы 14 байтами, потому что тогда три последних этапа были бы сведены к одному:источник
> <> ,
464335 + 4 для-s=
= 39 байтЭто реализация алгоритма xnor в> <>.
Он принимает входную строку в стеке (
-s
флаг со стандартным интерпретатором).Вы можете попробовать это на онлайн-переводчике .
источник
> <> , 26 + 4 = 30 байт
Попробуйте онлайн! +4 байта для
-s=
флага - если-s
все в порядке (это будет означать, что флаг должен быть полностью удален для пустого ввода), тогда это будет +3 вместо этого.Предполагается, что вход STDIN является пустым, так что
i
выдает -1 (что он делает в EOF). Ошибка программы при попытке напечатать это -1 как символ.Использует максимальное количество подходов
>
, минимальное количество<
подходов.Программа, которая выходит чисто и не делает предположения о STDIN, составляет 4 дополнительных байта:
источник
CJam , 16 байтов
Попробуйте онлайн!
Порт моего Retina ответа .
объяснение
источник
Perl, 29 байт
Включает +2 для
-lp
Запустить с вводом на STDIN, например
Выход:
order.pl
:объяснение
Имейте два счетчика, максимум начинающийся с длины строки, минимум начинающийся с 0. Затем на каждой границе (включая начало и конец строки), если он находится непосредственно перед
<
положением минимума туда и увеличивайте на 1, в противном случае ставьте максимум там и уменьшайте на 1 (в конце строки не имеет значения, какой счетчик вы используете, так как они оба одинаковы)источник
s{}{/\G/...}
Я никогда не видел этого раньше, это блестяще.Python 2, 67 байт
Рекурсивная функция. Удовлетворяет каждого оператора по очереди, выставляя наименьшее неиспользованное значение
x
дляx<
и наибольшее дляx>
. Наименьшее неиспользуемое значение сохраняетсяi
и обновляется, а наибольшее неиспользуемое значение определяетсяi
по оставшейся длине.источник
(s>'=')
вместо того,(s>='>')
чтобы сохранить байт?<
и>
не является последовательной кодовой точкой.=
между<
и>
.Python 2,
163137 байтПеретасовывает числа до тех пор, пока утверждение не укажет
True
.Попробуй.
источник
APL, 33 байта
⍋⍋
необычайно полезен.объяснение
источник
⍋⍋
)?⍋
это оценка, которая возвращает признаки в отсортированном порядке. Сделав это дважды, вы получите,1
где было наименьшее число,2
где было следующее наименьшее число, ect.JavaScript (ES6),
7456 байтНачинается с набора чисел
0...N
. На каждом этапе просто берется наибольшее (l
) или наименьшее (j
) из оставшихся чисел; следующее число по определению должно быть меньше или больше этого. Редактировать: благодаря @Arnauld сэкономлено 18 байт.источник
replace
? Возможноs=>s.replace(/./g,c=>(c<'>'?j++:l--)+c,j=0,l=s.length)+j
replace
) до 74 байтов ...Pyth - 19 байт
Ура для сравнения цепочки!
Не работает онлайн потому что Eval безопасности.
источник
2sable , 20 байтов
объяснение
Попробуйте онлайн!
Для N <10 это могло быть 14 байтов:
источник
C #,
10299 байтUngolfed:
источник
r = r +
часть на составное назначение, сэкономив пару байтов?r+
часть с правой стороны сообщает компилятору, что все это строка, поэтому используется строковое представлениеc
. Если бы я использовалr+=
,?:
часть оценивалась бы как aint
, к нейc
добавлялось бы порядковое значение , и только тогда она была бы преобразована в ее строковое представление.Java 8,
126125 байтЯ не думаю, что это даже работает, хе-хе
Тестовая программа Ungolfed
источник
.replaceAll
чтобы.replace
и удалить скобки вокруг ,(c+"")
чтобы сохранить 5 байт.Желе ,
27 1412 байтПорт @Martin Enders CJam-решение
-2 байта благодаря @Dennis
Проверьте это в TryItOnline
Как?
Предыдущий метод был интересен математически, но не настолько, чтобы играть в гольф ...
При этом используется факторная базовая система, чтобы найти индекс перестановок [0, N], который будет удовлетворять уравнению.
источник
U
векторизация, так что вам не нужно€
.żJ0;
сохраняет еще один байт.Clojure,
152132126 байтСохранено значительное количество байтов за счет устранения как можно большего количества пробелов. Я понял, что пробел не нужен, чтобы отделить скобки от другого символа.
В основном порт Clojure ответа @ Scepheo. Работает одинаково.
Эти
recur
звонки убийцы!Я полагаю, я мог бы использовать атомы, чтобы очистить его.Этиswap!
вызовы , необходимые для использования атомов добавляются к графе: /Спасибо @amalloy за то, что сэкономили мне несколько байтов.
Ungolfed:
источник
loop
привязке, доs
и послеa
. Кроме того, можно бриться немного, заменивif
дерево сcase
:(case c \< (recur ...) nil (str ...) (recur ...))
. И, конечно,cr
может быть более коротким именем.Haskell, 162 байта
Это чертовски долго.
источник
Perl (107 + 1 для -p) 108
Алгоритм, украденный из ответа Мартина Эндера
источник
Рубин, 135 байт
Примечание: сложность по времени велика (O (n!)).
источник
Python 2,
176172 байтаОн не очень короткий по сравнению с другими, но я рад, что решил это так быстро.
Попробуйте онлайн
Ungolfed:
Попробуйте онлайн
источник
zip
pop
), но это немного короче. Если быN<10
я мог сделать стренификацию короче.PHP, 190 байт
случайный случайный выбор, пока не найдется правильное решение
381 байт получает все решения и выбирает одно
источник