... "97% will fail this test"

Begonnen von herrmannj, 28 Januar 2021, 01:18:27

Vorheriges Thema - Nächstes Thema

herrmannj

#45
ZitatZur 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 :D Ein Wettbewerb würde den Reiz noch erhöhen :D :D :D

herrmannj

#46
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

Zitat von: xenos1984 am 29 Januar 2021, 17:58:54
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

Zitat von: xenos1984 am 29 Januar 2021, 17:58:54
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
- Bitte um Input für Output
- When there is a Shell, there is a Way
- Wann war Dein letztes Backup?

Wie man Fragen stellt: https://tty1.net/smart-questions_de.html

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.
hue, tradfri, alexa-fhem, homebridge-fhem, LightScene, readingsGroup, ...

https://github.com/sponsors/justme-1968

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

#54
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
Zitatnennt 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
ZitatAufgabe 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

Zitat von: Prof. Dr. Peter Henning am 30 Januar 2021, 05:19:53
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.
hue, tradfri, alexa-fhem, homebridge-fhem, LightScene, readingsGroup, ...

https://github.com/sponsors/justme-1968

herrmannj

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

8)

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