Verfasst: 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.
Das deutsche Python-Forum
Seit 2002 Diskussionen rund um die Programmiersprache Python
https://www.python-forum.de/
Open Contest 2007
Seite 1 von 2
Verfasst: Freitag 27. April 2007, 15:45
Mist! Dann werd ich die Lösungen nie herausfinden
Verfasst: 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 
Verfasst: 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.
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.
Verfasst: Freitag 27. April 2007, 19:42
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 zuletztBlackJack hat geschrieben:Ansonsten kann ich nur verraten was ich gelöst habe und könnte natürlich auch sagen wie.
), werd ich dich zwecks Lösungsvergleich belästigen, wenn ich darf Verfasst: Freitag 27. April 2007, 22:08
Na dann habe ich hoffentlich nicht zu viel verraten.