Historia
Indiana Jones estaba explorando una cueva donde se encuentra un tesoro precioso. De repente, ocurrió un terremoto.
Cuando terminó el terremoto, notó que algunas rocas que habían caído del techo bloquearon su camino hacia el tesoro. También notó que podía empujar una piedra, pero como las piedras eran muy pesadas, no podía empujar dos piedras consecutivas .
Su objetivo es ayudar a Indiana Jones a obtener el tesoro. Dado que es muy difícil empujar incluso una sola piedra, la cantidad de empujes es muy importante.
Problema
Encuentre la mejor manera (donde Indiana Jones empuja las piedras lo menos posible), para encontrar el tesoro.
Mapa (entrada)
El mapa es una matriz m
by n
(ambas mayores que 1) que puede contener cinco tipos de celdas:
0
lo que significa la celda en blanco,1
lo que significa la pared2
en el que se encuentra Indiana Jones (solo existe uno),3
en el que se encuentra el tesoro (solo existe uno),- y
4
, lo que significa una roca.
En la primera fila del mapa, la dimensión del mapa se especifica como 4 6
, y desde la segunda fila hasta la última fila del mapa, la estructura de la cueva se especifica de esta manera.
110131
104040
100101
200000
Por lo tanto, el mapa completo es:
4 6
110131
104040
100101
200000
lo que significa
El mapa está dado por stdin, un archivo (puede especificar el nombre del archivo) o una matriz en el código que contiene solo la información anterior.
Salida
La cantidad mínima que Indiana Jones debería impulsar. Si no hay tal forma, salida X
.
En el caso anterior , puede empujar una piedra en la izquierda hacia arriba, luego puede empujar una piedra en la derecha hacia la derecha para obtener el tesoro. Por lo tanto, la salida en este caso es 2
.
Sin embargo. en este caso :
4 6
111131
104040
100101
200000
(mira debajo de la sección) no puede empujar la piedra derecha porque destruirá el tesoro. Además, empujar la piedra izquierda hacia la derecha no cambia nada. Por lo tanto, la salida es X
.
Reglas
- Puede moverse solo en cuatro direcciones, arriba, abajo, izquierda y derecha.
- No puede empujar dos piedras consecutivas .
- No puede tirar ninguna piedra, y puede empujar una piedra solo en una dirección ('hacia adelante').
- No puede atravesar paredes. Solo los lugares a los que puede ir son celdas en blanco y la celda del tesoro.
- La piedra no se puede colocar sobre el tesoro. Eso destruirá el tesoro. :(
- No puede salir del mapa.
Metas
Programa que puede manejar la mayoría de los mapas (proporcionados en la sección 'Ejemplo' + otros) en un tiempo razonable (específicamente, 10 segundos) y genera la respuesta correcta gana.
Aquí "otros" significa entradas de ejemplo proporcionadas en las respuestas. Esto significa que debe crear un algoritmo inteligente para que otros programas no puedan resolver mapas que su programa puede resolver, y los mapas resueltos por otros programas pueden ser resueltos por su programa. Sin embargo, poner soluciones en el código no se considerará válido.
Nota
Originalmente era un proyecto de mitad de período de una clase de IA que escuché, solo una cosa era diferente: se decía que solo había dos rocas.
Se dijo que este problema es NP, pero también se dijo que un buen algoritmo heurístico puede resolver el problema de manera bastante eficiente. Utilicé algunas ideas y heurísticas para resolver el problema de manera eficiente, y mi código pudo encontrar todas las soluciones de muestras muy rápidamente (menos de un segundo).
Sin embargo, cuando había más de dos rocas, hubo algunos casos en los que el código no pudo encontrar la respuesta en un tiempo razonable. Tenía algunas ideas, pero algunas de ellas estaban 'equivocadas', y no podía expresar otras ideas al código. Quería ver qué algoritmos inteligentes existen para resolver este problema, así que escribí esto.
Como ya completé el proyecto (por cierto, las imágenes no son mías, busqué en Google), no tiene que preocuparse por eso.
Ejemplos
Se pueden ver ejemplos aquí. También puede ver ejemplos y probar sus resultados aquí (esto debería funcionar en los navegadores modernos). Puede obtener el mapa en el formato descrito anteriormente, escribiendo whatisthis()
en la consola JS.
http://bit.sparcs.org/~differ/sokoban/#0 ~ http://bit.sparcs.org/~differ/sokoban/#19 contiene ejemplos que originalmente eran la clase proporcionada.
Resultado
Lo siento, llegué tarde ... bastante en realidad. : P (Era demasiado vago para anotar. Lo siento).
A continuación se muestra el resultado. (X: incorrecto, O: correcto,?: Toma al menos 10 segundos, detenido)
Map#: 0 1 2 3 4 5 12 15 19 T1 T2 T3 T4 T5 T6 T7
Ruby: X O O ? O O O X ? ? O ? ? ? ? ?
Java: O O X O X X O O ? ? O O O X O O
(Java 19: tardó 25 segundos, el resultado fue correcto). (Usé ruby 1.9.3 y javac 1.7.0_13)
Parece que el algoritmo de Java fue realmente mejor. (Por cierto, pensé en un método similar, pero me di cuenta de que existen mapas como el mapa de prueba 5).
fuente
Respuestas:
Java: un poco más inteligente / más rápido
Un poco de código allí. Intento ser más rápido evaluando los empujes en orden de "cuán probable es que esto libere un camino al tesoro", que en sí mismo se basa en dos recorridos de Dijkstra (uno se detiene al encontrar rocas, el otro ignora las rocas). Está funcionando bastante bien, y el único ejemplo del pastebin que parece ser problemático para el autor se resuelve en aproximadamente 2 segundos con esta implementación. Algunos otros ejemplos toman hasta 30-40 segundos, que todavía encuentro demasiado tiempo, pero no pude encontrar una manera de mejorar eso sin romper las cosas :)
He dividido mis cosas en varios archivos para obtener una mejor estructura (también por qué cambié a Ruby desde Java):
Punto de entrada:
Direction helper enum:
Una clase abstracta para representar una parte ubicada del "laberinto":
Y finalmente, el laberinto en sí:
fuente
Ruby - Enorme y arruinado
Implementación algo ingenua que las fuerzas brutas atraviesan el laberinto. No es súper rápido en algunos (no tan) casos extraños. Se puede mejorar encontrando mejores heurísticas que simplemente "si está más cerca del tesoro, primero queremos investigar", pero las ideas generales están ahí.
También le mostrará cómo Indiana consiguió el tesoro en caso de que pueda, eso es una ventaja.
Editar: Pensé en formas de posiblemente mejorar considerablemente el rendimiento de esto en situaciones no obvias (donde actualmente chupa huevos verdes) dejando caer una evaluación de movimiento simple (por ejemplo, solo me importa cuando Indy empuja rocas y / o llega al tesoro). Probablemente actualizaré el código más tarde, una vez que haya tenido tiempo de implementarlo.
fuente
C ++ 14 de 16
El algoritmo es ineficiente y necesita mucha memoria. Además, no podía permitirme el tiempo para ordenarlo, pero lo haré cuando tenga más tiempo;) Un punto interesante es que mi algoritmo falla en los mismos mapas de prueba que el interrogador. En mi antiguo cuaderno, el proceso comienza a cambiar por los mapas T4 y T6. El mapa 3 lleva bastante tiempo, pero se resuelve a tiempo. Todos los demás se resuelven casi al instante. Así que tendré que descubrir cómo resolver T4 y T6 y probar el algoritmo en una máquina con más memoria. Eventualmente puedo resolver T4 y T6 allí. Mantendré la publicación actualizada ...
A continuación se muestra el resultado. (X: incorrecto, O: correcto,?: Toma al menos 10 segundos, detenido)
Como el código fuente es bastante largo y no es realmente agradable de leer ... Básicamente solo busca todas las rocas que Indiana Jones puede alcanzar. Para las rocas a las que se puede llegar, almacena la información en qué direcciones se puede mover. Entonces se crea una lista de posibles movimientos para el mapa actual. Para cada uno de estos posibles movimientos, se crea una copia del mapa y se aplica el movimiento. Para los mapas recién creados, el algoritmo verificará nuevamente qué movimientos se pueden aplicar ... Esto se hace hasta que no sea posible realizar más movimientos o se encuentre un camino hacia el cofre del tesoro. Como el algoritmo primero intenta todos los movimientos que solo tomarían un movimiento para llegar al cofre, luego todo lo que tomaría dos, y así sucesivamente ... la primera forma encontrada también es automáticamente la más corta. Para evitar bucles, el algoritmo recuerda para cada mapa qué movimientos podrían aplicarse. Si se crea otro mapa que da como resultado una lista de movimientos que ya se encontraron anteriormente, entonces se descartan en silencio, ya que ya se están procesando. Desafortunadamente, no es posible ejecutar cada movimiento solo una vez, ya que podría haber mapas que requieren que una roca se mueva sobre el mismo campo varias veces. De lo contrario, podría ahorrar mucha memoria. Además, para resolver mapas como el mapa 3 a tiempo, el algoritmo ignora todas las rocas que se pueden caminar ... Entonces, en el mapa 3, la roca en el medio de la nada se moverá, pero solo hasta que no haya más paredes a su alrededor. El código se puede compilar con g ++ --std = c ++ 0x con g ++ versión 4.4.3 o posterior. No es posible ejecutar cada movimiento solo una vez, ya que podría haber mapas que requieran que una roca se mueva sobre el mismo campo varias veces. De lo contrario, podría ahorrar mucha memoria. Además, para resolver mapas como el mapa 3 a tiempo, el algoritmo ignora todas las rocas que se pueden caminar ... Entonces, en el mapa 3, la roca en el medio de la nada se moverá, pero solo hasta que no haya más paredes a su alrededor. El código se puede compilar con g ++ --std = c ++ 0x con g ++ versión 4.4.3 o posterior. No es posible ejecutar cada movimiento solo una vez, ya que podría haber mapas que requieran que una roca se mueva sobre el mismo campo varias veces. De lo contrario, podría ahorrar mucha memoria. Además, para resolver mapas como el mapa 3 a tiempo, el algoritmo ignora todas las rocas que se pueden caminar ... Entonces, en el mapa 3, la roca en el medio de la nada se moverá, pero solo hasta que no haya más paredes a su alrededor. El código se puede compilar con g ++ --std = c ++ 0x con g ++ versión 4.4.3 o posterior. pero solo hasta que no haya más paredes a su alrededor. El código se puede compilar con g ++ --std = c ++ 0x con g ++ versión 4.4.3 o posterior. pero solo hasta que no haya más paredes a su alrededor. El código se puede compilar con g ++ --std = c ++ 0x con g ++ versión 4.4.3 o posterior.
Editar: el programa toma su entrada de stdin e ignora la primera línea que contiene el tamaño del mapa. Comprueba si solo se usan los caracteres permitidos en el mapa, pero no verifica que solo haya un Indiana Jones y un cofre del tesoro. Por lo tanto, es posible colocar más de uno y los movimientos mínimos necesarios para alcanzar uno de los cofres se imprimen en stdout. Se omiten los caracteres no válidos en el mapa y el programa intentará calcular la menor cantidad de movimientos para el mapa resultante. El cálculo comenzará cuando stdin esté cerrado (en mi sistema ctrl + d).
fuente