Laberintos infinitos

35

Fondo

Eres el aprendiz de un poderoso mago, y tu maestro está desarrollando un hechizo para crear un laberinto interdimensional para atrapar a sus enemigos. Quiere que programes su computadora a vapor para analizar los posibles diseños. Programar esta máquina diabólica es muy peligroso, por lo que querrá mantener el código lo más corto posible.

Entrada

Su entrada es una cuadrícula bidimensional de puntos .y hashes #, que significa espacio vacío y paredes, dados como una cadena delimitada por una nueva línea. Siempre habrá al menos uno .y uno #, y usted puede decidir si hay una nueva línea final o no.

Esta cuadrícula es el plano de un laberinto infinito, que se realiza alineando infinitas copias de la cuadrícula una al lado de la otra. El laberinto se divide en cavidades , que son componentes conectados de espacios vacíos (los espacios diagonalmente adyacentes no están conectados). Por ejemplo, la cuadrícula

##.####
...##..
#..#..#
####..#
##...##

da como resultado el siguiente laberinto (continúa infinitamente en todas las direcciones):

##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##

Este laberinto en particular contiene una cavidad de área infinita. Por otro lado, este plan resulta en un laberinto con solo cavidades finitas:

##.####
##..###
####...
..####.
#..####

Salida

Su salida será un valor verdadero si el laberinto contiene una cavidad infinita, y un valor falso si no. Tenga en cuenta que el laberinto puede contener cavidades finitas e infinitas; en ese caso, el resultado será verdadero.

Reglas

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba adicionales

Caries infinitas:

.#

#.#
...
#.#

#.###.#.###.#
#.#...#...#.#
#.#.#####.#.#
..#.#...#.#..
###.#.#.#.###
#...#.#.#...#
#.###.#.###.#

##.###
#..###
..##..
###..#
##..##

..#..#..#..#..#..#
.#..#..#..#..#..#.
#..#..#..#..#..#..

#.####.###.###.####
#...#..#...###..###
###.#..#.######..##
....####.#######...
###..###...########
##########.##....##
..###......##.##...
#.........##..#####
###########..###..#
#...........####..#
#.###########.##..#
#.##....##.....####
#.####.###.###.####

Cavidades finitas:

###
#.#
###

.#
#.

####
.#..
####

#.#.#
..#..
#####
..#..
#.#.#

#.#.#.#.#.#
..#...#.#..
###.###.###
..#.#......
#.#.#######
#.#.......#
#.#######.#
#.#.....#.#
#.#.#.#.#.#

##....#####
.#..#...##.
.##.#..#...
..###.###..
#..##.#####
#...##....#
#.#.#####.#
###..####.#
....####...
###...#####

###....##.#########
####...##....#...##
..####.#######.###.
....##..........##.
###..#####.#..##...
####..#..#....#..##
..###.####.#.#..##.
..###...#....#.#...
..####..##.###...##
#.####.##..#####.##
####...##.#####..##


###########
........#..
#########.#
..........#
.##########
.#.........
##.########
...#.......
Zgarb
fuente
¿Hay un carácter de nueva línea al final?
FUZxxl
@FUZxxl Eso depende de ti.
Zgarb
¿Puede el laberinto infinito ser una línea recta que va al infinito?
1
@Neil, no estoy seguro de lo que quieres decir. El primer y segundo ejemplos infinitos tienen líneas infinitas, pero hay al menos uno .y uno #en la entrada.
Zgarb
1
Bonito desafío, más difícil de lo que parece
edc65

Respuestas:

2

JavaScript (ES6), 235253

El mismo método utilizado por @mac. Para cada celda libre, intento un relleno recursivo, marcando las celdas usadas con la coordenada que estoy usando (que puede estar fuera de la plantilla original). Si durante el relleno llego a una celda ya marcada con una coordenada diferente, estoy en un camino infinito.

La forma peculiar de manejar el módulo en JS es bastante molesta.

L=g=>(
  g=g.split('\n').map(r=>[...r]),
  w=g[0].length,h=g.length,
  F=(x,y,t=((x%w)+w)%w,u=((y%h)+h)%h,v=g[u][t],k=0+[x,y])=>
    v<'.'?0:v>'.'?v!=k
    :[0,2,-3,5].some(n=>F(x+(n&3)-1,y+(n>>2)),g[u][t]=k),
  g.some((r,y)=>r.some((c,x)=>c=='.'&&F(x,y)))
)

Prueba en la consola Firefox / FireBug

Infinito

['##.###\n#..###\n..##..\n###..#\n##..##'
,'#.#\n...\n#.#'
,'#.###.#.###.#\n#.#...#...#.#\n#.#.#####.#.#\n..#.#...#.#..\n###.#.#.#.###\n#...#.#.#...#\n#.###.#.###.#'
,'##.###\n#..###\n..##..\n###..#\n##..##'
,'#.####.###.###.####\n#...#..#...###..###\n###.#..#.######..##\n....####.#######...\n###..###...########\n##########.##....##\n..###......##.##...\n#.........##..#####\n###########..###..#\n#...........####..#\n#.###########.##..#\n#.##....##.....####\n#.####.###.###.####'
].forEach(g=>console.log(g,L(g)))

