2D Maze Minus 1D

27

Este desafío consiste en convertir laberintos 2D en laberintos 1D.

Visión general

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

Para los propósitos de este desafío, un laberinto 2D tradicional es un laberinto rectangular formado a partir de puntos de celosía donde se cumple todo lo siguiente:

  • Está cerrado (el borde exterior está conectado por paredes).
  • Todos los puntos de la red están conectados a las paredes.
  • Está conectado (por cada dos espacios X e Y hay un camino entre ellos)
  • Es acíclico (no hay rutas desde ningún espacio X de regreso a X sin retroceder)

La Figura 1 muestra un laberinto tradicional en 2D. Estos laberintos tienen tres áreas de interés:

  • Callejones sin salida : lugares desde los que solo hay un camino disponible
  • Corredores : lugares desde los cuales hay dos caminos disponibles
  • Puntos de decisión : lugares desde los cuales hay tres o cuatro rutas disponibles

Para cada laberinto, se puede crear un gráfico donde los callejones sin salida y los puntos de decisión son nodos, y hay un borde entre cada dos nodos conectados por un camino a lo largo de un corredor. La Figura 2 muestra el mismo laberinto con dichos nodos etiquetados, y la Figura 3 el gráfico del laberinto (en notación de puntos ASCII y Graphviz).

Laberintos 1D

Los laberintos 1D incorporan puntos de urdimbre, que vienen en pares, y se identifican usando una letra (en cualquier caso). La Figura 4 muestra un ejemplo de laberinto 1D. De lo contrario, esto es idéntico a un laberinto 2D con una altura de 1, como se muestra en la Figura 5. Observe en particular en la Figura 5 las posiciones de los puntos de celosía marcadas por +, que alternan de izquierda a derecha; en el laberinto 1D, cualquier otro personaje que comience con la pared más a la izquierda también es un punto de red.

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

Las reglas para navegar por este laberinto son las siguientes. Cada movimiento se puede representar como adelante ( >) o hacia atrás ( <). Adelante y atrás aquí por defecto tienen el mismo significado que nuestra conciencia espacial intuitiva; adelante va a la posición inmediatamente a la derecha y hacia atrás inmediatamente a la izquierda.

Los puntos de deformación representan ubicaciones que intercambian asimétricamente la conexión con los vecinos. Si viene de un vecino a un punto warp, la posición de los dos puntos warp se intercambia; Si vienes desde un punto de urdimbre a un vecino, no se intercambian. Por ejemplo, en la Figura 6, moverse hacia atrás desde 1 lo lleva a 2 (dado que 1 es vecino de G y nos movemos desde el vecino, los puntos 2 y @ se intercambian). Avanzar desde 2 (punto de deformación G) lo lleva a 3 (aquí, comenzamos desde un punto de deformación, por lo que no hay intercambio). Del mismo modo, retroceder desde 3 te lleva a @.

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

La Figura 6 también muestra un ejemplo de navegación de X a Y, usando la secuencia de movimientos <<>><>>>>>. Estos movimientos lo llevan a los puntos etiquetados 123456789^respectivamente, en ese orden. Siéntase libre de explorarlo usted mismo usando el fragmento de código en la siguiente sección.

Convertir 2D a 1D

Dado un laberinto 1D, uno puede crear un gráfico donde cada nodo sea un callejón sin salida o un par de puntos de deformación, y existen bordes entre dos nodos conectados a lo largo de un corredor. Este gráfico nos permite comparar laberintos 1D y 2D.

Por ejemplo, el laberinto 1D en la Figura 4 es el mismo laberinto en la Figura 1. Para ver por qué, la Figura 7 agrega etiquetas a los callejones sin salida. Usando esas etiquetas para construir un gráfico, el gráfico de la Figura 7 es simplemente la Figura 3 nuevamente. La Figura 8 muestra un desglose de la construcción de este gráfico.

|  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

(Tenga en cuenta que las etiquetas y el diseño de cada gráfico se seleccionaron artificialmente para alinearse con fines ilustrativos; en general, esto es un problema de isomorfismo gráfico ).

El siguiente fragmento se proporciona para ayudar a visualizar la mecánica del laberinto 1D y la conexión entre el laberinto 1D, el gráfico de equivalencia y el laberinto 2D.

