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 L
auf der linken Seite und nur die Zahl N
auf 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 werden1337
) - Es werden nur natürliche Zahlen und Null angezeigt
L
. - Die Reihenfolge
L
spielt keine Rolle. - Sie müssen alle Zahlen in verwenden
L
. - Nur die Betreiber
+
,-
,*
,/
erscheinen inO
. O
kann mehr Operatoren haben, als Sie benötigen, aber zumindest|L|-1
Operatoren- Sie können jeden Operator beliebig oft bis zum Wert in verwenden
O
. - Alle vier Operationen in
O
sind 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 :
- Sie haben eine Instanz der Teilmengen-Summe (daher eine Menge S von ganzen Zahlen und eine Zahl x)
- L: = S + [0, ..., 0] (| S | mal eine Null), N: = x, O: = {+: | S | -1, *: | S | - 100}
- Lösen Sie nun diese Instanz meines Problems
- 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
quelle
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./
Zahlen ( ≡div
), nur Gleitkomma- und Hoffnung auf keine Rundungsfehler, ...?5+10+2*3+7*0+0...
Antworten:
Python 2.7 / 478 Zeichen
Die Hauptidee besteht darin, die Postfix-Form eines Ausdrucks für die Suche zu verwenden. Zum Beispiel
2*(3+4)
in Postfix-Form234+*
. Das Problem besteht also darin, eine teilweise Permutation vonL
+ zu findenO
, die sich zu bewertetN
.Die folgende Version ist die ungolfed Version. Der Stapel
stk
sieht aus wie[(5, '5'), (2, '5-3', (10, ((4+2)+(2*(4/2))))]
.quelle
P[opr](v1, v2)
. Ich hätte nie gedacht, Lambdas und Wörterbücher wie dieses zu kombinieren, obwohl es jetzt offensichtlich erscheint.