Se le da una lista de números L = [17, 5, 9, 17, 59, 14]
, una bolsa de operadores O = {+:7, -:3, *:5, /:1}
y un número N = 569
.
Tarea
Genere una ecuación que use todos los números en L
el lado izquierdo y solo el número N
en el lado derecho. Si esto no es posible, envíe False. Solución de ejemplo:
59*(17-5)-9*17+14 = 569
Limitaciones y aclaraciones
- No puede concatenar números (
[13,37]
no puede usarse como1337
) - Solo aparecerán números naturales y cero
L
. - El orden en
L
no importa. - Debes usar todos los números
L
. - Sólo los operadores
+
,-
,*
,/
aparecerán enO
. O
puede tener más operadores de los que necesita, pero al menos|L|-1
operadores- Puede usar cada operador cualquier cantidad de veces hasta el valor en
O
. - Las cuatro operaciones en
O
son las operaciones matemáticas estándar; en particular,/
es una división normal con fracciones exactas.
Puntos
- Cuantos menos puntos, mejor
- Cada caracter de tu código te da un punto
Debe proporcionar una versión sin golf que sea fácil de leer.
Antecedentes
Se hizo una pregunta similar en Stack Overflow. Pensé que podría ser un interesante desafío de código de golf.
Complejidad computacional
Como Peter Taylor dijo en los comentarios, puede resolver la suma de subconjuntos con esto:
- Tiene una instancia de suma de subconjuntos (de ahí un conjunto S de enteros y un número x)
- L: = S + [0, ..., 0] (| S | veces un cero), N: = x, O: = {+: | S | -1, *: | S | - 1, /: 0, -: 0}
- Ahora resuelve esta instancia de mi problema
- La solución para la suma de subconjuntos son los números de S que no se multiplican por cero.
Si encuentra un algoritmo que es mejor que O (2 ^ n), demuestra que P = NP. Como P vs NP es un problema del Premio del Milenio y, por lo tanto, vale 1,000,000 de dólares estadounidenses, es muy poco probable que alguien encuentre una solución para esto. Así que eliminé esta parte de la clasificación.
Casos de prueba
Las siguientes no son las únicas respuestas válidas, existen otras soluciones y están permitidas:
- (
[17,5,9,17,59,14]
,{+:7, -:3, *:5, /:1}
,569
)
=>59 * (17-5)- 9 * 17 + 14 = 569
- (
[2,2]
,{'+':3, '-':3, '*':3, '/':3}
,1
)
=>2/2 = 1
- (
[2,3,5,7,10,0,0,0,0,0,0,0]
,{'+':20, '-':20, '*':20, '/':20}
,16
)
=>5+10-2*3+7+0+0+0+0+0+0+0 = 16
- (
[2,3,5,7,10,0,0,0,0,0,0,0]
,{'+':20, '-':20, '*':20, '/':20}
,15
)
=>5+10+0*(2+3+7)+0+0+0+0+0+0 = 15
fuente
m = |L|
? En caso afirmativo, ¿cómo puede esperar que el tiempo de ejecución no dependa del tamaño de esa lista? Por ejemplo,[2,2],[+,+,...,+,/],1
. De hecho, dado que n es O (m), podría escribirlo todo en términos de m./
≡div
), solo coma flotante y esperanza de errores sin redondeo, ...?5+10+2*3+7*0+0...
Respuestas:
Python 2.7 / 478 caracteres
La idea principal es utilizar la forma postfix de una expresión para buscar. Por ejemplo,
2*(3+4)
en forma de postfix será234+*
. Entonces el problema se convierte en encontrar una permutación parcial deL
+O
que se traduce enN
.La siguiente versión es la versión sin golf. La pila se
stk
ve así[(5, '5'), (2, '5-3', (10, ((4+2)+(2*(4/2))))]
.fuente
P[opr](v1, v2)
. Nunca pensé en combinar lambdas y diccionarios como este, aunque ahora parece obvio.