Salida

"##.###
#..###
..##..
###..#
##..##" true

"#.#
...
#.#" true

"#.###.#.###.#
#.#...#...#.#
#.#.#####.#.#
..#.#...#.#..
###.#.#.#.###
#...#.#.#...#
#.###.#.###.#" true

"##.###
#..###
..##..
###..#
##..##" true

"#.####.###.###.####
#...#..#...###..###
###.#..#.######..##
....####.#######...
###..###...########
##########.##....##
..###......##.##...
#.........##..#####
###########..###..#
#...........####..#
#.###########.##..#
#.##....##.....####
#.####.###.###.####" true

Finito

['###\n#.#\n###', '.#\n#.', '####\n.#..\n####'
,'#.#.#\n..#..\n#####\n..#..\n#.#.#'
,'#.#.#.#.#.#\n..#...#.#..\n###.###.###\n..#.#......\n#.#.#######\n#.#.......#\n#.#######.#\n#.#.....#.#\n#.#.#.#.#.#'
,'##....#####\n.#..#...##.\n.##.#..#...\n..###.###..\n#..##.#####\n#...##....#\n#.#.#####.#\n###..####.#\n....####...\n###...#####'
,'###....##.#########\n####...##....#...##\n..####.#######.###.\n....##..........##.\n###..#####.#..##...\n####..#..#....#..##\n..###.####.#.#..##.\n..###...#....#.#...\n..####..##.###...##\n#.####.##..#####.##\n####...##.#####..##'
].forEach(g=>console.log(g,L(g)))

Salida

"###
#.#
###" false

".#
#." false

"####
.#..
####" false

"#.#.#
..#..
#####
..#..
#.#.#" false

"#.#.#.#.#.#
..#...#.#..
###.###.###
..#.#......
#.#.#######
#.#.......#
#.#######.#
#.#.....#.#
#.#.#.#.#.#" false

"##....#####
.#..#...##.
.##.#..#...
..###.###..
#..##.#####
#...##....#
#.#.#####.#
###..####.#
....####...
###...#####" false

"###....##.#########
####...##....#...##
..####.#######.###.
....##..........##.
###..#####.#..##...
####..#..#....#..##
..###.####.#.#..##.
..###...#....#.#...
..####..##.###...##
#.####.##..#####.##
####...##.#####..##" false
edc65
fuente
Sí, Daft Modulo también fue un dolor en C #, pero creo que he encontrado una manera de hacer un buen uso de él en mi copia de trabajo con el código direccional (solo volveré a publicar si puedo obtener un 10% reducción o mejor): (j%4-1)%2da un bonito patrón repetitivo.
VisualMelon
Creo que las funciones sin nombre son permisibles y, por lo tanto, a menos que la función incluya una llamada a sí misma (parece que no), es permisible no contar L=hacia el conteo de bytes.
SuperJedi224
@ SuperJedi224 probablemente tengas razón, pero es lo suficientemente corto como es después de todo
edc65
21

C # - 423 375 bytes

Complete el programa C #, acepta la entrada a través de STDIN, emite "Verdadero" o "Falso" a STDOUT según corresponda.

No podía soportar dejar ese Linq allí ... ¡afortunadamente su eliminación valió la pena! Ahora realiza un seguimiento de las celdas vistas y visitadas en una matriz (dado que de todos modos solo mira un número finito de ellas). También reescribí el código direccional, eliminando la necesidad de un Lambda y, en general, haciendo que el código sea más imposible de entender (pero con un considerable ahorro de bytes).

using C=System.Console;struct P{int x,y;static void Main(){int w=0,W,k=0,o,i,j;P t;string D="",L;for(;(L=C.ReadLine())!=null;D+=L)w=L.Length;for(i=W=D.Length;i-->0&k<W;){k=1;P[]F=new P[W];for(F[j=0].x=i%w+W*W,F[0].y=i/w+W*W;D[i]>35&j<k;)for(t=F[j++],o=1;o<5&k<W;t.y+=(o++&2)-1){t.x+=o&2;if(D[--t.x%w+t.y%(W/w)*w]>35&System.Array.IndexOf(F,t)<0)F[k++]=t;}}C.WriteLine(k>=W);}}

Es una búsqueda de amplitud (no es que esto importe) que simplemente continúa hasta que se atasca en una caverna finita, o decide que la caverna es lo suficientemente grande como para que sea infinitamente grande (cuando tiene tantas celdas como rectángulo original, esto significa que debe haber un camino desde una celda a sí mismo en otro lugar, que podemos seguir para siempre).

