Labyrinthe 2D moins 1D

27

Ce défi consiste à convertir des labyrinthes 2D en labyrinthes 1D.

Présentation

+-+-+-+-+-+-+   +-+-+-+-+-+-+                    graph {
| |   |     |   |A|   |    B|   A         B        A -- D
+ + + + +-+-+   + + + + +-+-+    \        |        C -- D
|   | |     |   |   | |     |     \       |        D -- E
+-+-+ +-+-+ +   +-+-+ +-+-+ +      \      |        E -- F
|           |   |C   D E   F|   C---D-E---F        E -- G
+-+-+-+ +-+ +   +-+-+-+ +-+ +         |   |        B -- F
|         | |   |      G  | |     .---G   |        F -- J
+ +-+-+-+ + +   + +-+-+-+ + +   .'   /    |        G -- H
| |       | |   |H|I      |J|   H I-'     J        G -- I
+-+-+-+-+-+-+   +-+-+-+-+-+-+     (ascii)        } // (graphviz dot)       
   Figure 1       Figure 2                 Figure 3

Aux fins de ce défi, un labyrinthe 2D traditionnel est un labyrinthe rectangulaire formé de points de réseau où toutes les conditions suivantes sont réunies:

  • Il est fermé (le bord extérieur est relié par des murs).
  • Tous les points du réseau sont connectés aux murs
  • Il est connecté (pour tous les deux espaces X et Y, il y a un chemin entre eux)
  • Il est acyclique (il n'y a pas de chemin depuis n'importe quel espace X vers X sans retour en arrière)

La figure 1 montre un labyrinthe 2D traditionnel. Ces labyrinthes ont trois domaines d'intérêt:

  • Impasses - lieux à partir desquels il n'y a qu'un seul chemin disponible
  • Couloirs - lieux à partir desquels il existe deux chemins disponibles
  • Points de décision - lieux à partir desquels il existe trois ou quatre chemins disponibles

Pour chacun de ces labyrinthes, on peut créer un graphique où les impasses et les points de décision sont des nœuds, et il y a un bord entre tous les deux nœuds reliés par un chemin le long d'un couloir. La figure 2 montre le même labyrinthe avec de tels nœuds étiquetés, et la figure 3 le graphique du labyrinthe (en notation ASCII et Graphviz dot).

Labyrinthes 1D

Les labyrinthes 1D intègrent des points de chaîne, qui se présentent par paires, et sont identifiés à l'aide d'une lettre (dans les deux cas). La figure 4 montre un exemple de labyrinthe 1D. Ceci est par ailleurs identique à un labyrinthe 2D d'une hauteur de 1, comme le montre la figure 5. Notons en particulier sur la figure 5 les positions des points du réseau marquées par +, qui alternent de gauche à droite; dans le labyrinthe 1D, tout autre personnage commençant par le mur le plus à gauche est également un point de réseau.

                                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  D|  D E|G E F|  F  |  G  |    |  D|  D E|G E F|  F  |  G  |
                                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            Figure 4                         Figure 5

Les règles de navigation dans ce labyrinthe sont les suivantes. Chaque mouvement peut être représenté en avant ( >) ou en arrière ( <). Avant et arrière ici par défaut ont la même signification que notre conscience spatiale intuitive; en avant va à la position immédiatement à droite, et en arrière immédiatement à gauche.

