En el juego de Flood Paint, el objetivo del juego es conseguir que todo el tablero sea del mismo color en el menor número de turnos posible.
El juego comienza con un tablero que se parece a esto:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 3[3]1 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
Actualmente, el número (que representa un color) en el centro del tablero es 3. Cada turno, el cuadrado en el centro cambiará de color, y todos los cuadrados del mismo color que son accesibles desde el centro moviéndose horizontal o verticalmente ( es decir, en la región de inundación del cuadrado central) cambiará los colores con él. Entonces, si el cuadrado central cambia de color a 5:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 5[5]1 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
entonces el 3 que estaba a la izquierda del centro 3 también cambiará de color. Ahora hay un total de siete 5's accesibles desde el centro, y si cambiamos de color a 4:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 4 4 4 4 1 4
6 2 4 4[4]1 1 6 6
5 5 1 2 4 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
La región pintada nuevamente aumenta de tamaño dramáticamente.
Su tarea es crear un programa que tome una cuadrícula de colores de 19 por 19 del 1 al 6 como entrada, en cualquier forma que elija:
4 5 1 1 2 2 1 6 2 6 3 4 2 3 2 3 1 6 3
4 2 6 3 4 4 5 6 4 4 5 3 3 3 3 5 4 3 4
2 3 5 2 2 5 5 1 2 6 2 6 6 2 1 6 6 1 2
4 6 5 5 5 5 4 1 6 6 3 2 6 4 2 6 3 6 6
1 6 4 4 4 4 6 4 2 5 5 3 2 2 4 1 5 2 5
1 6 2 1 5 1 6 4 4 1 5 1 3 4 5 2 3 4 1
3 3 5 3 2 2 2 4 2 1 6 6 6 6 1 4 5 2 5
1 6 1 3 2 4 1 3 3 4 6 5 1 5 5 3 4 3 3
4 4 1 5 5 1 4 6 3 3 4 5 5 6 1 6 2 6 4
1 4 2 5 6 5 5 3 2 5 5 5 3 6 1 4 4 6 6
4 6 6 2 6 6 2 4 2 6 1 5 6 2 3 3 4 3 6
6 1 3 6 3 5 5 3 6 1 3 4 4 5 1 2 6 4 3
2 6 1 3 2 4 2 6 1 1 5 2 6 6 6 6 3 3 3
3 4 5 4 6 6 3 3 4 1 1 6 4 5 1 3 4 1 2
4 2 6 4 1 5 3 6 4 3 4 5 4 2 1 1 4 1 1
4 2 4 1 5 2 2 3 6 6 6 5 2 5 4 5 4 5 1
5 6 2 3 4 6 5 4 1 3 2 3 2 1 3 6 2 2 4
6 5 4 1 3 2 2 1 1 1 6 1 2 6 2 5 6 4 5
5 1 1 4 2 6 2 5 6 1 3 3 4 1 6 1 2 1 2
y devuelve una secuencia de colores que el cuadrado central cambiará en cada turno, nuevamente en el formato que elija:
263142421236425431645152623645465646213545631465
Al final de cada secuencia de movimientos, los cuadrados en la cuadrícula de 19 por 19 deben ser todos del mismo color.
Su programa debe ser completamente determinista; Se permiten soluciones pseudoaleatorias, pero el programa debe generar la misma salida para el mismo caso de prueba cada vez.
El programa ganador tomará la menor cantidad total de pasos para resolver los 100,000 casos de prueba encontrados en este archivo (archivo de texto comprimido, 14.23 MB). Si dos soluciones toman el mismo número de pasos (por ejemplo, si ambos encontraron la estrategia óptima), el programa más corto ganará.
BurntPizza ha escrito un programa en Java para verificar los resultados de la prueba. Para usar este programa, ejecute su envío y canalice la salida a un archivo llamado steps.txt
. Luego, ejecute este programa con steps.txt
y el floodtest
archivo en el mismo directorio. Si su entrada es válida y produce soluciones correctas para todos los archivos, debe pasar todas las pruebas y regresarAll boards solved successfully.
import java.io.*;
import java.util.*;
public class PainterVerifier {
public static void main(String[] args) throws FileNotFoundException {
char[] board = new char[361];
Scanner s = new Scanner(new File("steps.txt"));
Scanner b = new Scanner(new File("floodtest"));
int lineNum = 0;
caseloop: while (b.hasNextLine()) {
for (int l = 0; l < 19; l++) {
String lineb = b.nextLine();
if (lineb.isEmpty())
continue caseloop;
System.arraycopy(lineb.toCharArray(), 0, board, l * 19, 19);
}
String line = s.nextLine();
if (line.isEmpty())
continue;
char[] steps = line.toCharArray();
Stack<Integer> nodes = new Stack<Integer>();
for (char c : steps) {
char targetColor = board[180];
char replacementColor = c;
nodes.push(180);
while (!nodes.empty()) {
int n = nodes.pop();
if (n < 0 || n > 360)
continue;
if (board[n] == targetColor) {
board[n] = replacementColor;
if (n % 19 > 0)
nodes.push(n - 1);
if (n % 19 < 18)
nodes.push(n + 1);
if (n / 19 > 0)
nodes.push(n - 19);
if (n / 19 < 18)
nodes.push(n + 19);
}
}
}
char center = board[180];
for (char c : board)
if (c != center) {
s.close();
b.close();
System.out.println("\nIncomplete board found!\n\tOn line " + lineNum + " of steps.txt");
System.exit(0);
}
if (lineNum % 5000 == 0)
System.out.printf("Verification %d%c complete...\n", lineNum * 100 / 100000, '%');
lineNum++;
}
s.close();
b.close();
System.out.println("All boards solved successfully.");
}
}
Además, un marcador, ya que los resultados no están ordenados por puntaje y aquí realmente importa mucho:
- 1,985,078 - smack42, Java
- 2,075,452 - usuario1502040, C
- 2,098,382 - tigrou, C #
- 2,155,834 - CoderTao, C #
- 2.201.995 - MrBackend, Java
- 2,383,569 - CoderTao, C #
- 2,384,020 - Herjan, C
- 2,403,189 - Origineil, Java
- 2,445,761 - Herjan, C
- 2,475,056 - Jeremy List, Haskell
- 2,480,714 - SteelTermite, C (2,395 bytes)
- 2,480,714 - Herjan, Java (4,702 bytes)
- 2,588,847 - BurntPizza, Java (2,748 bytes)
- 2,588,847 - Gero3, node.js (4,641 bytes)
- 2.979.145 - Teun Pronk, Delphi XE3
- 4.780.841 - BurntPizza, Java
- 10,800,000 - Joe Z., Python
Respuestas:
Java - 1,985,078 pasos
https://github.com/smack42/ColorFill
Otra entrada tardía. El archivo de resultados que contiene los 1.985.078 pasos se puede encontrar aquí .
Alguna información de fondo:
Descubrí este desafío hace algunos años, cuando comencé a programar mi propio clon del juego Flood-it.
Algoritmo DFS y A * "lo mejor de lo incompleto"
Desde el principio, quería crear un buen algoritmo de solución para este juego. Con el tiempo, podría mejorar mi solucionador al incluir varias estrategias que hicieron diferentes búsquedas incompletas (similares a las utilizadas en los otros programas aquí) y al usar el mejor resultado de esas estrategias para cada solución. Incluso volví a implementar el algoritmo A * de tigrou en Java y lo agregué a mi solucionador para lograr mejores soluciones generales que el resultado de tigrou.
algoritmo DFS exhaustivo
Luego me centré en un algoritmo que siempre encuentra las soluciones óptimas. Dediqué mucho esfuerzo a optimizar mi exhaustiva estrategia de búsqueda en profundidad. Para acelerar la búsqueda, incluí un hashmap que almacena todos los estados explorados, para que la búsqueda pueda evitar explorarlos nuevamente. Si bien este algoritmo funciona bien y resuelve todos los rompecabezas de 14x14 lo suficientemente rápido, utiliza demasiada memoria y funciona muy lentamente con los rompecabezas de 19x19 en este desafío de código.
Algoritmo Puchert A *
Hace unos meses, Aaron y Simon Puchert me contactaron para ver el solucionador Flood-It . Ese programa utiliza un algoritmo de tipo A * con una heurística admisible (en contraste con la de tigrou) y poda de movimiento similar a Jump-Point Search. Rápidamente noté que este programa es muy rápido y encuentra las soluciones óptimas. !
Por supuesto, tuve que volver a implementar este gran algoritmo y lo agregué a mi programa. Hice un esfuerzo para optimizar mi programa Java para que se ejecutara tan rápido como el programa C ++ original de los hermanos Puchert. Entonces decidí intentar los 100.000 casos de prueba de este desafío. En mi máquina, el programa se ejecutó durante más de 120 horas para encontrar los 1,985,078 pasos, usando mi implementación del algoritmo Puchert A * .
Esta será la mejor solución posible para este desafío, a menos que haya algunos errores en el programa que resulten en soluciones subóptimas. Cualquier comentario es bienvenido!
editar: se agregaron partes relevantes del código aquí:
clase AStarPuchertStrategy
parte de la clase AStarSolver
parte de la clase AStarNode
fuente
C # - 2,098,382 pasos
Intento muchas cosas, la mayoría de ellas falla y simplemente no funcionó en absoluto, hasta hace poco. Tengo algo lo suficientemente interesante como para publicar una respuesta.
Ciertamente, hay formas de mejorar esto aún más. Creo que ir bajo los pasos de 2M podría ser posible.
Se tardó aproximadamente
7 hours
en generar resultados. Aquí hay un archivo txt con todas las soluciones, en caso de que alguien quiera verificarlas: results.zipMás detalles sobre cómo funciona:
Utiliza A * Pathfinding algoritmo .
Lo que es difícil es encontrar un bien
heuristic
. Siheuristic
subestima el costo, funcionará casi como el algoritmo Dijkstra y, debido a la complejidad de una placa de 19x19 con 6 colores, funcionará para siempre. Si sobreestima el costo, convergerá rápidamente en una solución, pero no dará ninguna buena (algo así como 26 movimientos fueron 19 posibles). Encontrar el perfectoheuristic
que dé la cantidad exacta de pasos restantes para alcanzar la solución sería lo mejor (sería rápido y daría la mejor solución posible). Es (a menos que me equivoque) imposible. En realidad, primero es necesario resolver el tablero, mientras que esto es lo que realmente está tratando de hacer (problema de pollo y huevo)Intenté muchas cosas, esto es lo que funcionó para
heuristic
:node
representa un conjunto de cuadrados contiguos del mismo color. Usando esograph
, puedo calcular fácilmente la distancia mínima exacta desde el centro a cualquier otro nodo. Por ejemplo, la distancia desde el centro hasta la parte superior izquierda sería 10, porque al menos 10 colores los separan.heuristic
: juego el tablero actual hasta el final. Para cada paso, elijo el color que minimizará la suma de distancias desde la raíz a todos los demás nodos.El número de movimientos necesarios para alcanzar ese fin es el
heuristic
.Estimated cost
(utilizado por A *) =moves so far
+heuristic
No es perfecto ya que sobrestima ligeramente el costo (por lo tanto, se encuentra una solución no óptima). De todos modos, es rápido calcular y dar buenos resultados.
Pude obtener una gran mejora de la velocidad utilizando el gráfico para realizar todas las operaciones. Al principio tenía una
2-dimension
gran variedad. Lo inundo y recalculo el gráfico cuando es necesario (por ejemplo: para calcular la heurística). Ahora todo se hace utilizando el gráfico, que se calcula solo al principio. Para simular pasos, ya no es necesario el relleno de inundación, sino que combino nodos. Esto es mucho más rápidofuente
code blocks
para enfatizar el texto. Tenemos cursiva y negrita para eso.Python - 10,800,000 pasos
Como solución de referencia de último lugar, considere esta secuencia:
Recorrer todos los colores
n
significa quen
se garantizará que cada cuadrado que se encuentre sea del mismo color que el cuadrado central. Cada cuadrado está a más de 18 pasos del centro, por lo que 18 ciclos garantizarán que todos los cuadrados sean del mismo color. Lo más probable es que termine en menos de eso, pero no se requiere que el programa se detenga tan pronto como todos los cuadrados sean del mismo color; es mucho más beneficioso hacerlo. Este procedimiento constante es de 108 pasos por caso de prueba, para un total de 10,800,000.fuente
1 2 3 4 5 6 ...
lugar de su solución actual que da123456...
.Java - 2,480,714 pasos
Cometí un pequeño error antes (pongo una oración crucial antes de un bucle en lugar de en el bucle:
fuente
C - 2,075,452
Sé que llego extremadamente tarde a la fiesta, pero vi este desafío y quise intentarlo.
El algoritmo se basa en la búsqueda de árboles de Montecarlo con muestreo de Thompson y una tabla de transposición para reducir el espacio de búsqueda. Tarda unas 12 horas en mi máquina. Si desea verificar los resultados, puede encontrarlos en https://dropfile.to/pvjYDMV .
fuente
hash ^= zobrist_table[i][(int)solution[i]];
ahash ^= zobrist_table[i%len][(int)solution[i]];
para arreglar el bloqueo del programa.Java -
2,434,1082,588,847 pasosActualmente ganador (~ 46K por delante de Herjan) a partir del 26/04Bueno, no solo el Sr. Backend me ganó, sino que encontré un error que produjo una puntuación engañosamente buena. Ahora está arreglado (¡también estaba en el verificador! Ack), pero desafortunadamente no tengo tiempo en este momento para intentar recuperar la corona. Intentaré más tarde.
Esto se basa en mi otra solución, pero en lugar de pintar con el color más común para los bordes de relleno, pinta con el color que dará como resultado la exposición de los bordes que tienen muchos cuadrados adyacentes del mismo color. Llámalo LookAheadPainter. Lo jugaré más tarde si es necesario.
EDITAR: Escribí un verificador, siéntase libre de usar, espera un archivo steps.txt que contenga los pasos que genera su programa, así como el archivo de prueba de inundación: Editar-Editar: (Ver OP)
Si alguien encuentra un problema, ¡infórmelo!
fuente
C - 2,480,714 escalones
Todavía no es óptimo, pero ahora es más rápido y tiene mejores puntajes.
fuente
Java -
2,245,5292,201,995 pasosBúsqueda de árboles paralelos y en caché a profundidad 5, minimizando el número de "islas". Como la mejora de la profundidad 4 a la profundidad 5 fue tan pequeña, no creo que tenga mucho sentido mejorarla mucho más. Pero si fuera necesario mejorar, mi instinto me dice que trabaje calculando el número de islas como una diferencia entre dos estados, en lugar de volver a calcular todo.
Actualmente sale a stdout, hasta que sepa el formato de entrada del verificador.
fuente
24
lo que resultaría en un tiempo de ejecución mucho más eficiente.Mi última entrada: C - 2,384,020 pasos
Esta vez, un 'comprobar todas las posibilidades' ... Esta puntuación se obtiene con la profundidad establecida en 3. La profundidad en 5 debería dar ~ 2.1M pasos ... DEMASIADO LENTO. La profundidad 20+ ofrece la menor cantidad de pasos posible (solo verifica todas las coincidencias y las victorias más cortas) ... Tiene la menor cantidad de pasos, aunque lo odio ya que solo es un poquito mejor, pero el rendimiento apesta. Prefiero mi otra entrada C, que también está en esta publicación.
Otra IA mejorada escrita en C - 2,445,761 pasos
Basado en SteelTermite:
fuente
Java -
2,610,7974,780,841 pasos(Fill-Bug solucionado, la puntuación ahora es dramáticamente peor -_-)
Este es mi envío de algoritmo de referencia básico, simplemente hace un histograma de los cuadrados en los bordes del área pintada y pinta con el color más común. Corre los 100k en un par de minutos.
Obviamente no ganará, pero ciertamente no es el último. Probablemente haré otra presentación para cosas inteligentes. Siéntase libre de usar este algoritmo como punto de partida.
Descomente las líneas comentadas para la salida completa. El valor predeterminado es imprimir el número de pasos dados.
Golf a 860 caracteres (sin incluir las nuevas líneas para formatear), pero podría reducirse más si tuviera ganas de probar:
fuente
Haskell - 2,475,056 escalones
El algoritmo es similar al sugerido por MrBackend en los comentarios. La diferencia es: su sugerencia encuentra el camino más barato hacia el cuadrado de mayor costo, la mía reduce con avidez la excentricidad del gráfico en cada paso.
fuente
C # - 2,383,569
Es un recorrido profundo de posibles soluciones que elige aproximadamente el camino de la mejor mejora (similar / igual que la entrada C de Herjan), excepto que invirtí hábilmente el orden de generación de soluciones candidatas después de ver que Herjan publicó los mismos números. Sin embargo, lleva más de 12 horas para correr.
fuente
Java - 2,403,189
Se suponía que este era mi intento de una fuerza bruta. ¡Pero! Mi primera implementación de la "mejor" opción de profundidad única arrojó:
El código utilizado para ambos es el mismo con la fuerza bruta que almacena una "instantánea" de los otros movimientos posibles y ejecuta el algoritmo sobre todos ellos.
Si se ejecuta con el enfoque de "paso múltiple", se producirán fallas aleatorias. Configuré las primeras 100 entradas de rompecabezas en una prueba unitaria y puedo lograr un pase del 100% pero no el 100% del tiempo. Para compensar, acabo de rastrear el número actual del rompecabezas en el momento de falla y comencé un nuevo hilo retomando donde quedó el último. Cada hilo escribió sus respectivos resultados en un archivo. El grupo de archivos se condensó en un solo archivo.
Node
representa un mosaico / cuadrado del tablero y almacena una referencia a todos sus vecinos Realizar un seguimiento de tresSet<Node>
variables:Remaining
,Painted
,Targets
. Cada iteración miraTargets
agrupar todos loscandidate
nodos por valor, seleccionandotarget value
el número de nodos "afectados". Estos nodos afectados se convierten en objetivos para la próxima iteración.La fuente se distribuye en muchas clases y los fragmentos no son muy significativos fuera del contexto del conjunto. Mi fuente se puede navegar a través de GitHub . También me metí con un demostración de JSFiddle para la visualización.
Sin embargo, mi método de caballo de batalla de
Solver.java
:fuente
C # -
2,196,4622,155,834Este es efectivamente el mismo enfoque de 'buscar el mejor descendiente' que mi otro solucionador, pero con algunas optimizaciones que apenas, con paralelismo, le permiten llegar a la profundidad 5 en poco menos de 10 horas. En el curso de la prueba, también encontré un error en el original, de modo que el algoritmo ocasionalmente tomaría rutas ineficientes hacia el estado final (no contaba la profundidad de los estados con puntaje = 64; descubierto mientras jugaba con resultados de profundidad = 7).
La principal diferencia entre este y el solucionador anterior es que mantiene los estados del juego de inundación en la memoria, por lo que no tiene que regenerar 6 ^ 5 estados. Según el uso de la CPU durante la ejecución, estoy bastante seguro de que esto se ha movido del límite de la CPU al ancho de banda de la memoria. Gran diversión. Tantos pecados.
Editar: por razones, el algoritmo de profundidad 5 no siempre produce el mejor resultado. Para mejorar el rendimiento, hagamos profundidad 5 ... y 4 ... y 3 y 2 y 1, y veamos cuál es el mejor. Se afeitó otros 40k movimientos. Como la profundidad 5 es la mayor parte del tiempo, agregar 4 a 1 solo aumenta el tiempo de ejecución de ~ 10 horas a ~ 11 horas. ¡Hurra!
fuente
Delphi XE3 2,979,145 pasos
Ok, este es mi intento. Llamo a la parte cambiante un blob, cada turno hará una copia de la matriz y probaré todos los colores posibles para ver qué color dará el blob más grande.
Ejecuta todos los rompecabezas en 3 horas y 6 minutos.
Pensando en un método de retroceso de fuerza bruta también.
Quizás divertido para este fin de semana ^^
fuente
Javascript / node.js - 2,588,847
Algoritmo es un poco diferente a la mayoría aquí, ya que utiliza regiones precalculadas y estados de diferencia entre los cálculos. Aquí se ejecuta en menos de 10 minutos si le preocupa la velocidad debido a javascript.
fuente
Código C que garantiza encontrar una solución óptima por simple fuerza bruta. Funciona para cuadrículas de tamaño arbitrario y todas las entradas. Tarda mucho, mucho tiempo en ejecutarse en la mayoría de las cuadrículas.
El relleno de inundación es extremadamente ineficiente y depende de la recursividad. Es posible que deba aumentar su pila si es muy pequeña. El sistema de fuerza bruta utiliza una cuerda para contener los números y un simple complemento con transporte para recorrer todas las opciones posibles. Esto también es extremadamente ineficiente, ya que repite la mayoría de los pasos miles de millones de veces.
Desafortunadamente, no pude probarlo en todos los casos de prueba, ya que moriré de vejez antes de que termine.
Por lo que puedo decir, este es el ganador actual. La competencia requiere que:
Comprobar
Como esto siempre encuentra el menor número de pasos para completar cada tablero y ninguno de los otros lo hace, actualmente está por delante. Si alguien puede idear un programa más corto, podría ganar, así que presento la siguiente versión optimizada para el tamaño. La ejecución es un poco más lenta, pero el tiempo de ejecución no es parte de las condiciones ganadoras:
fuente