Hash Code 2019 – Photo slideshow

Gruppe 10

• Nikolaus Funk
• Andreas Merckel
• Rainer Zachmann

Aufgabenstellung

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.

Ergebnisse

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.

Implementierung

In der Verzeichnissen java, python und c sind die jeweiligen Implementierungen zu finden:

	Name	Last modified	Size	Description
	Parent Directory		-
	python/	2020-01-28 14:28	-
	presentation.pdf	2020-01-28 14:28	480K
	java/	2020-01-28 14:27	-
	input_qualification_round_2019/	2020-01-28 14:28	-
	hashcode2019_qualification_task.pdf	2020-01-28 14:28	147K
	c/	2020-01-28 14:28	-