![[ICO]](/icons/blank.gif){kind=icon}
![[DIR]](/icons/back.gif){kind=icon}
![[DIR]](/icons/folder.gif){kind=icon}
![[ ]](/icons/layout.gif){kind=icon}
Die ausgewählte Problemstellung ist von Googles Programmierwettbewerb Hash Code übernommen und soll dort in 4er-Teams innerhalb von vier Stunden bearbeitet werden. Das heißt, in dieser Zeit sollen möglichst viele Punkte für die Lösung NP-schwerer Probleme erreicht werden.
Als Angabe wird die Aufgabe in einem PDF-Dokument erklärt. Als Eingabe wird eine Textdatei mit Tag-Informationen fiktiver Fotos eingelesen. Diese sollen dann neu arrangiert und deren Indizes als Text ausgegeben werden. Je nach Anordnung der Fotos können unterschiedlich viele Punkte erreicht werden.
siehe auch: Präsentation (PDF)
Zu dieser Problemstellung konnten sowohl algorithmische Verbesserungen als auch klassische Optimierungstransformationen angewandt werden. Zuerst wurde ein Algorithmus in Python entworfen, der möglichst viele Punkte und annehmbarer Zeit erreicht. Schließlich wurde dieser in C nachimplementiert und effizienter gemacht.
In der C-Implementierung konnten die CPU-Zyklen der Instanz
c_memorable_moments.txt (Beispiel mit 1000 Fotos), kompiliert mit
dem GCC-Flag -Ofast, von 575 Millionen auf
314 Millionen reduziert werden.
In der Verzeichnissen java, python und
c sind die jeweiligen Implementierungen zu finden:
| Name | Last modified | Size | Description |
|---|---|---|---|---|
| Parent Directory | - | ||
| c/ | 28-Jan-2020 14:28 | - | |
| hashcode2019_qualification_task.pdf | 28-Jan-2020 14:28 | 147K | |
| input_qualification_round_2019/ | 28-Jan-2020 14:28 | - | |
| java/ | 28-Jan-2020 14:27 | - | |
| presentation.pdf | 28-Jan-2020 14:28 | 480K | |
| python/ | 28-Jan-2020 14:28 | - | |