Zeichnen Sie einen Pfad, der von Richtungswechslern erstellt wurde

25

Diese Herausforderung findet in einem Raster statt.

+----------+
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
+----------+

Dies ist 10 x 10, aber es kann jede rechteckige Form sein.

Es gibt vier Richtungen in diesem Raster. Hoch, runter, links und rechts.

Die Aufgabe besteht darin, einen Pfad zu zeichnen, der mit einem Richtungsinitial in Großbuchstaben beginnt. In diesem Beispiel geht es direkt von der U nach oben.

+----------+
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|   U      |
+----------+

Der Pfad geht nach oben und besteht aus Punktzeichen (.), Bis er an eine Wand stößt und mit einem Sternchen (*) endet.

+----------+
|   *      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

Zusätzlich zu den Pfadstarts gibt es auch Richtungsänderer, die durch ein Richtungsinitial in Kleinbuchstaben dargestellt werden.

+----------+
|          |
|          |
|          |
|   r.....*|
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

Auch ein Großbuchstabe X ist ein Hindernis, das den Pfad beendet.

+----------+
|          |
|          |
|          |
|          |
|   r...*X |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

Regeln

  • Die Eingabe ist eine Zeichenfolge, die aus einem Rahmen (bestehend aus |, - und + Zeichen) besteht, der Zeichen für Pfadanfang, Richtungsänderungen und Hindernisse enthält.
  • Ihr Code sollte Punktzeichen hinzufügen, um dem von Starts und Richtungswechslern beschriebenen Pfad zu folgen, und ein Sternchen, wenn der Pfad auf eine Wand oder ein Hindernis stößt.
  • Es kann mehrere Pfadstarts geben.
  • Der Code wird weiterhin fehlerfrei beendet, wenn der Pfad eine Schleife beschreibt.
  • Wenn ein Pfad auf einen Pfadanfang trifft, fungiert er als Richtungswechsler.
  • Es ist Code-Golf, Low-Byte-Code und keine Standard-Lücken, bitte.
  • Ich bevorzuge immer Links zu einem Online-Dolmetscher.

Testfälle

1: Einfach

+----------+
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|   U      |
+----------+


+----------+
|   *      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

2: Rechts abbiegen

+----------+
|          |
|          |
|          |
|   r      |
|          |
|          |
|          |
|          |
|   U      |
+----------+


+----------+
|          |
|          |
|          |
|   r.....*|
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

3: Kreuzung

+----------+
|          |
|          |
|          |
|   r  d   |
|          |
| u    l   |
|          |
|          |
|   U      |
+----------+


+----------+
| *        |
| .        |
| .        |
| . r..d   |
| . .  .   |
| u....l   |
|   .      |
|   .      |
|   U      |
+----------+

4: 4 Wege kreuzen

+----------+
|      D   |
|          |
|          |
|R         |
|          |
|         L|
|          |
|          |
|   U      |
+----------+


+----------+
|   *  D   |
|   .  .   |
|   .  .   |
|R........*|
|   .  .   |
|*........L|
|   .  .   |
|   .  .   |
|   U  *   |
+----------+

5: Erste Schleife

+----------+
|          |
|          |
|          |
|   r  d   |
|          |
|   u  l   |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|   r..d   |
|   .  .   |
|   u..l   |
|   .      |
|   .      |
|   U      |
+----------+

6: Starter als Wechsler

+----------+
|          |
|          |
|          |
|   L      |
|          |
|          |
|          |
|          |
|   U      |
+----------+


+----------+
|          |
|          |
|          |
|*..L      |
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

7: Gerade Schleife

+----------+
|          |
|          |
|          |
|          |
|   r  l   |
|          |
|          |
|          |
|   U      |
+----------+


+----------+
|          |
|          |
|          |
|          |
|   r..l   |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

8: Enger Knoten

+----------+
|          |
|          |
|          |
|  d  l    |
|   r u    |
|  r u     |
|          |
|          |
|   U      |
+----------+


+----------+
|    *     |
|    .     |
|    .     |
|  d..l    |
|  .r.u    |
|  r.u     |
|   .      |
|   .      |
|   U      |
+----------+

9: Ein Hindernis

+----------+
|          |
|          |
|          |
|          |
|   r    X |
|          |
|          |
|          |
|   U      |
+----------+


+----------+
|          |
|          |
|          |
|          |
|   r...*X |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

10: S-Form

+----------+
|r     d   |
|          |
|  XXXXXXXX|
| d      l |
|ul        |
|XXXXXXX   |
|          |
|R       u |
|          |
+----------+


+----------+
|r.....d   |
|.     *   |
|. XXXXXXXX|
|.d......l |
|ul      . |
|XXXXXXX . |
|        . |
|R.......u |
|          |
+----------+

11: 4-Wege-Knoten

