Open Contest 2007

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

Open Contest 2007

Beitragvon BlackJack » Dienstag 10. April 2007, 08:20

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:

Beitragvon EnTeQuAk » Dienstag 10. April 2007, 08:55

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

Beitragvon BlackJack » Dienstag 10. April 2007, 10:50

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

Beitragvon BlackJack » Dienstag 17. April 2007, 08:44

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:

Beitragvon EnTeQuAk » Dienstag 17. April 2007, 13:11

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

Beitragvon BlackJack » Dienstag 17. April 2007, 14:09

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:

Beitragvon EnTeQuAk » Dienstag 17. April 2007, 14:29

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

Beitragvon BlackJack » Dienstag 17. April 2007, 14:57

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:

Beitragvon Sr4l » Dienstag 17. April 2007, 16:42

Ich steige auch mit ein ;-)
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Dienstag 17. April 2007, 18:14

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

Beitragvon BlackJack » Dienstag 17. April 2007, 18:42

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:

Beitragvon Sr4l » Dienstag 17. April 2007, 19:49

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

Beitragvon BlackJack » Dienstag 17. April 2007, 22:33

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

Beitragvon BlackJack » Freitag 27. April 2007, 13:53

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])

Beitragvon mawe » Freitag 27. April 2007, 14:00

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

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder