Hol mich hier raus

12

Herausforderung

Bei gegebener Gittergröße, Hindernisposition, Spielerposition und Zielposition besteht Ihre Aufgabe darin, einen Weg für den Spieler zu finden, um zum Ziel zu gelangen und die Hindernisse gleichzeitig zu umgehen (falls erforderlich).

Bildbeschreibung hier eingeben


Eingang

  • N : GittergrößeN x N
  • P : Position des Spielers[playerposx, playerposy]
  • T : Zielposition[targetposx, targetposy]
  • O : Positionen der Hindernisse[[x1, y1], [x2, y2],...,[xn, yn]]

Ausgabe

Pfad : Ein Pfadspieler kann das Ziel erreichen[[x1, y1], [x2, y2],...,[xn, yn]]


Regeln

  1. Der Punkt [0,0]befindet sich in der oberen linken Ecke des Rasters.
  2. Die Position des Spielers befindet sich immer auf der linken Seite des Gitters.
  3. Die Position des Ziels befindet sich immer auf der rechten Seite des Gitters.
  4. Das Gitter wird immer mindestens ein Hindernis haben.
  5. Sie können davon ausgehen, dass kein Hindernis den Spieler oder die Zielposition überlappt.
  6. Sie müssen nicht unbedingt den minimalen Pfad finden.
  7. Der Spieler kann sich nur nach links, rechts, oben und unten bewegen, nicht diagonal.
  8. Sie können die Eingabe auf jede bequeme Weise vornehmen.
  9. Sie können davon ausgehen, dass es immer einen Weg gibt, über den der Spieler zum Ziel gelangt.
  10. Offensichtlich gibt es für jede Eingabe mehrere gültige Pfade. Wählen Sie einen aus.
  11. Angenommen N > 2, das Gitter wird mindestens so sein 3 x 3.

Beispiele

Input: 9, [6, 0], [3, 8], [[0, 5], [2, 2], [6, 4], [8, 2], [8, 7]]
Mögliche Ausgabe:[[6, 0], [6, 1], [6, 2], [6, 3], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [4, 8], [3, 8]]

Input: 6, [1, 0], [3, 5], [[1, 2], [2, 5], [5, 1]]
Mögliche Ausgabe:[[1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 5]]


Hinweis

Beachten Sie, dass dies Xfür Zeilen und YSpalten gilt. Verwechseln Sie sie nicht mit den Koordinaten in einem Bild.

Bearbeiten

Wie @digEmAll wies darauf hin, aufgrund Regeln #2und #3, playerY = 0und targetY = N-1. Also, wenn Sie möchten, können Sie nur playerXund und als Eingabe nehmen targetX(wenn das Ihren Code kürzer macht).

DimChtz
quelle
1
"Spielerposition ist immer links und Ziel rechts": Bedeutet dies, dass Spieler-y = 0 und Ziel-y = N-1 ist? Wenn ja, können wir einfach die x-Koordinate (eine Zahl) für Spieler und Ziel akzeptieren?
digEmAll
1
@ DigEmAll Guter Punkt. Ehrlich gesagt, ich habe nicht daran gedacht und ja, Sie können, ich werde das bearbeiten.
DimChtz
Verwandte aber einfacher. Verwandt, aber schwerer.
user202729
Muss der Pfad von Anfang bis Ende verlaufen oder kann er in umgekehrter Reihenfolge verlaufen?
Kamoroso94
1
@ kamoroso94 Ja, beginne zu zielen (Ziel) :)
DimChtz

Antworten:

5

JavaScript (ES6), 135 Byte

Nimmt Eingaben als an (width, [target_x, target_y], obstacles)(source_x, source_y), wobei Hindernisse eine Reihe von Zeichenfolgen im "X,Y"Format sind.

Gibt ein Array von Zeichenfolgen im "X,Y"Format zurück.

(n,t,o)=>g=(x,y,p=[],P=[...p,v=x+','+y])=>v==t?P:~x&~y&&x<n&y<n&[...o,...p].indexOf(v)<0&&[0,-1,0,1].some((d,i)=>r=g(x+d,y-~-i%2,P))&&r

Probieren Sie es online!

Kommentiert

(n, t, o) =>              // n = width of maze, t[] = target coordinates, o[] = obstacles
  g = (                   // g() = recursive search function taking:
    x, y,                 //   (x, y) = current coordinates of the player
    p = [],               //   p[] = path (a list of visited coordinates, initially empty)
    P = [                 //   P[] = new path made of:
      ...p,               //     all previous entries in p
      v = x + ',' + y     //     the current coordinates coerced to a string v = "x,y"
    ]                     //
  ) =>                    //
    v == t ?              // if v is equal to the target coordinates:
      P                   //   stop recursion and return P
    :                     // else:
      ~x & ~y             //   if neither x nor y is equal to -1
      && x < n & y < n    //   and both x and y are less than n
      & [...o, ...p]      //   and neither the list of obstacles nor the path
        .indexOf(v) < 0   //   contains a position equal to the current one:
      && [0, -1, 0, 1]    //     iterate on all 4 possible directions
        .some((d, i) =>   //     for each of them:
          r = g(          //       do a recursive call with:
            x + d,        //         the updated x
            y - ~-i % 2,  //         the updated y
            P             //         the new path
          )               //       end of recursive call
        ) && r            //     if a solution was found, return it
