Эластичная змея выглядит примерно так:
<||=|||:)~
Каждая отдельная последовательность вертикальных столбцов ( |
) в эластичной змеи, известная как эластичная часть , индивидуально расширяется вдвое по ширине и рисуется с помощью чередующихся косых черт ( /
, \
) после расширения.
У конкретной змеи выше есть две такие эластичные части, что дает ей четыре возможных позы:
<||=|||:)~
</\/\=|||:)~
<||=/\/\/\:)~
</\/\=/\/\/\:)~
Общая форма эластичной змеи в ее наименее растянутой позе определяется этим регулярным выражением :
<(\|+=)*\|+:\)~
Который можно выразить словами:
<
, За которым следует любое количество последовательностей|
«ы вступил с=
признаками, а затем:)~
.
Так <|:)~
и <||:)~
и <|=|:)~
и <|=|=||=|||||=||:)~
растягиваются змеями, но <=:)~
и <=|:)~
и <||=:)~
и <|==||:)~
не являются.
Эластичные змеи также могут быть направлены влево, а не вправо, например ~(:|||=||>
. Формы одинаковые, просто зеркальные.
Вызов
Напишите программу, которая принимает в одну строку строку из двух растягивающихся змей, обращенных друг к другу, с некоторым количеством пробелов между ними. Обе змеи будут в своей наименее растянутой позе (все вертикальные полосы, без слешей). Строка начинается с хвоста змеи, обращенной вправо, и заканчивается хвостом змеи, обращенной налево (вы можете при желании предположить, что есть также завершающий символ новой строки).
Например, вот возможный ввод с пятью пробелами между змеями:
<|=||:)~.....~(:||||>
Я использую period ( .
) вместо реальных пробелов для ясности.
Ноль пробелов между змеями также допустим:
<|=||:)~~(:||||>
Мы говорим, что змеи целуются, когда их языки соприкасаются вот так.
Ваша программа должна расширить некоторую комбинацию растягивающихся частей обеих змей так, чтобы у змей было как можно меньше промежутков между ними (без наложения), то есть так, чтобы змеи были как можно ближе к поцелуям .
Хвосты обеих змей фиксированы, но их головы и тела могут двигаться - вправо для змеи, обращенной вправо, влево для змеи, обращенной налево, - в зависимости от того, какие вытянутые части были вытянуты.
Результатом вашей программы является однострочная строка (плюс необязательный завершающий символ новой строки), который показывает змей как можно ближе к поцелуям, с чередующимися косыми чертами вместо вертикальных полос для растянутых участков, которые были расширены.
Например, вывод для <|=||:)~.....~(:||||>
(сверху) будет:
</\=||:)~~(:/\/\/\/\>
Это единственное решение здесь, потому что с любой другой комбинацией вытянутых частей, змеи будут либо перекрываться, либо удаляться от поцелуев.
Если существует несколько возможных решений, вывод может быть любым из них.
Например, если входные данные были
<|=||:)~.....~(:|||=|>
выход может быть
<|=/\/\:)~~(:/\/\/\=|>
или же
</\=||:)~~(:/\/\/\=/\>
Помните, что не всегда можно поцеловать змей, но вам все равно нужно как можно ближе подойти к ним.
Например, если входные данные были
<||=||||:)~...~(:||>
выход может быть
</\/\=||||:)~.~(:||>
или же
<||=||||:)~.~(:/\/\>
Если змеи уже целуются, результат будет таким же, как и у входа. например
<|=||:)~~(:||||>
В общем, выходные данные будут такими же, как и входные, если расширение любой растянутой части приведет к перекрытию змей. например
<|||=|||:)~..~(:||||=|||||=||||||>
Примечания
- Принимает ввод из stdin или командной строки, как обычно, или пишет функцию, которая принимает строку. Распечатать или вернуть вывод.
- Вы можете использовать period (
.
) на входе и выходе вместо пробелов (), если хотите.
- Важно только, чтобы косые черты чередовались в последовательности вертикальных полос, которые они заменяли. Их порядок в змее в целом или то, идет ли вперед или назад косая черта, не имеет значения.
- Эластичные участки не могут расширяться частично - это ровно удвоение или вообще не удлинение.
счет
Это код-гольф . Победит самая короткая подача в байтах. Tiebreaker - более ранний ответ.
источник
>
не стал бы<
ни тот же, для for(
и)
), но он также говорит: «Важно, чтобы косые черты чередовались в последовательности вертикальных полос, которые они заменяли. Их порядок в змея на свободе, или то, будет ли впереди или сзади косая черта, не имеет значения ".Ответы:
CJam,
87717068 байтПопробуйте онлайн в интерпретаторе CJam .
Как это устроено
источник
Retina ,
209107999792 байтаВ целях подсчета каждая строка идет в отдельном файле, но вы можете запустить код из одного файла с
-s
флагом.Объединение лучших возможностей регулярных выражений .NET и Retina: балансировка групп, просмотр за произвольной длиной и повторная замена регулярных выражений.
По сути, длинное регулярное выражение кодирует правильное решение, и средство отслеживания движка регулярного выражения находит одно из оптимальных для меня.
объяснение
Во-первых, давайте рассмотрим, как мы можем найти правильное решение (не обязательно производящее правильный вывод) с помощью регулярного выражения. Мы можем использовать группы балансировки .NET, чтобы помочь нам подсчитать растягивающиеся части. Рассмотрим следующее более простое регулярное выражение:
Мы можем разобрать это.
Это соответствует всей строке, помещая один захват в
1
стек групп для каждого пробела во входных данных. Мы будем использовать этот стек, чтобы гарантировать, что эластичные части точно заполняют пространство, занятое в этих группах.Следующее - взгляд назад. Загвоздка в том, что взгляды совпадают справа налево в .NET (так вы должны их читать). Это дает нам возможность пересечь строку во второй раз, выяснив, есть ли подмножество растягивающейся части, которое суммируется с количеством соответствующих пробелов. Пройдя сквозь обзор справа налево:
Это просто гарантирует, что мы на самом деле начинаем с конца строки (хвост змеи).
Для каждой эластичной части это либо просто совпадает со всей частью, ничего не делая (
\|+
), либо совпадает со всей частью, пока выталкивание захватывает из stack1
((?<-1>\|)*
). Наличие этого чередования гарантирует, что мы можем только полностью вытянуть эластичную часть или оставить ее без изменений, и не получать подобные вещи|/\|
. Затем мы переходим к следующей эластичной части с[^|]+
.Наконец, мы гарантируем, что мы прошли всю строку (обе змеи), и этот стек
1
полностью пуст. Т.е. мы нашли подмножество растягивающейся части, которое точно соответствует количеству пробелов, которые мы захватили ранее.Бэктрекер будет перебирать строку вперед и назад, пробуя все комбинации неизмененных и расширенных частей до тех пор, пока проблема суммы подмножеств не будет решена. Если такого подмножества не существует, просмотр сзади не удастся. Это заставит бэктрекер вернуться к
\S+( )+.+
части и попытаться захватить на один пробел меньше( )+
(который будет.+
вместо этого прикрыт).+
Поэтому из-за жадности мы стараемся заполнить как можно больше пробелов.Вы можете проверить правильность этого подхода с помощью этой слегка измененной замены:
Что даст вам строку
=spaces=
с точным количеством пробелов, которые могут быть заполнены заданными змеями.Мне пришлось добавить еще одну хитрость, чтобы действительно расширить правильные значения
|
. По сути, я хочу заменить все|
s, которые были сопоставлены с использованием(?<-1>\|)+
ветви. Идея состоит в том, чтобы соответствовать индивидуальному персонажу, поместить решатель в обход и установить флаг, если совпадение происходит внутри этой ветви. Если этот флаг не был установлен, мы аннулируем совпадение в конце, чтобы избежать замены других символов.Для этого мы используем несколько вложенных lookarounds. Опять же, взглядовые объекты переменной длины .NET сопоставляются справа налево, поэтому, если мы вкладываем в объекты lookaheads и lookbehinds, мы можем позволить механизму регулярных выражений проходить строку несколько раз. По причинам, связанным с игрой в гольф, решатель перевернут в моем реальном решении (начиная с конца, выбирая пробелы справа налево, а затем решая сумму поднабора слева направо), но в остальном структура решателя точно такая же , Давайте рассмотрим полное регулярное выражение:
Мы сопоставляем один символ, затем фиксируем остаток строки и перемещаем курсор в конец строки. Мы будем использовать эту группу
1
позже, чтобы проверить в решателе, находимся ли мы в позиции матча.Это похоже на первую часть простого решателя выше, за исключением того, что мы выбираем пробелы справа налево. Возврат количества пробелов работает точно так же, как и раньше, за исключением того, что мы сейчас используем группу
5
.Это то же самое, что и раньше, за исключением того, что мы идем слева направо, и всякий раз, когда мы сопоставляем a
|
в расширяющейся ветви, мы проверяем, совпадает ли это с правойЭто необязательный взгляд. Он
1
снова пытается сопоставить группу (что, в данном случае, возможно только в том случае, если мы находимся сразу после сопоставляемого символа), и если мы это сделаем, мы собираем пустую строку в группу4
, что указывает на то, что мы нашли текущий символ в одном из расширенных битов. Если\1
не совпадает,4
не будет ничего захватывать, и?
гарантирует, что неудачный просмотр не повлияет на решатель вообще.Наконец, после того, как все решение завершено, мы просто проверяем, использовался
\4
ли этот прогноз. Если это так, мы хотим заменить текущий символ на/\
.Остается одна трудность: удаление нужного количества пробелов. Я нашел самый короткий способ сделать это, вставить пробел вместе с
/\
и затем избавиться от одного пробела между языками для каждого из этих маркерных пространств на отдельном шаге:источник
Рубин
191 187 186 170162Это функция, которая принимает строку в качестве параметра и возвращает строку.
Онлайн тесты: http://ideone.com/uhdfXt
Вот читаемая версия:
В версии для гольфа основная функция является эквивалентом
KISS
функции, указанной выше, и этаCOMBINATIONS
функция была встроена.источник
<|=||:)~~(:||||>
, что в спецификации является допустимым вводом.Python, 205 байт
Одна лямбда выглядит аккуратно, но я почти уверен, что это не лучший способ. Но я публикую это, потому что все, что у меня есть, выглядит наполовину прилично.
Это простая перебор всех возможных замен
|
с/\
, отфильтровывая недопустимые конфигурации. Единственный аккуратный немного я думаю, что мы на самом деле не заменить какой - либо|
с/\
напрямую - мы сначала заменим|
сX
и опускаем.
с середины для каждой замены, возьмите строку минимальной длины на все действительные строки, а затем заменитьX
с с/\
.Я попробовал несколько других подходов, включая рекурсивные, но они оказались довольно грязными. Я также узнал, что в
re.split
настоящее время не разбиваются на пустые строки, что было неудачно, потому что одна из моих идей заключалась в разделении на\b
границы слов.источник
Mathematica, 381 байт
Чистая функция, принимающая строку в качестве аргумента. Ожидает,
.
а немежду змеями.
Я не думал, что это будет так плохо ... Вот что у меня было до того, как я разбил его и вставил все.
Вот пример прогона с объяснением:
источник
a=StringReplace;b=StringSplit;c=StringLength;d=Total;
что нужно, и заменяя их в других местах:a=StringReplace;b=StringSplit;c=StringLength;d=Total;a[MapAt[a[#,"|"->"/\\"]&,b[#<>"="<>#2,"="],#3]~StringRiffle~"=",")="->")~"<>If[#4>0,"."~StringRepeat~#4,""]<>"~"]&[#1,#3,Sequence@@Function[{l,s},{#,#2-d@Extract[l,#]}&[Flatten[l~Position~#~Take~#2&@@@Tally@#&@@Select[Subsets@l,d@#<=s&]~MaximalBy~d,1],s]][c/@StringCases[#1<>#3,"|"..],c@#2]]&@@#~b~"~"&
Пролог (ECLiPSe), 438 байт
Мои другие ответы решали не ту проблему (извините за шум). Вот еще одна попытка в Прологе, которая на самом деле соблюдает все правила.
тесты
(формат: ввод, вывод, перевод строки)
Пояснения
Основной предикат
s/2
, который принимает входные данные в качестве первого аргумента и возвращает результат со вторым аргументом (обе строки). Вход преобразуется в список кодов символов,E
.Затем
s(E,Z,X,Y,L)
разбивает список на следующие элементы:Z
количество пробелов между змеямиX
иY
, абстрактное представление левого и правого органовФормат тела - это список
n:N
илиs:N
выражения, гдеN
положительная длина;n
средстваnormal
иs
средстваstretched
.L
общая длина спискаЧто интересно, так
s/5
это то, что он идет обоими путями , то есть мы можем построить змею, если будут созданы другие аргументы:Q
, разделяющее новых змей. Общая длина вычисляемой строки ограничена, поэтому поиск прекращается.источник
Python 2.7.3
427421400371 байтКод не для игры в гольф здесь -
Тестирование гольф-решения -
Конечно, это можно сделать лучше (я не могу понять, как :)).
Дайте мне знать, если я упустил что-то очевидное во время игры в гольф (это мой первый код-гольф, возможно, я делаю что-то глупое: P)
источник
exit
наsys.exit()
(забыл,exit
существовал). И вы правы,__import__
могут быть удалены, что устранено, как 20 символов :)> 6
символы, которые стоит использовать для псевдонимов, если вы используете его дважды, и> 3
символы, если вы используете его три раза. Я не уверен, чтоf=' '
псевдоним того стоит (я считаю дважды)05AB1E , 93 байта
Слишком долго ..>.>
Попробуйте онлайн или проверьте все тестовые случаи или проверьте все возможные результаты для всех тестовых случаев .
Объяснение:
источник