Su objetivo es escribir un programa que crea un mapa utilizando al azar 10x10 0
, 1
y 2
, y encuentra el camino más corto desde la parte superior izquierda a la inferior derecha, en el supuesto de que:
0 representa un campo de hierba: cualquiera puede caminar sobre él;
1 representa un muro: no puedes cruzarlo;
2 representa un portal: al ingresar a un portal, puede moverse a cualquier otro portal en el mapa.
Especificaciones:
- El elemento superior izquierdo y el inferior derecho deben ser 0 ;
- Al crear el mapa aleatorio, cada campo debe tener un 60% de posibilidades de ser un 0 , un 30% de ser un 1 y un 10% de ser un 2 ;
- Puedes moverte en cualquier campo adyacente (incluso los diagonales);
- Su programa debe generar el mapa y el número de pasos de la ruta más corta;
- Si no hay una ruta válida que conduzca al campo inferior derecho, su programa solo debería generar el mapa;
- Puede usar cualquier recurso que desee;
- El código más corto gana.
Cálculo de pasos:
un paso es un movimiento real; Cada vez que cambia de campo, incrementa el contador.
Salida:
0000100200
0100100010
1000000111
0002001000
1111100020
0001111111
0001001000
0020001111
1100110000
0000020100
9
code-golf
path-finding
maze
Vereos
fuente
fuente
Respuestas:
GolfScript, 182 caracteres
Ejemplos:
fuente
Mathematica (344)
Bonus: resaltado del camino
Creo el gráfico de todas las películas posibles en vértices vecinos y agrego todos los "teletransportes" posibles.
fuente
Mathematica,
208caracteresBase en las soluciones de David Carraher y ybeltukov. Y gracias a la sugerencia de ybeltukov.
fuente
n/n
lugar den/10
:)〚 〛
para los corchetes (son símbolos Unicode correctos)Norm[# - #2] & @@ # < 2 || # \[Union] u == u &
Norm[# - #2] & @@ # < 2
significa que la distancia entre dos puntos es menor que 2, por lo que deben ser adyacentes.# ⋃ u == u
significa que ambos puntos están en u.Pitón 3, 279
Alguna variante de Dijkstra. Feo, pero jugué tanto como pude ...
Ejecución de muestra
fuente
Mathematica
316 279275El objeto básico es una matriz de 10x10 con aproximadamente 60 0, 30 1 y 10 2. La matriz se utiliza para modificar un 10x10
GridGraph
, con todos los bordes conectados. Los nodos que corresponden a las celdas que contienen 1 en la matriz se eliminan del gráfico. Esos nodos "que sostienen 2" están todos conectados entre sí. Luego se busca la ruta más corta entre el vértice 1 y el vértice 100. Si dicha ruta no existe, se devuelve el mapa; si existe tal ruta, se muestran el mapa y la longitud de ruta más corta.Ejecución de muestra :
fuente
Pitón (1923)
Búsqueda de retrocesoEs cierto que no es el más corto ni el más eficiente, aunque hay algunas memorias presentes.
fuente
JavaScript (541)
La generación de gráficos ocurre en las primeras cinco líneas.
f
contiene los campos,p
contiene los portales. La búsqueda real se implementa a través de BFS.Salida de ejemplo:
fuente
Pitón 3 (695)
Dijkstra!
Salida de ejemplo:
fuente
Python, 314
Es una implementación desagradable de Bellman-Ford. Este algoritmo es O (n ^ 6)! (Lo cual está bien para n = 10)
fuente
print '\n'.join(map(str,a))
; Lo hiceprint a
por el bien del golf.r*10
tiene 100 elementos).