Время гексагональной лабиринт!

27

Время для другого испытания лабиринта, но не так, как вы его знаете.

Правила для этой задачи немного отличаются от большинства задач лабиринта. Типы плиток определены следующим образом:

  • 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

(Обратите внимание, что у некоторых лабиринтов есть другие решения, которые имеют ту же длину, но не перечислены здесь)

Дж Аткин
источник
27
Надеясь на решение Hexagony ...
bkul
3
Я назначу награду в 500 баллов за решение Hexagony.
lirtosiast
@ lirtosiast2 годами позже, я думаю, что гексагония может быть натяжкой для этой проблемы;)
J Аткин
Давайте подождем еще несколько лет.
user202729
Может ли быть завершающий перевод строки?
user202729

Ответы:

17

Python 2, 291 байт

def f(M):
 Y=map(max,M).index("S");X=M[Y].find("S");V={()};Q=[(0,0,0,1,"")]
 while Q:
    try:x,y,u,v,p=s=Q.pop(0);c=(Y>=y<=X-2*x)*ord(M[Y-y][X-2*x-y])
    except:c=0
    if c==69:return p
    if{c%2*s[:4]}-V:V|={s[:4]};Q+=(x+u,y+v,u,v,p+"F"),(x,y,-v,u+v,p+"R"),(x,y,u+v,-u,p+"L")
 return"Invalid maze!"

Функция, которая fберет лабиринт в виде списка строк и возвращает решение, если оно существует.

объяснение

Выполняет поиск в ширину на графике пар положение / направление, чтобы найти кратчайший путь от Sдо E.

Что интересно, так это найти компактный способ представления позиций и направлений на шестиугольной сетке, который допускает простой «шаг» (то есть движение в определенном направлении) и вращение. Здесь заманчиво использовать комплексные числа для представления координат на «реальной» гексагональной сетке, но это не очень хорошая идея по ряду причин, наиболее серьезной из которых является тот факт, что нам нужно подключить √3 где-нибудь, чтобы заставить его работать (грех 60 ° = √3 / 2), что при использовании чисел с плавающей запятой не имеет смысла, если нам нужна абсолютная точность (например, для отслеживания состояний, которые мы уже посетили;) Вы можете попробовать запустить консоль JavaScript и набрать текст, Math.sqrt(3)*Math.sqrt(3) == 3и убедитесь сами.

Но мы можем использовать маленький трюк! Вместо того, чтобы использовать комплексные числа, давайте определим гексагональные числа в аналогичном ключе как пару действительных чисел a + bh , где h играет роль, аналогичную мнимой i при работе с комплексными числами. Как и с комплексными числами, мы можем связать пару ( a , b ) с точкой на плоскости, где действительная ось направлена ​​вправо, мнимая ось направлена ​​вверх на 60 °, и они оба пересекают единичный правильный шестиугольник, когда действительное и мнимые части равны 1 соответственно. Отображение этой системы координат в ячейки лабиринта тривиально.

Рисунок 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).

Программа использует гексагональные числа таким образом, чтобы представлять текущую позицию в лабиринте и текущее направление, для продвижения в указанном направлении и для поворота влево и вправо.

флигель
источник
31

Гексагония , 2437 байт

Долгожданная программа здесь:

