Dadas 2 entradas enteras que representan el tamaño del campo, x
y y
, generan una ruta a través del campo.
Ejemplo de salida para 5, 4
:
#
#
# ###
### #
Todo el campo es de 5 por 4, y hay un camino hecho de marcas que cruzan el campo.
La ruta siempre debe comenzar en la esquina superior izquierda e ir a la esquina inferior derecha. Toda la ruta debe ser aleatorizada cada vez que se ejecuta el programa. Cada ruta válida debe ser una salida posible.
Las reglas para los caminos son:
Hecho de hashmarks
Cada hash solo está conectado a otros 2 hashes (es decir, el camino no se cruza ni corre junto a sí mismo)
Los espacios no hash pueden llenarse con cualquier otro carácter, pero deben ser consistentes (es decir, todos los espacios, todos los puntos, etc.)
Ejemplos:
2, 2
##
#
3, 4
##
##
#
#
5, 5
#####
#
#
#
#
6, 5
## ###
# # #
## # #
# ## #
### #
7, 9
#######
#
#### #
# # #
# # #
# # #
# ####
#
#######
Este tipo de camino es similar a una caminata aleatoria que se evita a sí mismo, sin embargo, no puede ser adyacente a sí mismo a diferencia de una verdadera SIERRA.
La continuidad del camino y el contacto del camino se definen sin diagonales.
Respuestas:
MATLAB,
316 305 300293 bytesGracias @LuisMendo por varias sugerencias y un montón de bytes =)
Pruébalo en línea! (Sin garantía: tenga en cuenta que se necesitaron algunos ajustes para que se ejecute en Octave: en primer lugar, necesitaba eliminar la
function
palabra clave y codificar los valores, en segundo lugar: los espacios no se imprimen correctamente como en Matlab. Tampoco lo hice verifique los comandos de convolución de Octave, que podrían actuar de manera diferente).Ejemplo de salida para entrada
(7,10)
(ya puede tomar bastante tiempo):Explicación
Esto genera rutas secuencialmente desde la parte superior izquierda a la parte inferior derecha con la conectividad 4 deseada, y luego utiliza el muestreo de rechazo para rechazar rutas que violan el criterio de que no puede tener partes adyacentes.
Ah y como siempre:
fuente
Befunge, 344 bytes
Pruébalo en línea!
Como @flawr mencionó en su respuesta de MATLAB, esto puede llevar algún tiempo si el tamaño del campo no es trivial. De hecho, es bastante fácil entrar en una situación en la que realmente no vale la pena intentar esperar a que termine, porque es muy probable que espere hasta el final de los tiempos.
Para entender por qué sucede esto, es útil ver el programa mientras se ejecuta en uno de los muchos "depuradores visuales" de Befunge. Dado que los datos y el código son lo mismo en Befunge, podrá ver la ruta a medida que cambia con el tiempo. Por ejemplo, aquí hay una breve animación que muestra cómo se vería una parte de una carrera en una ruta lenta.
Una vez que el algoritmo decide hacer ese giro fatídico a la izquierda en la parte inferior del límite del campo, esencialmente se ha condenado a una vida de vagar sin rumbo. A partir de ese momento, debe seguir todos los caminos posibles en esa área cercada antes de que pueda retroceder e intentar girar a la derecha. Y la cantidad de caminos potenciales en estos casos puede convertirse fácilmente en astronómica.
En pocas palabras: si parece que lleva mucho tiempo, probablemente sea una buena idea abortar la ejecución y comenzar de nuevo.
Explicación
Esto es básicamente un algoritmo recursivo, que prueba todas las rutas posibles a través del campo y luego desenrolla los pasos que ya se han seguido cada vez que se atasca. Como Befunge no tiene el concepto de funciones, una función recursiva está fuera de discusión, pero podemos emular el proceso rastreando el estado en la pila.
Esto funciona al llenar la pila con coordenadas potenciales que podemos querer seguir. Luego sacamos un conjunto de la pila y verificamos si es adecuado (es decir, dentro del rango y no superpuesto con una ruta existente). Una vez que tenemos un buen lugar, escribimos un
#
en el campo de juego en esa ubicación y agregamos esos detalles a la pila en caso de que necesitemos retroceder más tarde.Luego empujamos cuatro conjuntos de coordenadas adicionales en la pila (en orden aleatorio) que indican los posibles caminos que podemos tomar desde esta nueva ubicación, y saltamos de regreso al inicio del ciclo. Si ninguna de las rutas potenciales es factible, llegaremos al punto en la pila donde guardamos la ubicación de
#
que escribimos, por lo que desharemos ese paso y continuaremos probando las coordenadas potenciales de un paso anterior.Así es como se ve el código con las diversas partes componentes resaltadas:
Lea el ancho y la altura del campo, y presione las coordenadas de inicio junto con un
0
marcador de tipo para indicar una ruta potencial en lugar de una ubicación de retroceso.Verifique las ubicaciones de retroceso (indicadas por un
1
marcador de tipo) que se revierten con unp
comando simple , ya que se almacenan en el formato exacto necesario para volver a escribir un espacio en el campo de juego.Comprueba si las coordenadas todavía están dentro del campo de juego. Si están fuera de alcance, suéltelos de la pila y vuelva a intentarlo para probar las siguientes coordenadas potenciales.
Si están dentro del rango, obtenga los siguientes dos valores de la pila, que es la ubicación del paso anterior (requerido en la prueba que sigue a esto).
Compruebe si las coordenadas van a entrar en contacto con un segmento existente de la ruta. La ubicación del paso anterior obviamente se ignora de esta verificación.
Si todas las pruebas son exitosas, escriba unEmpuje cuatro destinos potenciales a los que se puede llegar desde la ubicación actual. El número aleatorio determina el orden en que se empujan y, por lo tanto, el orden en que se seguirán.
#
en el campo de juego y verifica si hemos llegado a la ubicación de destino.Si es así, escriba la ruta final y salga.
De lo contrario, guarde las coordenadas en la pila con un
1
marcador de tipo para retroceder más tarde.Esto se interrumpe con un cálculo de número aleatorio que vamos a necesitar pronto. Regrese al inicio del bucle principal y procese los siguientes valores en la pila.
fuente
QBasic, 259 bytes
Seguro que amo
GOTO
s.Estrategia básica: en cada paso, imprima
#
a en la ubicación actual y muévase en una dirección aleatoria. Un conjuntoa
de 0 y 1 realiza un seguimiento de dónde hemos estado. Si el movimiento es legal y nos lleva al punto final,GOTO 9
para salir del bucle e imprimir el final#
. De lo contrario, si el movimiento es legal, dé otro paso. De lo contrario, borre la pantalla y comience de nuevo (¡mucho más golf que codificar un algoritmo de retroceso!).Probado en mi computadora portátil en QB64, esto generalmente produce un resultado
9, 9
en cinco segundos o menos. Las carreras de10, 10
han tomado entre tres y 45 segundos. Teóricamente, todas las rutas legales tienen una probabilidad distinta de cero, pero la probabilidad de una ruta con curvas grandes es muy pequeña. Sin embargo, ocasionalmente he visto caminos con una o dos curvas pequeñas:Versión sin golf y / o explicación en profundidad disponible bajo petición.
fuente
R, 225 bytes
Explicación:
Generamos un gráfico regular (reticular) [x * y] no dirigido con pesos aleatorios en los bordes y luego encontramos el camino más corto desde el principio hasta el final. Sin embargo, en la ruta generada puede haber celdas que tengan más de dos vecinos, por ejemplo:
Entonces deberíamos aplicar el algoritmo de ruta más corta dos veces. En la segunda vez, establecemos todos los pesos en 1, excepto los que están en la ruta actual que se establece en 0;
resultado
Sin golf:
fuente
JavaScript (ES7),
333331330329324318312 bytesExpansión: los
#
s se colocan aleatoriamente en la matriz hasta que se encuentra una ruta a través del campo mediante una búsqueda de amplitud; el primero, y por lo tanto el más corto, ese camino se emite; Esto garantiza que el camino no se cruce. Tenga en cuenta que, en particular para campos más grandes, es posible superar la pila del motor JS antes de encontrar una ruta. Sin golf:fuente