Die Menschen vom Sphere Online Judge veranstalten mal wieder einen Programmierwettbewerb: Open Contest 2007.
Der Wettbewerb geht vom 15.04. bis zum 27.04. und beinhaltet 10 Aufgaben, von denen die Hälfte auch für Anfänger geeignet sein sollen.
Sofern in der Aufgabe keine Einschränkungen gemacht werden, kann man jede Programmiersprache benutzen, die vom SPOJ-System unterstützt wird, also auch Python. Damit wird man bei Aufgaben, bei denen es auf Ausführungsgeschwindigkeit ankommt, zwar nicht immer punkten können, aber Spass macht es auf jeden Fall.
Open Contest 2007
hi hi ich hab mich einfach mal angemeldet. Es geht ja direkt um nichts
Und ich hab endlich mal nen Grund, mich ausschließlich mit Python 2.5 zu beschäftigen
Hat da schonmalk jemand von euch mitgemacht?
MfG EnTeQuAk
Und ich hab endlich mal nen Grund, mich ausschließlich mit Python 2.5 zu beschäftigen
Hat da schonmalk jemand von euch mitgemacht?
MfG EnTeQuAk
Ich beschäftige mich ab und zu mit den Aufgaben, so als Denksport. Die haben ja schon eine ganze Menge aus vorherigen Wettbewerben gesammelt.
Der Wettbewerb hat ja nun mittlerweile angefangen. Die erste Aufgabe ist Sudoku's lösen. An die Spitzenpositionen kommt man mit Python wohl nicht heran, aber ich mache das ja auch nur aus Spass. Von mir ist bis jetzt die einzige Python-Lösung:
http://www.spoj.pl/ZFUN07/ranks/SUD/lang=PYTH
Es gilt ca. 100 Punkte zu schlagen, was nicht so schwierig sein sollte, da ich einfach meine Lösung angepasst habe, die hier im Forum irgendwo zu finden ist. Und die war mehr auf Lesbarkeit als auf Geschwindigkeit ausgelegt.
Neben Python 2.5 und dessen Standardbibliothek gibt's übrigens auch `psyco` auf dem Judge-Rechner. Das hat mir bei dem Programm immerhin 3 Sekunden und knapp 2 Punkte gebracht. Aber wie gesagt, die Lösung ist nicht auf Geschwindigkeit optimiert.
http://www.spoj.pl/ZFUN07/ranks/SUD/lang=PYTH
Es gilt ca. 100 Punkte zu schlagen, was nicht so schwierig sein sollte, da ich einfach meine Lösung angepasst habe, die hier im Forum irgendwo zu finden ist. Und die war mehr auf Lesbarkeit als auf Geschwindigkeit ausgelegt.
Neben Python 2.5 und dessen Standardbibliothek gibt's übrigens auch `psyco` auf dem Judge-Rechner. Das hat mir bei dem Programm immerhin 3 Sekunden und knapp 2 Punkte gebracht. Aber wie gesagt, die Lösung ist nicht auf Geschwindigkeit optimiert.
Ich bastel noch
Hab noch ein paar Probleme mit dem Lösungsalgorythmus... der braucht zZ knapp 2 Minuten zum Lösen. Das ist weniger Vorteilhaft
Habe passend zum Thema noch folgendes gefunden: http://markbyers.com/moinmoin/moin.cgi/ ... dokuSolver
Was es alles gibt *grinz*
MfG EnTeQuAk
Hab noch ein paar Probleme mit dem Lösungsalgorythmus... der braucht zZ knapp 2 Minuten zum Lösen. Das ist weniger Vorteilhaft
Habe passend zum Thema noch folgendes gefunden: http://markbyers.com/moinmoin/moin.cgi/ ... dokuSolver
Was es alles gibt *grinz*
MfG EnTeQuAk
Zwei Minuten für *ein* Sudoku!? Das wäre bei einer Zeitbeschränkung von 30 Sekunden bei der Aufgabe natürlich sehr ungünstig.
Ansonsten sollte man nicht einfach alles lösen (wollen). Auch die in C, C++ und Pascal geschriebenen Spitzenreiter lösen nicht alle Sudokus, man kann ja beliebig viele ablehnen.
Das war auch der erste Test, für den ich 0 Punkte bekam: Einfach bei jedem Sudoku 'N'ein gesagt.
Als nächstes habe ich dann *ein* Sudoku gelöst, um zu sehen ob mein Programm immer noch funktioniert und dann habe ich mich langsam an die maximale Zahl herangetastet, die das Programm in 30 Sekunden schafft. Das sind jetzt 113 Sudokus in 25.4 Sekunden.
Die momentan beste Lösung in C schafft 386 Sudokus in 0.2 Sekunden.
Ansonsten sollte man nicht einfach alles lösen (wollen). Auch die in C, C++ und Pascal geschriebenen Spitzenreiter lösen nicht alle Sudokus, man kann ja beliebig viele ablehnen.
Das war auch der erste Test, für den ich 0 Punkte bekam: Einfach bei jedem Sudoku 'N'ein gesagt.
Als nächstes habe ich dann *ein* Sudoku gelöst, um zu sehen ob mein Programm immer noch funktioniert und dann habe ich mich langsam an die maximale Zahl herangetastet, die das Programm in 30 Sekunden schafft. Das sind jetzt 113 Sudokus in 25.4 Sekunden.
Die momentan beste Lösung in C schafft 386 Sudokus in 0.2 Sekunden.
au backe... das ist arg.... Der würde (wenn alles gut geht) gute ** 57900 ** Sudokus in den 30 Sekunden lösen können... oh oh... :'(Die momentan beste Lösung in C schafft 386 Sudokus in 0.2 Sekunden.
Ich habe mal versucht, den Alhorithmus zum Lösen von Sudokus von Wikipedia in Python umzusetzen. Schon sind aus 2 Minuten (ja, das war **kein** Scherz) knapp 4 Sekunden geworden. (für ein Sudoku!)
Das ist aber immernoch nicht genug. 50 Sudokus mag ich mindestens schaffen. *grr*
Ich merke schon. Python alleine reicht hier nicht aus. Ich muss mich mal wieder mehr mit Mathe beschäftigen *grinz*
Man... dachte nicht, das ich bei dem Contest so schnell an die ersten Grenzen kommen würde.
ach...
Schön Das heißt ich bräuchte nicht nur nen Lösealgorithmus sondern noch nen Überprüfer oh oh LoooL Sudokus sind so einfach... und doch so kompliziertAnsonsten sollte man nicht einfach alles lösen (wollen). Auch die in C, C++ und Pascal geschriebenen Spitzenreiter lösen nicht alle Sudokus, man kann ja beliebig viele ablehnen.
Mal schaun, was es noch so für Probleme gibt
MfG EnTeQuAk
Du musst einen "Filter" einbauen, ob Du ein gegebenes Sudoku überhaupt lösen willst. Die Laufzeit hängt ja auch ganz stark davon ab, wieviele Felder leer sind und diese Abhängigkeit ist nicht linear. Das heisst Du darfst die Ergebnisse für die C Lösung im Wettbewerb nicht einfach so hochrechnen.
Verstärkte Mathekenntnisse sind IMHO nicht notwendig. Habe ich jedenfalls in meiner Lösung nicht eingesetzt.
Verstärkte Mathekenntnisse sind IMHO nicht notwendig. Habe ich jedenfalls in meiner Lösung nicht eingesetzt.
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Also die Bisher eingesendeten Vorschläge sind alle in "Standardprogrammiersprachen" geschrieben: C, C++, C+, Java, Pascal. Sonst gibts nur das Programm von BlackJack, welches etwas Abwechslung reinbringt.BlackJack hat geschrieben:An die Spitzenpositionen kommt man mit Python wohl nicht heran, aber ich mache das ja auch nur aus Spass. Von mir ist bis jetzt die einzige Python-Lösung:
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Was ich interessant finde ist, dass es Leute gibt, die ein *schlechteres* Ergebnis mit C erzielen als ich mit dem lahmen Python-Programm und dabei nicht mal ansatzweise die zur Verfügung stehende Zeit ausnutzen.
- Sr4l
- User
- Beiträge: 1091
- Registriert: Donnerstag 28. Dezember 2006, 20:02
- Wohnort: Kassel
- Kontaktdaten:
Wie lange habe ich für Aufgabe eins Zeit? Weil ich habe eben erstangefangen habe jetzt keine Lust / Zeit mehr und wollte lieber noch das für Schule morgen fertig machen. Aber wieviel Zeit habe ich dafür?
Steht im ersten Beitrag: bis zum 27.04. für alle Aufgaben.
Man kann aber auch nach dem Wettbewerb noch Lösungen abgeben und bewerten lassen. Die Seite hat auch massenhaft Aufgaben von vorherigen Wettbewerben. Ist immer ganz nett um die kleinen grauen Zellen ein bisschen zu trainieren.
Man kann aber auch nach dem Wettbewerb noch Lösungen abgeben und bewerten lassen. Die Seite hat auch massenhaft Aufgaben von vorherigen Wettbewerben. Ist immer ganz nett um die kleinen grauen Zellen ein bisschen zu trainieren.
Sooo der Wettbewerb ist zuende. Meine Strategie nur die einfacheren Aufgaben in einer "langsamen" Sprache zu lösen, hat mir immerhin Platz 89 eingebracht.
Hat denn aus dem Forum noch jemand mitgemacht? Beim Sudoku gibt's nur noch eine andere Lösung in Python von einem Mike aus Australien. Nehme mal an, das war keiner von Euch!?
Hat denn aus dem Forum noch jemand mitgemacht? Beim Sudoku gibt's nur noch eine andere Lösung in Python von einem Mike aus Australien. Nehme mal an, das war keiner von Euch!?
Nein. Die Probleme wandern alle in den grossen allgemeinen Aufgabenpool und man kann da noch weiter dran rumrätseln.
@mawe: Du musst die Aufgaben nur selber lösen.
Ansonsten kann ich nur verraten was ich gelöst habe und könnte natürlich auch sagen wie.
Für das Sudoku habe ich, wie weiter oben schon ausgeführt, meine alte Lösung hier aus dem Forum verwendet. Musste geringfügig angepasst werden, damit Ein- und Ausgabeformat zum Wettbewerb passen. Und das Programm suchte alle Lösungen, während der Wettbewerb mit irgendeiner zufrieden war. Das habe ich recht "quick'n'dirty" gelöst: Wenn eine Lösung gefunden wird, wird sie an eine Ausnahme gepappt und damit aus der Rekursion zum Aufrufer transportiert. Nicht besonders schön, aber eben die kleinste Änderung am Quelltext die mir einfiel.
Später kam dann noch ein kleiner Kniff ausserhalb des "Solvers" hinzu: Die Aufgabe ist nicht *ein* Sudoku zu lösen, sondern *viele*. Dass heisst es kann Fälle geben, wo man schonmal eine passende Lösung gesehen hat. So wurden 11 zusätzliche Lösungen gefunden und ca. 2 Sekunden eingespart.
Zur Problems Collection (Volume 2):
Problem 3 kann man entweder sehen wenn man sich anstrengt, oder man kann mit einem Grafikprogramm drangehen. Ich habe Gimp benutzt.
Auf Problem 4 kann man ein kleines Programm loslassen, das die "bouncy numbers" zählt, bis das Verhältnis von 99% erreicht ist. Das komplizierteste ist also eine Funktion zu schreiben, die entscheidet ob eine Zahl "bouncy" ist oder nicht.
Problem 5 ist auch per Programm lösbar. Für die Funktion `rad(n)` lässt sich das Sieb des Eratosthenes recht einfach modifizieren.
Auf die Formel für Problem 9 kommt man durch ein wenig Nachdenken was sich denn von einer Minute zur nächsten verändert. Wenn man nicht auf die geschlossene Formel kommt, kann man die 1 Stunde und 33 Minuten Notfalls auch in Minutenschritten durchrechnen lassen.
Das Bild in Problem 10 sollte man sich in einem Grafikprogramm genauer anschauen. Dabei ist eine der Eigenschaften von GIF-Bildern wichtig.
Das verkabeln von Häusern habe ich nicht wirklich gelöst. Soll heissen ich habe zwar ein Programm eingereicht, aber das war nur um zu sehen, ob ich Ein- und Ausgabe richtig verarbeite bzw. erzeuge. Das Programm legt einfach je ein Kabel vom ersten Haus zu allen anderen. Mit ein bisschen mehr Zeit hätte ich mindesten einen Algorithmus für einen minimalen Spannbaum geschrieben.
Bei den lügenden Universitätsangestellten geht's mir wie jemandem aus dem SPOJ-Forum: Ich habe eine funktionierende Lösung, kann aber nicht erklären warum.
Die Aufgabe mit dem Quadrat habe ich auch nicht so gelöst, dass es für eine Hausaufgabe reichen würde. Die Lösung funktioniert, ich habe aber nicht bewiesen bzw. nachvollzogen warum. Der Lösungsansatz war eher experimentell. Dabei habe ich den Umgang mit ein paar Geometrieprogrammen gelernt. kig (KDE) und DrGeo (Gtk) kann ich empfehlen. Bei beiden kann man Elemente in der Zeichnung mit der Maus in der Gegend herum schubsen und "live" sehen, was für Auswirkungen das auf die anderen Elemente hat. Wenn man Punkt `P` bewegt, wird sehr schnell eine ganz simple Beziehung zum gesuchten Schnittpunkt klar.
Bei den Nachkommastellen von Wurzel(2) habe ich es mir auch erst einmal einfach gemacht. Wozu gibt's schliesslich das `decimal`-Modul. Nachdem damit eine supersimple Lösung fertig war, die 11564 Dezimalstellen innerhalb des Zeitlimits schafft, dachte ich eine selbstgeschriebene Lösung, die nur mit ganzen Zahlen operiert, müsste schneller sein. Aber das war sie leider nicht. Nach Wettbewerbsende viel mir ein, dass ich in dem Skript nach den berechneten Stellen ja noch ein paar anhängen kann, die einfach als Konstante im Programm untergebracht werden. Da wären 6000 Stellen mehr, mit nahezu Null zusätzlichem Rechenaufwand drin gewesen. Gnarf.
Ansonsten kann ich nur verraten was ich gelöst habe und könnte natürlich auch sagen wie.
Für das Sudoku habe ich, wie weiter oben schon ausgeführt, meine alte Lösung hier aus dem Forum verwendet. Musste geringfügig angepasst werden, damit Ein- und Ausgabeformat zum Wettbewerb passen. Und das Programm suchte alle Lösungen, während der Wettbewerb mit irgendeiner zufrieden war. Das habe ich recht "quick'n'dirty" gelöst: Wenn eine Lösung gefunden wird, wird sie an eine Ausnahme gepappt und damit aus der Rekursion zum Aufrufer transportiert. Nicht besonders schön, aber eben die kleinste Änderung am Quelltext die mir einfiel.
Später kam dann noch ein kleiner Kniff ausserhalb des "Solvers" hinzu: Die Aufgabe ist nicht *ein* Sudoku zu lösen, sondern *viele*. Dass heisst es kann Fälle geben, wo man schonmal eine passende Lösung gesehen hat. So wurden 11 zusätzliche Lösungen gefunden und ca. 2 Sekunden eingespart.
Zur Problems Collection (Volume 2):
Problem 3 kann man entweder sehen wenn man sich anstrengt, oder man kann mit einem Grafikprogramm drangehen. Ich habe Gimp benutzt.
Auf Problem 4 kann man ein kleines Programm loslassen, das die "bouncy numbers" zählt, bis das Verhältnis von 99% erreicht ist. Das komplizierteste ist also eine Funktion zu schreiben, die entscheidet ob eine Zahl "bouncy" ist oder nicht.
Problem 5 ist auch per Programm lösbar. Für die Funktion `rad(n)` lässt sich das Sieb des Eratosthenes recht einfach modifizieren.
Auf die Formel für Problem 9 kommt man durch ein wenig Nachdenken was sich denn von einer Minute zur nächsten verändert. Wenn man nicht auf die geschlossene Formel kommt, kann man die 1 Stunde und 33 Minuten Notfalls auch in Minutenschritten durchrechnen lassen.
Das Bild in Problem 10 sollte man sich in einem Grafikprogramm genauer anschauen. Dabei ist eine der Eigenschaften von GIF-Bildern wichtig.
Das verkabeln von Häusern habe ich nicht wirklich gelöst. Soll heissen ich habe zwar ein Programm eingereicht, aber das war nur um zu sehen, ob ich Ein- und Ausgabe richtig verarbeite bzw. erzeuge. Das Programm legt einfach je ein Kabel vom ersten Haus zu allen anderen. Mit ein bisschen mehr Zeit hätte ich mindesten einen Algorithmus für einen minimalen Spannbaum geschrieben.
Bei den lügenden Universitätsangestellten geht's mir wie jemandem aus dem SPOJ-Forum: Ich habe eine funktionierende Lösung, kann aber nicht erklären warum.
Die Aufgabe mit dem Quadrat habe ich auch nicht so gelöst, dass es für eine Hausaufgabe reichen würde. Die Lösung funktioniert, ich habe aber nicht bewiesen bzw. nachvollzogen warum. Der Lösungsansatz war eher experimentell. Dabei habe ich den Umgang mit ein paar Geometrieprogrammen gelernt. kig (KDE) und DrGeo (Gtk) kann ich empfehlen. Bei beiden kann man Elemente in der Zeichnung mit der Maus in der Gegend herum schubsen und "live" sehen, was für Auswirkungen das auf die anderen Elemente hat. Wenn man Punkt `P` bewegt, wird sehr schnell eine ganz simple Beziehung zum gesuchten Schnittpunkt klar.
Bei den Nachkommastellen von Wurzel(2) habe ich es mir auch erst einmal einfach gemacht. Wozu gibt's schliesslich das `decimal`-Modul. Nachdem damit eine supersimple Lösung fertig war, die 11564 Dezimalstellen innerhalb des Zeitlimits schafft, dachte ich eine selbstgeschriebene Lösung, die nur mit ganzen Zahlen operiert, müsste schneller sein. Aber das war sie leider nicht. Nach Wettbewerbsende viel mir ein, dass ich in dem Skript nach den berechneten Stellen ja noch ein paar anhängen kann, die einfach als Konstante im Programm untergebracht werden. Da wären 6000 Stellen mehr, mit nahezu Null zusätzlichem Rechenaufwand drin gewesen. Gnarf.
-
- Python-Forum Veteran
- Beiträge: 1209
- Registriert: Montag 29. September 2003, 17:18
- Wohnort: Purkersdorf (bei Wien [Austria])
Darum sag ich ja: Mist!BlackJack hat geschrieben:@mawe: Du musst die Aufgaben nur selber lösen.
Bitte nicht zuviel verraten, ich möchte ein bisschen selber tüfteln. Sollt ich mal eine Aufgabe schaffen (die Hoffnung stirbt zuletzt ), werd ich dich zwecks Lösungsvergleich belästigen, wenn ich darfBlackJack hat geschrieben:Ansonsten kann ich nur verraten was ich gelöst habe und könnte natürlich auch sagen wie.