... "97% will fail this test"

[herrmannj]

Auf linkedin gefunden. Hat innerhalb weniger Stunden knapp 2k an Lösungsvorschlägen eingefahren.
"Aufgabe" im Anhang, copyright "The Cyber Security Hub".

Ich teile es, weil ich's echt cool genial finde.

Die Lösung lautet .. ?

[CoolTux]

34

[Icinger]

45

[micky0867]

13

[gloob]

45

Wann gibt es die Auflösung?

[Stelaku]

45

[enno]

34

da gehe ich mit.

Ich korrigiere! Würde das so rechnen und dann komme ich auch auf 45

Code Auswählen Erweitern

1+4=5+(2+5)=12+(3+6)=21+(4+7)=32+(5+8)=45

Gruss
  Enno

[borsti67]

verflixt, bei meiner spontanen Antwort hätte ich auch zu den 97% gehört und 34 gesagt. Bei genauerem Hinschauen dann doch 45...
Nun bin ich auf die Auflösung mit Begründung gespannt...

[rabehd]

wieso fängt es mit 1+4 an?

[herrmannj]

Ich kenne auch nur die Frage. ... Und glaube(tm) die Antwort zu kennen. Mehr leider auch nicht.

Deswegen habe ich das ja hier auch geteilt.

[kumue]

34

zum eigentlich richtigem ergebnis wird noch das ergebnis aus der zeile darüber addiert
also 2+5 = 7 + die 5 darüber =12
usw...
so sehe ich das..

[Pfriemler]

Ich kann es nicht mathematisch begründen, aber wenn ich richtig liege, dann sind 999 + 1002 = 1001997.
Und ansonsten bin ich auch bei 45.

[tomster]

Ich korrigiere! Würde das so rechnen und dann komme ich auch auf 45

Code Auswählen Erweitern

1+4=5+(2+5)=12+(3+6)=21+(4+7)=32+(5+8)=45

Oder halt bissi komplizierter:
1 x 4 + 1 = 5
2 x 5 + 2 = 12
3 x 6 + 3 = 21
(4 x 7 + 4 = 32)
5 x 8 + 5 = 45
...

[JoWiemann]

Tja, da steht etwas, was nach Mathematik aussieht. Und schon wird eine mathematische Lösung gesucht. Schaut man sich die Problemstellung in Ruhe an, so handelt es sich m.E. um eine Aufgabe aus der Mustererkennung. Folglich ist die Lösung das richtige Muster, was in diesem Fall nichts mit Mathematik zu hat.

Grüße Jörg

[Pfriemler]

5 x 8 + 5 = 45
...

Yep. Ich hätte es so genannt: Wenn "x + y -> z" dann ist "x + x*y = z"
Und das funktioniert eben ohne Vorergebnisse.

Nachtrag: Muster hin oder her: klar, nach Muster der Angaben müsste man 34 sagen, weil das neue Ergebnis immer das vorige mit einschließt. Aber die Angaben in Form einer Gleichung zu machen ist so oder so falsch. Ich war auch anfangs beim 5er-System (x=1..5), dann hätte 1+4 = 5 und 2+5 = 12 tatsächlich noch gepasst, aber dann eben nicht mehr.

[kumue]

sch.. auf die vorergebniss... 8+5 =13 

oder 44 ? Zahl1 x Zahl2 + Reihe
1 Reihe    1*4 +1 =5
2. Reihe   2*5 +2 =12
3. Reihe  3*6 +3 =21
4. Reihe   5*8 +4 = 44

[Newbee]

Wenn ich jetzt gar kein Ergebnis poste, gehöre ich dann statistisch zu den 3% 

[herrmannj]

Wenn ich jetzt gar kein Ergebnis poste, gehöre ich dann statistisch zu den 3% 

Nö, das ist vmtl der einzige Weg sicher zu den 97% zu gehören ;P

[Wernieman]

Also entweder 34 oder 45 ... nicht eindeutig definiert. Also 2 Lösungen möglich.

[CQuadrat]

Ich würde es so begründen:
Das "+" ist eine (mathematische) Verknüpfung zwischen zwei (natürlichen) Zahlen a und b mit der Definition

a "+" b = a +  (a*b)


Wenn 45 die Lösung ist  .

[Wernieman]

Abgesehen von der letzten Zeile ist das Rätsel schon etwas älter:
Mal ein "schneller" Fund im Netz
https://www.welt.de/kmpkt/article166759187/Ueber-dieses-Zahlenraetsel-gruebelt-das-Internet-seit-einem-Jahr.html

[herrmannj]

Wow! Ich hab das gestern das erste mal gesehen. Faszinierend!

Meine erste Idee war auch 34, dann das 45er Muster entdeckt.

Meine Theorie: wir sind in der Psychologie.

Nur weil jemand anderes (fälschlicherweise) behauptet, dass 3+6=21 ist, ist "man" (ich) sofort bereit x Jahre Mathematik direkt über Bord zu werfen.

Frage: "was ist 5+8"? Ich tendiere (lege mich fest) zu 13. Eine authoritative Antwort gibt es aber wohl nicht, wie auch der Link zur Welt zeigt ... echt grazy. Genial.

[marvin78]

Wow! Ich hab das gestern das erste mal gesehen. Faszinierend!

Meine erste Idee war auch 34, dann das 45er Muster entdeckt.

Meine Theorie: wir sind in der Psychologie.

Nur weil jemand anderes (fälschlicherweise) behauptet, dass 3+6=21 ist, ist "man" (ich) sofort bereit x Jahre Mathematik direkt über Bord zu werfen.

Frage: "was ist 5+8"? Ich tendiere (lege mich fest) zu 13. Eine authoritative Antwort gibt es aber wohl nicht, wie auch der Link zur Welt zeigt ... echt grazy. Genial.

Witzig. Ich war auch sofort bei 13, als ich den Eingangspost gelesen habe (und nicht, weil ich den Rest nicht gelesen hätte ). Ich hatte mal ne Freundin, die Psychologin ist...

[herrmannj]

Je nach Ausgang der Beziehung : Frag mal ob es einen Fachbegriff dafür gibt.

[micky0867]

Ich kenne das mit der Aufforderung

Nenne die mathematisch korrekte Lösung

Da es zwischen den Zeilen keine Verbindung gibt (außer unserer Phantasie), muss die Lösung 13 lauten.
Die anderen Rechenfehler dienen nur der Ablenkung.

[enno]

Jetzt würde mich noch interessieren auf welcher Datenbasis die 97% berechnet wurden?

Gruss
  Enno

[Christoph Morrison]

Wer (irgendwas) rechnet, ist auf den 97%-Bait reingefallen. Die restlichen 3% sind zu schlau, zu dumm oder zu uninteressiert um mitzuspielen und daher die Gewinner.

[Prof. Dr. Peter Henning]

Da setze ich mal eins drauf.

Gegeben sind die vier Zahlen 3, 3, 8 , 8

Verwendet werden dürfen: Alls Operatoren alle Grundrechenarten sowie Klammerung.

Aufgabenstellung: Kombiniere diese vier Zahlen mit Rechenoperatoren so, dass das Ergebnis der Rechnung ein bestimmter Wert ist.

Beispiele:

3*8 + 8 - 3 = 29
(8-3) * (8-3) = 25
3*(8-3)+8 = 23
3+3+8+8 = 22
3*8-8+3 = 19

Welche Operatoren werden benötigt, damit das Ergebnis 24 ist?

(Keine faulen Tricks, keine unsaubere Lösung)

LG

pah

[justme1968]

8 / (3 - 8/3 ) = 24

und in lang:

8 / (3 - 8/3 ) = 8 / ( 9/3 - 8/3) =  8 / (1/3) = 8 * 3 = 24

[herrmannj]

@justme1968: RESPEKT!

PAHs Idee weiter gesponnen: Welche Operatoren werden benötigt, damit das Ergebnis -24 ist?

[rischbiter123]

Moin,

ganz spartanisch:
die Rechnung von justme1968 in Klammern setzen und ein Minuszeichen davor.

LG

Andreas

[Prof. Dr. Peter Henning]

Interessant. Bei einem Professorenstammtisch (so etwas gibt es wirklich, im Wesentlichen Mathematiker und Informatiker) habe ich das vor einigen Jahren vorgestellt, und fast niemand hat weniger als 30 Minuten gebraucht.

Gute Leistung !

LG

pah

[justme1968]

das war ein mehr oder weniger 'einfach'. wenn man davon ausgeht das 3*8 vorkommen muss und als nächstes probiert welcher dieser beiden faktoren sich dann durch die übrigen drei ausdrücken lässt. wenn man da etwas glück hat geht es dann ganz schnell.

dafür habe ich mit dem zettel aus dem eingangs post ein riesen problem. da in zeile 2 und 3 eindeutig falsche aussagen stehen halte ich das ganze ding einfach nur sinnlos.

[KölnSolar]

dafür habe ich mit dem zettel aus dem eingangs post ein riesen problem. da in zeile 2 und 3 eindeutig falsche aussagen stehen halte ich das ganze ding einfach nur sinnlos.

Aber das ist doch der Trick. Die ersten Zeilen lenken ab, dass nur(da mathematisch) 13 richtig ist. Alles andere ist ein vermeintliches System in den mathematisch falschen Aussagen zu erkennen.
Ich wollte mich schon zu Beginn schon outen, dass ich die falschen mathematischen Aussagen und somit die Frage gar nicht verstehe. 
Grüße Markus

[Prof. Dr. Peter Henning]

Soso.

Dann löse mal Folgendes:

1 + 4 = 5
2 + 5 = 11
3 + 6 = 13
5 + 8 = ?

Achtung: Da ist keine falsche Aussage drin, das geht wirklich. Und wenn Du es kannst, schreib nur die Lösung, un dnicht die Methode. Mal sehen, wie lange die anderen so brauchen.

LG

pah

[herrmannj]

21

[KölnSolar]

wieder 13.

Da ist keine falsche Aussage drin

Ich sehe 2.

[JoWiemann]

Sind wir bei der Mathematik und mathematischen Regeln, oder sind wir bei Mustern repräsentiert durch Zeichen?

aufgestelltes Muster -> könnte auch so dargestellt werden:
1 + 4 = 5     
2 + 5 = 11
3 + 6 = 13
5 + 8 = ?

könnte auch so dargestellt werden:

a ~ d # e
b ~ e # aa
c ~ f  # ac
e ~ h # was steht hier für ein Muster

[herrmannj]

Nachricht gelöscht (damit ich nicht aus versehen zur Spaß Bremse werde)

[lin_win]

Ich misch mich auch mal ein und antworte mutig zur Aufgabe von pah mit
21

[xenos1984]

Ich stimme mit herrmannj überein: 21. Obwohl die 8 mich skeptisch stimmt. Ich hätte 5 + 12 = 21 erwartet.

[herrmannj]

gespannt wie (und wann) PA das auflöst..

[Laffer72]

Also ich hätte jetzt ja auf 17 getippt.
Bin auch gespannt auf die Auflösung.

[herrmannj]

btw: Nachdem Justme gestern in Rekordzeit gelöst hat, habe ich mich Abends mal hingesetzt und (zur Vermeidung wichtiger aber nicht dringender anderer Aufgaben;)) ein kleines script geschrieben mit der Idee die Lösung zu brutforcen.

Ansatz, Zeichensatz "38+-*/"  und Permutation, dann eval solange bis 24 rauskommt. Das geht relativ gut, ohne Klammern jedoch keine 24. Mit Klammern und Permutation wird es  sehr langsam und ineffizient. Nach ca 1h waren zwar Lösungen zu -24 zb dabei. Die 24 noch nicht. Nicht desto trotz ist die Aufgabe ein script dazu zu erstellen umso spannender, je mehr man sich damit beschäftigt.

Hat jemand Lust auf einen kleinen Wettbewerb wer die effizienteste (schnellste) Lösung für diese Klasse von Aufgaben findet?

Rahmen: pure perl, (kein xc oder c), keine Module (Math::..).

Um zu verhindern das man zu sehr auf die (schon gelöste) Aufgabe von PAH optimiert: gegeben (Vorschlag)
- ein Satz von natürlichen Zahlen XX.
- Grundrechenarten
- Klammern
Gesucht: Ergebnis Y

Schnellstes Script gewinnt.

Einreichen innerhalb von 1-2 Wochen oder so.

Vielleicht hat PAH als Mathematiker auch 'ne bessere Idee die Aufgabenstellung zu definieren...

[Prof. Dr. Peter Henning]

Also erstmal die Auflösung: Linke Seite ist zur Basis 10 (darum sind auch 6 und 8 erlaubt). Rechte Seite ist zur Basis 6. Richtig ist also 21.

Ich hatte überlegt, die Zahlen links zu ändern - dann hätte es aber nicht mehr mit dem Zettel im ersten Post übereingestimmt.

Mathematiker

