© ANTONIO BALAGUER SOLER, 123RF

Die gestellte Programmieraufgabe verlangte, einen Fischer in seinem Boot einen See mit m x n Quadraten abfahren zu lassen, in denen sich zufällig verteilt Fische befinden, die es zu fangen galt.

Die besten Einsendungen zum Wettbewerb lieferten bei der bis dato geheim gehaltenen Fischverteilung je Testfall (Listing 1) für die Aufgabe allesamt sehr gute Ergebnisse. Die Gewinner konnten sich also letztlich nur mit minimal weniger Schritten beim möglichst schnellen Absolvieren des Fischfangs von der starken Konkurrenz absetzen.

1 --size=1x1 --fish=0:0
2 --size=5x5 --fish=0:0,1:0,2:0,3:0,4:0
3 --size=4x4 --fish=0:0
4 --size=4x4 --fish=0:3,1:3,2:3,3:3,0:0,1:0,2:0,3:0
5 --size=4x4 --fish=0:0,1:1,3:3
6 --size=100x100 --fish=0:0,99:99,0:49,49:0,49:49
7 --size=4x4 --fish=0:0,1:0,2:0,3:0,2:1,1:2,0:3,1:3,2:3,3:3
8 --size=5x5 --fish=0:0,0:2,0:4,1:0,1:2,1:4,2:0,2:2,2:4,3:0,3:2,3:4,4:0,4:2,4:4
9 --size=7x7 -fish=3:0,2:1,3:1,4:1,1:2,3:2,5:2,1:3,3:3,5:3,1:4,3:4,5:4,2:5,3:5,4:5,3:6

Die Aufgabe

Zur Erinnerung: In der Wettbewerbsaufgabe ist ein See gegeben, der sich rechteckig über m x n Quadrate ausdehnt. Ein Fischer fährt mit seinem Boot die Quadrate in einer zu bestimmenden Reihenfolge ab. Sein Ziel ist es, auf schnellstem Wege alle im See zufällig verteilten Fische einzufangen. Die purzeln ins Boot, sobald er mit seinem Boot ins Quadrat des Fisches einfährt.

Als Beispiel diente im Artikel ein Listing, das garantiert keinen Preis gewinnen könnte, weil es die Quadrate des Sees von links nach rechts und von oben nach unten abfuhr und der Reihe nach alle gefundenen Fische meldete. Da der Fischer jeweils pro Schritt nur ein Quadrat weiter wandern darf, rudert er mit diesem Listing die erste Reihe von links nach rechts durch, in der zweiten dann von rechts nach links und so weiter, bis er am unteren Ende des Sees entweder links oder rechts anschlägt, abhängig davon, ob die Anzahl der Quadratzeilen gerade oder ungerade ist.

Während es also garantiert bessere Verfahren als dieses Listing gibt, die das Puzzle knacken, sollte es als Blaupause für eingesandte Lösungen dienen.

Gewinnende Ansätze

Die meisten Einsender erkannten korrekt, dass es sich um eine Variation des bekannten “Traveling Salesman”-Problems [2] handelt. Das Problem des Handlungsreisenden ist ein Klassiker, bei dem es darauf ankommt, den Reisenden keinen Ort – außer dem ersten – zweimal besuchen zu lassen. Außerdem soll die Strecke möglichst kurz sein.

Die Gewinner (Listing 2) stürzten sich mit “Nearest Neighbor” auf die Fische. Diese Strategie bedeutet, jeweils den nächstgelegenen Ort zu besuchen und diesen Ansatz weiter anzuwenden.

01  1           olaf-f   377 (1-5-1-10-7-297-13-17-26)
02
03  2           ralf-h   378 (1-5-1-10-7-297-14-17-26)
04
05  3         rainer-t   379 (1-5-1-10-7-297-13-17-28)
06  3      christoph-g   379 (1-5-1-10-7-297-13-17-28)
07  3          peter-m   379 (1-5-1-10-7-297-13-17-28)
08
09  4            [...]   380 (1-5-1-10-7-297-14-17-28)
10  5            [...]   382 (1-5-1-10-7-297-14-17-30)
11  6            [...]   447 (1-8-1-10-11-348-16-24-28)

Wie haarscharf es dabei zuging, zeigen die unterschiedlichen Routen des Fischers beim Testfall 7 (Abbildung 1). Der Algorithmus des Gewinners [1] schlängelt sich in 13 Schritten zuerst ganz nach rechts und dann entlang der Diagonalen nach links unten (Abbildung 2). Der Zweitplatzierte wählt statt der rechten oberen Ecke zunächst den Weg der Diagonalen, um dann am Ende doch wieder hochzufahren und die Ecke mitzunehmen – was jedoch insgesamt 14 Schritte braucht und damit nicht ganz zum Sieg reicht (Abbildung 3).

Abbildung 1: Die Fischverteilung beim Testfall 7.

Abbildung 2: Der Algorithmus des Gewinners findet die Fische in 13 Schritten.

Abbildung 3: Der Zweitplatzierte braucht 14 Schritte, um alle Fische zu angeln.

Auch die Algorithmen der Teilnehmer, die einige Schritte mehr brauchen und damit leider auf den hinteren Plätzen landen, beweisen allesamt das hohe Programmierniveau der Leserschaft des Linux-Magazins. Die Redaktion bedankt sich herzlich bei allen Einsendern und wünscht den Gewinnern viel Freude mit ihren Buchpreisen!