Open Contest 2007

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

Beitragvon BlackJack » Freitag 27. April 2007, 14:31

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

Beitragvon mawe » Freitag 27. April 2007, 15:45

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:

Beitragvon Sr4l » Freitag 27. April 2007, 16:56

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

Beitragvon BlackJack » Freitag 27. April 2007, 18:48

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

Beitragvon mawe » Freitag 27. April 2007, 19:42

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 :)
BlackJack

Beitragvon BlackJack » Freitag 27. April 2007, 22:08

Na dann habe ich hoffentlich nicht zu viel verraten.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder