Pfade und Zeitverschwendung

22

Prämisse

Vor kurzem war ich ungefähr eine halbe Stunde zu früh zu einem Termin und beschloss, draußen zu warten. Ich entschied auch, dass es seltsam aussehen würde, wenn ich nur regungslos vor dem Haus stand. Aus diesem Grund habe ich mich für einen kurzen Spaziergang in einem begrenzten Gebiet entschieden. Ich kam auch zu dem Schluss, dass ich herumlungern würde, wenn ich anfinge, im Kreis zu laufen. So war ich inspiriert, meine erste Code Golf-Herausforderung zu erstellen.

Spezifikation

Sie erhalten eine Liste, eine Karte des Gebiets, die entweder " "oder enthält "#", die Freiräume und Hindernisse darstellen. Freie Plätze können nur einmal gekreuzt werden, und es dauert 1 Minute, um sie zu kreuzen. Ihre Ausgangsposition wird durch eine "@"pro roguelike Tradition gekennzeichnet, und das Ziel wird durch eine dargestellt, "$"weil Sie dort genau diese verlieren werden. Sie erhalten auch eine Ganzzahl, die angibt, wie viele Minuten Sie verschwenden müssen, bevor Sie nicht so wirken, als ob Sie eingedrungen wären. Wenn du auf dem landest"$" . Es muss sich um die genaue Anzahl der Minuten handeln (wenn Sie also rückwärts gezählt haben, muss dies 1 auf einem benachbarten Feld und 0 auf dem Feld sein). Es ist immer möglich, das Ziel zu erreichen. Ihr Programm oder Ihre Funktion muss eine Liste mit dem kürzesten Pfad mit <,>, ^ und v zurückgeben, um die vier möglichen Richtungen darzustellen.

Beispiele

Eingang:

[[" ", " ", " ", " "],
 ["@", " ", " ", "$"],
 [" ", " ", " ", " "],
 [" ", " ", " ", " "]]

und

5

Ausgang:

[[">", ">", ">", "v"],
 ["^", " ", " ", "$"],
 [" ", " ", " ", " "],
 [" ", " ", " ", " "]]

Eingang:

[[" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 ["@", "#", " ", "$", " "],
 [" ", " ", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

und

7

Ausgabe:

[[" ", "#", " ", " ", " "],
 [" ", "#", ">", "v", " "],
 ["v", "#", "^", "$", " "],
 [">", ">", "^", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

Eingang:

[[" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 ["@", "#", " ", "$", " "],
 [" ", " ", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

und

17

Ausgabe:

[[" ", "#", " ", "v", "<"],
 [" ", "#", " ", "v", "^"],
 ["v", "#", " ", "$", "^"],
 [">", ">", "v", ">", "^"],
 [" ", "#", "v", "^", "<"],
 [" ", "#", ">", ">", "^"]]

Regeln

  • Es gelten Standardlücken
  • Jedes Plättchen darf nur einmal verschoben werden
  • Die genaue Zeit muss an der Tafel verbracht werden
  • Bei mehreren Pfaden muss nur ein Pfad angezeigt werden
  • Dies ist eine Code Golf Frage, also gewinnt die kürzeste Antwort
  • Gemäß der Frage von user202729 in den Kommentaren können Sie eine gültige Eingabe annehmen.

Fügen Sie einen Kommentar hinzu, wenn weitere Erläuterungen erforderlich sind

LForchini
quelle
1
Ist gewährleistet, dass "das Ziel immer in der angegebenen Zeit erreicht werden kann "?
user202729
Ja, es wird immer einen Weg geben, auch wenn er
verschlungen ist
5
Willkommen bei PPCG! :) Schöne erste Herausforderung.
Giuseppe
Was ist mit der halben Minute an jedem Ende passiert ?! (Keine Notwendigkeit, etwas zu ändern, wenn es nicht offensichtlich ist)
Jonathan Allan

Antworten:

6

JavaScript (ES6), 171 Byte

Übernimmt Eingaben in der Currying-Syntax (a)(n). Ausgaben durch Ändern der Eingabematrix.

a=>g=(n,y=a[F='findIndex'](r=>~(i=r[F](v=>v>'?'))),x=i,R=a[y])=>!n--|[-1,0,1,2].every(d=>(R[x]='<^>v'[d+1],(c=(a[Y=y+~-d%2]||0)[X=x+d%2])<1?g(n,Y,X):n|c!='$')&&(R[x]=' '))

Probieren Sie es online!

Kommentiert

a =>                           // a[] = input matrix
g = (                          // g = recursive function taking:
  n,                           //   n = number of remaining moves
                               //   (x, y) = current coordinates, initialized as follows:
  y = a[F = 'findIndex'](r =>  //     y = index of the row containing the starting point,
    ~(i = r[F](v => v > '?'))  //         found by iterating over all rows r until we
  ),                           //         find some i such that r[i] > '?'
  x = i,                       //     x = index of the column of the starting point
  R = a[y]                     //   R[] = current row
) =>                           //
  !n-- |                       // decrement n; force failure if we're out of moves
  [-1, 0, 1, 2].every(d =>     // for each direction d, where -1 = left, 0 = up,
    (                          // 1 = right and 2 = down:
      R[x] = '<^>v'[d + 1], (  //   update the current cell with the direction symbol
        c = (                  //   c = content of the new cell at (X, Y) with:
          a[Y = y + ~-d % 2]   //     Y = y + dy
          || 0                 //     (use a dummy value if this row does not exist)
        )[X = x + d % 2]       //     X = x + dx
      ) < 1 ?                  //   if c is a space:
        g(n, Y, X)             //     we can go on with a recursive call
      :                        //   else:
        n | c != '$'           //     return false if n = 0 and we've reached the target
    ) &&                       //   unless the above result is falsy,
    (R[x] = ' ')               //   restore the current cell to a space
  )                            // end of every()
Arnauld
quelle
5

Python 2 , 310 256 Bytes

Danke @cairdcoinheringaahing für except:0-3 Bytes
Danke @Mnemonic für -8 Bytes
Danke @JonathanAllan für -3 Bytes
Danke @ovs für -5 Bytes

G,L=input()
R=[]
def S(x,y,G,c,R):
 try:
	if x>-1<y<G[y][x]in' @':i=0;exec"T=[r[:]for r in G];T[y][x]='<v^>'[i];S(x+~-i/2,y+~-(i^2)/2,T,c-1,R);i+=1;"*4
	R+=[G]*(0==c<'$'==G[y][x])
 except:0
for i,y in enumerate(G):"@"in y>S(y.index("@"),i,G,L,R)
print R[0]

Probieren Sie es online!

Einige Erklärungen:

try-exceptwird verwendet , um sicherzustellen, dass beide xund yin Grenzen sind Koordinaten. Eine Ausnahme wird beim Zugriff auf ausgelöst G[y][x]. Python ist zu gut und negative Indizes sind akzeptabel, daher wird ein Häkchen x>-1<yhinzugefügt.

T=[r[:]for r in G]wird verwendet, um eine Kopie von Gby-Werten zu erstellen

~-i/2und ~-(i^2)/2werden verwendet, um Paare zu generieren (-1, 0), (0, 1), (0, -1), (1, 0), die sich früher im Gitter bewegten (es sollte noch einen kürzeren Weg geben!)

R+=[G]*(0==c<'$'==G[y][x])überprüfen Sie, ob dies '$'in der erforderlichen Anzahl von Schritten erreicht wurde. Rwird verwendet, um dieses Ergebnis von rekursiven Funktionsaufrufen zu erhalten.

for i,y in enumerate(G):"@"in y>S(y.index("@"),i,G,L,R)Gefunden xund yvon '@'in Ein- und Anruffunktion S.

print R[0] R könnte mehr als eine Lösung enthalten, also erst ausgeben

Totes Opossum
quelle
-4 Bytes
Caird Coinheringaahing
1
Sie können durch Ersetzen eines Byte speichern if G[y][x]=='$':mit if'$'==G[y][x]:.
1
Tatsächlich kann diese gesamte Bedingung durch ein R+=(G[y][x]=='$')*(c==0)*[G]anderes Byte ersetzt werden.
1
Ich bin mir nicht sicher, was ich gesehen habe. Sie können ein paar Bytes in der ersten Bedingung mitif(x>-1<y)*(G[y][x]in' @'):
1
Ein kürzerer Weg für Sie y+cmp(i%2,i/2)wäre y+~-(i^2)/2; es kann durchaus noch kürzer sein.
Jonathan Allan
2

Python 2 , 264 261 251 249 Bytes

def f(a,n,r=-1,s=0):
 j=len(a[0]);x=1;z=y=0
 if r<0:s,r=divmod(sum(a,[]).index('@'),j)
 for c in'>v<^':
	u=r+x;v=s+y;x,y=-y,x
	if j>u>-1<v<len(a):b=[e[:]for e in a];b[s][r]=c;w=a[v][u];z=n*(w<'!')and f(b,n-1,u,v)or n==1and w=='$'and b
	if z:return z

Probieren Sie es online!

Chas Brown
quelle
1
@ Arnauld: Ups! Ich bin ein bisschen zu schick geworden. Fest.
Chas Brown