+----------+
|      D   |
|          |
|   r      |
|R    d    |
|          |
|    u    L|
|      l   |
|          |
|   U      |
+----------+


+----------+
|    * D   |
|    . .   |
|   r.....*|
|R....d.   |
|   ....   |
|   .u....L|
|*.....l   |
|   . .    |
|   U *    |
+----------+

12: Busy Junctions

+----------+
|rrrrr rrrd|
| rlrl     |
|ul rrd    |
|ruX X     |
|udl ll    |
|ull       |
|rlr       |
|rdr  d    |
|Uruull    |
+----------+


+----------+
|rrrrr.rrrd|
|.rlrl    .|
|ul rrd   .|
|ruX.X.   .|
|udl.ll   .|
|ull.     .|
|rlr.     .|
|rdr..d   .|
|Uruull   *|
+----------+

13: Startet in Edge

+----------+
|   U      |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
+----------+

+----------+
|   U      |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
+----------+

14: Überqueren von toten Pfaden

+----------+
|          |
|          |
|          |
|      R   |
|          |
|          |
|          |
|          |
|         U|
+----------+


+----------+
|         *|
|         .|
|         .|
|      R..*|
|         .|
|         .|
|         .|
|         .|
|         U|
+----------+
code-golf AJFaraday
quelle
@TFeld Hinzugefügt, danke!
AJFaraday,
1
Es scheint, dass in Ihren Testfällen immer alle Richtungsänderer erreicht sind, was eine Vereinfachung des Algorithmus ermöglichen könnte. Ich würde vorschlagen, einen Testfall hinzuzufügen, bei dem dies nicht zutrifft.
Arnauld
@ Arnauld Ich bin mir ziemlich sicher, dass es in Fall 12 einige unbenutzte Richtungswechsler gibt.
AJFaraday
1
Vorgeschlagener Testfall
Dienstag,
3
Es wird angegeben, dass das Gitter jede rechteckige Form haben kann, aber alle Testfälle scheinen in Größe und Form identisch zu sein.
Gastropner

Antworten:

9

JavaScript (ES6),  191 183  181 Byte

Vielen Dank an @tsh für die Behebung eines Fehlers

Nimmt die Eingabe als eine Matrix von Zeichen. Ausgänge durch Ändern des Eingangs.

f=(a,X,Y,d,n=0)=>a.map((r,y)=>r.map((v,x)=>(a+0)[i=' .*dlurDLUR'.indexOf(v),n]?X?X-x+~-d%2|Y-y+(d-2)%2?0:~i?f(a,x,y,i>2?i&3:d,n+1,r[x]=i?v:'.'):n?a[Y][X]='*':0:i>6&&f(a,x,y,i&3):0))

Probieren Sie es online!

Kommentiert

f = ( a,                           // a[]  = input matrix
      X, Y,                        // X, Y = coordinates of the previous cell
      d,                           // d    = current direction (0 .. 3)
      n = 0                        // n    = number of iterations for the current path
    ) =>                           //
  a.map((r, y) =>                  // for each row r[] a position y in a[]:
    r.map((v, x) =>                //   for each character v at position x in r[]:
      (a + 0)[                     //
        i = ' .*dlurDLUR'          //     i = index of the character
            .indexOf(v),           //     blocking characters '-', '|' and 'X' gives -1
        n                          //     by testing (a + 0)[n], we allow each cell to be
      ]                            //     visited twice (once horizontally, once vertically)
      ?                            //     if it is set:
        X ?                        //       if this is not the 1st iteration:
          X - x + ~-d % 2 |        //         if x - X is not equal to dx[d]
          Y - y + (d - 2) % 2 ?    //         or y - Y is not equal to dy[d]:
            0                      //           ignore this cell
          :                        //         else:
            ~i ?                   //           if this is not a blocking character:
              f(                   //             do a recursive call:
                a,                 //               pass a[] unchanged
                x, y,              //               pass the coordinates of this cell
                i > 2 ? i & 3 : d, //               update d if v is a direction char.
                n + 1,             //               increment n
                r[x] = i ? v : '.' //               if v is a space, set r[x] to '.'
              )                    //             end of recursive call
            :                      //           else (this is a blocking character):
              n ?                  //             if this is not the 1st iteration:
                a[Y][X] = '*'      //               set the previous cell to '*'
              :                    //             else:
                0                  //               do nothing
        :                          //       else (1st iteration):
          i > 6 &&                 //         if v is a capital letter:
            f(a, x, y, i & 3)      //           do a recursive call with this direction
      :                            //     else ((a + 0)[n] is not set):
        0                          //       we must be in an infinite loop: abort
    )                              //   end of inner map()
  )                                // end of outer map()
Arnauld
quelle
btw, [...""+a].mapkönnte ein Array mit mindestens 2x Länge von a erstellen. Ich bin mir nicht sicher, ob es hilft.
Dienstag,
(a+0)[n]Speichert ein Byte, obwohl es njetzt initialisiert werden muss.
Arnauld
8