Arnauld
quelle
5

R , 227 Bytes

function(N,P,G,O){M=diag(N+2)*0
M[O+2]=1
b=c(1,N+2)
M[row(M)%in%b|col(M)%in%b]=1
H=function(V,L){if(all(V==G+2))stop(cat(L))
M[t(V)]=2
M<<-M
for(i in 0:3){C=V+(-1)^(i%/%2)*(0:1+i)%%2
if(!M[t(C)])H(C,c(L,C-2))}}
try(H(P+2,P),T)}

Probieren Sie es online!

Nicht wirklich kurz und definitiv nicht auf dem kürzesten Weg (z. B. das erste Beispiel überprüfen).
Grundsätzlich führt es eine rekursive Tiefensuche durch und stoppt, sobald das Ziel erreicht ist, und druckt den Pfad aus.

Vielen Dank an JayCe für die Verbesserung der Ausgabeformatierung

digEmAll
quelle
+1 Ich mag die Art und Weise, wie Sie die Ausgabe drucken (nicht die typische langweilige Liste von Listen) :)
DimChtz
@DimChtz: Nun, danke, aber ... das ist die Hilfsfunktion, die Code-Golf-Funktion gibt nur eine Liste von Koordinaten aus x1 y1 x2 y2 ... xn yn: D
digEmAll
1
Ja, ich weiß: P aber trotzdem nett.
DimChtz
1
stimme mit @DimChtz überein ... und ich denke, es sieht noch besser aus, wenn Sie write(t(mx),1,N)statt printing :)
JayCe
@ JayCe: gute Idee, geändert!
digEmAll
4

Python 2 , 151 149 Bytes

N,s,e,o=input()
P=[[s]]
for p in P:x,y=k=p[-1];k==e>exit(p);P+=[p+[[x+a,y+b]]for a,b in((0,1),(0,-1),(1,0),(-1,0))if([x+a,y+b]in o)==0<=x+a<N>y+b>-1]

Probieren Sie es online!

ovs
quelle
3

Haskell , 133 131 130 Bytes

  • -1 Byte dank BWO
(n!p)o=head.(>>=filter(elem p)).iterate(\q->[u:v|v@([x,y]:_)<-q,u<-[id,map(+1)]<*>[[x-1,y],[x,y-1]],all(/=u)o,x`div`n+y`div`n==0])

Probieren Sie es online! (mit ein paar Testfällen)

Eine Funktion, !die als Eingabe verwendet wird

  • n :: Int Größe des Gitters
  • p :: [Int] Spielerposition als Liste [xp, yp]
  • o :: [[Int]] Hindernisse positionieren sich als Liste [[x1, y1], [x2, y2], ...]
  • t :: [[[Int]]](implizite) Position des Ziels als Liste [[[xt, yt]]](dreifache Liste nur zur Vereinfachung)

und Zurückgeben eines gültigen Pfads als Liste [[xp, yp], [x1, y1], ..., [xt, yt]].

Als Bonus findet es einen der kürzesten Pfade und funktioniert für die Position jedes Spielers und Ziels. Auf der anderen Seite ist es sehr ineffizient (aber die bereitgestellten Beispiele laufen in angemessener Zeit ab).

Erläuterung

(n ! p) o =                                                         -- function !, taking n, p, o and t (implicit by point-free style) as input
    head .                                                          -- take the first element of
    (>>= filter (elem p)) .                                         -- for each list, take only paths containing p and concatenate the results
    iterate (                                                       -- iterate the following function (on t) and collect the results in a list
        \q ->                                                       -- the function that takes a list of paths q...
            [u : v |                                                -- ... and returns the list of paths (u : v) such that:
                v@([x, y] : _) <- q,                                -- * v is an element of q (i.e. a path); also let [x, y] be the first cell of v
                u <- [id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]],   -- * u is one of the neighbouring cells of [x, y]
                all (/= u) o,                                       -- * u is not an obstacle
                x `div` n + y `div` n == 0                          -- * [x, y] is inside the grid
            ]
    )

iteratekk-1[[xt, yt]]

Der scheinbar obskure Ausdruck [id, map (+ 1)] <*> [[x - 1,y], [x, y - 1]]ist nur eine "golfige" (-1 Byte) Version von [[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]].

