En nuestros amigos de Puzzling.SE , se publicó el siguiente rompecabezas: ¿Este rompecabezas cromático siempre tiene solución? por Edgar G. Puedes jugarlo aquí .
Explicación del rompecabezas
Dada una m x n
cuadrícula con mosaicos de tres colores diferentes, puede seleccionar dos mosaicos adyacentes , si sus colores son diferentes . Estas dos fichas se convierten al tercer color, es decir, el único color no representado por estas dos fichas. El rompecabezas se resuelve si todas las fichas tienen el mismo color . Al parecer, se puede demostrar que este rompecabezas es siempre solucionable, si ninguno m
, ni n
son divisible por 3.
Por supuesto, esto exige un algoritmo de resolución. Escribirás una función o programa que resuelva este rompecabezas. Tenga en cuenta que las funciones con 'efectos secundarios' (es decir, la salida está activada en stdout
lugar de en algún valor de retorno de tipo de datos incómodo) están explícitamente permitidas.
De entrada y salida
La entrada será una m x n
matriz que consiste de los números enteros 1
, 2
y 3
(o 0
, 1
, 2
si es conveniente). Puede tomar esta entrada en cualquier formato cuerdo. Ambos m
y n
son >1
y no son divisibles por 3. Puede suponer que el rompecabezas no está resuelto
Entonces resolverás el rompecabezas. Esto implicará una selección repetida de dos mosaicos adyacentes para ser 'convertidos' (ver arriba). Producirá las dos coordenadas de estos mosaicos para cada paso que tomó su algoritmo de resolución. Esto también puede estar en cualquier formato de salida sano. Puede elegir entre la indexación de sus coordenadas basada en 0 y en 1, y si las filas o columnas se indexan primero. Sin embargo, mencione esto en su respuesta.
Su algoritmo debe ejecutarse dentro de un tiempo razonable en el caso original de 8x8. Forzarlo por completo está explícitamente prohibido, es decir, su algoritmo debe ejecutarse O(k^[m*(n-1)+(m-1)*n])
con k
la cantidad de pasos necesarios para la solución. Sin embargo, no se requiere que la solución sea óptima. La prueba dada en la pregunta vinculada puede darle una idea de cómo hacer esto (por ejemplo, primero haga todas las columnas usando solo mosaicos adyacentes verticalmente y luego haga todas las filas)
Casos de prueba
En estos casos de prueba, las coordenadas se basan en 1 y las filas se indexan primero (como MATLAB / Octave y probablemente muchas otras).
Input:
[1 2]
Output: (result: all 3's)
[1 1],[1,2]
Input:
[ 1 2
3 1 ]
Output: (result: all 1's)
[1 1],[2 1] (turn left column into 2's)
[2 1],[2 2] (turn right column into 3's)
[1 1],[1 2] (turn top row into 1's)
[2 1],[2 2] (turn bottom row into 1's)
Input:
[1 2 3 2
3 2 1 1]
Output: (result: all 3's)
[1 1],[1 2]
[1 3],[1 4]
[1 2],[1 3]
[1 1],[1 2]
[1 2],[1 3]
[1 1],[1 2]
[1 3],[1 4]
[2 1],[2 2]
[1 1],[2 1]
[1 2],[2 2]
[1 3],[2 3]
[1 4],[2 4]
Si lo desea, puedo publicar una pastebin de casos de prueba más grandes, pero creo que esto debería ser suficiente.
fuente
Respuestas:
Rubí, 266 bytes
Más o menos solo un puerto de la solución Octave, excepto que primero resuelve las filas en lugar de las columnas. La entrada es una matriz de matrices, siendo las matrices internas las filas. Los movimientos de salida son
[row, column, row, column]
. Banco de pruebasSin disculpas con la explicación
fuente
intersect
es una palabra clave tan voluminosa)intersect
eso, no sé si puede arreglar la forma en que funciona la mía porque Rubyfind
básicamente opera en funciones, y sufunction
palabra clave es igual de voluminosa.find
... ¡gracias! Aún así, nada cerca deOctava,
334313 bytesDado que el desafío puede parecer un poco desalentador, presento mi propia solución. No probé formalmente que este método funciona (supongo que se reducirá a probar que el algoritmo nunca se quedará atrapado en un bucle), pero hasta ahora funciona perfectamente, haciendo 100x100 casos de prueba en 15 segundos. Tenga en cuenta que elegí usar una función con efectos secundarios en lugar de una que devuelva todas las coordenadas, ya que eso me ahorró algunos bytes. Las coordenadas son principales de fila, basadas en 1 y formateadas como
row1 col1 row2 col2
. Los colores de entrada son0,1,2
ya que esto funciona mejormod
, a costa de tener que usar ennumel
lugar dennz
. Versión de golf: Editar: guardó otros pocos bytes utilizando una técnica de la respuesta de Kevin Lau.Ejemplo de GIF del algoritmo de resolución:
Versión sin golf:
fuente
Lua,
594575559 BytesAdvertencia ¡ Todavía hay mucho trabajo antes de que termine este golf! Debería poder tomar eso por debajo de 500 Bytes, como mínimo. Por el momento, es la primera solución que funcionó, y todavía estoy trabajando en ello.
Proporcionaré una explicación completa una vez que haya terminado.
fuente
Óxido,
496495 bytesLamentablemente, no puedo vencer a OP, pero para una respuesta de Rust, estoy bastante satisfecho con el bytecount.
Entrada: un vector de números, así como el número de columnas. P.ej
salidas
a la línea de comando.
Primero resuelvo cada fila y luego resuelvo la columna resultante solo una vez, pero imprimo los pasos para todas las columnas. Por lo tanto, en realidad es bastante eficiente :-P.
Con formateo:
Editar: ahora devuelve el color de la solución que me ahorra un punto y coma ^^
fuente
Befunge ,
197368696754 Bytes(sí, estoy haciendo golf de código inverso, cuantos más bytes, mejor)
Estaba pensando que podría ser un desafío escribir este algoritmo en Befunge y que podría ser divertido
Me gustaría que fuera un programa comunitario, así que si alguien quiere trabajar en él, por favor, hágalo.Al final, hice todo solo hasta ahora, así que terminaré por mi cuenta (está casi listo)
Lo que está hecho todavía: un código en forma de troll
(sí, es un troll, créeme)
Básicamente, lee una matriz y calcula el movimiento a realizar para resolver las filas, dada una entrada como
(toda la matriz se pasa como una lista [fila1, fila2, fila3, ...])
la salida es
las filas y los cols comienzan en 0.
Ahora que las filas están resueltas, ¡está casi listo! ¡Hurra!
Explicación: (se actualizará más adelante)
Entonces hay 5 partes principales:
Las partes grises son inicializaciones
Aquí hay una explicación más profunda del módulo que encuentra las casillas para combinar (que está codificada aquí, por cierto)
La parte CALL es cuando el puntero de instrucción va a otro módulo, para combinar en cajas. Vuelve a este módulo a través de la entrada 'B'
Aquí hay un pseudocódigo: (currentx está relacionado con la lectura de la matriz) Para:
Tenga en cuenta que si desea probarlo, tendrá que poner algo de espacio final y nuevas líneas finales para que haya suficiente espacio para almacenar la matriz, si desea utilizar la interpretación que vinculé. 22 + el número de filas en la entrada como líneas finales, y 34 + el número de columnas como espacios finales en una línea debería estar bien.
fuente
\r\n
lugar de\n
solo?)C, 404 bytes
Mi primer código de golf, estoy bastante contento con cómo resultó. Sin embargo, tomó demasiado tiempo. No es completamente C estándar, solo lo que sea que se compilará bajo gcc sin banderas especiales (e ignorando las advertencias). Entonces hay una función anidada allí. La función
f
toma las dimensionesm
yn
como sus primeros argumentos, y como su tercer argumento toma toma un (int puntero) a una matriz de tamañom
×n
(indexado por filas primero). Los otros argumentos son argumentos ficticios, no necesita pasarlos, solo están allí para guardar bytes en la declaración de variables. Escribe cada par modificado en STDOUT en el formatorow1,col1:row1,col1;
, con el punto y coma que separa los pares. Utiliza indexación basada en 0.Utilicé un algoritmo ligeramente diferente al OP para resolver filas / columnas individuales. Va algo como esto (pseudocódigo):
El
for(;~b;b--)
bucle se ejecuta exactamente dos veces, en la segunda pasada resuelve columnas en lugar de filas. Esto se realiza intercambiandon
ym
, y cambiando los valores deo
yp
que se utilizan en la aritmética del puntero para abordar la matriz.Aquí hay una versión que no tiene golf, con una prueba principal, e imprime toda la matriz después de cada movimiento (presione enter para el paso 1 a su vez):
fuente