ist er nicht - Theoretischer Physiker. Die wissen mehr, als die Mathematiker ...

Zur Brute Force-Methode: Die hatte tatsächlich auch in dem oben genannten Zirkel jemand ausprobiert. Es stellte sich heraus, dass die Anzahl der Möglichkeiten mindestens exponentiell mit der Zahl der Ziffern wächst. Es ist uns aber nicht gelungen, die Komplexität des Problems wirklich zu bestimmen.

Es könnte also wirklich sein, dass ich damit die Aufgabe stelle, die Funktion Sigma(N) für Fleißige Biber der Ordnung N zu bestimmen.

LG

pah

[herrmannj]

Zur Brute Force-Methode: Die hatte tatsächlich auch in dem oben genannten Zirkel jemand ausprobiert. Es stellte sich heraus, dass die Anzahl der Möglichkeiten mindestens exponentiell mit der Zahl der Ziffern wächst. Es ist uns aber nicht gelungen, die Komplexität des Problems wirklich zu bestimmen.

Yes, wobei ich davon ausgehe, dass es intelligente Optimierungen gibt. Bei reiner Permutation kommt viel "Ausschuss" zusammen der eliminiert wird. Außerdem doppeln sich Aussagen wie "=8*3+8" mit "=(8*3)+8" etc. Sehr reizvolles Thema (optimieren). Ich denke da geht noch einiges Ein Wettbewerb würde den Reiz noch erhöhen

[herrmannj]

so, day job done für heute!

Folgende Hypothese:
Aus zwei beliebigen Ziffern [1..9] lässt sich, unter Verwendung der Grundrechenarten [+-*/], jede beliebige (positive) ganze Zahl herstellen.

Aus der PAH Aufgabe (Ziffern '3' und '8') kann man (unter anderem) eine 23 und eine 25 erzeugen. ergo auch eine 2 (25-23). Damit auch eine 27 (25+2). Und so weiter. Gesucht wird die Implementierung, die das am schnellsten schafft.  Wie siehts aus - jemand dabei ?

Nachtrag: die Aufgabe macht keinen Sinn. Könnte man einfach (3/3)+(8/8) ... usw nehmen.

[xenos1984]

Dafür reicht eine Ziffer, wenn man beliebig viele Operationen durchführen darf.

x/x + x/x + ... + x/x = n

(Wenn links n Terme stehen, ist das eben n * 1 = n.)

[herrmannj]

Dafür reicht eine Ziffer, wenn man beliebig viele Operationen durchführen darf.

x/x + x/x + ... + x/x = n

(Wenn links n Terme stehen, ist das eben n * 1 = n.)

Auch gerade gemerkt. Vielleicht hat jemand eine bessere Aufgabe

[Wernieman]

Dafür reicht eine Ziffer, wenn man beliebig viele Operationen durchführen darf.

x/x + x/x + ... + x/x = n

(Wenn links n Terme stehen, ist das eben n * 1 = n.)

Dann weißt Du jetzt die Anzahl der maximal benötigten Zahlen. Wenn jetzt das Script einen längeren Term herstellt und prüfen will, kann es den "Pfad" gleich verlassen ... also maximal 2*n Zahlen

[herrmannj]

Die Frage könnte also lauten: welches script schafft den kürzesten Term?

[justme1968]

das problem dabei wird sein das mit 'nacktem' perl ganz schnell rundungsfehler sobald einzelne komponenten nicht mehr endlich sind also z.b. bei den periodischen zahlen bzw. bei brüchen auftreten werden. und je nach länge des ausdrucks auch schon bei vermeintlich einfachen termen.

das implementieren einer lib für beliebige genauigkeit würde aber eindeutig übers ziel hinaus schießen und dann wäre auch die geschwindigkeit nicht mehr vergleichbar.

[herrmannj]

Auch wieder richtig. Wird wohl nix aus der challenge

[xenos1984]

Die Suche nach dem kürzesten Term bzw. dem kürzesten Algorithmus in einer gegebenen Sprache (in dem Fall sind die Grundrechenarten diese "Sprache") nennt sich Bestimmung der Kolmogorov-Komplexität - und die ist nicht berechenbar...

Gut, dann vielleicht etwas anders. Gegeben sind k (nicht notwendigerweise verschiedene) natürliche Zahlen sowie eine zu erreichende Zahl n. Die Aufgabe besteht darin, aus genau diesen k Zahlen die Zahl n zu erzeugen, durch Grundrechenarten und Klammern. Soll heißen, wenn unter den k Zahlen manche mehrfach vorkommen, müssen sie auch genau so oft benutzt werden, wie sie in der Aufgabenstellung vorkommen.

