... "97% will fail this test"

[justme1968]

done. etwa 5 minuten

[herrmannj]

Ich kann bestätigen, dass alle eingetroffenen Antworten korrekt sind! Gratulation!

Unter allen Einsendern wird, unter Ausschluss des Rechtsweges, eine Fahrradreise nach Helgoland mit eigener Anreise und Unterkunft verlost. Alle Teilnehmer sind Gewinner und werden in den kommenden Tagen von unserem Werbepartner, einer namhaften Versicherung, telefonisch  benachrichtigt.

Hatte mich gestern Abend doch noch mal da ran gesetzt.

Die ursprüngliche Frage von PAH kann ich jetzt in ca 100ms beantworten lassen. Je nach Input (sind Zahlen doppelt, in 3,3,8,8 jeweils die '3' und die '8') - auf alle Fälle aber unter 500ms.

Idee also, dreh ich das um schau mir den Raum 1111-9999 an.
Kriterium: die Antwort (Regeln: 21er Regeln nach PAH;)) soll nur ein einziges mal existieren.

Da gibt es in Bereich 1111-9999 einige, die 36/1,9,6,8 war darunter.

Wenn ihr wollt hätte ich noch einige. Irgendwann lässt der Reiz aber nach.

[Prof. Dr. Peter Henning]

Für eine Veröffentlichung ist das noch zu dünn. Interessant wäre eine Statistik über den Zahlenraum der Ergebniszahlen, wie viele Möglichkeiten bestehen, wie viele Operatoren wie häufig vorkommen, welche Rolle Primzahlen spielen etc.

Sicher, dass 36 ein Ausnahmefall ist ?

LG

pah

[herrmannj]

An dieser Stelle müssten Mathematiker übernehmen.

Meine Entscheidung zur Vorgehensweise ist ja brute-forcen. Das script habe ich so optimiert, dass dies effizient und schnell ist.

Die Schritte
- erstelle eine Liste der Permutationen (mit Berücksichtigung der Wiederholungen) der Eingabe Zahlen. Komplexität: n!/(a! * b! ... ). a, b etc sind die Anzahl der Wiederholungen bei den Eingabenummern. 3,3,8,8 = 4!/2!*2! = 24/2*2 = 6.
- erstelle eine Liste der Kombination der Operanten. 4^3 = 64.
- erstelle eine Liste aller möglichen Klammerkombinationen. Das ist die 'Catalan number'. Da ich nur die Vollständige Klammerung berechne ist das hier 14.

Final dann eine verschachtelte Schleife. Damit ist die Gesamtkomplexität bei 3,3,8,8 auf 6 * 64 *14 = 5376 Möglichkeiten reduziert die einzeln berechnet werden.

Ist das Ergebnis 24 dann ist der gesuchte Rechenweg gefunden, in etwa 100ms auf meinem Rechner.

Das geht auch "Rückwärts". eine Schleife von 1111-9999. Für jeden Wert die Schritte, dadurch alle durch Kombination und Klammerung möglichen Ergebnisse berechnen und notieren. Kommt ein Ergebnis genau einmal vor, ist ganzzahlig und positiv lasse ich es ausgeben.

Das ist vermutlich nicht exakt, da ich die Klammern nicht auf ein Minimalset reduziere. Es gibt (möglicherweise) Ergebnisse die eigentlich einmalig sind weil die Klammerung in der Probeliste bei gegebener Operatoren Kombination überflüssig ist. Diese Ergebnisse werden dann mehrfach gezählt und nicht ausgegeben.

Theoretisch kann man im Algorithmus weiter reduzieren da die Einmaligkeit (vermutlich) nur besteht wenn die Operanten aus der Klasse '/' '-' kommen. Bei '*' kann ich die Operanten tauschen, hätte also bereits zwei mögliche Rechenwege.

