Задний план
Вы просыпаетесь, чтобы оказаться потерянным в одномерном лабиринте! Появляется мистический джинн (или что-то в этом роде), объясняющий, что перед вами лежит выход, но между вами и выходом есть ряд проблем. По мере продвижения вперед вы понимаете, что все так называемые вызовы - это просто запертые двери. Сначала вы видите дверь с отверстием для ключа в T
форме тройника и, не имея такого ключа самостоятельно, проследите свои шаги в поисках ключа с формой.
Разочарованный, вы найдете алфавитный суп из ключей на земле, ни один из которых не соответствует двери, с которой вы столкнулись. Каким-то гениальным ходом (или идиотизмом) вы решаете, что t
строчный ключ в форме буквы может уместиться в слоте, если вы зажмете его там достаточно сильно. Когда вы подходите к двери с t
ключом в нижнем регистре в руке, T
отверстие горит зеленым, и дверь распадается перед вами.
Один вниз, еще много, чтобы пойти ...
Вызов
Цель этого задания - указать, сколько шагов вам нужно, чтобы выйти из лабиринта.
Вход этой задачи - лабиринт: одна строка, содержащая только символы [A-Za-z^$ ]
. Глоссарий:
^
- Стартовое пространство. Вход будет содержать ровно один^
.$
- Выход (свобода!). Вход будет содержать ровно один$
.[A-Z]
- Прописные буквы обозначают двери. Вы можете пройти через эту дверь, только если уже собрали необходимый ключ.[a-z]
- Строчные буквы обозначают клавиши. Вы собираете эти ключи, идя на место, где находится ключ.
На входе будет не более одной заглавной буквы. Это означает, что общее количество дверей будет от 0 до 26 включительно.
Каждая запертая дверь [A-Z]
будет иметь только один соответствующий ключ в нижнем регистре [a-z]
. Во входе может быть любое количество пробелов ( ).
Все двери будут справа от начала и слева от выхода. При этом не будет лишних дверей. Все входные данные будут разрешимыми.
Выход для этого вызова будет число, количество шагов, необходимых для выхода из лабиринта.
Алгоритм
Ваш методичный подход к выходу из этого жалкого места заключается в следующем:
- Начать с начала (
^
) и двигайтесь вперед (вправо), собирая любые ключи, с которыми вы сталкиваетесь. - Когда вы сталкиваетесь с дверью, если у вас есть правильный ключ, вы идете вперед к двери. Если у вас нет правильного ключа, вы идете назад (влево), собирая ключи, с которыми сталкиваетесь, пока не найдете ключ для самой последней двери, которую вы не могли открыть.
- Как только вы соберете ключ от текущей проблемной двери, вы поворачиваете назад направо и продолжаете идти дальше.
- Повторяйте этот процесс, пока не наступите на выход (
$
).
Опытные игроки в гольф поймут, что ваш код не должен реализовывать этот специфический алгоритм, если он выдает тот же результат, как если бы вы запускали этот алгоритм.
Counting
Каждый раз, когда вы переходите от одного квадрата к другому, это считается одним шагом. Поворот на 180º не требует дополнительного шага. Вы не можете выйти на дверь без необходимого ключа. Вы должны встать на ключ, чтобы забрать его, и должны выйти на выход, чтобы выиграть. После вашего первого хода начальная пробел ( ^
) ведет себя так же, как и любой другой обычный пробел.
Примеры
В этих примерах я оставил пробелы в качестве подчеркивания для удобства чтения.
Вход есть _a_^_A__$__
. Выход есть 11
. Вы делаете 1
шаг вперед, замечаете, что у вас нет ключа от A
двери, а затем около лица. Вы идете назад, пока не займете пространство, содержащее a
( 3
шаги назад, теперь 4
всего). Затем вы идете вперед, пока не займете пространство, содержащее выход ( 7
шаги вперед,11
всего).
Вход есть b__j^__a_AJB_$
. В результате 41
вы совершаете две отдельные поездки в заднюю часть лабиринта: одна для получения j
ключа, а вторая для получения b
ключа.
Вход есть __m__t_^__x_T_MX_$____
. Выход есть 44
. Вы не совершите дополнительную поездку, чтобы получить x
ключ, так как подобрали его по пути от начала до двери T
.
Вход есть g_t_^G_T$
. Выход есть 12
. Вы не можете выйти на G
пространство без ключа и сразу же повернуть лицом к лицу. Вам посчастливилось поднять t
ключ на пути к g
ключу и, таким образом, открыть обе двери на пути к свободе.
Вход есть _^_____$
. Выход есть 6
. Это было просто.
Руководство по вводу / выводу и критерий выигрыша
Применяются стандартные правила ввода / вывода. Это вызов для игры в гольф .
A
вbA^aB$
не будет лишним ни. ;)Ответы:
CJam, 45
Попробуйте онлайн
Объяснение:
источник
Pyth, 51 байт
Суммируйте расстояние между дверью и ее ключом (удвоенное, чтобы совершить поездку в оба конца), игнорируя «вложенные» ключи и расстояние от начала до конца:
тот же алгоритм в python2.7:
источник
Python 2,
155154134128 байтРедактировать: Спасибо @ user2357112 и @loovjo за их комментарии, которые помогли мне убрать еще
2026 байтов из моего решения!источник
i
это не нужно?i
отслеживает положение двери, обрабатываемой в данный момент, и требуется, если ее ключ еще не был поднят (т. е. еслиk
- положение ключа - меньше, чемf
- крайний левый угол, который мы прошли, - то нам нужно добавить2*(i-k-1)
шаги к нашему общему количеству (идем налево, чтобы получить ключ, и идем обратно к двери) ...?i
ли заменитьl.index(d)
на пятую строку, а назначение удалить на четвертой?e
иf
переменные выглядят избыточными. Кроме того, вы можете сохранить несколько символов, сохранивl.index
переменную.x
также является избыточным. Похоже, мой гольф-нуб-инесс показывает. :) Спасибо за помощь!C 136 байтов
источник
PHP 5.3, 123 байта
Это мой первый пост на Code Golf, надеюсь, он достаточно высокого качества для первого поста. Определенно веселый вызов и потрясающий вопрос!
Эта программа злоупотребляет тем фактом, что PHP не требует предварительного объявления каких-либо переменных перед их использованием.
Кроме того, в моем конечном решении оказалось, что на пару байт короче начинать с 0 и сбрасывать счетчик шагов при обнаружении начального символа, а не начинать с «^».
Любые советы, безусловно, приветствуются!
источник
JavaScript (ES6), 110 байт
Порт @ Роба Pyth ответ.
источник
Python 2.7,
234199179источник
AWK, 174 байта
Там, вероятно, более жесткий алгоритм, но это то, что я придумал.
Обратите внимание, что я использую
gawk
. Некоторые реализацииAWK
могут не разбивать строку""
таким образом.источник
C #, 309 байт
Безголовая версия:
Ничего особенного в этом нет, просто перебирайте строку и меняйте направление в зависимости от символа и от того, содержится ли ключ в строке ключей.
м = лабиринт
k = строка ключей
F = направление (истина вперед в лабиринте)
b = ключ для поиска при возврате
c = заполнитель для m [j] для сохранения некоторых байтов из-за частого использования
j = индекс символа строки для просмотра
т = количество
Все еще относительно новичок в гольфе, так что, если вы видите где-нибудь, я могу уменьшить его, дайте мне знать!
источник