Ich denke, das kommt der Aufgabenstellung von pah am nächsten, wo ja 3, 3, 8, 8 gegeben waren.

Man kann die Aufgabe auch folgendermaßen formulieren. Anfangs ist die Liste der Zahlen, z.B. [3, 3, 8, 8] gegeben. Diese Liste ist nun schrittweise zu verkürzen, wobei jeder Schritt darin besteht, zwei beliebige Zahlen auszuwählen und mit einer der Grundrechenarten zu verknüpfen, und dann beide Zahlen durch das Ergebnis zu ersetzen. Beispiel, wie man damit auf 24 kommt:

• Wähle (/ 8 3): [8/3, 3, 8]
• Wähle (- 3 8/3): [1/3 8]
• Wähle (/ 8 1/3): [24]

Damit hat man die Aufgabe auf endlich viele Möglichkeiten in jedem Schritt reduziert, und man kann nun alle möglichen Schrittfolgen untersuchen. Diese Art der Aufgabe ist eine Baumsuche, und dafür gibt es verschiedene Algorithmen. Auf die Art und Weise spielen Computer auch Strategiespiele und können eben auch solche Puzzle lösen.

Übrigens braucht es keine beliebige Genauigkeit, weil nur rationale Zahlen vorkommen - mit Zähler und Nenner reichen da zwei Ganzzahlen, um die exakt zu beschreiben. Ich würde mich wundern, wenn es sowas nicht für Perl schon gäbe. Für Python würde ich SymPy nehmen. Man könnte die Aufgabenstellung auch in Ludii übersetzen und schauen, wie die dort mitgelieferten AIs sich schlagen.

[Prof. Dr. Peter Henning]

So einfach ist es nicht, und die Formulierung der Aufgabenstellung wird auch nicht besser, wenn man von "k Zahlen" spricht.

Ich habe zwar selbst die nicht berechenbare Funktion Sigma(N) ins Spiel gebracht, aber

nennt sich Bestimmung der Kolmogorov-Komplexität

stimmt in dem Fall nicht. Das Problem ist bei meiner Aufgabenstellung deutlich schwieriger, weil die mathematischen Beziehungen und die Zwangsbedingung (das Ergebnis) berücksichtigt werden müssen. Beispielsweise sind Teilausdrücke substituierbar  3/3 <-> 8/8, und die Verschiebung von Klammern ändert das Ergebnis drastisch. Es handelt sich also nicht einfach um eine Zeichenkette, sondern um eine Zeichenkette mit Zwangsbedingungen.

Vielleicht sollte ich noch hinzufügen, dass einer der elegantesten Lösungswege ist, von einer Kettenbruchentwicklung auszugehen.

Das schließt dennoch nicht aus, dass für eine gegebene Menge von Zahlen die Bestimmung des kürzesten Algorithmus möglich ist. Das wiederum hat damit zu tun, dass die Aussage

Aufgabe ist eine Baumsuche

eher trivial ist - selbstverständlich gibt es nur endlich viele Möglichkeiten. Die Nicht-Berechenbarkeit bezieht sich nur darauf, dass keine Aussage über die Länge des Algorithmus im allgemeinen Fall zu machen ist.


LG

pah

[xenos1984]

Das Problem ist bei meiner Aufgabenstellung deutlich schwieriger, weil die mathematischen Beziehungen und die Zwangsbedingung (das Ergebnis) berücksichtigt werden müssen. Beispielsweise sind Teilausdrücke substituierbar  3/3 <-> 8/8, und die Verschiebung von Klammern ändert das Ergebnis drastisch. Es handelt sich also nicht einfach um eine Zeichenkette, sondern um eine Zeichenkette mit Zwangsbedingungen.

Hm... Ich dachte, ich hatte das bei meinem Ansatz berücksichtigt. Mein Ausgangspunkt ist keine Zeichenkette, sondern ein Ausdrucksbaum. Damit sollte Klammersetzung berücksichtigt sein. Soll heißen, jede Rechenvorschrift, die eine Liste von k Zahlen auf eine einzige reduziert, indem sie Grundrechenarten und Klammern benutzt, lässt sich durch so einen Baum ausdrücken, weil jede Operation zwei Zahlen zu einer kombiniert, und die Klammern angeben, in welcher Reihenfolge das passiert. Letztlich ist das ja nur ein Umschreiben von Infix auf Präfix Notation:

