Löse ein Eislabyrinth

19

Eislabyrinthe sind seit ihrem Debüt in Pokémon Gold und Silber eine meiner Lieblingsheftklammern bei Pokémon- Spielen. Ihre Aufgabe wird es sein, ein Programm zu entwickeln, das diese Art von Problemen löst.

Eislabyrinthe bestehen hauptsächlich aus Eis, wie der Name schon sagt. Sobald sich der Spieler auf Eis in eine Richtung bewegt, bewegt er sich weiter in diese Richtung, bis er auf ein Hindernis stößt. Es gibt auch Boden, der frei bewegt werden kann und jeden Spieler davon abhält, sich darüber zu bewegen. Das letzte Hindernis ist Stein. Der Stein kann nicht das gleiche Feld wie der Spieler einnehmen. Wenn der Spieler versucht, sich darin zu bewegen, hört er auf, sich zu bewegen, bevor er kann.

Sie erhalten einen zweidimensionalen Wertebehälter, z. B. eine Liste mit Listen oder eine durch Zeilenumbrüche getrennte Zeichenfolge, die drei unterschiedliche Werte für jeden der drei Bodentypen (Eis, Boden und Stein) enthält. Sie erhalten außerdem zwei Paare (oder andere gleichwertige zwei Wertecontainer), die eine Start- und Zielkoordinate im Labyrinth angeben. Diese können null oder eins sein.

Sie müssen eine Liste von Zügen ausgeben (4 verschiedene Werte mit einer Bijektion auf N, E, S, W), die den Spieler veranlassen würden, am Ende anzukommen, wenn sie ausgeführt werden.

Die Eingabe hat immer einen geschlossenen Steinumfang um das Labyrinth, sodass Sie sich keine Sorgen machen müssen, dass der Spieler das Labyrinth verlässt

Dies ist Code-Golf, so dass die wenigsten Bytes gewinnen

Testfälle

Hier .wird Eis dargestellt, ~wird Boden dargestellt und Owird ein Stein dargestellt. Koordinaten sind 1 indiziert. Jeder Buchstabe in der Lösung stellt die Richtung dar, die mit diesem Buchstaben beginnt (z. B. N= Norden).

Eingang

OOOOO
OO.OO
O...O
OOOOO

Start : 3,3
End   : 3,2

Ausgabe

N

Eingang

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

Ausgabe

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

Eingang

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

Ausgabe

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

Eingang

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

Ausgabe

E,E,E,E,E,S,S,E,N,W,S,E,N,N,N
code-golf grid path-finding maze Weizen-Assistent
quelle
Wird die Eingabe immer mindestens eine gültige Lösung enthalten?
Pavel
@Pavel Das kannst du annehmen.
Weizen-Zauberer
Sind die Testfälle (Zeile, Spalte) oder (Spalte, Zeile)? 1 oder 0 indiziert? Zählen die Plattenkanten als Wände?
MildlyMilquetoast
5
Related
Peter Taylor
2
@busukxuan Sie können dauerhaft im Labyrinth gefangen sein (siehe Testfall 1)
Weizen-Assistent

Antworten:

4

Mathematica, 247 Bytes

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

Mit Zeilenumbrüchen:

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

Meine unmittelbare Idee war es, die Eis- und Bodenpositionen als Knoten in einem Diagramm mit gerichteten Kanten darzustellen, die legalen Bewegungen entsprechen, und dann zu verwenden FindPath. Man könnte denken, dass die Bestimmung der rechtlichen Schritte der einfache Teil und das Finden der Lösung der schwierige Teil wäre. Für mich war es das Gegenteil. Offen für Vorschläge zur Berechnung der Kanten.

Das erste Argument #ist ein 2D-Array, in dem 0Eis, 1Boden und 2Stein dargestellt werden.

Das zweite Argument #2und das dritte Argument #3sind die Start- bzw. Endpunkte in der Form {row,column}.

ist das 3-Byte-Zeichen U+F4A1für den privaten Gebrauch \[Function].

Erläuterung

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

Definiert eine Funktion, pdie eine Liste xder Formulare {row,column}und Ausgaben annimmt #[[row,column]]. dh der Eis- / Boden- / Steinwert bei dieser Koordinate.

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

Definiert eine Funktion, mdie eine Startposition cund einen Richtungsvektor annimmt vund rekursiv festlegt, wo Sie enden würden. Wenn c+ves Eis gibt, gleiten wir von diesem Punkt aus weiter, sodass es zurückkehrt m[c+v,v]. Wenn c+vErde ist, dann bewegen wir uns zu c+vund halten an. Andernfalls (wenn c+vStein oder außerhalb der Grenzen), bewegen Sie sich nicht. Beachten Sie, dass dies nur für Eis- oder Bodenpositionen vorgesehen ist.

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

Definiert die Liste gder Eis- und Bodenpositionen ( pWert kleiner als 2).

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

Definiert eine Funktion , adie eine Startposition einnimmt cund gibt die Ergebnisse des Bewegens in den {1,0}, {-1,0}, {0,1}, und {0,-1}Richtungen. Möglicherweise liegt eine gewisse Redundanz vor. Dies setzt wiederum voraus, dass dies cEis oder Erde entspricht.

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

Definiert die Liste eder gerichteten Kanten, die zulässige Bewegungen darstellen. Berechnen Sie für jede Position #in gdie Kantentabelle #->cfür jede cin a@#. Da wir dann für jede Position eine Unterliste haben #, reduziere ich die erste Ebene. Es kann einige Schleifen und mehrere Kanten geben.

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

Graph[e]ist die Grafik, in der die Knoten die legalen Positionen (Eis oder Boden) und die Kanten legale Bewegungen darstellen (möglicherweise gegen einen Stein stoßen und sich nicht bewegen). Wir verwenden dann FindPath, um einen Pfad von #2bis zu finden , #3der als Liste von Knoten dargestellt wird. Da FindPathzusätzliche Argumente erforderlich sind, um mehr als einen Pfad zu finden, ist das Ergebnis tatsächlich eine Liste, die einen einzelnen Pfad enthält. Daher verwende ich das erste Element [[1]]. Dann nehme ich nacheinander Differencesdie Koordinaten und Normalizediese. Also oben ist {-1,0}, unten ist {1,0}, rechts ist {0,1}und links ist {0,-1}.

Testfälle

Bildbeschreibung hier eingeben

Bildbeschreibung hier eingeben

Bildbeschreibung hier eingeben

Bildbeschreibung hier eingeben

Bildbeschreibung hier eingeben

Genisis
quelle
4

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")

Verwenden eines BFS , wie ich es getan habe, um diese verwandte Herausforderung zu lösen

Eingabe
Die Labyrinthkarte ist eine mehrzeilige Zeichenfolge mit Ooder 0für Stein 8für Erde und einer beliebigen Ziffer ungleich Null, die für Eis kleiner als 8 ist ( 7sehen Sie gut aus).
Start- und Endposition sind nullbasiert.

Ausgabe
Eine Liste von Offsets, wobei -1 ist W, 1 ist E, negativ kleiner als -1 ist Nund positiv größer als 1 istS

Weniger golfen

(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
}

Prüfung

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>
Erweitern Sie das Snippet

edc65
quelle