Время для другого испытания лабиринта, но не так, как вы его знаете.
Правила для этой задачи немного отличаются от большинства задач лабиринта. Типы плиток определены следующим образом:
S: Расположение в лабиринте, с которого вы начинаетеE: Место, куда вы пытаетесь добраться0: Стена, которую вы не можете пересечь+: Этаж, который вы можете пересечь
Вы можете перемещаться в одном из шести направлений: вверх-влево, вверх-вправо, влево, вправо, вниз-влево или вниз-вправо.
\ /
-S-
/ \
Лабиринт не укутывает. Цель состоит в том, чтобы найти кратчайшую строку пути, чтобы добраться Sдо E.
Входные данные:
Ввод - разделенные пробелом строки, как показано на лабиринтах. Никакой пробел не будет следовать за линией.
Выход:
Строка R, Lи Fгде
Rповорачивает вас вправо (по часовой стрелке) на 60 градусовLповорачивает вас влево (против часовой стрелки) на 60 градусовFперемещает вас на одну позицию в направлении, на которое вы указываете
Вы начинаете указывать left-up
Кратчайший путь учитывается по длине создаваемой строки, а не по количеству посещенных позиций. Ваша программа должна распечатать кратчайший путь в качестве решения.
Если лабиринт неразрешим, вы должны вывести Invalid maze!.
( >>>это выход)
0 0 0 0
0 + 0 + 0
0 0 0 + + 0
0 + 0 + 0 + 0
0 0 + + 0 0 + 0
0 0 + 0 + 0 0 + 0
E 0 + 0 0 + + 0
+ + 0 + 0 + 0
0 0 0 0 0 +
+ 0 + + +
0 S 0 0
>>>RFRFFLFLFRFFLFFFLFLFFRFLFLFRFRFRF
+ 0 0 0 0 0 0
0 0 0 0 0 + + 0
0 0 E 0 + 0 0 + 0
0 0 0 0 0 0 0 +
0 + 0 0 + + +
0 0 + + 0 0
S + 0 0 0
>>>Invalid maze!
0 E S
>>>LF
E + 0
0 + + +
0 0 S
+ +
>>>FFLF
E
0 +
0 + +
0 +
S
>>>RFFLFF
0 E + 0 0
0 + 0 0 + +
+ 0 + + + 0
+ 0 + 0 + 0
+ + + 0 S
>>>FFLFLFFRFRFFRFF
E 0 + + 0
0 + 0 + + 0
+ + + 0 + 0
+ 0 0 0 0 0
+ + + + 0
+ 0 S 0
>>>FLFFRFFRFLF
(Обратите внимание, что у некоторых лабиринтов есть другие решения, которые имеют ту же длину, но не перечислены здесь)
источник
Ответы:
Python 2, 291 байт
Функция, которая
fберет лабиринт в виде списка строк и возвращает решение, если оно существует.объяснение
Выполняет поиск в ширину на графике пар положение / направление, чтобы найти кратчайший путь от
SдоE.Что интересно, так это найти компактный способ представления позиций и направлений на шестиугольной сетке, который допускает простой «шаг» (то есть движение в определенном направлении) и вращение. Здесь заманчиво использовать комплексные числа для представления координат на «реальной» гексагональной сетке, но это не очень хорошая идея по ряду причин, наиболее серьезной из которых является тот факт, что нам нужно подключить √3 где-нибудь, чтобы заставить его работать (грех 60 ° = √3 / 2), что при использовании чисел с плавающей запятой не имеет смысла, если нам нужна абсолютная точность (например, для отслеживания состояний, которые мы уже посетили;) Вы можете попробовать запустить консоль JavaScript и набрать текст,
Math.sqrt(3)*Math.sqrt(3) == 3и убедитесь сами.Но мы можем использовать маленький трюк! Вместо того, чтобы использовать комплексные числа, давайте определим гексагональные числа в аналогичном ключе как пару действительных чисел a + bh , где h играет роль, аналогичную мнимой i при работе с комплексными числами. Как и с комплексными числами, мы можем связать пару ( a , b ) с точкой на плоскости, где действительная ось направлена вправо, мнимая ось направлена вверх на 60 °, и они оба пересекают единичный правильный шестиугольник, когда действительное и мнимые части равны 1 соответственно. Отображение этой системы координат в ячейки лабиринта тривиально.
В отличие от i , постоянная h определяется соотношением h 2 = h - 1 (решение для h может выявить некоторые идеи). И это все! Шестигранные числа могут быть добавлены и умножены, используя описанное выше соотношение, так же, как комплексные числа: ( + BH ) + ( C + дк ) = ( + C ) + ( б + д ) ч , и ( + BH ) · ( c + dh ) = ( ac - bd
) + ( ad + bc + bd ) h . Эти операции имеют ту же геометрическую интерпретацию, что и их сложные аналоги: сложение - это сложение вектора, а умножение - это масштабирование и вращение. В частности, чтобы повернуть шестиугольное число на 60 ° против часовой стрелки, мы умножим его на h :
( a + bh ) · h = - b + ( a + b ) h , а чтобы повернуть то же число на 60 ° по часовой стрелке, мы разделим по ч :
( а + чч ) / ч = ( а +bh ) · (1 - h ) = (a + b) - ах . Например, мы можем взять единичное шестиугольное число, указывающее вправо, 1 = (1, 0), полный круг, идущий против часовой стрелки, умножив его на h шесть раз:
(1, 0) · h = (0, 1 ); (0, 1) · h = (-1, 1); (-1, 1) · h = (-1, 0); (-1, 0) · h = (0, -1); (0, -1) · h = (1, -1);
(1, -1) · h = (1, 0).
Программа использует гексагональные числа таким образом, чтобы представлять текущую позицию в лабиринте и текущее направление, для продвижения в указанном направлении и для поворота влево и вправо.
источник
Гексагония , 2437 байт
Долгожданная программа здесь:
Попробуйте онлайн!
«Читаемая» версия:
Протестировано на Esoteric IDE: TIO может выдержать тайм-аут в некоторых из более крупных тестовых случаев, но все проверены. Большое спасибо Тимви, это не было бы возможно без IDE.
Там довольно много пустого пространства, поэтому я мог бы разместить его на шестиугольнике с длиной стороны 28 (вместо 29 с длиной стороны), но это будет огромной задачей, так что я, вероятно, не собираюсь пытаться это делать.
Основное объяснение
Нажмите на изображения, чтобы увеличить и детализировать версию.
функции
Примечание: деления, как правило, правильные, но иногда могут быть приблизительными.
Этот код достаточно «функционален» - насколько позволяет Hexagony. В этом коде есть восемь основных функций, помеченных на приведенной выше диаграмме и названных номерами, с которыми они вызываются (поэтому номера их указателей команд - это число mod 6). В (грубом) порядке вызова они (цитируемые имена - это места в памяти, которые будут объяснены позже):
F,RиLготовы к основной обработке. Указатель инструкции 0 переходит к функции 0, а выполнение переходит к функции 1.+течение 2-х ходов после его первого достижения. Возвращает к функции 1.F. Возвращает к функции 1.F,Rлибо сLдобавлением. Возвращает к функции 1.FFLF), затем завершает программу.Invalid maze!и завершениеобъем памяти
Примечание: еще раз спасибо Esoteric IDE за диаграмму
Память состоит из трех основных частей:
0или действительное место , которое было открыто несколько ходов назад , чем требовалось бы , чтобы выйти из места в любом направлении.+который еще не был достигнут.-1s с одним-2слева, позволяет указателю памяти быстро вернуться в область обработки ядра.F,R,Lа1,2,3соответственно ,-1s, а затем значение y увеличивается (хотя y = 0 в любом случае обрабатывается как 1 для отделения рельса от справочных данных)Другие важные области памяти:
Eхранится здесь.источник
Python 3, 466 байт
Вероятно, в итоге я бы стал меньше, если бы использовал поиск в глубину или что-то в этом роде Это чудовище использует Дейкстра и довольно быстро, но очень долго.
Код определяет функцию
Sкоторая берет многострочную строку с лабиринтом и возвращает результат.Вот тест кода.
Ungolfed
источник
L,,R.Groovy, 624 байта. Fore!
Время, время, когда мяч катится с большой. Принимает многострочную строку как аргумент
QБезголовая версия:
источник
C #,
600574 байтаЗавершить программу, принимает ввод из STDIN, вывод в STDOUT.
Редактировать: была ошибка в обработке переноса (не нарушалась ни в одном из приведенных тестовых случаев), которая добавляла 1 байт, поэтому я сделал немного больше игры в гольф, чтобы компенсировать это.
Это начинается с чтения на карте, добавляя
(к каждой строке, чтобы он знал, где она заканчивается, и может вернуться назад и добавить множество пробелов, чтобы сделать карту прямоугольной, и с рядом пробелов по правой стороне (это сохраняет мы делаем проверку упаковки, как будет объяснено ниже). Он определяет ширину прямоугольника в некоторой точке и определяет общую длину карты.Затем он инициализирует все для поиска в ширину. Созданы два массива biggish: один для хранения всех состояний, которые мы должны исследовать в нашем поиске, другой для записи маршрута, который мы выбрали, чтобы добраться до каждого состояния. Начальное состояние добавляется в должный массив с указателями головы и хвоста, предварительно установленными как-то выше. Все 1 проиндексировано.
Затем мы повторяем, пока хвост не врезается в голову, или, по крайней мере, не появляется , что врезался в голову. Для каждого состояния, которое мы посетили, мы пытаемся добавить новое состояние в ту же позицию, где мы поворачиваемся влево или вправо, а затем в то, где мы продвинулись. Направления индексируются, причем начальное направление (по умолчанию
0) соответствует значению «вверх-влево».Когда мы пытаемся поставить в очередь состояние, оно проверяется с привязкой, но не с проверкой на перенос, из-за столбцов пробелов с правой стороны, на которые указывает «мы можем быть здесь?» проверить (вам не разрешено находиться на пробелах). Если состояние ставится в очередь, мы затем проверяем, находится ли оно в
Eячейке, и если оно есть, мы устанавливаем начало очереди как минус, что приводит к выходу из основного цикла, и выдает последнюю строку программы для печати. соответствующий маршрут, а не сообщение об ошибке (которое показывает, если у нас кончаются состояния для расширения (хвост врезается в голову)).Как и большинство моих поисков по графику на этом сайте, я хорошо использую структуры C #, которые по умолчанию сравниваются по буквальному значению.
источник
Python 2, 703 байта
Не так хорошо, как две другие версии, но, по крайней мере, это работает, ха-ха. Установите
Mв лабиринт.Поскольку у меня нет опыта в решении лабиринтов, он просто использует подход грубой силы, где он найдет все возможные решения, которые не включают в себя пересечение. Он рассчитывает ходы из самых коротких, а затем выбирает из этого самый короткий результат.
Грязная негольфированная версия:
источник
if heading != required_heading: while heading != required_heading:простоwhile heading != required_heading: