Rozwiąż lodowy labirynt

Lodowe labirynty to jedna z moich ulubionych gier Pokémon od czasu ich debiutu w Pokémon Gold i Silver. Twoim zadaniem będzie stworzenie programu, który rozwiąże tego rodzaju problemy.

Lodowe labirynty składają się przede wszystkim, jak sama nazwa wskazuje, z lodu. Gdy gracz porusza się w kierunku na lodzie, będzie kontynuować ruch w tym kierunku, dopóki nie zderzy się z jakąś przeszkodą. Istnieje również gleba, którą można swobodnie przesuwać, co powstrzyma każdego gracza. Ostatnią przeszkodą jest kamień. Kamień nie może zajmować tego samego pola co gracz, a jeśli gracz spróbuje się do niego przenieść, przestanie się nim poruszać, zanim będzie mógł.

Otrzymasz dwuwymiarowy pojemnik wartości, taki jak lista list lub ciąg znaków oddzielone znakami nowej linii, zawierający 3 różne wartości dla każdego z 3 rodzajów podłóg (Lód, Gleba i Kamień). Otrzymasz również dwie pary (lub inne równoważne dwa kontenery wartości), które wskazują współrzędną początkową i bramkową w labiryncie. Mogą to być zero lub jeden indeks.

Musisz wypisać listę ruchów (4 odrębne wartości z wstrzyknięciem na N, E, S, W), które spowodują, że gracz dotrze do końca, gdy zostanie wykonany.

Wejście zawsze będzie miało zamknięty obwód kamienia wokół labiryntu, więc nie musisz się martwić, że gracz wyjdzie z labiryntu

To jest golf golfowy, więc wygrywa najmniej bajtów

Przypadki testowe

Tutaj .będzie reprezentować lód, ~będzie reprezentować glebę i Obędzie reprezentować kamień. Współrzędne są indeksowane 1. Każda litera w rozwiązaniu reprezentuje kierunek rozpoczynający się od tej litery (np. N= Północ)

Wejście

OOOOO
OO.OO
O...O
OOOOO

Start : 3,3
End   : 3,2

Wynik

Wejście

OOOOOOOOOOOOOOOOO
O........O.....OO
O...O..........OO
O.........O....OO
O.O............OO
OO.......O.....OO
O.............OOO
O......O.......~O
O..O...........~O
O.............OOO
O.......O......OO
O.....O...O....OO
O..............OO
OOOOOOOOOOOOOO~~O
OOOOOOOOOOOOOOOOO

Start : 15,12
End   : 16,8

Wynik

N,W,N,E,N,E,S,W,N,W,S,E,S,E,N,E,N

Wejście

OOOOOOOOOOOOOOOO
O~~~~~OOOOO~~~~O
O~~O~OOOOOOO~~OO
O...O..........O
O........O.....O
O..............O
OO.............O
O.............OO
O....~....O....O
O..............O
O..............O
OOOOOOOOOOOOOOOO

Start : 2,2
End   : 14,3

Wynik

E,S,S,W,N,E,N

Wejście

OOOOOOOOOOOOOOOOOOO
O~~~~~~~OOOOOOOOOOO
O~~~~...OOOOOOOOOOO
OO~O~..OOOOOOOOOOOO
O..OO.............O
O..............O..O
O....O............O
O.O............~..O
O........OOOO.....O
O.......OOOOO.....O
O.......O~~~O.....O
O.......~~~~~.....O
O.......~~~~~.....O
O..........O......O
O..O..~...........O
O...............O.O
O.....O...........O
O.................O
OOOOOOOOOOOOOOOOOOO

Start : 2,2
End   : 11,11

Wynik

E,E,E,E,E,S,S,E,N,W,S,E,N,N,N

code-golf grid path-finding maze Kreator pszenicy
źródło

Czy dane wejściowe zawsze będą zawierały co najmniej jedno prawidłowe rozwiązanie?

Pavel

@Pavel Możesz to założyć.

Wheat Wizard

Czy przypadki testowe (wiersz, kolumna) czy (kolumna, wiersz)? 1 czy 0 indeksowanych? Czy krawędzie deski liczą się jako ściany?

MildlyMilquetoast,

Powiązane

Peter Taylor

@busukxuan Możesz zostać na stałe uwięziony w labiryncie (patrz przypadek testowy 1)