Delfad0r
quelle
2
Willkommen bei PPCG! Schöne erste Antwort!
Arnauld
1
@ Arnauld Danke!
Tatsächlich habe
1
Schönes Golf! Sie können ein Byte speichern, indem Sie einen Operator anstelle einer Funktion verwenden: Probieren Sie es online aus!
5.
@ BWO Danke für den Tipp. Ich bin neu hier, also gibt es viele Tricks, von denen ich noch nie gehört habe
Delfad0r
1
Btw. Es gibt einen Abschnitt mit Tipps speziell für Haskell, in dem Sie diese und viele weitere Tricks finden. Oh und es gibt immer auch Chat: Von Monaden und Männern
ბიმო
1

Retina 0.8.2 , 229 Bytes

.
$&$&
@@
s@
##
.#
{`(\w.)\.
$1l
\.(.\w)
r$1
(?<=(.)*)\.(?=.*¶(?<-1>.)*(?(1)$)\w)
d
}`\.(?=(.)*)(?<=\w(?(1)$)(?<-1>.)*¶.*)
u
+T`.`#`.(?=(.)*)(?<=d#(?(1)$)(?<-1>.)*¶.*)|(?<=(.)*.).(?=.*¶(?<-2>.)*(?(2)$)u#)|(?<=#r).|.(?=l#)
.(.)
$1

Probieren Sie es online! Nicht sicher, ob das E / A-Format geeignet ist. Erläuterung:

.
$&$&

Dupliziere jede Zelle. Die linke Kopie wird als temporärer Arbeitsbereich verwendet.

@@
s@

Markiere den Anfang des Labyrinths als besucht.

##
.#

Markiere das Ende des Labyrinths als leer.

{`(\w.)\.
$1l
\.(.\w)
r$1
(?<=(.)*)\.(?=.*¶(?<-1>.)*(?(1)$)\w)
d
}`\.(?=(.)*)(?<=\w(?(1)$)(?<-1>.)*¶.*)
u

Während verfügbare Arbeitszellen vorhanden sind, zeigen Sie auf benachbarte zuvor besuchte Zellen.

+T`.`#`.(?=(.)*)(?<=d#(?(1)$)(?<-1>.)*¶.*)|(?<=(.)*.).(?=.*¶(?<-2>.)*(?(2)$)u#)|(?<=#r).|.(?=l#)

Verfolgen Sie den Pfad vom Ausgang bis zum Start anhand der Arbeitszellen als Leitfaden.

.(.)
$1

Löschen Sie die Arbeitszellen.

Neil
quelle
1

JavaScript, 450 Byte

Übernimmt die Eingabe als (n, {playerx, playery}, {targetx, targety}, [{obstaclex, obstacley}]). Gibt ein Array von zurück {hopx, hopy}.

j=o=>JSON.stringify(o);l=a=>a.length;c=(a,o)=>{let i=l(a);while(i>0){i--;if(j(a[i])==j(o)){return 1;}}return 0;}h=(p,t,o)=>{if(p.y<t.y&&!c(o,{x:p.x,y:p.y+1})){return{x:p.x,y:p.y+1};}if(p.y>t.y&&!c(o,{x:p.x,y:p.y-1})){return{x:p.x,y:p.y-1};}if(p.x<t.x&&!c(o,{x:p.x+1,y:p.y})){return{x:p.x+1,y:p.y};}if(p.x>t.x&&!c(o,{x:p.x-1,y:p.y})){return{x:p.x-1,y:p.y};}return t;}w=(n,p,t,o)=>{let r=[];r.push(p);while(j(p)!==j(t)){p=h(p,t,o);r.push(p);}return r;}

Hier ist eine ungeteilte Version meines Chaos:

// defining some Array's function for proper comparaisons
json = (object) => { return JSON.stringify(object) };
length = (array) => { return array.length; }
contains = (array, object) => {
    let i = length(array);
    while (i > 0) {
    i--;
        if (json(array[i]) == json(object)) { return true; }
    }
    return false;
}
//return next found hop
getNextHop = (player, target, obstacles) => {
    //uggly serie of conditions
    //check where do we have to go and if there is an obstacle there
    if(player.y<target.y && !contains(obstacles, [x:player.x, y:player.y+1])) { return [x:player.x, y:player.y+1]; }
    if(player.y>target.y && !contains(obstacles, [x:player.x, y:player.y-1])) { return [x:player.x, y:player.y-1]; }
    if(player.x<target.x && !contains(obstacles, [x:player.x+1, y:player.y])) { return [x:player.x+1, y:player.y]; }
    if(player.x>target.x && !contains(obstacles, [x:player.x-1, y:player.y])) { return [x:player.x-1, y:player.y]; }
    return target;
}
//return found path
getPath = (gridsize, player, target, obstacles) => {
    let path = [];
    path.push(player);
    //while player is not on target
    while(json(player)!=json(target)) {
        player = getNextHop(player, target, obstacles); //gridsize is never used as player and target are in the grid boundaries
        path.push(player);
    }
    return path;
}
MinerBigWhale
quelle