Su trabajo es escribir un programa (o dos programas separados) en cualquier idioma que:
- Puede tomar una placa Sudoku completa como entrada (en cualquier formato lógico) y comprimirla en una cadena de caracteres
- Puede tomar la cadena comprimida como entrada y descomprimirla para obtener exactamente la misma placa Sudoku completa (salida en cualquier formato lógico de 9 filas)
Nota: Use las reglas del Sudoku para su ventaja Esa es la idea detrás de este desafío.
Las reglas del sudoku en Wikipedia
Reglas
- Solo se permiten caracteres ASCII imprimibles (32 - 126) en la salida comprimida (por ejemplo, sin caracteres multibyte ).
- Puede suponer que la entrada es un tablero Sudoku 3x3 válido (reglas normales, sin variaciones).
- No impondré un límite de tiempo, pero no cree un algoritmo de fuerza bruta. O bien, los remitentes deben poder probar sus envíos antes de publicarlos (Gracias Jan Dvorak).
Si tiene alguna pregunta o inquietud, puede solicitar una aclaración o hacer sugerencias en los comentarios.
Condiciones ganadoras
Puntuación = suma del número de caracteres de los diez casos de prueba
La puntuación más baja gana.
Casos de prueba
Puede usarlos para probar qué tan bien funciona su programa.
9 7 3 5 8 1 4 2 6
5 2 6 4 7 3 1 9 8
1 8 4 2 9 6 7 5 3
2 4 7 8 6 5 3 1 9
3 9 8 1 2 4 6 7 5
6 5 1 7 3 9 8 4 2
8 1 9 3 4 2 5 6 7
7 6 5 9 1 8 2 3 4
4 3 2 6 5 7 9 8 1
7 2 4 8 6 5 1 9 3
1 6 9 2 4 3 8 7 5
3 8 5 1 9 7 2 4 6
8 9 6 7 2 4 3 5 1
2 7 3 9 5 1 6 8 4
4 5 1 3 8 6 9 2 7
5 4 2 6 3 9 7 1 8
6 1 8 5 7 2 4 3 9
9 3 7 4 1 8 5 6 2
1 5 7 6 8 2 3 4 9
4 3 2 5 1 9 6 8 7
6 9 8 3 4 7 2 5 1
8 2 5 4 7 6 1 9 3
7 1 3 9 2 8 4 6 5
9 6 4 1 3 5 7 2 8
5 4 1 2 9 3 8 7 6
2 8 9 7 6 1 5 3 4
3 7 6 8 5 4 9 1 2
8 3 5 4 1 6 9 2 7
2 9 6 8 5 7 4 3 1
4 1 7 2 9 3 6 5 8
5 6 9 1 3 4 7 8 2
1 2 3 6 7 8 5 4 9
7 4 8 5 2 9 1 6 3
6 5 2 7 8 1 3 9 4
9 8 1 3 4 5 2 7 6
3 7 4 9 6 2 8 1 5
6 2 8 4 5 1 7 9 3
5 9 4 7 3 2 6 8 1
7 1 3 6 8 9 5 4 2
2 4 7 3 1 5 8 6 9
9 6 1 8 2 7 3 5 4
3 8 5 9 6 4 2 1 7
1 5 6 2 4 3 9 7 8
4 3 9 5 7 8 1 2 6
8 7 2 1 9 6 4 3 5
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 8 9 7 2
6 4 8 9 7 2 5 3 1
9 7 2 5 3 1 6 4 8
1 4 5 7 9 2 8 3 6
3 7 6 5 8 4 1 9 2
2 9 8 3 6 1 7 5 4
7 3 1 9 2 8 6 4 5
8 5 9 6 4 7 3 2 1
4 6 2 1 3 5 9 8 7
6 2 4 8 7 3 5 1 9
5 8 7 4 1 9 2 6 3
9 1 3 2 5 6 4 7 8
5 2 7 4 1 6 9 3 8
8 6 4 3 2 9 1 5 7
1 3 9 5 7 8 6 4 2
2 9 1 8 5 4 3 7 6
3 4 8 6 9 7 5 2 1
6 7 5 1 3 2 4 8 9
7 1 2 9 4 5 8 6 3
4 8 3 2 6 1 7 9 5
9 5 6 7 8 3 2 1 4
2 4 6 7 1 3 9 8 5
1 8 5 4 9 6 7 3 2
9 3 7 8 2 5 1 4 6
6 7 8 5 4 2 3 9 1
4 9 3 1 6 8 2 5 7
5 1 2 3 7 9 4 6 8
8 2 4 9 5 7 6 1 3
7 5 9 6 3 1 8 2 4
3 6 1 2 8 4 5 7 9
8 6 1 2 9 4 5 7 3
4 7 5 3 1 8 6 9 2
3 9 2 5 6 7 8 1 4
2 3 6 4 5 9 7 8 1
1 5 4 7 8 3 2 6 9
9 8 7 6 2 1 3 4 5
5 2 9 1 7 6 4 3 8
6 4 8 9 3 2 1 5 7
7 1 3 8 4 5 9 2 6
Crédito a http://www.opensky.ca/~jdhildeb/software/sudokugen/ por algunos de estos
Si encuentra algún problema con los casos de prueba, dígame.
code-challenge
compression
sudoku
kukac67
fuente
fuente
fudge
subrutina en mi segunda respuesta que gana 12 puntos). Una prueba más justa sería requerir que (a) las soluciones de prueba funcionen, (b) puntúen en 1,000 cuadrículas de Sudoku generadas aleatoriamente y dividan la respuesta por 100. Creo que lo mejor que se puede hacer con datos aleatorios es aproximadamente 110, basado en 10 x log-base-95 (6670903752021072936960)Respuestas:
Haskell, 107 puntos
Los resultados del caso de prueba:
El código no es bonito, pero funciona. La base del algoritmo es que si bien enumerar todas las soluciones llevaría demasiado tiempo, enumerar todas las soluciones dentro de un solo bloque es bastante rápido; de hecho, es más rápido que la conversión posterior a base95. Todo se ejecuta en segundos en el intérprete en mi máquina de gama baja. Un programa compilado terminaría de inmediato.
El trabajo pesado se realiza mediante la
solution2ix
función, que, para cada bloque de 3x3, genera todas las permutaciones posibles, sujetas a restricciones desde la izquierda y desde arriba, hasta que encuentra la que está en la solución codificada, recordando solo el índice de dicha permutación. Luego combina los índices utilizando algunos pesos calculados previamente y el esquema de Horner.En la otra dirección, la
ix2solution
función primero descompone el índice en nueve valores. Luego, para cada bloque indexa la lista de posibles permutaciones con su valor respectivo, luego extrae las restricciones para los siguientes bloques.assignments
es una recursión desenrollada simple pero fea usando la lista mónada. Genera la lista de permutaciones dado un conjunto de restricciones.El poder real proviene de los estrechos límites en las longitudes de la lista de permutación:
9!
. Este valor nunca se usa, excepto para encontrar un límite superior para la longitud de salida.6*5*4*6!
es siete veces peor que el recuento real encontrado por la enumeración:12096
El producto de todos estos límites es
71025136897117189570560
~ =95^11.5544
, lo que significa que ningún código tiene más de 12 caracteres y casi la mitad de ellos debe tener 11 caracteres o menos. He decidido no distinguir entre una cadena más corta y la misma cadena con espacios a la derecha. Los espacios en cualquier otro lugar son significativos.El límite teórico de la eficiencia de codificación para códigos libres de prefijos (logaritmo de base 95 de
6670903752021072936960
) es11.035
, lo que significa que incluso un algoritmo óptimo no puede evitar producir salidas de longitud 12, aunque las producirá en solo el 3.5% de todos los casos. Permitir que la longitud sea significativa (o equivalente, agregar espacios finales) agrega algunos códigos (1% de la cantidad total), pero no lo suficiente como para eliminar la necesidad de códigos de longitud 12.fuente
Python, 130 puntos
El algoritmo funciona codificando cada posición en el tablero, una a la vez, en un gran número entero. Para cada posición, calcula los valores posibles dados todas las asignaciones codificadas hasta ahora. Entonces, si [1,3,7,9] son los valores posibles para una posición dada, se necesitan 2 bits para codificar la elección.
Lo bueno de este esquema es que si una posición solo tiene una única opción restante, no ocupa espacio para codificar.
Una vez que tenemos el entero grande, lo escribimos en la base 95.
Probablemente hay mejores ordenaciones de codificación que lexicográficas, pero no he pensado mucho en ello.
Codificador:
Descifrador:
Ejecútelo así:
fuente
Perl - La puntuación de
115113103113Salida:
Salida:Ninguna de esas líneas tiene un espacio de terminación. Tenga en cuenta que la primera línea está vacía.
Este algoritmo funciona de la siguiente manera. Para comprimir:
Comience con una cadena 'actual' vacía que represente la cuadrícula de Sudoku
Considere agregar a su vez cada uno de los dígitos 1 .. 9 a esa cadena, y determine cuál es viable.
Obtenga el siguiente dígito de la cuadrícula de respuestas (y agréguelo a la actual)
Si solo uno es viable, no hay nada que codificar
Si más de una es viable, cuente la cantidad de opciones viables, ordénelas y codifique ese dígito como índice en la matriz ordenada. Registre el dígito y el número viable como una tupla de 2 en una matriz.
Cuando todo esté listo, codifique cada una de las 2 tuplas (en orden inverso) en un número basado en variables almacenado como un bigint.
Exprese el bigint en base 95.
Para decodificar:
Comience con una cadena 'actual' vacía que represente la cuadrícula de Sudoku
Decodifica el número base95 en un bigint
Considere agregar a su vez cada uno de los dígitos 1 .. 9 a esa cadena, y determine cuál es viable.
Si solo uno es viable, no hay nada que codificar; agregue esa opción a la cuadrícula
Si más de una es viable, cuente la cantidad de opciones viables, ordénelas y codifique ese dígito como índice en la matriz ordenada.
Decodifique el bigint de base variable utilizando el número de opciones viables como base y el módulo como índice en la matriz, y genere ese dígito como valor de celda.
Para determinar la cantidad de opciones viables, se utiliza Games :: Sudoku :: Solver. Eso es principalmente por claridad, ya que hay solucionadores de Sudoku de 3 líneas en este sitio.
Hacer los 10 tomó 8 segundos en mi computadora portátil.
La
fudge
operación clasifica la matriz de manera diferente para lograr el valor mínimo para los casos de prueba. Como se documenta, esto es un dulce de azúcar. El dulce de azúcar reduce el puntaje de 115 a 103. Está hecho a mano para garantizar que el código bigint para la primera prueba sea 0. El peor puntaje para cualquier sudoku es 12, dando un puntaje de 120. Por lo tanto, no creo que esto cuente como codificación rígida; más bien se optimiza para los datos de prueba. Para verlo funcionar sin esto, cambiesort fudge
asort
ambos lugares.El código sigue:
fuente
CJam, 309 bytes
Esta es solo una solución de referencia rápida. Lo siento, hice esto en un lenguaje de golf, pero en realidad fue la forma más sencilla de hacerlo. Agregaré una explicación del código real mañana, pero describí el algoritmo a continuación.
Codificador
Descifrador
Pruébalo aquí.
La entrada del codificador (en STDIN) y la salida del decodificador (en STDOUT) tienen la forma de una matriz CJam anidada. P.ej
Las 10 salidas de prueba son:
El algoritmo es muy simple:
fuente
Python 2.7, 107 caracteres en total
TL; DR enumeración de fuerza bruta de cuadrados 3x3 con restricciones superior + izquierda
Casos de prueba:
función auxiliar para imprimir sudoku
genera todos los cuadrados posibles dados las limitaciones arriba y a la izquierda
ver comentario de código para más detalles
extrae todos los cuadrados del tablero de sudoku como tuplas
ver comentario de código para más detalles
convierte cuadrados de nuevo a tablero de sudoku
básicamente un inverso de la función anterior
cuadrados dados a la izquierda, restricciones de retorno
ver comentario de código para más detalles
cuadrados dados arriba, restricciones de retorno
ver comentario de código para más detalles
hace una cuerda
Esta es una lista codificada de dependencias para cada cuadrado
ver comentario de código para más detalles
Esta es una lista codificada del número máximo de opciones posibles para cada cuadrado
ver comentario de código para más detalles
estos combinan las funciones anteriores y convierten una placa en una lista de enteros
y de vuelta a un tablero
bien, esas son todas las funciones
para cada tabla, haga una cadena e imprímala
ahora imprime la longitud total de todas las cadenas
y un-stringify, para demostrar que no es una compresión unidireccional
salida:
fuente
Mathematica, puntuación:
1309Actualizar:
Después de que esta respuesta fue publicada, inspiró un nuevo vacío legal: "Optimización para los casos de prueba dados" . Sin embargo, dejaré esta respuesta como está, como un ejemplo de la laguna. Siéntase libre de votar a favor. No me lastimaré.
Esto codifica una celda a la vez en orden de ráster, y para cada celda descarta su valor de manera apropiada para las celdas posteriores usando las reglas básicas de Sudoku. Entonces, por ejemplo, cuando una celda está codificada y solo tiene cuatro posibilidades, se agrega una base de 4 dígitos al entero grande. También codifica los casos de prueba directamente como números enteros pequeños, aún comprimiendo y descomprimiendo correctamente todas las placas Sudoku válidas con una longitud comprimida promedio de ~ 12.5 caracteres, 1.5 más que el 11.035 óptimo, con un código relativamente simple y no se requiere un solucionador de Sudoku.
Casos de prueba codificados:
Esto no da como resultado una codificación perfecta (promedio ~ 11), ya que las reglas básicas no descartan algunas opciones para las que de hecho no hay solución. El rendimiento podría perfeccionarse (es decir, el número entero grande siempre sería menor que el número de posibles tablas de Sudoku) verificando si no hay una solución para algunas de las opciones actuales usando un solucionador de Sudoku, y eliminándolas también.
fuente
J, 254 puntos
Compresión DescompresiónLa E / S estándar es un poco torpe en J ya
jconsole
que en realidad es una REPL, por lo que me tomé la libertad de escribir la salida comprimida en el archivo.Encuentra el índice de anagrama de cada línea, trata los nueve números resultantes como un número base- (¡9!), Y finalmente convierte a base-95, agrega 32 y convierte a ASCII como en la solución de Martin Büttner. El índice de anagrama de una permutación de 1..n es simplemente el índice de la permutación en la lista ordenada léxicamente de todas esas permutaciones, por ejemplo, ¡
5 4 3 2 1
tiene un índice de anagrama 5! - 1 = 119 .Todas las operaciones tienen inversas fáciles, por lo que la descompresión es simple.
Como beneficio adicional, los ejemplos están en un formato muy amigable con J, por lo que la entrada / salida para sudokus descomprimido es exactamente como se da en los ejemplos (aunque la entrada al codificador requiere una nueva línea final).
Cuerdas comprimidas para las cajas de prueba:
fuente
Python 3, 120 puntos
Este programa enumera todos los posibles bloques de 3x3 y recuerda cuál de ellos estaba realmente presente en el Sudoku original, luego reúne todos esos números en una representación de base 95. Aunque esto está muy cerca de la codificación rígida, comprime y descomprime los ejemplos en aproximadamente 5 segundos cada uno en mi máquina.
Las funciones principales son
compress(sudoku)
ydecompress(text)
.Salidas:
fuente
Python 2.5, 116 puntos
Código:
Resultados:
Muy lento. Tomó 517 segundos para ejecutar y verificar en mi máquina.
encconfig toma una tabla de sudoku y un dígito del 1 al 9, enumera las coordenadas xy donde aparece ese dígito y genera un número en el rango (6 ** 6) que representa esas coordenadas. (la "configuración de dígitos")
decconfig es la función inversa. Se necesita un número en el rango (6 ** 6), un dígito y un tablero de sudoku (el valor predeterminado es vacío). Emite la placa de sudoku superpuesta con la configuración de dígitos. Si una de las posiciones en la configuración de dígitos ya está tomada en el tablero de sudoku ingresado, el dígito en esa posición se sobrescribe con el nuevo dígito.
compatible toma una placa de sudoku y una configuración de dígitos (definida por conf y dig), superpone la configuración de dígitos sobre la placa de sudoku y comprueba si hay conflictos. Luego devuelve Verdadero o Falso dependiendo del resultado.
codificar es la función de compresión. Toma un tablero de sudoku y genera un número que lo representa. Para ello, primero copia las posiciones de los 1 en un tablero vacío y hace una lista de todas las configuraciones del número 2 que son compatibles con la configuración 1 (que no ocupan ninguno de los lugares ya ocupados por el 1's). Luego encuentra el orden de la configuración 2 real de la placa en la lista y la almacena, luego copia esa configuración en la nueva placa, que ahora contiene solo los 1 y los 2. Luego enumera todas las configuraciones del número 3 que son compatibles con las posiciones de los 1 y 2, y así sucesivamente.
decodificar es la función inversa.
Python 2.5.
fuente
C #, 150 bytes
Salida comprimida:
Cómo funciona:
Genera todas las permutaciones posibles de 123456789 y las recuerda. Luego compara las permutaciones con las filas en el sudoku. Cuando se encuentra una permutación coincidente para una fila de donación, recuerda el índice de esa permutación. Después de cada fila, eliminará todas las permutaciones donde haya al menos un carácter en la misma posición que la fila actual. Esto asegura que cada número sea único en su columna. Luego elimina todas las permutaciones que ya no funcionan según los criterios de cuadro. Como la última fila es trivial, genera 8 números. Probé cuál sería el valor máximo de cada uno de esos números y generé una máscara de conteo de dígitos para cada posición de esos. {6, 5, 3, 5, 3, 1, 2, 1, 1}. El primero es obviamente el más largo con 362880 permutaciones. Usando la máscara digital, construyo un BigInteger con un 1 inicial para que tenga 28 dígitos. Esto da como resultado un total de 11 bytes. Entonces esos bytes se convierten a base64. Para guardar un carácter, elimino el signo = al final.
La reconstrcution funciona de manera similar.
Reconstruye el BigInteger a partir de la cadena base64 y luego lo convierte en una cadena nuevamente y lo divide nuevamente usando la máscara de conteo de dígitos mencionada. Esas cadenas se vuelven a analizar en los índices.
Luego, el algoritmo hace casi lo mismo, en lugar de encontrar la fila en las permutaciones, solo usa el índice para obtener la fila, el resto funciona igual.
Probablemente esto podría ser un poco mejor para usar realmente los 94 caracteres posibles en lugar de solo 64, pero me falta el cerebro para hacer esto.
Fuente : Copiar y pegar para que se ejecute con los 10 ejemplos. .dotNet-Fiddle me dice que esto excede el límite de memoria, por lo que debe ejecutarlo en su máquina para enviar mensajes de texto.
fuente
Perl - 290 caracteres = 290 puntos
Este programa no utiliza codificación rígida y comprime de manera confiable una cuadrícula en exactamente 29 caracteres (en teoría, sería posible encontrar algunos más pequeños).
Así es como funciona:
Primero convierta la matriz de 9 x 9 a 60 números. Esto se puede hacer como la última columna, la última fila y el cuadrado final de cada celda de 3 x 3 se pueden soltar.
Luego convierta usando bigint a un solo entero, usando 9 ^ 60 elementos.
Luego convierta el bigint a base 95.
Compresor y descompresor:
fuente
PHP, 214
Esta solución primero borra la columna derecha y la fila inferior, así como la esquina inferior derecha de cada bloque de 3x3. Luego intenta limpiar una celda. Si existe una solución simple, la celda permanece en blanco.
Luego, la cuadrícula de sudoku se formatea en una cadena, de izquierda a derecha y de arriba a abajo, excluyendo la columna derecha, la fila inferior y la esquina inferior derecha. Los ceros a la izquierda se cuentan (que sea así
z
) y se eliminan. Los ceros finales también se eliminan.La cadena está formateada en un entero base 10, 11 o 12 (deje que esta base sea
b
),A
representando dos ceros yB
tres.Esto se convierte en un entero de base 95, y antepuesto por el dígito de base 95 que representa
z << 2 | (b - 10)
.Llame
php sudoku-compress.php enc
para codificar yphp sudoku-compress.php dec
decodificar. El codificador toma el formato dado en la pregunta, con una nueva línea final obligatoria.Salidas de prueba:
fuente
Java, 330 puntos
Antes de que me ridiculicen por un puntaje tan alto, déjenme aclarar que intenté intentar resolver esto de una manera diferente sabiendo que probablemente no sería tan óptimo como algunas de las mejores respuestas aquí. Tenía más o menos curiosidad si podía acercarme, lo que para mi sorpresa, no me di cuenta de cuánto peor resultaría. Aquí está el descuido de mi enfoque aquí:
Desarrolla un algoritmo para resolver un rompecabezas de Sudoku.
Desarrolle un algo de codificación que aún pueda resolverse. Lo hace de manera algo aleatoria mientras elimina las pistas que pueden determinarse trivialmente de antemano. Podía obtener aproximadamente 22 pistas de manera confiable antes de que tomara demasiado tiempo.
Una vez revuelto, el rompecabezas podría representarse mediante un triplete de enteros de un solo dígito para cada pista, en mi caso 22 tripletas de 3. Pensé que si podía combinarlos en un solo número de 66 dígitos, entonces base95 codificaría esto, entonces tengo algo que puede ser fácilmente decodificado
La cadena codificada terminó siendo más larga de lo que esperaba, en general, alrededor de 33 caracteres. En ese momento probé una forma alternativa que usar Java BigInteger, donde creé un gran número a partir de una máscara de 81 bits que representa las 81 celdas de una cuadrícula donde 1 significa que existe una pista para esta celda. Luego combiné esa máscara de bits con representaciones de 4 bits de cada valor de celda en orden secuencial, redondeé a bytes y descubrí que obtuve aproximadamente la misma longitud de cadena codificada después de codificar base95.
Básicamente, estoy publicando mi código en caso de que alguien esté interesado en un enfoque diferente que no funcionó tan bien.
Puzz de clase
Mi caso de prueba
Prueba de salida
fuente
C ++ 241, puntaje: 82 * 10 = 820
Agrega '!' al comienzo de la cadena codificada para determinar qué operación realizar.
Golfizado 241 caracteres
Ungolfed 312 caracteres
fuente