Autor Thema: ... "97% will fail this test"  (Gelesen 6965 mal)

Offline herrmannj

  • Global Moderator
  • Hero Member
  • ****
  • Beiträge: 6128
Antw:... "97% will fail this test"
« Antwort #45 am: 29 Januar 2021, 17:22:25 »
Zitat
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 :D Ein Wettbewerb würde den Reiz noch erhöhen :D :D :D
« Letzte Änderung: 29 Januar 2021, 17:23:59 von herrmannj »
smartVisu mit fronthem, einiges an HM, RFXTRX, Oregon, CUL, Homeeasy, ganz viele LED + Diverse

Offline herrmannj

  • Global Moderator
  • Hero Member
  • ****
  • Beiträge: 6128
Antw:... "97% will fail this test"
« Antwort #46 am: 29 Januar 2021, 17:43:24 »
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. :(
« Letzte Änderung: 29 Januar 2021, 18:02:39 von herrmannj »
smartVisu mit fronthem, einiges an HM, RFXTRX, Oregon, CUL, Homeeasy, ganz viele LED + Diverse

Offline xenos1984

  • Developer
  • Full Member
  • ****
  • Beiträge: 462
Antw:... "97% will fail this test"
« Antwort #47 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.)
Zustimmung Zustimmung x 1 Liste anzeigen

Offline herrmannj

  • Global Moderator
  • Hero Member
  • ****
  • Beiträge: 6128
Antw:... "97% will fail this test"
« Antwort #48 am: 29 Januar 2021, 18:04:05 »
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 :(
smartVisu mit fronthem, einiges an HM, RFXTRX, Oregon, CUL, Homeeasy, ganz viele LED + Diverse

Offline Wernieman

  • Developer
  • Hero Member
  • ****
  • Beiträge: 8125
Antw:... "97% will fail this test"
« Antwort #49 am: 29 Januar 2021, 18:08:22 »
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

Offline herrmannj

  • Global Moderator
  • Hero Member
  • ****
  • Beiträge: 6128
Antw:... "97% will fail this test"
« Antwort #50 am: 29 Januar 2021, 18:10:02 »
Die Frage könnte also lauten: welches script schafft den kürzesten Term?
smartVisu mit fronthem, einiges an HM, RFXTRX, Oregon, CUL, Homeeasy, ganz viele LED + Diverse

Offline justme1968

  • Developer
  • Hero Member
  • ****
  • Beiträge: 21267
Antw:... "97% will fail this test"
« Antwort #51 am: 29 Januar 2021, 18:17:28 »
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

Offline herrmannj

  • Global Moderator
  • Hero Member
  • ****
  • Beiträge: 6128
Antw:... "97% will fail this test"
« Antwort #52 am: 29 Januar 2021, 18:30:15 »
Auch wieder richtig. Wird wohl nix aus der challenge
smartVisu mit fronthem, einiges an HM, RFXTRX, Oregon, CUL, Homeeasy, ganz viele LED + Diverse

Offline xenos1984

  • Developer
  • Full Member
  • ****
  • Beiträge: 462
Antw:... "97% will fail this test"
« Antwort #53 am: 29 Januar 2021, 19:22:19 »
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.

Offline Prof. Dr. Peter Henning

  • Developer
  • Hero Member
  • ****
  • Beiträge: 8409
Antw:... "97% will fail this test"
« Antwort #54 am: 30 Januar 2021, 05:19:53 »
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
 
Zitat
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
Zitat
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
« Letzte Änderung: 30 Januar 2021, 10:13:25 von Prof. Dr. Peter Henning »

Offline xenos1984

  • Developer
  • Full Member
  • ****
  • Beiträge: 462
Antw:... "97% will fail this test"
« Antwort #55 am: 30 Januar 2021, 08:40:34 »
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.

Offline justme1968

  • Developer
  • Hero Member
  • ****
  • Beiträge: 21267
Antw:... "97% will fail this test"
« Antwort #56 am: 30 Januar 2021, 09:50:42 »
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

Offline herrmannj

  • Global Moderator
  • Hero Member
  • ****
  • Beiträge: 6128
Antw:... "97% will fail this test"
« Antwort #57 am: 31 Januar 2021, 03:05:49 »
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)
smartVisu mit fronthem, einiges an HM, RFXTRX, Oregon, CUL, Homeeasy, ganz viele LED + Diverse

Offline herrmannj

  • Global Moderator
  • Hero Member
  • ****
  • Beiträge: 6128
Antw:... "97% will fail this test"
« Antwort #58 am: 31 Januar 2021, 04:49:34 »
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.



smartVisu mit fronthem, einiges an HM, RFXTRX, Oregon, CUL, Homeeasy, ganz viele LED + Diverse

Offline Prof. Dr. Peter Henning

  • Developer
  • Hero Member
  • ****
  • Beiträge: 8409
Antw:... "97% will fail this test"
« Antwort #59 am: 31 Januar 2021, 07:00:57 »
Ich habe drei Minuten gebraucht...Beweis per PM

LG

pah
Gefällt mir Gefällt mir x 1 Liste anzeigen

 

decade-submarginal