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.

— Maltysen
źródło

Prawdopodobnie warto wyraźnie stwierdzić, że problem został wydany na licencji CC-BY-NA-SA, a zatem remiks jest koniecznie na tej samej licencji.

— Nick Kennedy,

Czy otrzymujemy wartość solvedwyjściową no exit? Jeśli tak, proszę podać to w regulaminie, nie tylko w przypadkach testowych!

— wastl

„ Twojemu programowi nie wolno dwa razy poruszać się w tym samym kierunku z tego samego kwadratu. ” Dwa pytania dotyczące tego: 1. Powiedzmy, że jestem na pozycji x,yi idę upz odpowiedzią wall, a następnie rightz odpowiedzią wall, czy mogę spróbować upponownie, czy są dostępne tylko lefti downnadal, ponieważ nie przeprowadziłem się jeszcze z tego kwadratu?

— Kevin Cruijssen

2. Powiedzmy, że mam ten labirynt . Z tym przepływem: w prawo (ok); w porządku); prawa (ściana); w górę (ok) ; w górę (ok); w górę (ściana); lewy (ściana); w dół (ok); w dół (ok); w dół (ok); w dół (ok); w dół (ściana); prawa (ściana); w górę (ok); w górę (ok); Czy teraz mogę znowu iść w górę, mimo że już wcześniej robiłem to z tego konkretnego kwadratu (na odważnym)?

— Kevin Cruijssen

@KevinCruijssen W mojej odpowiedzi nie śledzę wprost, skąd pochodzę. Zamiast tego śledzę wszystkie kierunki, które zostały przetworzone na każdym kwadracie i najpierw próbuję niezwiedzonych kwadratów. Po wypróbowaniu wszystkich nieodwiedzonych kwadratów jedynym legalnym ruchem jest to, skąd przybyłem (już odwiedziłem, ale nie w tym kierunku).

— Arnauld

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

Rozwiń fragment kodu

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)

— Arnauld
źródło

Interactive Maze Solver