Интерактивный Лабиринт Солвер

13

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

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

Примечание: я взял эту проблему с http://acmgnyr.org/year2016/problems.shtml , но немного ее адаптировал и сам написал программу / тестовые задания для судей.

Спецификация

  • Это интерактивная проблема, поэтому ваша программа будет выводить ходы на стандартный вывод и получать ответы от стандартного ввода.
  • Ваша программа может выводить один из ходов right, left, down,up .
  • Затем он получит в качестве входных данных одно из следующих:
    • wall- это значит, что Боб врезался в стену. Боб останется на том же месте.
    • solved- Боб нашел выход! Теперь ваша программа также должна выйти без печати.
    • ok - Боб смог двигаться в заданном направлении.
  • Если у лабиринта нет выхода, ваша программа должна вывести no exit чтобы Боб знал, что он должен сдаться. Ваша программа должна выйти без печати чего-либо еще.
  • Поскольку Боб спешит уйти, ваша программа не должна делать никаких посторонних шагов. Другими словами, ваша программа не может двигаться в одном направлении от одного квадрата дважды .
  • Это код-гольф , поэтому выигрывает самая короткая программа!

Примеры

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

########
#S     #
###### #
     # #
     #X#

right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              solved

#####
# S #
#####

right
              ok
right
              wall
down
              wall
up
              wall
left
              ok
down
              wall
up
              wall
left
              ok
down
              wall
up
              wall
left
              wall
right
              ok
no exit
              solved

###############################
#S                            #
##############       ###      #
             #       #X#      #
             #                #
             ##################

right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              ok
down
              ok
down
              ok
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              ok
down
              ok
down
              ok
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              wall
down
              ok
left
              wall
down
              ok
left
              ok
down
              wall
up
              wall
left
              ok
down
              wall
up
              solved

Программа проверки

  • Я написал проверку решения в Python. Вы можете найти его по адресу https://gist.github.com/Maltysen/f0186019b3aa3812d812f8bb984fee19 .
  • Запустите это как python mazechecker.py ./mazesolver.
  • Он проверит вашу программу на всех лабиринтах в папке с именем mazes.
  • Лабиринты находятся в отдельных файлах в том же формате сверху.
  • Он проверяет все условия, перечисленные выше, и уведомляет вас, если ваше решение нарушает какие-либо.
  • Вы можете распечатать дополнительную диагностическую информацию с python mazechecker.py -d ./mazesolver .
  • Вы можете найти архивную mazesпапку здесь . Вы также можете добавить свои собственные, если хотите.
code-golf puzzle-solver maze interactive Maltysen
источник
1
Вероятно, стоит явно указать, что проблема была выпущена под лицензией CC-BY-NA-SA, и поэтому ваш ремикс обязательно под той же лицензией.
Ник Кеннеди
3
Мы получаем solvedпри выводе no exit? Если да, укажите это в правилах, а не только в тестовых случаях!
wastl
1
« Вашей программе не разрешено перемещаться в одном и том же направлении от одного и того же квадрата дважды». Два вопроса относительно этого: 1. Допустим, я нахожусь на позиции x,yи иду upс ответом wall, затем rightс ответом снова wall, могу ли я upповторить попытку , или только leftи downвсе еще доступны, так как я еще не переехал с этой площади?
Кевин Круйссен
1
2. Допустим, у меня есть этот лабиринт . С этим потоком: правильно (хорошо); правильно (хорошо); правый (стена); вверх (ок) ; вверх (ок); вверх (стена); левый (стена); вниз (ок); вниз (ок); вниз (ок); вниз (ок); вниз (стена); правый (стена); вверх (ок); вверх (ок); Разрешено ли мне снова подниматься, хотя я уже сделал это с этой конкретной площади раньше (на жирном)?
Кевин Круйссен
1
@KevinCruijssen Я не отслеживаю, откуда я пришел, в своем ответе. Вместо этого я отслеживаю все направления, которые были обработаны на каждом квадрате, и сначала пробую не посещенные квадраты. Когда все непосещенные квадраты были опробованы, единственный оставшийся законный ход - это то, откуда я пришел (уже посетил, но не в этом направлении).
Арно

Ответы:

7

JavaScript (ES6),  180  174 байта

Используется prompt()для вывода направления и получения результата.

_=>(g=p=>[...'012301234'].some((d,i)=>g[p]>>d&1|i<4&g[P=[p[0]+(d-2)%2,p[1]+~-d%2]]>0?0:(r=prompt('up/left/down/right/no exit'.split`/`[g[p]|=1<<d,d]))<'s'?g(P):r<'t'))([0,0])

Попробуйте онлайн! (с автоматизированным вводом / выводом)

Интерактивный фрагмент

ВНИМАНИЕ : этот код будет отображать диалоговое окно с приглашением () до тех пор, пока не будет введено «решено» или функция не обнаружит, что выхода нет вообще.

(
_=>(g=p=>[...'012301234'].some((d,i)=>g[p]>>d&1|i<4&g[P=[p[0]+(d-2)%2,p[1]+~-d%2]]>0?0:(r=prompt('up/left/down/right/no exit'.split`/`[g[p]|=1<<d,d]))<'s'?g(P):r<'t'))([0,0])
)()
Развернуть фрагмент

комментарии

_ => (                      // anonymous function taking no argument
  g = p =>                  // g = recursive function taking the current position p = [x, y]
    [ ...'0123',            // i<4  : try to move on squares that haven't been visited yet
      ...'0123',            // 3<i<8: try to go back to where we initially came from
      ...'4'                // i=8  : if everything failed, there must be no exit
    ].some((d, i) =>        // for each direction d at index i:
      g[p] >> d & 1         //   if this direction was already tried at this position
      | i < 4 &             //   or i is less than 4 and
      g[P = [               //   the square at the new position P = [X, Y] with:
        p[0] + (d - 2) % 2, //     X = x + dx[d]
        p[1] + ~-d % 2      //     Y = y + dy[d]
      ]] > 0 ?              //   was already visited:
        0                   //     abort
      : (                   //   else:
        r = prompt(         //     output the direction:
          [ 'up',           //       0 = up
            'left',         //       1 = left
            'down',         //       2 = down
            'right',        //       3 = right
            'no exit'       //       4 = no exit
          ][                //
            g[p] |= 1 << d, //       mark this direction as used
            d               //       d = actual index of the string to output
          ]                 //     r = result of prompt()
        )                   //
      ) < 's' ?             //     if r = 'ok':
        g(P)                //       do a recursive call at the new position
      :                     //     else:
        r < 't'             //       yield true if r = 'solved' or false if r = 'wall'
    )                       // end of some()
)([0, 0])                   // initial call to g at (0, 0)
Arnauld
источник