Wheat Wizard

Odpowiedzi:

Mathematica, 247 bajtów

(p=x#[[##&@@x]];m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c];g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};e=Flatten[Table[#->c,{c,a@#}]&/@g,1];Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]])&

Z podziałami linii:

(
p=x#[[##&@@x]];
m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c];
g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];
a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};
e=Flatten[Table[#->c,{c,a@#}]&/@g,1];
Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]]
)&

Mój bezpośredni pomysł polegał na przedstawieniu położenia lodu i gleby jako węzłów na wykresie z ukierunkowanymi krawędziami odpowiadającymi legalnym ruchom, a następnie użycia FindPath. Można by pomyśleć, że ustalenie legalnych ruchów byłoby łatwą częścią, a znalezienie rozwiązania byłoby trudną częścią. Dla mnie było odwrotnie. Otwórz się na sugestie dotyczące obliczania krawędzi.

Pierwszy argument #to tablica 2D, w której 0reprezentuje lód, 1reprezentuje glebę i 2kamień.

Drugi argument #2i trzeci argument #3są odpowiednio punktami początkowymi i końcowymi w formie {row,column}.

jest 3-bajtowym znakiem prywatnego użytku U+F4A1reprezentującym \[Function].

Wyjaśnienie

p=x#[[##&@@x]];

Definiuje funkcję, pktóra przyjmuje listę xformy {row,column}i wyników #[[row,column]]; tj. wartość lodu / gleby / kamienia przy tej współrzędnej.

m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c]

Definiuje funkcję, mktóra przyjmuje pozycję początkową ci wektor kierunku vi rekurencyjnie określa, gdzie miałbyś się skończyć. Jeśli c+vjest lodem, kontynuujemy ślizganie się od tego miejsca, więc powraca m[c+v,v]. Jeśli c+vjest to gleba, ruszamy się c+vi zatrzymujemy. W przeciwnym razie (jeśli c+vjest kamień lub poza granicami), nie ruszasz się. Należy pamiętać, że jest to przeznaczone tylko do wywoływania na lodzie lub w glebie.

g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];

Definiuje listę gpozycji lodu i gleby ( pwartość mniejsza niż 2).

a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};

Definiuje funkcję a, która pobiera pozycję wyjściową ci zwraca wyniki poruszania się w {1,0}, {-1,0}, {0,1}oraz {0,-1}kierunkach. Może wystąpić pewna nadmiarowość. Ponownie zakłada się, że codpowiada to lodzie lub glebie.

e=Flatten[Table[#->c,{c,a@#}]&/@g,1];

Definiuje listę eskierowanych krawędzi reprezentujących legalne ruchy. Dla każdej pozycji #w g, obliczyć tabelę krawędziach #->cdla każdego cin a@#. Ponieważ skończy się z podlistą dla każdej pozycji #, spłaszczam pierwszy poziom. Mogą występować pewne pętle i wiele krawędzi.

Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]]

Graph[e]to wykres, na którym węzły to pozycje prawne (lód lub gleba), a krawędzie reprezentują legalne ruchy (możliwe, że zderzają się z kamieniem i nie poruszają się). Następnie używamy FindPathdo znalezienia ścieżki od #2do #3reprezentowanej jako lista węzłów. Ponieważ FindPathmożna wziąć dodatkowe argumenty, aby znaleźć więcej niż jedną ścieżkę, wynikiem będzie faktycznie lista zawierająca jedną ścieżkę, więc biorę pierwszy element za pomocą [[1]]. Następnie biorę kolejno Differenceswspółrzędne i Normalizeje. Tak więc góra jest {-1,0}, dół jest {1,0}, prawo jest, {0,1}a lewa jest {0,-1}.

Przypadki testowe

ngenisis
źródło

JavaScript (ES6) 180 183

(m,[x,y],[t,u],o=~m.search`
`,s=[[x-y*o,[]]],k=[])=>eval("for(i=0;[p,l]=s[i++],k[p]=t-u*o-p;)[-1,o,1,-o].map(d=>k[q=(M=p=>+m[p+=d]?m[p]<8?M(p):p:p-d)(p)]||s.push([q,[...l,d]]));l")

Używając BFS , tak jak zrobiłem, aby rozwiązać to powiązane wyzwanie

