Open Contest 2007

Alles, was nicht direkt mit Python-Problemen zu tun hat. Dies ist auch der perfekte Platz für Jobangebote.
BlackJack

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.
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

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
BlackJack

Ich beschäftige mich ab und zu mit den Aufgaben, so als Denksport. Die haben ja schon eine ganze Menge aus vorherigen Wettbewerben gesammelt.
BlackJack

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.
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

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
BlackJack

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.
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

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... :'(

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...
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.
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 kompliziert

Mal schaun, was es noch so für Probleme gibt ;)

MfG EnTeQuAk
BlackJack

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.
Benutzeravatar
Sr4l
User
Beiträge: 1091
Registriert: Donnerstag 28. Dezember 2006, 20:02
Wohnort: Kassel
Kontaktdaten:

Ich steige auch mit ein ;-)
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

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:
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.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
BlackJack

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. :-)
Benutzeravatar
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?
BlackJack

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.
BlackJack

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!? ;-)
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Kann man sich eigentlich irgendwo den Code der Lösungen ansehen?
BlackJack

Nein. Die Probleme wandern alle in den grossen allgemeinen Aufgabenpool und man kann da noch weiter dran rumrätseln.
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Mist! Dann werd ich die Lösungen nie herausfinden :D
Benutzeravatar
Sr4l
User
Beiträge: 1091
Registriert: Donnerstag 28. Dezember 2006, 20:02
Wohnort: Kassel
Kontaktdaten:

Ich habe mit meiner Lösung angefangen aber dann nicht weiter gemacht wenn (falls) ich es irgendwann mal fertig habe poste ich mal code ;-)
BlackJack

@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.
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

BlackJack hat geschrieben:@mawe: Du musst die Aufgaben nur selber lösen.
Darum sag ich ja: Mist! :D
BlackJack hat geschrieben:Ansonsten kann ich nur verraten was ich gelöst habe und könnte natürlich auch sagen wie.
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 darf :)
Antworten