Python 2 , 283 279 293 288 279 Bytes

e=enumerate
def f(M):
 s=[(x,y,c)for y,l in e(M)for x,c in e(l)if'A'<c<'X'];v=set(s)
 for x,y,C in s:
	d=ord(C)%87%5;q=d>1;X,Y=x-d+q*3,y+~-d-q;c=M[Y][X];N=(X,Y,[C,c]['a'<c<'x'])
	if'!'>c:M[Y][X]='.'
	if(c in'-|X')*('/'>M[y][x]):M[y][x]='*'
	if(c in'udlr. *')>({N}<v):v|={N};s+=N,

Probieren Sie es online!

Nimmt eine Liste von Listen auf.

Ausgabe durch Ändern des Eingabearrays.

TFeld
quelle
6

Perl 5, 203 188 166 Bytes

$l='\K[ a-z](?=';$t='([-|X])?';$s=$_;/
/;$n='.'x"@-";{$_|=s/(?|R[.*]*$l$t)|$t${l}[.*]*L)|D$n(?:[.*]$n)*$l$n$t)|$t$n$l$n([.*]$n)*U))/$&eq$"?$1?'*':'.':uc$&/es?redo:$s}

TIO

Wie es funktioniert

  • $s=$_Speichern von Eingaben in $s, um Kleinbuchstaben-Wechsler wiederherzustellen. $_|=$sweil bitweise oder mit Leerzeichen wird sich nicht ändern .und *Kleinbuchstabenurld mit bitweisen oder Operationen wiederhergestellt werden.
  • /\n/;$n='.'x"@-" "width" bekommen und $n jedes Zeichen "width" mal zu finden
  • $l='\K[ a-z](?=';$t='([-|X])?'Regex-Länge zu reduzieren; $lum einen Kleinbuchstaben urldoder ein Leerzeichen auf einem Pfad zu finden, $tum einen Terminator zu finden.

Nach ersatz: (?| R[.*]*\K[ a-z](?=([-|X])?) | ([-|X])?\K[ a-z](?=[.*]*L) | D$n(?:[.*]$n)*\K[ a-z](?=$n([-|X])?) | ([-|X])?$n\K[ a-z](?=$n([.*]$n)*U) )

  • wechselt /ezu eval, /sso dass .(inside $n) auch ein Newline-Zeichen passt
  • $&eq$"?$1?'*':'.':uc$&wenn ein Raum angepasst ist, wenn termiator angepasst *sonst .sonst groß geschrieben.
Nahuel Fouilleul
quelle
1
@Arnauld, es funktioniert, wenn Sie jeweils einen Testfall eingeben.
Shaggy
Ja, ich habe schnell gepostet und konnte nicht überprüfen, ob das Zurücksetzen $sin der Fußzeile behoben ist . $sDient zum Speichern der Eingabe und zum Wiederherstellen von Kleinbuchstaben, da beim Zeichnen des Pfads die Großbuchstaben umgeschaltet werden
Nahuel Fouilleul,
4

Sauber , 409 Bytes

import StdEnv,Data.List
q=flatlines
$m=foldl(zipWith\a b|a=='*'||b=='*'='*'=max a b)(q m)[q(foldl(\m(_,y,x)=[[if(b<>x||a<>y)if(k=='*')'.'k'*'\\k<-r&b<-[0..]]\\r<-m&a<-[0..]])m(last(takeWhile(not o hasDup)(inits(f 0y 0x)))))\\l<-m&y<-[0..],c<-l&x<-[0..]|isUpper c]
where f a y b x=let(u,v)=(a+y,b+x)in(case toLower((m!!u)!!v)of' '=[((a,b),u,v):f a u b v];'r'=f 0u 1v;'l'=f 0u -1v;'u'=f -1u 0v;'d'=f 1u 0v;_=[])

Probieren Sie es online!

Οurous
quelle
3

Python 2 , 250 Bytes

def f(G,e=enumerate):
 for i,k in e(G):
	for j,l in e(k):
	 v=X=x=y=m,=l,
	 while(m in'-X|')<(l in'DLRU')>(X in v):v+=X,;y,x=zip((1,0,0,-1,y),(0,-1,1,0,x))['DLRU dlru'.find(m)%5];G[i][j]=(m,'.*'[G[i+y][j+x]in'-X|'])[m<'!'];i+=y;j+=x;X=x,i,j;m=G[i][j]

Probieren Sie es online!

Nimmt eine Liste von Listen mit Zeichenfolgen auf, wie dies vom OP ausdrücklich erlaubt ist.

Ändert die Liste.

Verwenden Sie diese Option, um die E / A zu vereinfachen .

Erik der Outgolfer
quelle