Combinaciones Kakuro
Debido a que no puedo hacer cálculos aritméticos mentales, a menudo lucho con el rompecabezas de Kakuro , que requiere que la víctima averigüe repetidamente qué números distintos en el rango del 1 al 9 (inclusive) suman otro número en el rango del 1 al 45 cuando sabes cómo muchos numeros hay. Por ejemplo, si desea saber cómo obtener 23 de 3 números, la única respuesta es 6 + 8 + 9. (Esta es la misma idea que Killer Sudoku si está familiarizado con eso).
A veces tendrá otra información, como que el número 1 no puede estar presente, por lo tanto, para lograr 8 en solo 2 números, solo puede usar 2 + 6 y 3 + 5 (no puede usar 4 + 4, porque son no distinto). Alternativamente, puede ser que ya haya encontrado un 3 en la solución, por lo que algo como 19 en 3 números debe ser 3 + 7 + 9.
Su tarea es escribir un programa que enumere todas las posibles soluciones a un problema dado, en un orden estricto, en un diseño estricto.
Entrada
Su solución puede recibir las entradas como una sola cadena ASCII, ya sea a través de stdin, un argumento de línea de comando, un argumento para una función, un valor que queda en la pila o cualquier locura que emplee su lenguaje esotérico favorito. La cadena tiene la forma
number_to_achieve number_of_numbers_required list_of_rejected_numbers list_of_required_numbers
Los primeros 2 argumentos son enteros típicos de base 10 no negativos no cero en los rangos 1 a 45 y 1 a 9 respectivamente (el uso de un punto decimal sería una entrada no válida), las dos listas son solo dígitos unidos sin ninguna delimitación en sin orden particular sin repetición, o '0' si son listas vacías. No puede haber dígitos compartidos entre las listas (excepto para 0). Los delimitadores son espacios individuales.
Salida
Su salida debe comenzar con una línea que contenga el número de posibles soluciones. Su programa debe imprimir soluciones delimitadas por saltos de línea, ordenadas por cada dígito cada vez más significativo, donde cada dígito se coloca en la posición en la que estaría si enumerara los números del 1 al 9. Los ejemplos a continuación, con suerte, lo aclararán.
Si se proporciona una entrada no válida, no me importa lo que haga su programa, aunque prefiero que no ponga a cero mi sector de arranque.
Ejemplos
Para este ejemplo de entrada
19 3 0 0
El resultado esperado sería
5
2 89
3 7 9
4 6 9
4 78
56 8
Tenga en cuenta los espacios en lugar de cada número "perdido", estos son obligatorios; No me preocupan los espacios que no tienen un número después de ellos (como los 9 que faltan arriba). Puede suponer que lo que sea que esté imprimiendo utilizará una fuente monoespacio. Tenga en cuenta también el orden, por el cual las soluciones con un dígito más pequeño más pequeño se enumeran primero, y luego aquellas con el siguiente dígito más pequeño, etc.
Otro ejemplo, basado en lo anterior
19 3 57 9
El resultado esperado sería
2
2 89
4 6 9
Tenga en cuenta que cada resultado contiene un 9, y ningún resultado contiene un 5 o 7.
Si no hay soluciones, por ejemplo
20 2 0 0
Entonces solo debe generar una sola línea con un 0.
0
He hecho que el análisis de la entrada sea parte de la diversión de esta pregunta. Este es el código de golf, que gane la solución más corta.
fuente
Respuestas:
GolfScript, 88 caracteres
Una implementación sencilla en GolfScript. Toma información de STDIN o stack.
El código se puede probar aquí .
Código con algunos comentarios:
fuente
JavaScript (E6) 172
180 275 296Como una función (comprobable) con 1 argumento de cadena y devolviendo la salida solicitada. Para tener un cambio de salida real, regrese con alert (), mismo conteo de bytes, pero tenga cuidado, la fuente de alerta no es monoespacio.
Prueba en la consola FireFox o FireBug
Prueba de salida:
Sin golf
fuente
Mathematica, 239 bytes
(Admito que comencé a trabajar en esto mientras todavía estaba en el sandbox).
Sin golf
Espera que la cadena de entrada se almacene en
i
.Es bastante sencillo. Primero, el análisis de entrada. Luego uso
IntegerPartitions
para descubrir cómo puedo dividir el primer número en los números permitidos. Luego filtro todas las particiones que usan duplicados o no contienen los números requeridos. Y luego, para cada solución, creo una lista de1
a9
y convierto los números actuales en su representación de cadena y los demás en espacios. Y luego concateno todo.fuente
Groovy - 494 caracteres
Respuesta grande y sin inspiración, pero utiliza Google Guava para generar el "conjunto de potencia".
Golfizado:
Ejecuciones de muestra:
Sin golf:
fuente