Mostrar fragmento de código

A medida que navega por el laberinto 1D en este fragmento, se resaltan los dos últimos nodos que toca. Los mismos nodos se resaltan de la misma manera en el gráfico de equivalencia y el laberinto 2D.

En general, para cualquier laberinto 2D tradicional se puede crear un laberinto 1D equivalente de este tipo. Un ejemplo un poco más complejo es la Figura 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

Este laberinto tiene un nodo con cuatro caminos (E en la Figura 10). La figura 11 muestra su gráfico. La Figura 12 es un laberinto 1D equivalente; y la Figura 13 muestra el mismo laberinto con etiquetas para callejones sin salida para comparar con la Figura 11.

Reto

Dado un laberinto 2D como entrada, escriba una función o programa que transforme el laberinto 2D en un laberinto 1D con puntos de urdimbre. Los puntos Warp pueden usar cualquiera de las 52 letras en cada caso.

Garantías de entrada (si alguno de estos no se cumple en la entrada, no tiene que lidiar con eso):

  • El laberinto de entrada está conectado (es decir, siempre puede ir de cualquier lugar a otro).
  • El laberinto de entrada está cerrado.
  • El laberinto de entrada es rectangular.
  • Todos los puntos de la red utilizan +.
  • Todos los muros entre puntos de celosía en la misma fila usan |
  • Todos los muros entre puntos de celosía en la misma columna usan -.
  • Todos los espacios son parte de un camino (y todos dentro del laberinto).
  • Los caminos son todos espacios (esto siempre será tradicional, sin deformación)
  • Los caminos son exactamente un espacio de ancho.
  • El laberinto se construye conectando puntos en una red.
  • No hay más de 52 nodos totales (es decir, callejones sin salida más puntos de decisión) en el gráfico del laberinto.

Formato de salida:

  1. Su salida debe ser una sola línea que muestre un laberinto 1D.
  2. Su salida no debe tener espacios en blanco iniciales / finales; excepto que una nueva línea final está bien.
  3. El primer personaje y todos los demás personajes posteriores son puntos de red.
  4. Todas las paredes deben estar en puntos de celosía; y todos los puntos de urdimbre entre ellos.
  5. El gráfico de tu laberinto 1D debe ser equivalente al gráfico del laberinto 2D.
  6. Sus laberintos 1D deben ser compactos; Todos los puntos no reticulados deben ser callejones sin salida (es decir, adyacentes a las paredes) o puntos de urdimbre.
  7. Las únicas letras en su salida deben ser puntos de urdimbre. Cada punto de urdimbre ocurre en la línea exactamente dos veces.

Ejemplo:

|  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

Este es el código de golf. El ganador es el envío correcto sin lagunas con la menor cantidad de bytes.

Pruebas

No hay casos de prueba para este desafío, ya que hay una gran cantidad de salidas correctas para cualquier laberinto no trivial.

Sin embargo, he construido un verificador en C ++ (este verificador grafica ambas soluciones a través de una canonicalización de grafos ).

Además, aquí hay algunos ejemplos para ayudar a ilustrar el formato adecuado:

Ejemplo 1

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

Ejemplo 2

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

Más ejemplos se pueden encontrar aquí .

code-golf graph-theory maze H Walters
fuente
1
No creo que la explicación de los laberintos 1D sea muy clara ... Quizás ayudaría agregar un ejemplo más pequeño / simple.
mbomb007
Eso es muy bonito. Sí, eso ayuda.
mbomb007
Aunque su script interactivo ayudó, sigue siendo un problema difícil. Así que solo me lo salto. Mi comprensión de esto sigue siendo tenue en el mejor de los casos.
mbomb007
La descripción del laberinto 1D es incompleta. Tuve que leer hasta la figura 7 para comprender que los caracteres de la barra vertical en un laberinto 1D son paredes que no se pueden pasar.
edc65
1
ejemplo 1 con el laberinto 1d apilado en un laberinto 2d donde cada par de letras es una escalera: gist.github.com/sparr/36d6355cc4c785a27b12157666169082
Sparr el

Respuestas:

3

Python 2 con igraph , 492 369 bytes

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+'|'

