Project Euler
Übersicht

![]() |
EingeproggtBetreff: Project Euler |
![]() Antworten mit Zitat ![]() |
---|---|---|
Habt ihr schonmal davon gehört?
Ein Kollege von mir versucht sich grad an einem der Aufgabenstellungen weil das bei seiner aktuellen Bewerbung bei ner Softwarefirma verlangt wird. Ich seh das zum ersten mal und bin grad ziemlich überwältigt ![]() So viele Problemstellungen für kluge Köpfe mit Englisch- und Mathe- und Programmierkenntnissen, hier die Liste wer Lust drauf hat: http://projecteuler.net/index.php?section=problems Von Ziffernsumme bis hin zu Mastermind mit 16 Stellen ist alles dabei, auch mathematische Akzente, zB Potenzrechnen kommen nicht zu kurz. Aber ich sags gleich: Mit BlitzBasic wird man in einigen Fällen sich die Zähne ausbeißen. Viel Spass damit. mfG, Christoph. |
||
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9 |
AvaGast |
![]() Antworten mit Zitat |
|
---|---|---|
Hehe, aber er muss nur eine Aufgabe für seine Bewerbung lösen? nicht alle 284, ja? *g*
Mich würde mal interessieren, welche Aufgabe davon es ist. ![]() |
||
![]() |
Eingeproggt |
![]() Antworten mit Zitat ![]() |
---|---|---|
Er darf sich eines aussuchen und lustig wie er ist nahm er dieses:
http://projecteuler.net/index....amp;id=185 Und ich verzweifel auch schön langsam dran ^^ Bis jetzt weiß ich nur dass man alle Zahlen mit ner 2 am Anfang vergesen kann (Siehe den einen "guess", wo ne Zahl mit 2 beginnend 0 richtige hat) Sein BruteForce Ansatz braucht 2min pro Million - es gibt *ähm* 10 Billiarden Möglichkeiten? oder? Also dauert das etwas zu lang... Aber ich hab den Thread auch nicht eröffnet weil wir unbedingt Hilfe brauchen. Ich mein wenn jemand n gten Tipp hat, gern. Aber an sich wollte ich euch nur n bisschen "Stoff" für die Osterferien geben, damit das Hirn nicht einrostet ![]() mfG, Christoph. |
||
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9 |
![]() |
ozzi789 |
![]() Antworten mit Zitat ![]() |
---|---|---|
Sehr schön , wenn ich nächstes mal nichts zu tun hab ![]() Thnx |
||
0x2B || ! 0x2B
C# | C++13 | Java 7 | PHP 5 |
![]() |
Xaymarehemals "Cgamer" |
![]() Antworten mit Zitat ![]() |
---|---|---|
Bis jetzt habe ich 3645555555554554 raus, anhand einer Tabellenartigen überprüfung die nur 1,6 Sekunden dauert. Sind mir aber noch zuviele Fünfen drin.
BlitzBasic: [AUSKLAPPEN] ;10000000000000000 Unreelle Möglichkeiten Bis jetzt prüfe ich auf meistverwendet, und nicht auf Korrektheit. |
||
Warbseite |
![]() |
Skabus |
![]() Antworten mit Zitat ![]() |
---|---|---|
@Eingeproggt:
Also ich glaub für die Aufgabe bin ich zu doof.... oO ich versteh net wo die schwierigkeit dran ist?Darf man das nur auf dem Papier lösen oder darf man keine konstruktive Programmierung nutzen? Also für mich klingt die Aufgabe net sonderlich schwer o.o Kann aber auch daran liegen dass ich sie falsch verstehe, wie gesagt XD btw.: Geile Seite, werd ich ab und an mal was lösen.Besonders den Mathekram XD Da brauch ich Übung... Und: wer hat Ferien?Also ich hab wieder Uni seit gestern xD MfG Ska EDIT: Was stellst du dir eigtl. unter BruteForce vor?Bzw. wie hast du/er die BruteForece-methode umgesetzt?Wir können eigtl. direkt von der Annahme ausgehen, dass es nur eine Zahl gibt die auf die Guess-Parameter zutreffen, somit wäre der effektivste BruteForce-Ansatz nicht einfach aufs Gradewohl Kombinationen zu suchen, die auf die Annahme überprüft werden sondern, aus der gegebenen Matrix kontruiert wird. Wäre zumindest meine erste Idee.Ich werd mal versuchen das Rätsel zu lösen XD Wenn mans verstanden hat ist des echt ne extrem harte Nuss! |
||
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat
aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu |
GERMAX |
![]() Antworten mit Zitat ![]() |
|
---|---|---|
Brute-force:
for i=0 to 9999999999999999 for k=0 to 21 datazeile k testen, ob Anzahl der correkten Zahlen stimmt- wenn ja: next k letzte zeile richtig --->alle Bedingungen erfüllt also Zahl (i) richtig. wenn nein: exit for--->next i next k next i Wenig elegant, aber findet die Lösung zu 100% |
||
Erfolglos begonnene BB-Projekte:TRON/CONVOY/MYSTIC |
![]() |
Skabus |
![]() Antworten mit Zitat ![]() |
---|---|---|
Aso....ich hab ne bessere idee glaube ich...
Ich probiers mal und schau ob ich ne richtige Lösung bekomme^^ Wäre auf jeden Fall schneller und eleganter...obgleich Groß-O immernoch quadratisch wäre, aber zumindest hängt die Anzahl nicht mehr von den Kombinationen ab, sondern von den Ziffern... Mal sehen, hab über Ostern ja Zeit^^ MfG Ska |
||
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat
aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu |
![]() |
Eingeproggt |
![]() Antworten mit Zitat ![]() |
---|---|---|
Ich bin mit dem genannten "NumberMind" Beispiel noch nicht weiter (Habs auch nicht weiter versucht), aber da es hier den einen oder anderen Kommentar gibt schreib ich mal was dazu:
@GERMAX: Ich schrieb anfangs dass man sich mit Blitz die Zähne ausbeißt - unter anderem an diesem Beispiel, weil BB kann nur Integers bis 2^32-1=4294967295. Und damit nur max, 9-stellige Dezimalzahlen. In diesem Beispiel geht es um 16stellige Zahlen, deine "9999999999999999" sind in Blitz schon gar nicht ähm... ja vorhanden... Das heißt man müsste mit Stringrechnern ran und das wird nochmal um ne Ecke langsamer. @Skabus: Ja es ist ein wenig tricky und ich hab grad seinen Code gar nicht mehr vor mir, wird ihn vermutlich eh schon umgeschmissen haben da sein erster Versuch mit lauter Stringbearbeitungs-Befehlen gearbeitet hat - und ist ja kein Geheimnis dass das langsam is. Er werkelt übrigens in C#. PS: Mein Beileid... Osterferien die nichtmal bis Ostern gehn? Also bei uns fingen die Ferien grad an und gehen je nach Schule / Uni bis zu 3 Wochen lang ![]() mfG, Christoph. |
||
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9 |
![]() |
hazumu-kun |
![]() Antworten mit Zitat ![]() |
---|---|---|
Ich habs mir auch schonmal angeguckt, und als ich die Zahlenbereiche sah wurde mir schlecht.
Sobald ich ein wenig Python kann (Superschneller Stringrechner, unendlich Stellen) schau ich mir das nochmal an. |
||
Warum kann es keine omnipotente Macht geben?
Weil diese omnipotente Macht in der Lage sein müsste, einen so schweren Stein zu schaffen, dass sie ihn nicht heben kann -> nicht omnipotent |
GERMAX |
![]() Antworten mit Zitat ![]() |
|
---|---|---|
@eingebroggt
![]() Allerdings könnte man die Sache beschleunigen, weil diese Arbeit vollständig parallelisierbar ist. Bei 4 Kernen geht es dann schon etwas flotter. Eventuell kann man sowas sogar auf der GPU laufen lassen (müsste man mal CUDA checken). Jetzt mal Gedankengänge, die man sowieso machen müsste, egal ob man es auf dem Papier lösen muß oder dann Code draus machen soll. 1. Die einfachste Zeile ist die mit den 0 correkten (jeweils in der Matrix löschen). 2. Als nächstes wären da die Daten 1+4. Die haben vorne jeweils eine 3 und nur 1 correkt---> 3 (1.Stelle) 3. Ab sofort brauchen wir deshalb nur noch ab der 2. Stelle prüfen 4. Aufgrund des Ergebnisses v. 2. können wir die falschen Zahlen aus der Matrix löschen 5. D12(69..) + D18(48..) haben 1 correkt und an der 11. Stelle eine 1 (Rest falsch und löschen) 6. D11/12 haben hinten 0 und 1 correkt--->Stelle 16=0 3 x x x x x x x x x 1 x x x x 0 und wie geht's jetzt weiter? ![]() |
||
Erfolglos begonnene BB-Projekte:TRON/CONVOY/MYSTIC |
![]() |
Skabus |
![]() Antworten mit Zitat ![]() |
---|---|---|
Man kann sich ja auch einfach einen schnellen, sinnvollen Algorithmus ausdenken, bzw. einen konstruieren der einfacher/schneller und vor allem zeitsparender ist...
Das macht nicht nur extrem viel Spaß sondern man lernt ne Menge über Algorithmen... Diese Matheaufgaben ließen sich mit einer von mir gehassten Sprache sogar sehr effizient lösen. Nenn sich Haskell...(kennt jemand Haskell? Na? Bestimmt nicht, unser Prof ist doof XD) Meine Idee ist folgende: Wir nehmen unsere Guess-Parameter und nutzen diese nicht nur zum Testen der korrekten Zahl sondern kontruieren aus den daraus resultierenden Annahmen, eine neue Zahl, die wir auf Korrektheit prüfen... Wenn wir z.B. bei: 9042 -> 2 korrekte Zahl an der richtigen Stelle haben, können wir davon ausgehen, dass IRGENDWO darin die richtigen 2 Zahlen(oder 3 oder whatever) enthalten sind.Wir können im oben genannten Fall aber sogar eine Sache ausklammern. Nämlich die Null.Weil in dem Beispiel diese Zeile hier vorhanden ist: 70794 -> mit 0 richtigen Zahlen an richtigen Stellen Damit können wir bereits aus jeder Stelle eine Zahl raushauen. Dann konstruieren wir aus allen Guess-Parametern einfach immer so Zahlenpaare das sie der Vorraussetzung entsprechen und wende unsere getroffene Annahme auf alle folgenden "Guesses" an. Also: Da 9042 genau 2 korrekte Parameter hat, brauchen wir hier nur alle Kombinationen von zweierpaaren durchlaufen. Nehmen wir(weils in diesem Fall korrekt ist) einfach die letzten beiden.Anhand dieser ANNAHME wissen wir dass in der folgenden Zahl, die letzten beiden Ziffern falsch sein müssen.Bei: 39458 Fallen dadurch die letzten 2 raus.Nehmen wir uns(weils ebenfalls korrekt ist) die ersten beiden Zahlenpaare, raus.Bleibt eine freie Stelle. Die aktuelle Zahl sieht somit so aus: 39X42 Die nächste Zahl geht dann davon aus, dass alle anderen Zahlenpaare bereits beesetzt sind, somit: 51545 Kann also nur noch die 3. Ziffer korrekt sein, da wir hier aber exakt 2 korrekte brauchen, kann hier gleich auf Korrektheit geprüft werden: 51545 Wir prüfen das mit unserer bissherigen Zahl und stellen fest, das nur eine Zahl bereits übereinstimmt, somit MUSS die letzte Zahl die 5 in der Mitte sein. Somit ist die Zahl 39542, was laut Aufgabenstellung die korrekte Lösung wäre. Leider ist das ganze net so optimal, da wir entsprechend der Länge der Ziffer immer einige weitere Guess-Parameter brauchen.Je weniger wir haben, desdo ungenauer wird das Ergebnis. Allerdings prüft der Algorithmus sich theoretisch selbst, vor allem in der Zeile mit der 51545. Da wir bereits aus der Annahme 4 Zahlen besetzt haben es in der 51545-Zeile aber 2 korrekte gibt, muss die bereits getroffene Annahme stimmen, sonst erkennt der Algborithmus bereits bei der Kontruktion einen Fehler, was die anschließende Überprüfung überflüssig macht. Vllt. ist das ja sogar bereits nen richtiger Ansatz.kA das als Algorithmus umzusetzen ist etwas kompliziert. Ich werd mich aber mal dran setzen.Die Aufgabe hats mir angetan^^ Vllt. findet ja auch wer bereits nen Denkfehler.Wäre toll wenn mir derjenige das dann sagen könnte^^ MfG Ska EDIT: Germax, deine Ideen sind gut, hab ich glatt übersehen.Das bau ich sicher auch noch auf die eine oder andere Weise ein.Hab auich bereits ein paar Optimierungsideen...dank meiner Freundin XD |
||
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat
aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu |
![]() |
ChaosCoder |
![]() Antworten mit Zitat ![]() |
---|---|---|
@germax
Ich denke deine Überlegungen sind teilweise falsch. Zitat: 2. Als nächstes wären da die Daten 1+4. Die haben vorne jeweils eine 3 und nur 1 correkt---> 3 (1.Stelle) Und was, wenn die Reihe 1 die 5. Stelle korrekt hätte und die Reihe 4 die 10. und die erste Stelle, da wo beide eine 3 haben, falsch wäre?
Deine Überlegungen klappen (leider) bei dem Beispiel mit den 5 Ziffern, dennoch ist die Annahme völlig unbegründet. Aber vielleicht lieg ich auch ganz falsch? Bei mir sind ab heute Ferien, vielleicht hat sich mein Hirn auch schon automatisch abgeschaltet^^ |
||
Projekte: Geolaria | aNemy
Webseite: chaosspace.de |
![]() |
Silver_Knee |
![]() Antworten mit Zitat ![]() |
---|---|---|
2321386104303845 ;0 correct
2326509471271448 ;2 correct 232 und die 4 könnens net sein da ja oben keins korrekt ist: Möglichkeiten die übrig bleiben: Code: [AUSKLAPPEN] ???65094712714?8
5251583379644322 ;2 correct Danach bleibt: Code: [AUSKLAPPEN] 525?5?33?9644322
Möglichkeiten nun: Code: [AUSKLAPPEN] 65094712714 8
525 5 33 9644322 Das kann man so lange machen bis man für jedes Feld die Möglichkeiten aufgelöst hat dann hat man schonmal n großteil vom bruteforce weg EDIT vllt bleibt zB die 5 stehen und man kann dann ein 1correct nutzen um mehr möglichkeiten zu killen |
||
![]() |
Firstdeathmaker |
![]() Antworten mit Zitat ![]() |
---|---|---|
Meine Lösung wäre ein reiner CSP-Ansatz:
Ein mögliches Wort besteht aus 16 Zeichen. Jedes Zeichen kann fest gesetzt und garantiert nicht vorkommende Ziffern markiert werden. Notation: /2 - 1 - /12 bedeutet, dass an der ersten Stelle noch alle außer der 2 gültig wären, an der zweiten Stelle die 1 steht und an der dritten Stelle alle Zeichen außer der 1 und der 2 stehen dürfen. Beispiel: 111 ist geheime Folge Gegeben: 122; 1 korrekt 212; 1 korrekt 221; 1 korrekt Der Algo würde jetzt die erste gegebene Zahlenfolge nehmen und davon mögliche Zahlen berechnen. Er weis, das genau 1 Ziffer richtig ist, die anderen müssten dann demnach immer falsch sein. Er generiert folgende Einträge: 1 - /2 - /2 /1 - 2 - /2 /1 - /2 - 2 Jetzt nimmt er sich die zweite gegebene Zahlenfolge, und berechnet zusammen mit den bisher gegebenen verbesserte Möglichkeiten: Aus 1 - /2 - /2 und der Zahl 212 mit 1 korrekter Ziffer ergibt sich: Erste Ziffer richtig: Nichts, da für den gegebenen Eintrag die erste Ziffer schon auf 1 gesetzt ist, sich also ein Widerspruch ergeben würde. Zweite Ziffer richtig: 1 - 1 - /2 Dritte Ziffer richtig: Nichts, da die dritte Zahl laut Eintrag ungleich 2 sein muss. Wenn jetzt die dritte Ziffer auf 2 gesetzt werden soll, ergibt das einen Widerspruch. Und so macht man das für alle drei Einträge. Man erhält die drei Einträge: 2 - 2 - /2 1 - 1 - /2 /12 - /12 - 2 Jetzt nimmt man sich die dritte gegebene Reihenfolge: 221 - 1 richtige (Die fette Zahl ist die, welche als richtig ausprobiert wird) Für 221 ergibt sich: 2 - 2 - /2 -> Nix, da durch 221 die mittlere Zahl <>2 sein müsste. 1 - 1 - /2-> Nix, da die 1 am Anfang schon feststeht, und nicht auf 2 gesetzt werden kann. /12 - /12 - 2 -> nichts, da die zu setzende 2 an erster Stelle nicht erlaubt ist. Für 221 ergibt sich: 2 - 2 - /2 -> Nix 1 - 1 - /2-> Nix /12 - /12 - 2 -> Nix Für 221 ergibt sich: 2 - 2 - /2 -> Nix 1 - 1 - /2-> 1 - 1 - 1 /12 - /12 - 2 -> Nix Die richtige Zahlenfolge ist diejenige, welche am Ende übrig bleibt. Falls mehrere Übrig bleiben, ist das Rätsel nicht richtig gestellt bzw. mehrdeutig. Falls keine übrig bleibt, gibt es auch keine Lösung. Die Laufzeit des Algorithmus ist auf jeden fall nicht sehr hoch, da in jeder Runde immer mehr Einträge rausgekickt werden. Der Hauptaufwand ist es, alle Kombinationen die richtig sein könnten durchzugehen. Das hält sich jedoch auch in Grenzen. Beispiel: 16 Ziffern zu finden. Pro Hinweis ergibt es einen Aufwand von 16 * Einträge. Am Start wären es für: 0 Richtige: 1 Eintrag 1 Richtige: 16 Einträge 2 Richtige: 120 Einträge 3 Richtige: 560 Einträge u.s.w. (Binomialkoeffizient n über k mit n=16 und k = Anzahl richtige) Wahrscheinlich sogar weniger als die genannten Einträge, weil die Reihenfolge egal ist. Für jeden weiteren müssten jeweils alle vorhandenen Einträge mit allen neuen generierten abgeglichen werden. Übrig bleiben aber nur noch die wenigsten, sodass sich das nicht sehr hoch aufmultipliziert. Beispiel: wir haben 2 Hinweise mit jeweils 2 richtigen. Das ergibt 120*120 Überprüfungen, von denen <=120 übrig bleiben. D.h. es werden mit jedem hinzukommenden Hinweis weniger Überprüfungen. |
||
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon Gewinner des BCC #57 User posted image |
Übersicht


Powered by phpBB © 2001 - 2006, phpBB Group