Gere um número usando uma determinada lista de números e operadores aritméticos

11

Você recebe uma lista de números L = [17, 5, 9, 17, 59, 14], uma bolsa de operadores O = {+:7, -:3, *:5, /:1}e um número N = 569.

Tarefa

Emita uma equação que usa todos os números no Llado esquerdo e apenas o número Nno lado direito. Se isso não for possível, produza False. Solução de exemplo:

59*(17-5)-9*17+14 = 569

Limitações e esclarecimentos

  • Você não pode concatenar números ( [13,37]não pode ser usado como 1337)
  • Somente números naturais e zero aparecerão em L.
  • A ordem Lnão importa.
  • Você deve usar todos os números em L.
  • Apenas os operadores +, -, *, /aparecerá na O.
  • Opode ter mais operadores do que você precisa, mas pelo menos |L|-1operadores
  • Você pode usar cada operador quantas vezes quiser até o valor em O.
  • Todas as quatro operações em Osão as operações matemáticas padrão; em particular, /é a divisão normal com frações exatas.

Pontos

  • Quanto menos pontos, melhor
  • Cada caractere do seu código fornece um ponto

Você deve fornecer uma versão não-golfe que seja fácil de ler.

fundo

Uma pergunta semelhante foi feita no Stack Overflow. Eu pensei que poderia ser um desafio interessante de código-golfe.

Complexidade computacional

Como Peter Taylor disse nos comentários, você pode resolver a soma do subconjunto com isso:

  1. Você tem uma instância da soma do subconjunto (portanto, um conjunto S de números inteiros e um número x)
  2. L: = S + [0, ..., 0] (| S | vezes um zero), N: = x, O: = {+: | S | -1, *: | S | - 1, /: 0, -: 0}
  3. Agora resolva esta instância do meu problema
  4. A solução para a soma do subconjunto é o número de S que não é multiplicado por zero.

Se você encontrar um algoritmo que é melhor que O (2 ^ n), você prova que P = NP. Como P vs NP é um problema do prêmio do milênio e, portanto, vale US $ 1.000.000, é muito improvável que alguém encontre uma solução para isso. Então eu removi esta parte do ranking.

Casos de teste

As seguintes não são as únicas respostas válidas, existem outras soluções e são 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
fonte
É m = |L|? Se sim, como você pode esperar que o tempo de execução não dependa do tamanho dessa lista? Por exemplo [2,2],[+,+,...,+,/],1,. De fato, como n é O (m), você pode escrever tudo em termos de m.
Boothby
3
Que tipo de aritmética é essa para usar - fracionários exatos, número inteiro ( /div), apenas ponto flutuante e erros de esperança de não arredondamento, ...?
deixou de girar no sentido anti-horáriowis
4
Por que as regras de pontuação complicadas para complexidade computacional? Há uma redução fácil da soma do subconjunto, então qualquer coisa melhor que O (2 ^ n) vale um milhão de dólares.
22813 Peter Taylor
1
Veja também: stackoverflow.com/questions/3947937/…
Dr. belisarius
1
O terceiro caso de teste não é falso ...5+10+2*3+7*0+0...
Shmiddty 27/02

Respostas:

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],[])

A idéia principal é usar a forma postfix de uma expressão para pesquisar. Por exemplo, 2*(3+4)no formato postfix será 234+*. Portanto, o problema passa a ser encontrar uma permutação parcial de L+ Oque é avaliada como N.

A versão a seguir é a versão não destruída. A pilha stkparece [(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))), [])
Raio
fonte
1
Uau, isso é mais curto do que eu esperava. Rabisquei um algoritmo que incluía um infixo pós-fixado <=>, mas meu rabisco não era muito menor que sua implementação. Impressionante. E obrigado pela construção P[opr](v1, v2). Eu nunca pensei em combinar lambdas e dicionários como este, embora pareça óbvio agora.
Martin Thoma
Eu tentei testar sua solução com meu 4º testcase. Após 2h, parei a execução.
Martin Thoma
@moose Vou tentar adicionar um pouco de heurística para torná-lo mais rápido. Mas depois disso, o comprimento do código pode dobrar.
21413 Ray
Usar Fraction como eu fiz aqui corrige um problema na sua resposta. Basta experimentá-lo para a instância especificada no link que forneci. Seu código atual não encontra uma resposta, mas quando você usa fração, ele encontra.
Martin Thoma