Bob został porwany i utknął w labiryncie. Twoim zadaniem jest pomóc mu znaleźć wyjście. Ale ponieważ jest to bardzo mroczny i przerażający labirynt, nic nie widzi. Czuje ściany tylko wtedy, gdy do nich podbiega, i wie, kiedy znalazł wyjście, ale nic więcej nie wie.

Ponieważ musi on uruchamiać Twój program według pamięci, musi on być jak najkrótszy.

Uwaga: wziąłem ten problem z http://acmgnyr.org/year2016/problems.shtml , ale nieco go dostosowałem i sam napisałem program oceniania / przypadki testowe.

Specyfikacja

• Jest to problem interaktywny, więc program wypisze ruchy na standardowe wyjście i przyjmie odpowiedzi ze standardowego wejścia.
• Twój program może jedno wyjście z ruchów right, left, down, up.
• Otrzyma wtedy jako dane wejściowe jedno z poniższych:
  • wall- oznacza to, że Bob uderzył w ścianę. Bob pozostanie w tym samym miejscu.
  • solved- Bob znalazł wyjście! Twój program powinien teraz również wyjść bez drukowania czegokolwiek innego.
  • ok - Bob był w stanie poruszać się w danym kierunku.
• Jeśli labirynt nie ma wyjścia, twój program powinien wypisać, no exitaby Bob wiedział, że powinien się poddać. Twój program powinien następnie wyjść bez drukowania niczego innego.
• Ponieważ Bobowi spieszy się z wydostaniem się, twój program nie powinien wykonywać żadnych obcych ruchów. Innymi słowy, twój program nie może poruszać się dwa razy w tym samym kierunku z tego samego kwadratu .
• To jest golf golfowy , więc wygrywa najkrótszy program!

Przykłady

W poniższych przykładach Sjest kwadratem początkowym, Xwyjściem, #ścianą, a spacje są prawidłowymi kwadratami. Ponieważ nie ma jednej poprawnej odpowiedzi, są to tylko przykładowe przebiegi rozwiązania. Zauważ też, że rysunki labiryntu są właśnie tam, abyś mógł je zobaczyć, a twój program nie otrzyma ich jako danych wejściowych.

########
#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

Program sprawdzający

• Napisałem narzędzie do sprawdzania rozwiązań w Pythonie. Można go znaleźć na https://gist.github.com/Maltysen/f0186019b3aa3812d812f8bb984fee19 .
• Uruchom to jak python mazechecker.py ./mazesolver.
• Testuje twój program na wszystkich labiryntach w folderze o nazwie mazes.
• Labirynty znajdują się w osobnych plikach w tym samym formacie od góry.
• Sprawdza wszystkie warunki wymienione powyżej i powiadamia cię, jeśli Twoje rozwiązanie narusza którekolwiek.
• Możesz wydrukować dodatkowe informacje diagnostyczne za pomocą python mazechecker.py -d ./mazesolver.
• Możesz znaleźć spakowany mazesfolder tutaj . Możesz także dodać własne, jeśli chcesz.

JavaScript (ES6),  180  174 bajtów

Wykorzystuje prompt()do wyprowadzenia kierunku i odzyskania wyniku.

_=>(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])

Wypróbuj online! (z automatycznymi I / O)

Interaktywny fragment kodu

OSTRZEŻENIE : ten kod będzie wyświetlał okno dialogowe zachęty (), dopóki nie zostanie wprowadzone słowo „rozwiązany” lub funkcja zorientuje się, że w ogóle nie ma wyjścia.

(
_=>(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])
)()

Skomentował

_ => (                      // 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)