(Las líneas quinta y sexta comienzan con una pestaña, no cuatro espacios como muestra StackExchange).

  • Guardado seis bytes reorganizando algo de aritmética
  • Guardado siete bytes usando un segmento en lugar de zip
  • Guardado tres bytes usando en g+=tuple(v.neighbors())lugar deg.add_edge(*v.neighbors())
  • Guardado siete bytes usando en g-=g.es[g.incident(v)]lugar deg.delete_edges(g.incident(v))
  • Alias ​​de once bytes guardados g.d=g.degree
  • Se guardaron 52 bytes (!) Eliminando un bucle que contrajo todos los corredores al reemplazar los vértices de grado 2 con un borde entre sus vecinos. En cambio, el bucle de salida simplemente ignora estos vértices.
  • Se guardaron 13 bytes notando que al asignar nombres, a igraph no le importa si el iterable proporcionado es demasiado largo
  • Ahorró cuatro bytes al no tener una variable Rpara el número de filas, moviendo su cálculo al único punto de uso
  • Se guardaron dos bytes cambiando la sangría de segundo nivel a pestañas en lugar de espacios
  • Se guardaron seis bytes que se reorganizaron 2*(i%C)en i%C*2, 2*(i/C)en i/C*2y (C-1)*jenj*C-j
  • Nombre de cuatro bytes guardado N='n'
  • Se guardó un byte para determinar si un carácter usa espacio en <'-'lugar de ==' ', bajo el supuesto de que solo aparecen caracteres válidos.
  • Luego me di cuenta de que puedo nombrar el atributo de vértice en ' 'lugar de 'n', y reutilizar Npara los dos espacios literales en la fuente, y en ==Nlugar de <'-'guardar cinco bytes más

A continuación se presenta una versión poco golfing. La idea básica es hacer primero un gráfico en todos los vértices del laberinto (los puntos con fila y columna impares cuando están indexados a cero). Hay un borde de un vértice al siguiente en la misma fila si el siguiente carácter es un espacio y no |. Hay un borde desde el vértice hasta el que está debajo de él si el carácter correspondiente en la siguiente fila es un espacio, y no -.

Después de construir este gráfico, seleccionamos cualquier hoja y seguimos a lo largo de vértices adyacentes sucesivamente, escribiendo sus nombres si no son un corredor y eliminando los bordes usados, hasta que nos atascamos. Luego tomamos otra hoja y continuamos hasta que todos los bordes se hayan ido.

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+'|'

Puede ver los resultados de los cinco laberintos de ejemplo . (Desafortunadamente, igraphno está disponible en Try It Online; estos resultados se exportaron desde SageMathCloud ).

Nick Matteo
fuente
4

Haskell - 481 405 387 bytes

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

Esto crea una lista de espacios que están en el laberinto, numerados por índice en la cadena, y los usa para encontrar todos los pares de espacios adyacentes. Luego une los pares en secuencias más largas de puntos basados ​​en el primer / último elemento y elimina los corredores, de modo que cada secuencia es una habitación en el laberinto 1D. Luego, las secuencias se traducen en una cadena reemplazando los puntos en el interior de al menos una habitación (los puntos de urdimbre) en las letras correspondientes y el resto en espacios.

El laberinto 2D se lee desde STDIN y el laberinto 1D se imprime en STDOUT.

Editar: reducido en 62 bytes reorganizando un montón de cosas y modificando un poco el algoritmo, y otros 14 reemplazando chrpor toEnumlo sugerido por Laikoni.

Edición 2: ahorró 13 bytes más al simplificar la lógica (!), 3 usando el patrón de lista de coincidencias de azúcar y 2 usando >>=para concat u.

faubi
fuente
Creo que no necesita las nuevas líneas y espacios antes de los protectores de patrones, por ejemplo o(x:p)q|x==last q=[q++p]|1>0=[], también debería funcionar.
Laikoni
También toEnumdebería funcionar en lugar de chr, luego import Data.Charpodría descartarse.
Laikoni
Y, por último, cuando el desafío solicita un programa o función, puede reemplazarlo main=interact(\m->...)por solo f m=.... Esto debería ser suficiente para superar la respuesta de Python, si eso significa algo para usted.
Laikoni