Dessinez un chemin tracé par des changeurs de direction

25

Ce défi se déroule sur une grille.

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

Celui-ci est de 10 x 10, mais il peut être de n'importe quelle forme rectangulaire.

Il y a quatre directions sur cette grille. Haut, bas, gauche et droite.

La tâche consiste à tracer un chemin commençant par une initiale en majuscule. Dans cet exemple, ira directement vers le haut à partir du U.

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

Le chemin ira vers le haut et sera composé de caractères pointillés (.), Jusqu'à ce qu'il atteigne un mur, quand il se terminera par un astérisque (*).

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

En plus des débuts de chemin, il existe également des changeurs de direction, représentés par une initiale de direction en minuscule.

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

De plus, un X majuscule représente un obstacle qui terminera le chemin.

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

Règles

  • L'entrée est une chaîne composée d'un cadre ((composé des caractères |, - et +)) contenant des caractères indiquant les débuts de chemin, les changeurs de direction et les obstacles.
  • Votre code doit ajouter des caractères de point final pour suivre le chemin décrit par les départs et les changeurs de direction, et un astérisque lorsque / si le chemin rencontre un mur ou un obstacle.
  • Il peut y avoir plusieurs démarrages de chemin.
  • Le code se terminera toujours sans erreur si le chemin décrit une boucle.
  • Si un chemin rencontre un début de chemin, il agira comme un changeur de direction.
  • C'est du golf de code, du code à faible octet et pas de failles standard, s'il vous plaît.
  • Je préfère toujours les liens à un interprète en ligne.

Cas de test

1: Simple

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


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

2: virage à droite

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


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

3: Carrefour

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


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

4: 4 Traversées

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


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

5: Première boucle

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

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

6: Démarreur comme changeur

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


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

7: Boucle droite

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


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

8: Noeud serré

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


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

9: Un obstacle

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


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

10: forme en S

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


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

11: Noeud à 4 voies

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


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

12: Jonctions occupées

+----------+
|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: commence dans Edge

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

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

14: Traverser les chemins morts

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


+----------+
|         *|
|         .|
|         .|
|      R..*|
|         .|
|         .|
|         .|
|         .|
|         U|
+----------+
AJFaraday
la source
@TFeld Ajouté, merci!
AJFaraday
1
Il semble que tous les changeurs de direction soient toujours atteints dans vos cas de test, ce qui pourrait permettre de simplifier l'algorithme. Je suggère d'ajouter un cas de test où ce n'est pas vrai.
Arnauld
@Arnauld Je suis presque sûr qu'il y a des changeurs de direction inutilisés dans le cas 12.
AJFaraday
3
Il est indiqué que la grille peut être de n'importe quelle forme rectangulaire, mais tous les cas de test semblent être identiques en taille et en forme.
gastropner le

Réponses:

9

JavaScript (ES6),  191 183  181 octets

Merci à @tsh d'avoir aidé à corriger un bogue

Prend l'entrée comme une matrice de caractères. Sorties en modifiant l'entrée.

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

Essayez-le en ligne!

Commenté

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
la source
btw, [...""+a].mappourrait créer un tableau avec au moins 2x longueur de a. Je ne sais pas si ça aide.
tsh
(a+0)[n]enregistre un octet, même s'il ndoit maintenant être initialisé.
Arnauld
8

Python 2 , 283 279 293 288 279 octets

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,

Essayez-le en ligne!

Prend une liste de listes.

Sorties en modifiant le tableau d'entrée.

TFeld
la source
6

Perl 5, 203 188 166 octets

$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

Comment ça marche

  • $s=$_pour enregistrer l'entrée dans $spour restaurer les changeurs minuscules. $_|=$scar au niveau du bit ou avec de l'espace ne changera pas .et *, les lettres minuscules urldseront restaurées avec le bit ou l'opération.
  • /\n/;$n='.'x"@-"pour obtenir "largeur" ​​et $npour correspondre à n'importe quel caractère "largeur" ​​fois
  • $l='\K[ a-z](?=';$t='([-|X])?'pour réduire la longueur des regex; $lpour faire correspondre une lettre minuscule urldou un espace sur un chemin, $tpour faire correspondre un terminateur.

Après remplacement: (?| 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) )

  • passe /eà eval, de /ssorte que .(à l'intérieur $n) corresponde également à un caractère de nouvelle ligne
  • $&eq$"?$1?'*':'.':uc$&si apparié est un espace, si le termiateur est apparié *sinon .sinon en majuscule.
Nahuel Fouilleul
la source
1
@Arnauld, cela fonctionne si vous entrez un cas de test à la fois.
Shaggy
Oui, j'ai posté rapidement et je n'ai pas pu vérifier qu'il s'agissait d'une réinitialisation fixe $sdans le pied de page. $sest utilisé pour enregistrer l'entrée et pour restaurer les lettres minuscules car elles sont commutées en majuscules lors du tracé du chemin
Nahuel Fouilleul
4

Nettoyer , 409 octets

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;_=[])

Essayez-le en ligne!

Οurous
la source
3

Python 2 , 250 octets

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]

Essayez-le en ligne!

Prend une liste de listes de chaînes de 1 caractère, comme explicitement autorisé par l'OP.

Modifie la liste en place.

Pour des E / S plus faciles, utilisez ceci .

Erik le Outgolfer
la source