Wejście
Mapa labiryntu jest ciągiem wielowierszowym, używającym Olub 0do kamienia, 8do gleby i każdej niezerowej cyfry mniejszej niż 8 dla lodu ( 7dobrze wygląda).
Pozycja początkowa i końcowa są zerowane.

Dane wyjściowe
Lista przesunięć, gdzie -1 to W, 1 to E, ujemna mniej niż -1 to Ni dodatnia większa niż 1 toS

Mniej golfa

(m,[x,y],[t,u])=>{
  o=~m.search`\n`
  s=[[x-y*o,[]]]
  k=[]
  for(i=0; [p,l]=s[i++], k[p]=1, t-u*o != p;)
  {
    [-1,o,1,-o].map(d=>(
      M=p=>+m[p+=d] ? m[p]<8 ? M(p) : p : p-d,
      q=M(p),
      k[q]||s.push([q,[...l,d]])
    ))
  }
  return l
}

Test

Solve=
(m,[x,y],[t,u],o=~m.search`
`,s=[[x-y*o,[]]],k=[])=>eval("for(i=0;[p,l]=s[i++],k[p]=t-u*o-p;)[-1,o,1,-o].map(d=>k[q=(M=p=>+m[p+=d]?m[p]<8?M(p):p:p-d)(p)]||s.push([q,[...l,d]]));l")

function Go(maze) {
  var map = maze.textContent;
  var [sx,sy, dx,dy] = map.match(/\d+/g)
  --sx, --sy // zero based
  --dx, --dy // zero based
  map = map.split('\n').slice(1).join('\n') // remove first line
  var result = Solve(map.replace(/\./g, 7).replace(/~/g, 8), [sx,sy], [dx,dy])
  S.textContent = result
  Animate(maze, map, result, sx, sy)
}

function Display(maze, map, pos) {
  var row0 = maze.textContent.split('\n')[0]
  map = [...map]
  map[pos] = '☻'
  maze.textContent = row0+'\n'+map.join('')
}

function Animate(maze, map, moves, x, y) {
  console.log('A',moves)
  var offset = map.search('\n')+1
  var curPos = x + offset * y
  var curMove = 0
  var step = _ => {
    Display(maze, map, curPos)
    if (curMove < moves.length) 
    {
      curPos += moves[curMove]
      if (map[curPos] == 'O')
      {
        curPos -= moves[curMove]
        ++curMove
      }  
      else 
      {
        if (map[curPos] == '~') {
          ++curMove
        }
      }
      setTimeout(step, 100)
    }
    else
      setTimeout(_=>Display(maze,map,-1),500)
  }
  step()
}

td { 
  border: 1px solid #888;
}

Select maze<pre id=S></pre>
<table cellspacing=5><tr>
<td valign=top><input type=radio name=R onclick='Go(M1)'><br>
<pre id=M1>3,3 to 3,2  
OOOOO
OO.OO
O...O
OOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M2)'><br>
<pre id=M2>15,12 to 16,8
OOOOOOOOOOOOOOOOO
O........O.....OO
O...O..........OO
O.........O....OO
O.O............OO
OO.......O.....OO
O.............OOO
O......O.......~O
O..O...........~O
O.............OOO
O.......O......OO
O.....O...O....OO
O..............OO
OOOOOOOOOOOOOO~~O
OOOOOOOOOOOOOOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M3)'><br>
<pre id=M3>2,2 to 14,3
OOOOOOOOOOOOOOOO
O~~~~~OOOOO~~~~O
O~~O~OOOOOOO~~OO
O...O..........O
O........O.....O
O..............O
OO.............O
O.............OO
O....~....O....O
O..............O
O..............O
OOOOOOOOOOOOOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M4)'><br>
<pre id=M4>2,2 to 11,11
OOOOOOOOOOOOOOOOOOO
O~~~~~~~OOOOOOOOOOO
O~~~~...OOOOOOOOOOO
OO~O~..OOOOOOOOOOOO
O..OO.............O
O..............O..O
O....O............O
O.O............~..O
O........OOOO.....O
O.......OOOOO.....O
O.......O~~~O.....O
O.......~~~~~.....O
O.......~~~~~.....O
O..........O......O
O..O..~...........O
O...............O.O
O.....O...........O
O.................O
OOOOOOOOOOOOOOOOOOO</pre></td>
</tr></table>

Rozwiń fragment kodu

edc65
źródło