Les points de distorsion représentent des emplacements qui échangent de manière asymétrique la connectivité avec les voisins. Si vous venez d'un voisin vers un point de distorsion, la position des deux points de distorsion est inversée; si vous venez d'un point de distorsion vers un voisin, ils ne sont pas échangés. Par exemple, dans la figure 6, le retour en arrière de 1 vous amène à 2 (puisque 1 est le voisin de G, et nous nous déplaçons du voisin, les points 2 et @ sont échangés). Avancer de 2 (point de déformation G) vous amène à 3 (ici, nous partons d'un point de déformation, donc il n'y a pas d'échange). De même, reculer de 3 vous amène à @.

        54 2367    89^   @1
|  D|  D E|G E F|  F  |  G  |
                     Y     X
          Figure 6

La figure 6 montre également un exemple de navigation de X à Y, en utilisant la séquence de mouvements <<>><>>>>>. Ces mouvements vous amènent 123456789^respectivement aux points étiquetés , dans cet ordre. N'hésitez pas à l'explorer vous-même à l'aide de l'extrait de code de la section suivante.

Conversion de 2D en 1D

Étant donné un labyrinthe 1D, on peut créer un graphique où chaque nœud est soit une impasse ou une paire de points de distorsion, et des arêtes existent entre deux nœuds connectés le long d'un couloir. Ce graphique nous permet de comparer des labyrinthes 1D et 2D.

Par exemple, le labyrinthe 1D de la figure 4 est le même labyrinthe de la figure 1. Pour comprendre pourquoi, la figure 7 ajoute des étiquettes aux impasses. En utilisant ces étiquettes pour construire un graphique, le graphique de la figure 7 est simplement à nouveau la figure 3. La figure 8 montre une répartition de la construction de ce graphique.

|  D|  D E|G E F|  F  |  G  |
 A   C           B   J H   I 
          Figure 7

|  D|  D E|G E F|  F  |  G  |
+ + + + + + + + + + + + + + + <- lattice points
|A  |C    |     |B   J|H   I| <- dead ends
|A D|C D E|G E F|B F J|H G I| <- all nodes (dead ends+warp points); i.e.:
                                 "where each end is either a dead end
                                  or a warp point pair"; note that each
                                  pair of warp points is the same node.
|A-D|C-D-E|G-E-F|B-F-J|H-G-I| <- corridors; note each is a connection, since
  1   2 3   4 5   6 7   8 9      "edges exist between any two nodes
                                  connected along a corridor"
   graph {                 graph {                 
     A -- D  // 1 <---->     A -- D                
     C -- D  // 2 <---->     C -- D                
     D -- E  // 3 <---->     D -- E                
     G -- E  // 4 <---->     E -- G                
     E -- F  // 5 <---->     E -- F                
     B -- F  // 6 <---->     B -- F                
     F -- J  // 7 <---->     F -- J                
     H -- G  // 8 <---->     G -- H                
     G -- I  // 9 <---->     G -- I                
   }                ^      }
    Built from      |      From Figure 3
     1D maze         `-> isomorphic mappings
                Figure 8

(Notez que les étiquettes et la disposition de chaque graphique ont été artificiellement choisies pour s'aligner à des fins d'illustration; en général, il s'agit d'un problème d'isomorphisme de graphique ).

L'extrait suivant est fourni pour aider à visualiser la mécanique du labyrinthe 1D et la connexion entre le labyrinthe 1D, le graphique d'équivalence et le labyrinthe 2D.

Afficher l'extrait de code

Lorsque vous parcourez le labyrinthe 1D dans cet extrait, les deux derniers nœuds que vous touchez sont mis en surbrillance. Les mêmes nœuds sont mis en évidence de la même manière sur le graphe d'équivalence et le labyrinthe 2D.

En général, pour tout labyrinthe 2D traditionnel, un labyrinthe 1D équivalent de ce type peut être créé. Un exemple un peu plus complexe est la figure 9:

+-+-+-+-+-+-+   +-+-+-+-+-+-+                   graph {
| |   |   | |   |A|   |   |B|   A         B       A -- D
+ + + + + + +   + + + + + + +    \       /        C -- D
|   | | |   |   |   | | |   |     \     /         D -- E
+-+-+ + +-+-+   +-+-+ + +-+-+      \   /          B -- E
|           |   |C   D E    |   C---D-E           E -- F
+-+-+-+ +-+ +   +-+-+-+ +-+ +         |\          E -- I
|         | |   |      F  | |     .---F \         F -- G
+ +-+-+-+ + +   + +-+-+-+ + +   .'   /   \        G -- H
| |       | |   |G|H      |I|   G H-'     I       H -- I
+-+-+-+-+-+-+   +-+-+-+-+-+-+     (ascii)       } // (graphviz dot)
   Figure 9       Figure 10             Figure 11

|  D|  D E  |F E  |  F  |       |  D|  D E  |F E  |  F  |
                                 A   C     I     B G   H
      Figure 12                       Figure 13

Ce labyrinthe a un nœud avec quatre chemins (E sur la figure 10). La figure 11 montre son graphique. La figure 12 est un labyrinthe 1D équivalent; et la figure 13 montre le même labyrinthe avec des étiquettes pour les impasses à comparer avec la figure 11.

Défi

Étant donné un labyrinthe 2D en entrée, écrivez une fonction ou un programme qui transforme le labyrinthe 2D en un labyrinthe 1D avec des points de déformation. Les points de distorsion peuvent utiliser n'importe laquelle des 52 lettres dans chaque cas.

Garanties d'entrée (si aucune de ces conditions n'est remplie dans l'entrée, vous n'avez pas à y faire face):

  • Le labyrinthe d'entrée est connecté (c'est-à-dire que vous pouvez toujours aller d'un endroit à un autre).
  • Le labyrinthe d'entrée est fermé.
  • Le labyrinthe d'entrée est rectangulaire.
  • Tous les points du réseau sont utilisés +.
  • Tous les murs entre les points du réseau sur la même rangée utilisent |
  • Tous les murs entre les points du réseau dans la même colonne utilisent -.
  • Tous les espaces font partie d'un chemin (et tous à l'intérieur du labyrinthe).
  • Les chemins sont tous des espaces (ce sera toujours traditionnel, sans déformation)
  • Les chemins ont exactement un espace.
  • Le labyrinthe est construit en reliant des points sur un treillis.
  • Il n'y a pas plus de 52 nœuds au total (c.-à-d., Impasses et points de décision) dans le graphique du labyrinthe.

Format de sortie:

  1. Votre sortie doit être une seule ligne montrant un labyrinthe 1D.
  2. Votre sortie ne doit pas avoir d'espace blanc de début / fin; sauf qu'une nouvelle ligne de fin est très bien.
  3. Le premier caractère et tous les autres caractères par la suite sont des points de réseau.
  4. Tous les murs doivent être sur des points en treillis; et tous les points de distorsion entre eux.
  5. Le graphique de votre labyrinthe 1D doit être équivalent au graphique du labyrinthe 2D.
  6. Vos labyrinthes 1D doivent être compacts; tous les points non-treillis doivent être des impasses (c.-à-d. adjacentes aux murs) ou des points de distorsion.
  7. Les seules lettres de votre sortie doivent être des points de distorsion. Chaque point de déformation se produit exactement deux fois sur la ligne.

Exemple:

|  D|  D E|G E F|  F  |  G  | <- (1,2) The single line output
+ + + + + + + + + + + + + + + <- lattice point spacing... (3) 
                                 (4,6) lattice points are all walls or spaces
                                 (5) See Figure 8
                                 (7) D, E, F, G appear twice; no other labels

C'est du code-golf. Le gagnant est la soumission correcte sans faille avec le moins d'octets.

Essai

Il n'y a pas de cas de test pour ce défi, car il existe un grand nombre de sorties correctes pour tout labyrinthe non trivial.

J'ai, cependant, construit un vérificateur en C ++ (ce vérificateur représente graphiquement les deux solutions via une canonisation graphique ).

De plus, voici quelques exemples pour illustrer la mise en forme appropriée:

Exemple 1

+-+-+-+-+-+-+
| |   |     |
+ + + + +-+-+
|   | |     |
+-+-+ +-+-+ +
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
->
|  D|  D E|G E F|  F  |  G  |

Exemple 2

+-+-+-+-+-+-+
| |   |   | |
+ + + + + + +
|   | | |   |
+-+-+ + +-+-+
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
->
|  D|  D E  |F E  |  F  |

Plus d'exemples peuvent être trouvés ici .

code-golf graph-theory maze H Walters
la source
1
Je ne pense pas que l'explication des labyrinthes 1D soit très claire du tout ... Peut-être que l'ajout d'un exemple plus petit / plus simple aiderait.
mbomb007
C'est plutôt cool. Ouais ça aide.
mbomb007
Même si votre script interactif a aidé, c'est toujours un problème difficile. Alors je le saute juste. Ma compréhension de cela est au mieux encore ténue.
mbomb007
La description du labyrinthe 1D est sommaire. J'ai dû lire jusqu'à la figure 7 pour comprendre que les caractères de la barre verticale dans un labyrinthe 1D sont des murs que vous ne pouvez pas franchir.
edc65
1
exemple 1 avec le labyrinthe 1d empilé dans un labyrinthe 2d où chaque paire de lettres est une échelle: gist.github.com/sparr/36d6355cc4c785a27b12157666169082
Sparr

Réponses:

3

Python 2 avec igraph , 492 369 octets

import igraph,string
def f(s):
 C=s.find('\n')/2;N=' ';g=igraph.Graph(0,[(i,i+j)for i in range(len(s)/(4*C+4)*C)for j in(1,C)if s[(i/C*2+1)*(2*C+2)+i%C*2+2*j+j/C*3]==N]);V=g.vs;g.d=g.degree;O='';V(_d=1)[N]=N;V(_d_gt=2)[N]=list(string.ascii_letters)
 while g.es:
    v=V(_d=1)[0];O+='|'+v[N]
    while g.d(v):w=v.neighbors()[0];g-=(v,w);v=w;O+=N+v[N]if v[N]else''
 print O+'|'

(Les cinquième et sixième lignes commencent chacune par une tabulation, pas quatre espaces comme le montre StackExchange.)

  • Enregistré six octets réarrangeant une certaine arithmétique
  • Enregistré sept octets en utilisant une tranche au lieu de zip
  • Enregistré trois octets en utilisant g+=tuple(v.neighbors())au lieu deg.add_edge(*v.neighbors())
  • Enregistré sept octets en utilisant g-=g.es[g.incident(v)]au lieu deg.delete_edges(g.incident(v))
  • Alias ​​de onze octets enregistrés g.d=g.degree
  • Économisé 52 octets (!) Éliminant une boucle qui contractait tous les couloirs en remplaçant les sommets de degré 2 par un bord entre leurs voisins. Au lieu de cela, la boucle de sortie ignore simplement ces sommets.
  • Enregistré 13 octets en notant que lors de l'attribution des noms, igraph ne se soucie pas si l'itérable fourni est trop long
  • Enregistré quatre octets en n'ayant pas de variable Rpour le nombre de lignes, en déplaçant son calcul vers le seul point d'utilisation
  • Enregistrement de deux octets en modifiant l'indentation de deuxième niveau en tabulations au lieu d'espaces
  • Six octets enregistrés réarrangés 2*(i%C)vers i%C*2, 2*(i/C)vers i/C*2et (C-1)*jversj*C-j
  • Nom de quatre octets enregistré N='n'
  • Enregistrement d'un octet déterminant si un caractère utilise l'espace <'-'plutôt que ==' ', sous l'hypothèse que seuls les caractères valides apparaissent.
  • Puis j'ai réalisé que je peux nommer l'attribut vertex ' 'au lieu de 'n', et réutiliser Npour les deux espaces littéraux dans la source, et ==Nau lieu de <'-', économiser cinq octets supplémentaires

Une version quelque peu non golfée suit. L'idée de base est de faire d'abord un graphique sur tous les sommets du labyrinthe (les points avec une ligne et une colonne impaires lorsqu'ils sont indexés à zéro.) Il y a un bord d'un sommet au suivant sur la même ligne si le caractère suivant est un espace et non |. Il y a un bord du sommet à celui juste en dessous si le caractère correspondant dans la ligne suivante est un espace, et non -.

Après avoir construit ce graphique, nous sélectionnons n'importe quelle feuille et suivons les sommets adjacents successifs, en écrivant leurs noms s'ils ne sont pas un couloir et en supprimant les bords utilisés, jusqu'à ce que nous soyons coincés. Ensuite, nous prenons une autre feuille et continuons jusqu'à ce que tous les bords aient disparu.

import string
import igraph
def f(s):
  C = s.find('\n')/2 # number of maze vertices in each row
  R = len(s)/(4*C+4) # number of rows
  def strpos(r, c):
    """Index of the vertex at row r, col c in the newline-delimited string s"""
    return (2*r+1)*(2*C+2) + 2*c + 1
  def vertpos(i):
    """Index of the i-th vertex in s"""
    return strpos(i/C, i%C)
  g = igraph.Graph(edges=[(i, i+(C if j else 1))
                          for i in range(R*C)
                          for j in (0, 1)
                          if s[vertpos(i)+(2*C+2 if j else 1)] == ' '])
  V = g.vs # the graph's vertex sequence
  O = ''
  V(_degree=1)['n'] = ' ' # All leaves are named space
  W = V(_degree_gt=2) # All warp points...
  W['n'] = list(string.ascii_letters[:len(W)]) # ...are named successive letters
  while g.es: # while any edges remain...
    v = V(_degree=1)[0] # find a leaf
    O += '|'+v['n'] # start a new 'block'
    while v.degree():
      w = v.neighbors()[0] # pick a neighbor
      g -= (v, w) # delete that edge
      v = w
      if v['n']: # If it's a dead end or warp point...
        O += ' '+v['n'] # ...write out the new neighbor
  print O+'|'

Vous pouvez voir les résultats pour les cinq exemples de labyrinthes . (Malheureusement, igraphn'est pas disponible sur Try It Online; ces résultats ont été exportés depuis SageMathCloud .)

Nick Matteo
la source
4

Haskell - 481 405 387 octets

import Data.List
s&t=elemIndices s t
l=last
c!(x:y:z)=l$(y:c)!(x:z):do{[x:p,q]<-mapM([id,reverse]<*>)[[x],[y]];x&[l q];[[]!((q++p):c++z)]}
c![x]=x:[]!c
c!z=z
main=interact(\m->let{g=' '&m;
u=(\\[k|k<-g,length(v>>=(k&))==2])<$>[]!v;
v=[[x,y]|x<-g,y<-g,elem(y-x-1)[0,head$'\n'&m]];
}in '|':(u>>=(++"|").init.(>>=(:" ").toEnum.((+)<*>(+65).(*32).(`div`26)).l.(-1:).(&(nub$u>>=init.tail)))))

Cela crée une liste d'espaces qui se trouvent dans le labyrinthe, numérotés par index dans la chaîne, et l'utilise pour trouver toutes les paires d'espaces adjacents. Il assemble ensuite les paires dans des séquences de points plus longues basées sur les premiers / derniers éléments correspondants et supprime les couloirs, de sorte que chaque séquence est une pièce dans le labyrinthe 1D. Les séquences sont ensuite traduites en une chaîne en remplaçant les points à l'intérieur d'au moins une pièce (les points de chaîne) en lettres correspondantes et le reste en espaces.

Le labyrinthe 2D est lu depuis STDIN et le labyrinthe 1D est imprimé vers STDOUT.

Edit: réduit de 62 octets réorganisant un tas de choses et modifiant un peu l'algorithme, et 14 autres en remplaçant chrpartoEnum comme suggéré par Laikoni.

Édition 2: économisé 13 octets supplémentaires en simplifiant la logique (!), 3 en utilisant le sucre de correspondance de modèle de liste et 2 en utilisant >>=pour concaténer u.

faubi
la source
Je pense que vous n'avez pas besoin des sauts de ligne et des espaces avant les protections de motif, par exemple o(x:p)q|x==last q=[q++p]|1>0=[]devrait fonctionner aussi.
Laikoni
Devrait également toEnumfonctionner au lieu de chr, puis import Data.Charpourrait être supprimé.
Laikoni
Et enfin, comme le défi demande un programme ou une fonction, vous pouvez le remplacer main=interact(\m->...)par juste f m=.... Cela devrait être suffisant pour battre la réponse python, si cela signifie quelque chose pour vous.
Laikoni