Código sin recortar:

using C=System.Console;

struct P
{
    int x,y;

    static void Main()
    {
        int w=0, // w is the width
        W, // W is the length of the whole thing
        k=0, // k is visited count
        o, // o is offset, or something (gives -1,0 0,-1 +1,0 0,+1 t offset pattern)
        i, // i is the start cell we are checking currently
        j; // j is the F index of the cell we are looking at

        P t; // t is the cell at offset from the cell we are looking at

        string D="", // D is the map
        L;

        for(;(L=C.ReadLine())!=null; // read a line, while we can
            D+=L) // add the line to the map
            w=L.Length; // record the width

        for(i=W=D.Length;i-->0&k<W;) // for each cell
        {
            k=1;

            P[]F=new P[W]; // F is the list of visited cells,

            for(F[j=0].x=i%w+W*W,F[0].y=i/w+W*W; // there are reasons (broken modulo)
                D[i]>35&j<k;) // for each cell we've visited, until we've run out
                for(t=F[j++], // get the current cell
                    o=1; // o is just a counter which we use to kick t about
                    o<5& // 4 counts
                    k<W; // make sure we havn't filled F
                    t.y+=(o++&2)-1) // kick and nudge y, inc o
                {
                    t.x+=o&2; // kick x
                    if(D[--t.x%w+t.y%(W/w)*w]>35 // nudge x, it's a dot
                       &System.Array.IndexOf(F,t)<0) // and we've not seen it before
                        F[k++]=t; // then add it
                }
        }

        C.WriteLine(k>=W); // result is whether we visited lots of cells
    }
}
VisualMelon
fuente
1
Probablemente la primera vez que he visto una C#respuesta como el principal votante aquí.
Michael McGriff
1
Main () en struct, ahora eso es lindo.
PTwr
10

Python 2 - 258 210 244 bytes

Verifique recursivamente las rutas, si el desbordamiento de la pila devuelve 1 (verdad), si no devuelve Ninguno (falsey).

import sys
def k(s):
 a=len(s);m=[[c=='.'for c in b]*999for b in s.split('\n')]*999;sys.setrecursionlimit(a)
 for x in range(a*a):
  try:p(m,x/a,x%a)
  except:return 1
def p(m,x,y):
 if m[x][y]:m[x][y]=0;map(p,[m]*4,[x,x,x+1,x-1],[y+1,y-1,y,y])
Kyle Gullion
fuente
1
Puede guardar algunos bytes utilizando ;las líneas p, ya que las obtendrá en la misma línea con el if.
PurkkaKoodari
11
"Si el desbordamiento de pila devuelve verdadero" - Me gusta la condición de fin de recursión :)
schnaader
3
No estoy convencido de que este sea un enfoque válido. El uso de desbordamientos de pila para detectar una región "infinita" producirá falsos positivos. La especificación del problema no establece ninguna limitación en los rangos de entrada, pero algo como un laberinto de 300x300 no parece irrazonable y podría encerrar caminos finitos muy largos.
JohnE
44
Casi todos los laberintos finitos también causarían un desbordamiento de la pila. Este no es un programa válido.
PyRulez
@johne Actualizado para que el límite de recursión sea del orden del tamaño de los laberintos. Desafortunadamente, se agregaron 34 bytes, pero ahora debería ser correcto (al menos tan correcto como un truco como este puede ser).
Kyle Gullion
5

Python 2 - 297 286 275 bytes

Selecciona una celda "abierta" arbitraria para comenzar un relleno de inundación. El laberinto es infinito si durante el llenado volvemos a visitar una celda que ya hemos visitado, pero tiene una coordenada diferente a la visita anterior. Si el relleno de inundación llena toda la región sin encontrar dicha celda, pruebe con una región diferente. Si no se puede encontrar esa región, el laberinto es finito.

Toma el archivo para procesar en la línea de comando, devuelve el código de salida 1para infinito y 0para finito.

Devuelve resultados correctos para todos los casos de prueba.

import sys
e=enumerate
C=dict([((i,j),1)for i,l in e(open(sys.argv[1]))for j,k in e(l)if'.'==k])
while C:
 d={}
 def f(r,c):
  n=(r%(i+1),c%j)
  if n in d:return(r,c)!=d[n]
  if C.pop(n,0):d[n]=(r,c);return any(map(f,[r-1,r,r+1,r],[c,c+1,c,c-1]))
 if f(*C.keys()[0]):exit(1)
Mac
fuente
1
No puede suponer que alguna célula será miembro de una caverna infinita, puede tener fácilmente cavernas infinitas y finitas.
VisualMelon
2
@VisualMelon: lo siento, la descripción no es del todo correcta. El código realmente verifica todas las regiones posibles de celdas interconectadas, no solo una (como está implícito actualmente). Para eso es para el ciclo while final: seleccionar regiones para verificar mientras aún quedan celdas sin marcar.
Mac