Generieren Sie eine Zahl mithilfe einer bestimmten Liste von Zahlen und arithmetischen Operatoren

11

Sie erhalten eine Liste mit Nummern L = [17, 5, 9, 17, 59, 14], eine Tasche mit Operatoren O = {+:7, -:3, *:5, /:1}und eine Nummer N = 569.

Aufgabe

Geben Sie eine Gleichung aus, die alle Zahlen Lauf der linken Seite und nur die Zahl Nauf der rechten Seite verwendet. Ist dies nicht möglich, geben Sie False aus. Beispiellösung:

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

Einschränkungen und Klarstellung

  • Sie dürfen keine Zahlen verketten ( [13,37]dürfen nicht als verwendet werden 1337)
  • Es werden nur natürliche Zahlen und Null angezeigt L.
  • Die Reihenfolge Lspielt keine Rolle.
  • Sie müssen alle Zahlen in verwenden L.
  • Nur die Betreiber +, -, *, /erscheinen in O.
  • Okann mehr Operatoren haben, als Sie benötigen, aber zumindest |L|-1Operatoren
  • Sie können jeden Operator beliebig oft bis zum Wert in verwenden O.
  • Alle vier Operationen in Osind die mathematischen Standardoperationen. insbesondere /ist normale Teilung mit exakten Brüchen.

Punkte

  • Je weniger Punkte, desto besser
  • Jedes Zeichen Ihres Codes gibt Ihnen einen Punkt

Sie müssen eine Version ohne Golf anbieten, die leicht zu lesen ist.

Hintergrund

Eine ähnliche Frage wurde zum Stapelüberlauf gestellt. Ich dachte, es könnte eine interessante Code-Golf-Herausforderung sein.

Rechenkomplexität

Wie Peter Taylor in den Kommentaren sagte, können Sie die Teilmengen-Summe folgendermaßen lösen :

  1. Sie haben eine Instanz der Teilmengen-Summe (daher eine Menge S von ganzen Zahlen und eine Zahl x)
  2. L: = S + [0, ..., 0] (| S | mal eine Null), N: = x, O: = {+: | S | -1, *: | S | - 100}
  3. Lösen Sie nun diese Instanz meines Problems
  4. Die Lösung für die Teilmengen-Summe sind die Zahlen von S, die nicht mit Null multipliziert werden.

Wenn Sie einen Algorithmus finden, der besser als O (2 ^ n) ist, beweisen Sie, dass P = NP ist. Da P vs NP ein Millennium-Preis-Problem ist und daher einen Wert von 1.000.000 US-Dollar hat, ist es sehr unwahrscheinlich, dass jemand eine Lösung dafür findet. Also habe ich diesen Teil des Rankings entfernt.

Testfälle

Die folgenden sind nicht die einzig gültigen Antworten, andere Lösungen existieren und sind zulässig:

  • ( [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
quelle
Ist m = |L|? Wenn ja, wie können Sie erwarten, dass die Laufzeit nicht von der Größe dieser Liste abhängt? Zum Beispiel [2,2],[+,+,...,+,/],1. Da n O (m) ist, können Sie alles in m schreiben.
Stand vom
3
Welche Art von Arithmetik ist dies zu verwenden - exakte Brüche, ganze /Zahlen ( ≡ div), nur Gleitkomma- und Hoffnung auf keine Rundungsfehler, ...?
hörte auf, gegen den Uhrzeigersinn zu drehen
4
Warum die komplizierten Bewertungsregeln für die Komplexität der Berechnungen? Es gibt eine einfache Reduzierung der Teilmengen, also ist alles, was besser als O (2 ^ n) ist, eine Million USD wert.
Peter Taylor
1
Siehe auch
Dr. belisarius
1
3. Testfall ist nicht falsch ...5+10+2*3+7*0+0...
Shmiddty

Antworten:

3

Python 2.7 / 478 Zeichen

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

Die Hauptidee besteht darin, die Postfix-Form eines Ausdrucks für die Suche zu verwenden. Zum Beispiel 2*(3+4)in Postfix-Form 234+*. Das Problem besteht also darin, eine teilweise Permutation von L+ zu finden O, die sich zu bewertet N.

Die folgende Version ist die ungolfed Version. Der Stapel stksieht aus wie [(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))), [])
Strahl
quelle
1
Wow, das ist kürzer als ich erwartet hatte. Ich habe einen Algorithmus gekritzelt, der ein Infix für das Konvertierungspostfix <=> enthielt, aber mein Scribble war nicht viel kürzer als Ihre Implementierung. Beeindruckend. Und danke für den Bau P[opr](v1, v2). Ich hätte nie gedacht, Lambdas und Wörterbücher wie dieses zu kombinieren, obwohl es jetzt offensichtlich erscheint.
Martin Thoma
Ich habe versucht, Ihre Lösung mit meinem 4. Testfall zu testen. Nach 2 Stunden stoppte ich die Ausführung.
Martin Thoma
@moose Ich werde versuchen, eine Heuristik hinzuzufügen, um es schneller zu machen. Danach kann sich die Codelänge verdoppeln.
Ray
Die Verwendung von Fraction wie hier behebt ein Problem in Ihrer Antwort. Probieren Sie es einfach für die angegebene Instanz unter dem von mir angegebenen Link aus. Ihr aktueller Code findet keine Antwort, aber wenn Sie einen Bruch verwenden, ist dies der Fall.
Martin Thoma