Project Euler

Übersicht Sonstiges Smalltalk

Neue Antwort erstellen

Eingeproggt

Betreff: Project Euler

BeitragDi, März 30, 2010 16:09
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Smile

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
 

Ava

Gast

BeitragDi, März 30, 2010 16:24
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. Smile

Eingeproggt

BeitragDi, März 30, 2010 16:43
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Razz

mfG, Christoph.
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9

ozzi789

BeitragDi, März 30, 2010 17:50
Antworten mit Zitat
Benutzer-Profile anzeigen
Sehr schön , wenn ich nächstes mal nichts zu tun hab Very Happy
Thnx
0x2B || ! 0x2B
C# | C++13 | Java 7 | PHP 5

Xaymar

ehemals "Cgamer"

BeitragDi, März 30, 2010 18:22
Antworten mit Zitat
Benutzer-Profile anzeigen
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

Graphics 800,600,0,2
Dim Unique$(22,1)
Dim SUnique$(22,1)
Dim Numbers(16,10)
Global MglString$ = ""

Restore Unique
For N = 1 To 22
Read Unique(N,0), Unique(N,1)
Next

;Dies ist ungefähr wie Brute Force, nur das wir Nummern an plätzen ausschließen.
;Sortieren wir erstmal das Array nach "Correct"
For A = 1 To 22
Local LowestU$ = "",LowestC = 65535, E
For B = 1 To 22
If Unique(B,1) < LowestC
LowestU = Unique(B,0)
LowestC = Unique(B,1)
E = B
EndIf
Next
SUnique(A,0) = LowestU
SUnique(A,1) = LowestC
Unique(E,0) = ""
Unique(E,1) = 65536 ;Den jetzt sortierten Eintrag ignorieren
Print RSet(A,2)+". "+SUnique(A,0) + " ("+SUnique(A,1) + " Richtige)"
Next

Print "Taste zum fortfahren drücken"
WaitKey

;Durch die Uniques die "0" "Correct" haben, kann man schonmal nummern ausschließen
Global MglStart = 1
Print "Setze 'unmögliche' Zahlen fest"
For A = 1 To 22
If SUnique(A,1) = 0
For Pos = 1 To 16
Local C$ = Mid(SUnique(A,0),Pos,1)
Numbers(Pos,Int(C$)) = True ;True = False in dem fall
Next
Else
MglStart = A
Exit ;Wir brauchen hier nicht alle durchgehen
EndIf
Next

Local TMgl# = 0
For A = 1 To 16
Local mgl = 10
For B = 0 To 9
mgl = mgl - Numbers(A,B)
Next
If TMgl = 0
TMgl = mgl
Else
TMgl = TMgl * mgl
EndIf
Next
Print "Möglichkeiten verbleibend: "+TMgl

Print "Taste zum fortfahren drücken"
WaitKey

;Wird noch geändert bzw weitere Methode eingefügt
For A = 1 To 16
Print "Suche Meistgenutze Zahl an Stelle "+A
Local Num[10]
For B = MglStart To 22
C = Int(Mid(SUnique(B,0),A,1))
Num[C] = Num[C] + 1
Next
Local HighC = 0, HighN = -1
For B = 0 To 9
If Num[B] > HighC And Numbers(A,B) = False
HighC = Num[B]
HighN = B
EndIf
Next
Print "Fand: "+HighN
MglString = MglString + HighN
Next
Print "Errechnete: "+MglString
WaitKey()

.Unique
Data "5616185650518293",2
Data "3847439647293047",1
Data "5855462940810587",3
Data "9742855507068353",3
Data "3174248439465858",1
Data "4513559094146117",2
Data "7890971548908067",3
Data "4296849643607543",3
Data "8157356344118483",1
Data "2615250744386899",2
Data "8690095851526254",3
Data "6375711915077050",1
Data "6913859173121360",1
Data "6442889055042768",2
Data "2321386104303845",0
Data "2326509471271448",2
Data "5251583379644322",2
Data "1748270476758276",3
Data "4895722652190306",1
Data "3041631117224635",3
Data "1841236454324589",3
Data "2659862637316867",2


Bis jetzt prüfe ich auf meistverwendet, und nicht auf Korrektheit.
Warbseite

Skabus

BeitragDi, März 30, 2010 18:23
Antworten mit Zitat
Benutzer-Profile anzeigen
@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

BeitragDi, März 30, 2010 21:34
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragDi, März 30, 2010 22:47
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragDi, März 30, 2010 23:03
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Smile

mfG, Christoph.
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9

hazumu-kun

BeitragMi, März 31, 2010 0:14
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, März 31, 2010 1:36
Antworten mit Zitat
Benutzer-Profile anzeigen
@eingebroggt

Very Happy hihi, das brute-force extrem langsam ist, ist ja klar. Selbst wenn man diese Methode in Assembler nutzen würde, wäre das noch ganz schön langsam. Übrigens müsste man sowieso mit Strings arbeiten, denn man muß ja die einzelnen Stellen der Zahl auf Korrektheit prüfen. Die andere Alternative wäre, die 16-stelligen Zahlen in ein 2-dim Feld zu transferieren um jederzeit Zugriff auf jede Stelle jeder Zahl zu erhalten.
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? Idea
Erfolglos begonnene BB-Projekte:TRON/CONVOY/MYSTIC

Skabus

BeitragMi, März 31, 2010 8:30
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, März 31, 2010 10:44
Antworten mit Zitat
Benutzer-Profile anzeigen
@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

BeitragMi, März 31, 2010 15:54
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, März 31, 2010 23:50
Antworten mit Zitat
Benutzer-Profile anzeigen
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

Neue Antwort erstellen


Übersicht Sonstiges Smalltalk

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group