8 / (3 - 8/3) = (/ 8 (- 3 (/ 8 3))) = 24

Klar, das ist natürlich nicht das gleiche wie

(8/3) - (8/3) = (- (/ 8 3) (/ 8 3)) = 0

Es stimmt natürlich, dass 3/3 = 8/8 ist. Aber als Operation auf die Liste macht es einen Unterschied, ob ich [3 3 8 8] durch [1 3 3] oder [1 8 8] ersetze. Natürlich kann ich in beiden Fälle im nächsten Schritt auf [1 1] kommen, von daher ist der Graph aller möglichen Schrittfolgen streng genommen kein Baum, wenn man äquivalente Lösungswege zusammenfasst.

[justme1968]

für das automatisierte suchen einer lösung würde ich es mit einer version probieren die ohne klammern auskommt und stack/rpn basiert ist. damit muss man sich nicht um die zusätzlichen randbedingungen wie klammern nur paarweise setzen kümmern. außerdem sind die ausdrücke kürzer und einfacher vergleichbar.

[herrmannj]

Code Auswählen Erweitern

try to solve the PAH riddle with 24 = 3,3,8,8
brooding over the problem ...
... need to probe up to 5376 candidates

found solution(s):
    > 24 = 8/(3-8/3);

5376 probes finished after 131.431 ms

[herrmannj]

Da habe ich doch direkt einen für Justme1968

Gespielt wird nach den 21er PAH Regeln (tm)

Gegeben sind die vier Zahlen 1, 9, 6 , 8

Verwendet werden dürfen: Alls Operatoren alle Grundrechenarten sowie Klammerung.

Aufgabenstellung: Kombiniere diese vier Zahlen mit Rechenoperatoren so, dass das Ergebnis der Rechnung ... 36 ist.

[Prof. Dr. Peter Henning]

Ich habe drei Minuten gebraucht...Beweis per PM

LG

pah

[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.)

[herrmannj]

Coole Lösung, auch von Wahl des Werkzeuges. Nochmals Faktor 10 schneller.

[xenos1984]

Es geht noch etwas schneller. C++, kompiliert mit

Code Auswählen Erweitern

g++ -O3 -o pah1 -std=c++2a pah1.cpp

Aufruf:

Code Auswählen Erweitern

./pah1 <Endergebnis> <Zahl1> <Zahl2> ... <ZahlN>

Timing mit den Beispielen:

Code Auswählen Erweitern


$ time ./pah1 24 3 3 8 8
(/ 8 1/3) : [ 24 ] <- [ 1/3 8 ]
(- 3 8/3) : [ 1/3 8 ] <- [ 8/3 3 8 ]
(/ 8 3) : [ 8/3 3 8 ] <- [ 3 3 8 8 ]

real    0m0,006s
user    0m0,001s
sys     0m0,006s

$ time ./pah1 36 1 9 6 8
(/ 9 1/4) : [ 36 ] <- [ 1/4 9 ]
(- 1 3/4) : [ 1/4 9 ] <- [ 3/4 1 9 ]
(/ 6 8) : [ 3/4 1 9 ] <- [ 1 6 8 9 ]

real    0m0,007s
user    0m0,003s
sys     0m0,004s

$ time ./pah1 54 1 9 6 8
(/ 6 1/9) : [ 54 ] <- [ 1/9 6 ]
(- 1 8/9) : [ 1/9 6 ] <- [ 8/9 1 6 ]
(/ 8 9) : [ 8/9 1 6 ] <- [ 1 6 8 9 ]

real    0m0,007s
user    0m0,007s
sys     0m0,000s

$ time ./pah1 -24 1 9 6 8
(* -3 8) : [ -24 ] <- [ -3 8 ]
(- 6 9) : [ -3 8 ] <- [ 6 8 9 ]
(* 1 6) : [ 6 8 9 ] <- [ 1 6 8 9 ]

real    0m0,006s
user    0m0,006s
sys     0m0,000s


[justme1968]

so ganz passt es nicht hier her, aber irgendwie doch...

https://shop.mathematikum.de/dies-das/sonstiges/247/die-mathe-uhr

[herrmannj]

Klar passt das, danke