Ich hänge das script an. Die Eingaben müssen im source getätigt werden (#150f). Nimm es gern als Basis, damit kann man ja Deine Fragen untersuchen (lassen;) ) und Wertelisten erstellen.

vg
joerg

[herrmannj]

noch das script um die "seltenen Ergebnisse" im Bereich 1111-9999 zu berechnen.

[Prof. Dr. Peter Henning]

Also zumindest ist 36 kein Ausnahmefall.

2*2*3*3 = 36

a-a+4*9 = 36 für beliebiges a

a-b+5*7 = 36 für a=b+1

c-d+4*8 = 36 für c=b+4

LG

pah

[herrmannj]

Da habe ich mich offensichtlich falsch ausgedrückt.

Für die gegeben Zahlen [1,9,6,8] und Regeln existieren 21504 syntaktisch korrekte Kombinationen. Anders: aus den Zahlen lassen sich 21504 formell richtige Berechnungen konstruieren.

12 davon enden in einer Division durch 0.
Die verbleibenden 21.492 Möglichkeiten liefern 611 unterschiedliche Ergebnisse wobei unterschiedliche Berechnungen zu gleichen Ergebnis führen können.
15 dieser Ergebnisse existieren nur ein einziges mal, sprich nur exakt ein Rechenweg führt zu dem Ergebnis.
Von diesen 15 Ergebnissen sind nur 3 ganzzahlig, nur 2 positiv. Für mich sind nur diese beiden als "PAH Riddle" geeignet. (Im Gegensatz zu: was muss ich rechnen um auf 0.205128205128205 zu kommen .. ?)

Für [1,9,6,8] sind die beiden Kandidaten genau [36,54].

Die Einzigartigkeit der "36" gilt nur bei [1,9,6,8] in der Form, dass genau ein einziger Rechenweg existiert um das Ergebnis zu bekommen.

Für [1,9,6,8] ist die Liste aller "Einmaligkeiten":

Code Auswählen Erweitern

result 0.205128205128205 is rare (1)
result 0.76056338028169 is rare (1)
result 1.53191489361702 is rare (1)
result 54 is rare (1)
result 0.90566037735849 is rare (1)
result 0.153846153846154 is rare (1)
result 1.35849056603774 is rare (1)
result 0.121212121212121 is rare (1)
result 1.14893617021277 is rare (1)
result 36 is rare (1)
result 0.136363636363636 is rare (1)
result 0.195652173913043 is rare (1)
result -48 is rare (1)
result 0.130434782608696 is rare (1)
result 0.676056338028169 is rare (1)

Bonusaufgabe:
Finde die Rechnung zu 54 = [1,9,6,8] *

^{* script zum lösen oben}

[xenos1984]

Ohne den Skript zu benutzen: 54 funktioniert nach dem gleichen Schema wie 36 (und die 24 aus [3, 3, 8, 8]). Scheint so, als wären die "eindeutigen" Ganzzahlen ähnlich aufgebaut.

Hast du bei der Eindeutigkeit a + b und b + a einfach oder doppelt gezählt? Wenn du die doppelt zählst, können + und * niemals in den eindeutigen Kombinationen vorkommen, weil man ja immer die beiden Operanden vertauschen kann. In dem Fall können also nur / und - vorkommen.

[herrmannj]

korrekt. Nun ist ja im "PAH Riddle" Einmaligkeit keine Vorgabe. Allerdings ist der Rätselspaß weg, wenn man direkt A+B*C+D rechnet und das gesuchte Ergebnis hat.

Nachtrag: wie Du bin ich auch der Ansicht, dass diese "Einmaligkeiten" alle nach dem gleichen Schema aufgebaut sind ...

[xenos1984]

Nachtrag: wie Du bin ich auch der Ansicht, dass diese "Einmaligkeiten" alle nach dem gleichen Schema aufgebaut sind ...

Interessanterweise scheint aber 48 = 6 / (9/8 - 1) mehrfach vorzukommen, dagegen -48 = 6 / (1 - 9/8) nur einmal.

[herrmannj]

"Fehler" im Script:

Code Auswählen Erweitern

try to solve the PAH riddle with 48 = 1,9,6,8
brooding over the problem ...
... need to probe up to 21504 candidates

found solution(s):
    > 48 = 6/((9/8)-1);
    > 48 = 6/(9/8-1);

Redundante Klammern. Da "müsste" man sich jetzt einen Algorithmus ausdenken der redundante Klammern entfernt.

[justme1968]

wie oben schon kurz geschrieben: ich denke man spart sich viel aufwand und redundanz wenn man das ganz ohne klammern angeht. d.h. stack/upn basiert. die klammern ergeben sich damit implizit aus der reihenfolge der operatoren und passende klammer paarungen oder redundante klammern erübrigen sich.

das sich die menge der positiven und negativen Lösungen unterscheidet hängt davon ab ob man das minus als reines vorzeichen erlaubt.

[herrmannj]

Theoretisch... Ja. Bekommst du das so hin dass die Laufzeit schnell bis sehr schnell ist ?

Nachtrag:
Für die ursprüngliche Fragestellung (finde die Lösung) war es egal. Da ich jedoch keinen Wettbewerb ausschlagen kann : Ich habe eine Idee wie ich die Klammer Thematik löse. Ich probiere das heute Abend mal aus.

[justme1968]

ich habe gerade keine zeit zum probieren, ich wüßte aber nicht warum es ohne klammern langsamer sein sollte. unterm strich ist so ja sogar weniger zu machen.

[xenos1984]

Ich habe mal meine Idee mit Jupyter umgesetzt. Die benutzt nun SymPy.Rational statt Gleitkommazahlen. Die Ausgabe kann man sicher noch optimieren Derzeit werden die Rechenschritte in umgekehrter Reihenfolge ausgegeben und nur die erste gefundene Lösung.

Code Auswählen Erweitern


[8, 1/3]  :  ('/', 8, 1/3)  ->  [24]
[3, 8, 8/3]  :  ('-', 3, 8/3)  ->  [8, 1/3]
[3, 3, 8, 8]  :  ('/', 8, 3)  ->  [3, 8, 8/3]
CPU times: user 9.63 ms, sys: 83 µs, total: 9.71 ms
Wall time: 8.86 ms


Code Auswählen Erweitern


[9, 1/4]  :  ('/', 9, 1/4)  ->  [36]
[1, 9, 3/4]  :  ('-', 1, 3/4)  ->  [9, 1/4]
[1, 9, 6, 8]  :  ('/', 6, 8)  ->  [1, 9, 3/4]
CPU times: user 28.7 ms, sys: 0 ns, total: 28.7 ms
Wall time: 27.3 ms


(Die Rechenzeiten variieren zwischen Durchläufen.)