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:
###
#.#
###
.#
#.
####
.#..
####
#.#.#
..#..
#####
..#..
#.#.#
#.#.#.#.#.#
..#...#.#..
###.###.###
..#.#......
#.#.#######
#.#.......#
#.#######.#
#.#.....#.#
#.#.#.#.#.#
##....#####
.#..#...##.
.##.#..#...
..###.###..
#..##.#####
#...##....#
#.#.#####.#
###..####.#
....####...
###...#####
###....##.#########
####...##....#...##
..####.#######.###.
....##..........##.
###..#####.#..##...
####..#..#....#..##
..###.####.#.#..##.
..###...#....#.#...
..####..##.###...##
#.####.##..#####.##
####...##.#####..##
###########
........#..
#########.#
..........#
.##########
.#.........
##.########
...#.......
.
y uno#
en la entrada.Respuestas:
JavaScript (ES6),
235253El 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.
Prueba en la consola Firefox / FireBug
Infinito
Salida
Finito
Salida
fuente
(j%4-1)%2
da un bonito patrón repetitivo.L=
hacia el conteo de bytes.C # -
423375 bytesComplete 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).
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:
fuente
C#
respuesta como el principal votante aquí.Python 2 -
258210244 bytesVerifique recursivamente las rutas, si el desbordamiento de la pila devuelve 1 (verdad), si no devuelve Ninguno (falsey).
fuente
;
las líneasp
, ya que las obtendrá en la misma línea con elif
.Python 2 -
297286275 bytesSelecciona 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
1
para infinito y0
para finito.Devuelve resultados correctos para todos los casos de prueba.
fuente