(.=$>({{{({}}{\>6'%={}{?4=$/./\_><./,{}}{<$<\?{&P'_("'"#<".>........_..\></</(\.|/<>}{0/'$.}_.....><>)<.$)).><$./$\))'"<$_.)><.>%'2{/_.>(/)|_>}{{}./..>#/|}.'/$|\})'%.<>{=\$_.\<$))<>(|\4?<.{.%.|/</{=....$/<>/...'..._.>'"'_/<}....({{>%'))}/.><.$./{}{\>$\|$(<><$?..\\<.}_>=<._..\(/.//..\}\.)))))<...2/|$\){}/{..><>).../_$..$_>{0#{{((((/|#.}><..>.<_.\(//$>))<(/.\.\})'"#4?#\_=_-..=.>(<...(..>(/\")<((.\=}}}\>{}{?<,|{>/...(...>($>{)<.>{=P&/(>//(_.)\}=#=\4#|)__.>"'()'\.'..".(\&P'&</'&\$_></}{)<\<0|\<.}.\"\.(.(.(/(\..{.>}=P/|><.(...(..."/<.{"_{{=..)..>})<|><$}}/\}}&P<\(/._...>\$'/.>}/{}}{)..|/(\'.<(\''"")$/{{}})<..'...}}>3#./\$<}|.}|..$.><${{}/>.}}{{<>(""''/..>){<}\?=}{\._=/$/=_>)\{_\._..>)</{\=._.....>(($>}}<.>5#.\/}>)<>-/(.....{\<>}}{{/)\$>=}}}))<...=...(\?{{{?<\<._...}.><..\}}/..>'P&//(\......(..\})"'/./&P'&P{}}&P'<{}\{{{({{{(.\&P=<.><$"&1}(./'"?&'&"\.|>}{?&"?&'P&/|{/&P''</(\..>P&{/&/}{}&'&},/"&P'&?<.|\}{&?"&P'&P'<._.>"&}\(>))<\=}{}<.{/}&?"&"&/"&"?&}\.|>?&"?&{{}}?&//x'&{((<._\($|(}.\/}{/>=&'P&"&/".{3?<.|\"&P'&P}{}&P'<.>&{}}?&"&'P&\=}}<.}/2?".?''5?"/?1{(}\."..../{},<../&//&"&P'&P'&"&"</{}}{{/>"?1''?.'({/}}{}<..>?&"?&}}$>)|P/<.>"&'P&'P&"&"&{/........._/"\$#1}/._.........|,($<'"}'?/_$P#"$0'${)$})$)|........(>/\.#1?<$<|.....>?&}$>=?&"?&/1$..>I;n;v;a;l;i;d;P0;m;a\|\"(}}({=/..$_...\"&P=},}}&P'<.|><....................;...>1"(}}){=/_....>'P&'P&}}_?&/#.>}?4'%\/<...@;1P;e;z<._><>"))'?=<.$$=..\&P}{&</\"><_'|/'&=}<.>{{.<.........|>(/>3")}}){=/=/_.>}P&"?/"<).}_.>?4{=:<.|_...........\$\2$'>4")}}({/."\{&P'&?/><.?|>P...."/=(>(/./(}{{\..>(<>(<>?5'"((..'/...#,</,}{{\.......;.F>..\(...}....._.._..._..._........__..'$......\.<R..$.>))<$}{{&P'&?}<.\$$.\...................$\.<>L\.\(('_"\>}P&"?&{/__/=(.(<.>_)..<...>....\..._.<.....&?=\}=&?"&<.."'>.\>))<.|>))\.|$.>&"?&{{}=P&}?&=}/{\.>&{{P/{">)<|\{<(|\(_(<>\_\?"&P'&P}{{{&<=_.>\&\?"&?<|'{/(/>{{/_>.{/=/\\.>'P&"?&"?&"?/._(\)\\>?&"/_|.>/.$/|$..\\><..\&?}{{}&P'&<}.._>{<|\{}<._$>-")<.>_)<|{)$|..>}=P&"?&"?/...{"./>'P&/=_\{?(/>(<>\(|)__.\&?}}{}&P<}.$.\&P'&P'&<\})))&=<\)<'.'_,><.>"?&'P&'/.|>?&{{}?&"?/>&"?&"?&}}<.".(\\\&?={&P<{..\"&?"&P'&<.?....|.$'\$/\"/.,.>{}{}=/..>&'P&}{{}P/\{}&P{(&?"&?"<'.(\&?"&<}..\?"&?"&<.>P&={}}?&}}P&'P&/.'.>&"?/..>P&}}{{P/\}&P'&?={&?<$}=\"."\P'<{..\'&P'&<....>'P&{}P&"?&{{<\\..>&/$.>}{?&"?/|'$&.P&$P\$'&P={(/..\P\\.\{&?"&?\...\?{{}=<$&P'&P<.,./<?\...{}=P\"&<.>=P&""'?&'P&'/$.#1.>{?1#=$\&'P/\}&P'&?={(,}<._?_&\&?{=&{*=}4<.>P&"?&"?&'P&/1_$>}?&}}=?&){?/\{}&P'&?={&?#<$

Попробуйте онлайн!

«Читаемая» версия:

                             ( . = $ > ( { { { ( { } } { \ > 6 ' % = { } { ? 4 = $ / .
                            / \ _ > < . / , { } } { < $ < \ ? { & P ' _ ( " ' " # < " .
                           > . . . . . . . . _ . . \ > < / < / ( \ . | / < > } { 0 / ' $
                          . } _ . . . . . > < > ) < . $ ) ) . > < $ . / $ \ ) ) ' " < $ _
                         . ) > < . > % ' 2 { / _ . > ( / ) | _ > } { { } . / . . > # / | }
                        . ' / $ | \ } ) ' % . < > { = \ $ _ . \ < $ ) ) < > ( | \ 4 ? < . {
                       . % . | / < / { = . . . . $ / < > / . . . ' . . . _ . > ' " ' _ / < }
                      . . . . ( { { > % ' ) ) } / . > < . $ . / { } { \ > $ \ | $ ( < > < $ ?
                     . . \ \ < . } _ > = < . _ . . \ ( / . / / . . \ } \ . ) ) ) ) ) < . . . 2
                    / | $ \ ) { } / { . . > < > ) . . . / _ $ . . $ _ > { 0 # { { ( ( ( ( / | #
                   . } > < . . > . < _ . \ ( / / $ > ) ) < ( / . \ . \ } ) ' " # 4 ? # \ _ = _ -
                  . . = . > ( < . . . ( . . > ( / \ " ) < ( ( . \ = } } } \ > { } { ? < , | { > /
                 . . . ( . . . > ( $ > { ) < . > { = P & / ( > / / ( _ . ) \ } = # = \ 4 # | ) _ _
                . > " ' ( ) ' \ . ' . . " . ( \ & P ' & < / ' & \ $ _ > < / } { ) < \ < 0 | \ < . }
               . \ " \ . ( . ( . ( / ( \ . . { . > } = P / | > < . ( . . . ( . . . " / < . { " _ { {
              = . . ) . . > } ) < | > < $ } } / \ } } & P < \ ( / . _ . . . > \ $ ' / . > } / { } } {
             ) . . | / ( \ ' . < ( \ ' ' " " ) $ / { { } } ) < . . ' . . . } } > 3 # . / \ $ < } | . }
            | . . $ . > < $ { { } / > . } } { { < > ( " " ' ' / . . > ) { < } \ ? = } { \ . _ = / $ / =
           _ > ) \ { _ \ . _ . . > ) < / { \ = . _ . . . . . > ( ( $ > } } < . > 5 # . \ / } > ) < > - /
          ( . . . . . { \ < > } } { { / ) \ $ > = } } } ) ) < . . . = . . . ( \ ? { { { ? < \ < . _ . . .
         } . > < . . \ } } / . . > ' P & / / ( \ . . . . . . ( . . \ } ) " ' / . / & P ' & P { } } & P ' <
        { } \ { { { ( { { { ( . \ & P = < . > < $ " & 1 } ( . / ' " ? & ' & " \ . | > } { ? & " ? & ' P & /
       | { / & P ' ' < / ( \ . . > P & { / & / } { } & ' & } , / " & P ' & ? < . | \ } { & ? " & P ' & P ' <
      . _ . > " & } \ ( > ) ) < \ = } { } < . { / } & ? " & " & / " & " ? & } \ . | > ? & " ? & { { } } ? & /
     / x ' & { ( ( < . _ \ ( $ | ( } . \ / } { / > = & ' P & " & / " . { 3 ? < . | \ " & P ' & P } { } & P ' <
    . > & { } } ? & " & ' P & \ = } } < . } / 2 ? " . ? ' ' 5 ? " / ? 1 { ( } \ . " . . . . / { } , < . . / & /
   / & " & P ' & P ' & " & " < / { } } { { / > " ? 1 ' ' ? . ' ( { / } } { } < . . > ? & " ? & } } $ > ) | P / <
  . > " & ' P & ' P & " & " & { / . . . . . . . . . _ / " \ $ # 1 } / . _ . . . . . . . . . | , ( $ < ' " } ' ? /
 _ $ P # " $ 0 ' $ { ) $ } ) $ ) | . . . . . . . . ( > / \ . # 1 ? < $ < | . . . . . > ? & } $ > = ? & " ? & / 1 $
  . . > I ; n ; v ; a ; l ; i ; d ; P 0 ; m ; a \ | \ " ( } } ( { = / . . $ _ . . . \ " & P = } , } } & P ' < . |
   > < . . . . . . . . . . . . . . . . . . . . ; . . . > 1 " ( } } ) { = / _ . . . . > ' P & ' P & } } _ ? & / #
    . > } ? 4 ' % \ / < . . . @ ; 1 P ; e ; z < . _ > < > " ) ) ' ? = < . $ $ = . . \ & P } { & < / \ " > < _ '
     | / ' & = } < . > { { . < . . . . . . . . . | > ( / > 3 " ) } } ) { = / = / _ . > } P & " ? / " < ) . } _
      . > ? 4 { = : < . | _ . . . . . . . . . . . \ $ \ 2 $ ' > 4 " ) } } ( { / . " \ { & P ' & ? / > < . ? |
       > P . . . . " / = ( > ( / . / ( } { { \ . . > ( < > ( < > ? 5 ' " ( ( . . ' / . . . # , < / , } { { \
        . . . . . . . ; . F > . . \ ( . . . } . . . . . _ . . _ . . . _ . . . _ . . . . . . . . _ _ . . ' $
         . . . . . . \ . < R . . $ . > ) ) < $ } { { & P ' & ? } < . \ $ $ . \ . . . . . . . . . . . . . .
          . . . . . $ \ . < > L \ . \ ( ( ' _ " \ > } P & " ? & { / _ _ / = ( . ( < . > _ ) . . < . . . >
           . . . . \ . . . _ . < . . . . . & ? = \ } = & ? " & < . . " ' > . \ > ) ) < . | > ) ) \ . | $
            . > & " ? & { { } = P & } ? & = } / { \ . > & { { P / { " > ) < | \ { < ( | \ ( _ ( < > \ _
             \ ? " & P ' & P } { { { & < = _ . > \ & \ ? " & ? < | ' { / ( / > { { / _ > . { / = / \ \
              . > ' P & " ? & " ? & " ? / . _ ( \ ) \ \ > ? & " / _ | . > / . $ / | $ . . \ \ > < . .
               \ & ? } { { } & P ' & < } . . _ > { < | \ { } < . _ $ > - " ) < . > _ ) < | { ) $ | .
                . > } = P & " ? & " ? / . . . { " . / > ' P & / = _ \ { ? ( / > ( < > \ ( | ) _ _ .
                 \ & ? } } { } & P < } . $ . \ & P ' & P ' & < \ } ) ) ) & = < \ ) < ' . ' _ , > <
                  . > " ? & ' P & ' / . | > ? & { { } ? & " ? / > & " ? & " ? & } } < . " . ( \ \
                   \ & ? = { & P < { . . \ " & ? " & P ' & < . ? . . . . | . $ ' \ $ / \ " / . ,
                    . > { } { } = / . . > & ' P & } { { } P / \ { } & P { ( & ? " & ? " < ' . (
                     \ & ? " & < } . . \ ? " & ? " & < . > P & = { } } ? & } } P & ' P & / . '
                      . > & " ? / . . > P & } } { { P / \ } & P ' & ? = { & ? < $ } = \ " . "
                       \ P ' < { . . \ ' & P ' & < . . . . > ' P & { } P & " ? & { { < \ \ .
                        . > & / $ . > } { ? & " ? / | ' $ & . P & $ P \ $ ' & P = { ( / . .
                         \ P \ \ . \ { & ? " & ? \ . . . \ ? { { } = < $ & P ' & P < . , .
                          / < ? \ . . . { } = P \ " & < . > = P & " " ' ? & ' P & ' / $ .
                           # 1 . > { ? 1 # = $ \ & ' P / \ } & P ' & ? = { ( , } < . _ ?
                            _ & \ & ? { = & { * = } 4 < . > P & " ? & " ? & ' P & / 1 _
                             $ > } ? & } } = ? & ) { ? / \ { } & P ' & ? = { & ? # < $

Протестировано на Esoteric IDE: TIO может выдержать тайм-аут в некоторых из более крупных тестовых случаев, но все проверены. Большое спасибо Тимви, это не было бы возможно без IDE.

Там довольно много пустого пространства, поэтому я мог бы разместить его на шестиугольнике с длиной стороны 28 (вместо 29 с длиной стороны), но это будет огромной задачей, так что я, вероятно, не собираюсь пытаться это делать.

Основное объяснение

Нажмите на изображения, чтобы увеличить и детализировать версию.

функции

функции
Примечание: деления, как правило, правильные, но иногда могут быть приблизительными.

Этот код достаточно «функционален» - насколько позволяет Hexagony. В этом коде есть восемь основных функций, помеченных на приведенной выше диаграмме и названных номерами, с которыми они вызываются (поэтому номера их указателей команд - это число mod 6). В (грубом) порядке вызова они (цитируемые имена - это места в памяти, которые будут объяснены позже):

  • S: начиная функция - читает входной и устанавливает «опорный» массив, а затем запускает «стек» пути с тремя путями F, Rи Lготовы к основной обработке. Указатель инструкции 0 переходит к функции 0, а выполнение переходит к функции 1.
  • 1 (-11): основная функция - использует 2, чтобы получить путь, 3, чтобы проверить его действительность, и, если действительный, дважды переходит к функции -110 / -10, а затем 4 три раза, чтобы скопировать новые пути в «путь». стек », заканчивая возвратом к себе. Может вызвать функцию 5, если путь находится в конечном местоположении.
  • 2: Получает следующий путь из «стека путей», готового к обработке, вызывает функцию -1, если в стеке не осталось путей. Возвращает к функции 1.
  • 3: принимает пару значений, а также номер хода и проверяет «контрольный массив», чтобы увидеть, закончился ли текущий путь в допустимом месте. Действительным местоположением является либо начало в течение первых 3-х ходов, либо любое в +течение 2-х ходов после его первого достижения. Возвращает к функции 1.
  • -10 / -110: копирует текущий путь. Возвращает к функции 1.
  • 0: помогает функции 1 управлять направлением движения с помощью F. Возвращает к функции 1.
  • 4: берет копию текущего пути и, связанную с функцией 1, меняет ее на тот же путь либо с добавлением F, Rлибо с Lдобавлением. Возвращает к функции 1.
  • 5: берет путь и распечатывает правильный путь (например FFLF), затем завершает программу.
  • -1: печать Invalid maze!и завершение
  • (Двойные стрелки): из-за недостатка места функция 1 / -11 должна была уйти в пространство над функцией -1.

объем памяти

Расположение памяти
Примечание: еще раз спасибо Esoteric IDE за диаграмму

Память состоит из трех основных частей:

  • Ссылочный массив: Сетка хранится в двух столбцах, со значением на каждом шаге:
    • 0 представляет собой либо , 0или действительное место , которое было открыто несколько ходов назад , чем требовалось бы , чтобы выйти из места в любом направлении.
    • 1 представляет собой, +который еще не был достигнут.
    • (большее число) представляет номер хода, на котором было достаточно ходов, чтобы покинуть место в любом направлении.
    • 10 также представляет новую строку: они никогда не достигаются, если они сразу следуют за последним символом, не являющимся пробелом.
  • Rail: Состоит из -1s с одним -2слева, позволяет указателю памяти быстро вернуться в область обработки ядра.
  • Стек путей: хранит каждый из непроверенных путей в порядке по идентификатору пути (который напрямую связан с номером хода, поэтому сначала проверяются более короткие пути). Путь хранится следующим образом:
    Макет пути
    • Rot: вращение в конце текущей траектории: 0 влево-вверх и увеличение по часовой стрелке до 5
    • Move: номер текущего хода (инструкции - 1)
    • Путь: текущий путь, хранится в четвертичном с F, R, Lа 1, 2, 3соответственно ,
    • x / y: координаты в конце текущего пути: x + 1 -1s, а затем значение y увеличивается (хотя y = 0 в любом случае обрабатывается как 1 для отделения рельса от справочных данных)

Другие важные области памяти:

  1. Х / у Eхранится здесь.
  2. Это пространство используется для перехода путей в и из памяти.
  3. Это место является центром, где каждый путь хранится во время обработки.
boboquack
источник
Следующим шагом является запуск вашей программы через вашу программу, чтобы найти кратчайший маршрут лабиринта.
Веска
Я знаю, что кто-то опубликует это. Наконец ... / У меня также есть другой план, который, вероятно, должен занимать меньше кода, чем ваш. На самом деле никогда не хватает времени для его реализации.
user202729
@ user202729 было бы интересно услышать об этом. Этот метод, вероятно, может быть использован как минимум на 2 размера меньше, но я бы сказал, что есть что-то лучшее.
boboquack
1
Просто жду @lirtosiast.
Дж Аткин
1
Простите за опоздание.
lirtosiast
6

Python 3, 466 байт

Вероятно, в итоге я бы стал меньше, если бы использовал поиск в глубину или что-то в этом роде Это чудовище использует Дейкстра и довольно быстро, но очень долго.

Код определяет функцию S которая берет многострочную строку с лабиринтом и возвращает результат.

def F(M,L,c):y=M[:M.index(c)].count("\n");return L[y].index(c),y
def S(M):
 L=M.split("\n");Q=[("",)+F(M,L,"S")+(0,)];D={};R=range;H=len;U=R(2**30)
 while Q:
  C,*Q=sorted(Q,key=H);w,x,y,d=C
  for e in R(H(L)>y>-1<x<H(L[y])>0<H(D.get(C[1:],U))>H(w)and(L[y][x]in"+SE")*6):D[C[1:]]=w;E=(d+e)%6;Q+=[(w+",R,RR,RRR,LL,L".split(",")[e]+"F",x+[-1,1,2,1,-1,-2][E],y+[-1,-1,0,1,1,0][E],E)]
 J=min([D.get(F(M,L,"E")+(d,),U)for d in R(6)],key=H);return[J,"Invalid maze!"][J==U]

Вот тест кода.

Ungolfed

def find_char(maze, lines, char):
    y = maze[:maze.index(char)].count("\n")
    return lines[y].index(char), y
def solve(maze):
    lines = maze.split("\n")
    x, y = find_char(maze, lines, "S")
    queue = [("", x, y, 0)]
    solutions = {}
    very_long = range(2**30)
    x_for_direction = [-1,1,2,1,-1,-2]
    y_for_direction = [-1,-1,0,1,1,0]
    rotations = ["","R","RR","RRR","LL","L"]
    while len(queue) > 0:
        queue = sorted(queue, key=len)
        current, *queue = queue
        route, x, y, direction = current
        if 0 <= y < len(lines) and 0 <= x < len(lines[y]) and lines[y][x] in "+SE" and len(solutions.get(current[1:], very_long)) > len(route):
            solutions[current[1:]] = route
            for change in range(6):
                changed = (direction + change) % 6
                queue += [(route + rotations[change] + "F", x + x_for_direction[changed], y + y_for_direction[changed], changed)]
    end_x, end_y = find_char(maze, lines, "E")
    solution = min([solutions.get((end_x, end_y, direction), very_long) for direction in range(6)], key=len)
    return "Invalid maze!" if solution == very_long else solution
PurkkaKoodari
источник
Вау очень приятно. Сколько времени тебе понадобилось, чтобы написать?
Дж Аткин
1
@JAtkin Ну, файл был создан 1,5 часа назад, хотя я не уверен, сколько времени я фактически потратил на работу над кодом. Кроме того, сейчас 3 часа ночи, поэтому моя производительность, очевидно, на максимуме.
PurkkaKoodari
Хорошо, я провел 2+ часа, и большая часть моей уже была написана для стандартного лабиринта.
Дж Аткин
У вас есть версия без гольфа?
Дж Аткин
1
@JAtkin Это необходимо, потому что вам, возможно, придется развернуться с самого начала. Без стартовой позиции это сработало бы L,,R.
PurkkaKoodari
3

Groovy, 624 байта. Fore!

Время, время, когда мяч катится с большой. Принимает многострочную строку как аргументQ

Q={a->d=[0]*4
a.eachWithIndex{x,y->f=x.indexOf('S');e=x.indexOf('E');
if(f!=-1){d[0]=f;d[1]=y}
if(e!=-1){d[2]=e;d[3]=y}}
g=[]
s={x,y,h,i,j->if(h.contains([x, y])|y>=a.size()||x>=a[y].size()|x<0|y<0)return;k = a[y][x]
def l=h+[[x, y]]
def m=j
def n=1
if(h){
o=h[-1]
p=[x,y]
q=[p[0]-o[0],p[1]-o[1]]
n=[[-2,0]:0,[-1,-1]:1,[1,-1]:2,[2,0]:3,[1,1]:4,[-1,1]:5][q]
r=n-i
m=j+((r==-5|r==5)?' LR'[(int)r/5]:['','R','RR','LL','L'][r])+'F'}
if(k=='E')g+=m
if(k=='+'|k=='S'){s(x-2,y,l,n,m)
s(x+2,y,l,n,m)
s(x+1,y+1,l,n,m)
s(x+1,y-1,l,n,m)
s(x-1,y+1,l,n,m)
s(x-1,y-1,l,n,m)}}
s(d[0],d[1],[],1,'')
print(g.min{it.size()}?:"Invalid maze!")}

Безголовая версия:

def map =
        """
  + 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""".split('\n').findAll()
//map =
//        """
// 0 + +
//E + 0 S 0
// 0 0 0 +
//  + + +""".split('\n').findAll()

//map = [""]// TODO remove this, this is type checking only
//map.remove(0)
//reader = System.in.newReader()
//line = reader.readLine()
//while (line != '') {
//    map << line
//    line = reader.readLine()
//}

startAndEnd = [0, 0, 0, 0]
map.eachWithIndex { it, idx ->
    s = it.indexOf('S'); e = it.indexOf('E');
    if (s != -1) {
        startAndEnd[0] = s; startAndEnd[1] = idx
    }
    if (e != -1) {
        startAndEnd[2] = e; startAndEnd[3] = idx
    }
}

def validPaths = []
testMove = { x, y, visited ->// visited is an array of x y pairs that we have already visited in this tree
    if (visited.contains([x, y]) || y >= map.size() || x >= map[y].size() || x < 0 || y < 0)
        return;


    def valueAtPos = map[y][x]
    def newPath = visited + [[x, y]]

    if (valueAtPos == 'E') validPaths += [newPath]
    if (valueAtPos == '+' || valueAtPos == 'S') {
        println "$x, $y passed $valueAtPos"
        testMove(x - 2, y, newPath)
        testMove(x + 2, y, newPath)

        testMove(x + 1, y + 1, newPath)
        testMove(x + 1, y - 1, newPath)

        testMove(x - 1, y + 1, newPath)
        testMove(x - 1, y - 1, newPath)
    }
}

//if (!validPath) invalid()
testMove(startAndEnd[0], startAndEnd[1], [])
println validPaths.join('\n')

//println validPath

def smallest = validPaths.collect {
    def path = ''
    def orintation = 1
    it.inject { old, goal ->
        def chr = map[goal[1]][goal[0]]
        def sub = [goal[0] - old[0], goal[1] - old[1]]
        def newOrin = [[-2, 0]: 0, [-1, -1]: 1, [1, -1]: 2, [2, 0]: 3, [1, 1]:4, [-1, 1]:5][sub]
        def diff = newOrin - orintation// 5L -5R
        def addedPath= ((diff==-5||diff==5)?' LR'[(int)diff/5]:['', 'R', 'RR', 'LL', 'L'][diff]) + 'F'//(diff == 0) ? '' : (diff > 0 ? 'R'*diff : 'L'*(-diff)) + 'F'
//        println "old:$old, goal:$goal chr $chr, orintation $orintation, sub:$sub newOrin $newOrin newPath $addedPath diff $diff"
        path += addedPath
        orintation = newOrin
        goal
    }
    path
}.min{it.size()}
//println "paths:\n${smallest.join('\n')}"
if (smallest)
    println "path $smallest"
else
    println "Invalid maze!"
Дж Аткин
источник
3

C #, 600 574 байта

Завершить программу, принимает ввод из STDIN, вывод в STDOUT.

Редактировать: была ошибка в обработке переноса (не нарушалась ни в одном из приведенных тестовых случаев), которая добавляла 1 байт, поэтому я сделал немного больше игры в гольф, чтобы компенсировать это.

using Q=System.Console;struct P{int p,d;static void Main(){string D="",L;int w=0,W=0,o,n=1;for(;(L=Q.ReadLine())!=null;D+=L)w=(o=(L+="X").Length+1)>w?o:w;for(;W<D.Length;)D=D.Insert(W+1,"".PadLeft(D[W++]>87?w-W%w:0));P[]K=new P[W*6];var T=new string[W*6];P c=K[o=0]=new P{p=D.IndexOf('S')};for(System.Action A=()=>{if(c.p>=0&c.p<W&System.Array.IndexOf(K,c)<0&&D[c.p]%8>0){T[n]=T[o]+L;K[n]=c;n=D[c.p]==69?-n:n+1;}};o<n;o++){c=K[o];L="R";c.d=++c.d%6;A();L="L";c.d=(c.d+4)%6;A();L="F";c=K[o];c.p+=new[]{~w,1-w,2,1+w,w-1,-2}[c.d%6];A();}Q.WriteLine(n>0?"Invalid maze!":T[-n]);}}

Это начинается с чтения на карте, добавляя ( к каждой строке, чтобы он знал, где она заканчивается, и может вернуться назад и добавить множество пробелов, чтобы сделать карту прямоугольной, и с рядом пробелов по правой стороне (это сохраняет мы делаем проверку упаковки, как будет объяснено ниже). Он определяет ширину прямоугольника в некоторой точке и определяет общую длину карты.

Затем он инициализирует все для поиска в ширину. Созданы два массива biggish: один для хранения всех состояний, которые мы должны исследовать в нашем поиске, другой для записи маршрута, который мы выбрали, чтобы добраться до каждого состояния. Начальное состояние добавляется в должный массив с указателями головы и хвоста, предварительно установленными как-то выше. Все 1 проиндексировано.

Затем мы повторяем, пока хвост не врезается в голову, или, по крайней мере, не появляется , что врезался в голову. Для каждого состояния, которое мы посетили, мы пытаемся добавить новое состояние в ту же позицию, где мы поворачиваемся влево или вправо, а затем в то, где мы продвинулись. Направления индексируются, причем начальное направление (по умолчанию 0) соответствует значению «вверх-влево».

Когда мы пытаемся поставить в очередь состояние, оно проверяется с привязкой, но не с проверкой на перенос, из-за столбцов пробелов с правой стороны, на которые указывает «мы можем быть здесь?» проверить (вам не разрешено находиться на пробелах). Если состояние ставится в очередь, мы затем проверяем, находится ли оно в Eячейке, и если оно есть, мы устанавливаем начало очереди как минус, что приводит к выходу из основного цикла, и выдает последнюю строку программы для печати. соответствующий маршрут, а не сообщение об ошибке (которое показывает, если у нас кончаются состояния для расширения (хвост врезается в голову)).

using Q=System.Console;

// mod 8 table (the block of zeros is what we are after - it's everywhere we /can't/ go)
//   0 (space)
// O 0
// X 0
// S 3
// + 3
// E 5

struct P
{
    int p,d;
    static void Main()
    {
        // it's probably a bad thing that I have my own standards for naming this stupid read sequence by now
        string D="", // map
        L; // line/path char

        int w=0, // width
        W=0, // full length
        o, // next state to expand
        n=1; // next state to fill

        for(;(L=Q.ReadLine())!=null;D+=L) // read in map
            w=(o=(L+="X").Length+1)>w?o:w; // assertain max length (and mark end, and remove any need for wrap checking)

        // now we need to add those trailing spaces...
        for(;W<D.Length;)
            D=D.Insert(W+1,"".PadLeft(D[W++]>87?w-W%w:0)); // inject a load of spaces if we hit an X

        P[]K=new P[W*6]; // create space for due states (can't be more states than 6*number of cells)
        var T=new string[W*6]; // create space for routes (never done it this way before, kind of exciting :D)
        P c=K[o=0]=new P{p=D.IndexOf('S')}; // set first state (assignment to c is just to make the lambda shut up about unassigned variables)

        // run bfs
        for(

            System.Action A=()=> // this adds c to the list of states to be expanded, if a whole load of checks pass
            {
                if(//n>0& // we havn't already finished - we don't need this, because we can't win on the first turn, so can't win unless we go forward, which we check last
                   c.p>=0&c.p<W& // c is within bounds
                   System.Array.IndexOf(K,c)<0&& // we havn't seen c yet (the && is to prevent the following lookup IOBing)
                   D[c.p]%8>0) // and we can move here (see table at top of code)
                {
                    T[n]=T[o]+L; // store route
                    K[n]=c; // store state
                    n=D[c.p]==69?-n:n+1; // check if we are at the end, if so, set n to be negative of itself so we know, and can look up the route (otherwise, increment n)
                }
            }

            ;o<n;o++) // o<n also catches n<0
        {
            c=K[o]; // take current
            L="R"; // say we are going right
            c.d=++c.d%6; // turn right
            A(); // go!

            L="L"; // say we are going left
            c.d=(c.d+4)%6; // turn left
            A(); // go!

            L="F"; // say we - you get the picture
            c=K[o];
            c.p+=new[]{~w,1-w,2,1+w,w-1,-2}[c.d%6]; // look up direction of travel (~w = -w-1)
            A();
        }

        // check if we visited the end
        Q.WriteLine(n>0?"Invalid maze!":T[-n]); // if n<0, then we found the end, so spit out the corresponding route, otherwise, the maze is invlida
    }
}

Как и большинство моих поисков по графику на этом сайте, я хорошо использую структуры C #, которые по умолчанию сравниваются по буквальному значению.

VisualMelon
источник
2

Python 2, 703 байта

Не так хорошо, как две другие версии, но, по крайней мере, это работает, ха-ха. Установите Mв лабиринт.

Поскольку у меня нет опыта в решении лабиринтов, он просто использует подход грубой силы, где он найдет все возможные решения, которые не включают в себя пересечение. Он рассчитывает ходы из самых коротких, а затем выбирает из этого самый короткий результат.

z=zip;d=z((-1,1,-2,2,-1,1),(-1,-1,0,0,1,1));E=enumerate;D={};t=tuple;o=list;b=o.index
for y,i in E(M.split('\n')):
 for x,j in E(o(i)):
  c=(x,y);D[c]=j
  if j=='S':s=c
  if j=='E':e=c
def P(s,e,D,p):
 p=o(p);p.append(s);D=D.copy();D[s]=''
 for i in d:
  c=t(x+y for x,y in z(s,i))
  if c not in p and c in D:
   if D[c]=='E':L.append(p+[c])
   if D[c]=='+':P(c,e,D,p)
def R(p):
 a=[0,1,3,5,4,2];h=d[0];x=p[0];s=''
 for c in p[1:]:
  r=t(x-y for x,y in z(c,x));n=0
  while h!=r:n+=1;h=d[a[(b(a,b(d,h))+1)%6]]
  s+=['L'*(6-n),'R'*n][n<3]+'F';x=t(x+y for x,y in z(x,h))
 return s
L=[];P(s,e,D,[])
try:l=len(min(L))
except ValueError:print"Invalid maze!"
else:print min([R(i)for i in L if len(i)==l],key=len)

Грязная негольфированная версия:

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
     """
directions = [(-1, -1), (1, -1),
              (-2, 0), (2, 0),
              (-1, 1), (1, 1)]


maze_dict = {}
maze_lines = maze.split('\n')
for y, row in enumerate(maze_lines):
    if row:
        for x, item in enumerate(list(row)):
            coordinates = (x, y)
            maze_dict[coordinates] = item
            if item == 'S':
                start = coordinates
            elif item == 'E':
                end = coordinates

list_of_paths = []


def find_path(start, end, maze_dict, current_path=None):
    if current_path is None:
        current_path = []
    current_path = list(current_path)
    current_path.append(start)
    current_dict = maze_dict.copy()
    current_dict[start] = '0'

    for direction in directions:
        new_coordinate = (start[0] + direction[0], start[1] + direction[1])

        if new_coordinate in current_path:
            pass

        elif new_coordinate in current_dict:
            if current_dict[new_coordinate] == 'E':
                list_of_paths.append(current_path + [new_coordinate])
                break
            elif current_dict[new_coordinate] == '+':
                find_path(new_coordinate, end, current_dict, current_path)


find_path(start, end, maze_dict)


def find_route(path):

    heading_R = [0, 1, 3, 5, 4, 2]
    heading = (-1, -1)
    current_pos = path[0]
    current_heading = directions.index(heading)
    output_string = []
    for coordinate in path[1:]:
        required_heading = (coordinate[0] - current_pos[0], coordinate[1] - current_pos[1])

        count_R = 0
        while heading != required_heading:
            count_R += 1
            heading_index = directions.index(heading)
            heading_order = (heading_R.index(heading_index) + 1) % len(heading_R)
            heading = directions[heading_R[heading_order]]

        if count_R:
            if count_R > 3:
                output_string += ['L'] * (6 - count_R)
            else:
                output_string += ['R'] * count_R

        output_string.append('F')
        current_pos = (current_pos[0] + heading[0], current_pos[1] + heading[1])
    return ''.join(output_string)


routes = []
try:
    min_len = len(min(list_of_paths))
except ValueError:
    print "Invalid maze!"
else:
    for i in list_of_paths:
        if len(i) == min_len:
            routes.append(find_route(i))

    print 'Shortest route to end: {}'.format(min(routes, key=len))
Питер
источник
Вы можете заменить if heading != required_heading: while heading != required_heading: простоwhile heading != required_heading:
J Atkin
Да, спасибо, ха-ха, я заметил несколько вещей, в том числе, что, когда делал версию для гольфа, просто не обновлял оригинальный код, я сделаю это сейчас, так как мне только что удалось сбрить еще несколько символов
Питер
Ницца! (заполнение 15 символов в минуту)
J Аткин
<Это нераспознанный HTML-тег, так что SE не похоже.>
CalculatorFeline