Genere un número utilizando una lista dada de números y operadores aritméticos.

11

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 Lel lado izquierdo y solo el número Nen 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 como 1337)
  • Solo aparecerán números naturales y cero L.
  • El orden en Lno importa.
  • Debes usar todos los números L.
  • Sólo los operadores +, -, *, /aparecerán en O.
  • Opuede tener más operadores de los que necesita, pero al menos |L|-1operadores
  • Puede usar cada operador cualquier cantidad de veces hasta el valor en O.
  • Las cuatro operaciones en Oson 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:

  1. Tiene una instancia de suma de subconjuntos (de ahí un conjunto S de enteros y un número x)
  2. L: = S + [0, ..., 0] (| S | veces un cero), N: = x, O: = {+: | S | -1, *: | S | - 1, /: 0, -: 0}
  3. Ahora resuelve esta instancia de mi problema
  4. 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
Martin Thoma
fuente
Es 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.
stand
3
¿Qué tipo de aritmética es esto para usar: fracciones exactas, enteros ( /div), solo coma flotante y esperanza de errores sin redondeo, ...?
dejó de girar en contra del reloj
44
¿Por qué las complicadas reglas de puntuación para la complejidad computacional? Hay una reducción fácil de la suma de subconjuntos, por lo que cualquier cosa mejor que O (2 ^ n) vale un millón de dólares.
Peter Taylor
1
Relacionado: stackoverflow.com/questions/3947937/…
Dr. belisarius
1
El tercer caso de prueba no es falso ...5+10+2*3+7*0+0...
Shmiddty

Respuestas:

3

Python 2.7 / 478 caracteres

L=[17,5,9,17,59,14]
O={'+':7,'-':3,'*':5,'/':1}
N=569
P=eval("{'+l+y,'-l-y,'*l*y,'/l/y}".replace('l',"':lambda x,y:x"))
def S(R,T):
 if len(T)>1:
  c,d=y=T.pop();a,b=x=T.pop()
  for o in O:
   if O[o]>0 and(o!='/'or y[0]):
    T+=[(P[o](a, c),'('+b+o+d+')')];O[o]-=1
    if S(R,T):return 1
    O[o]+=1;T.pop()
  T+=[x,y]
 elif not R:
  v,r=T[0]
  if v==N:print r
  return v==N
 for x in R[:]:
  R.remove(x);T+=[x]
  if S(R,T):return 1
  T.pop();R+=[x]
S([(x,`x`)for x in L],[])

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 de L+ Oque se traduce en N.

La siguiente versión es la versión sin golf. La pila se stkve así [(5, '5'), (2, '5-3', (10, ((4+2)+(2*(4/2))))].

L = [17, 5, 9, 17, 59, 14]
O = {'+':7, '-':3, '*':5, '/':1} 
N = 569

P = {'+':lambda x,y:x+y,
     '-':lambda x,y:x-y,
     '*':lambda x,y:x*y,
     '/':lambda x,y:x/y}

def postfix_search(rest, stk):
    if len(stk) >= 2:
        y = (v2, r2) = stk.pop()
        x = (v1, r1) = stk.pop()
        for opr in O:
            if O[opr] > 0 and not (opr == '/' and v2 == 0):
                stk += [(P[opr](v1, v2), '('+r1+opr+r2+')')]
                O[opr] -= 1
                if postfix_search(rest, stk): return 1
                O[opr] += 1
                stk.pop()
        stk += [x, y]
    elif not rest:
        v, r = stk[0]
        if v == N: print(r)
        return v == N
    for x in list(rest):
        rest.remove(x)
        stk += [x]
        if postfix_search(rest, stk):
            return True
        stk.pop()
        rest += [x]
postfix_search(list(zip(L, map(str, L))), [])
Rayo
fuente
1
Wow, eso es más corto de lo que esperaba. He garabateado un algoritmo que incluye un postfix de conversión <=> infijo, pero mi garabato no fue mucho más corto que su implementación. Impresionante Y gracias por la construcción P[opr](v1, v2). Nunca pensé en combinar lambdas y diccionarios como este, aunque ahora parece obvio.
Martin Thoma
He intentado probar su solución con mi 4º caso de prueba. Después de 2h, detuve la ejecución.
Martin Thoma
@moose Intentaré agregar algo de heurística para hacerlo más rápido. Pero después de eso, la longitud del código puede duplicarse.
Ray
Usar Fraction como lo hice aquí soluciona un problema en su respuesta. Simplemente pruébelo para la instancia dada en el enlace que he proporcionado. Su código actual no encuentra una respuesta, pero cuando usa fracción, lo hace.
Martin Thoma