© ANTONIO BALAGUER SOLER, 123RF

Eifrige Leser des Programmier-Snapshots haben über die vergangenen Jahre sicher genug Tipps gesammelt, um selbst einen Algorithmus zum Lösen eines mathematischen Puzzles zu entwerfen. Aus allen Einsendungen belohnen wir jene, die das von Mike Schilli ausgedachte Problem am schnellsten vollständig löst.

Der schnellste Algorithmus gewinnt also den Preis. Als zugelassene Programmiersprache kommt das im Snapshot häufig genutzte Python zum Einsatz. Preise, Einsendemöglichkeiten und die Regularien im Detail finden sich nochmals im Kasten “Wettbewerb” wieder.

Das Ganze Unterfangen als harmlose Spielerei abzutun könnte sich als Bumerang erweisen: Schließlich stellen große Softwarefirmen im Silicon Valley ganz ähnliche Fragen beim Einstellungstest [2]. Nur wer saubere Logik schreibt, die auch bei dehnbaren Rahmenbedingungen skaliert, kriegt den Job!

In der Aufgabe ist ein See gegeben, der sich rechteckig auf »m x n« Quadraten ausdehnt. Ein Fischer fährt mit seinem Boot die Quadrate in einer zu bestimmenden Reihenfolge ab. Angestrebtes Ziel ist es, auf schnellstem Wege alle im See zufällig verteilten Fische einzufangen, die ins Boot purzeln, sobald der Fischer mit seinem Boot ins Quadrat des Fisches einfährt.

Petri Heil

Als Beispiel liegt in Abbildung 1 ein See mit den Abmessungen 10 mal 10 vor, in dessen Quadraten [1,1]+[3,2] und [4,9]+ Fische schwimmen. Der Fischer startet im Quadrat links oben ([0,0]) und fährt von dort schrittweise entweder nach rechts, links, unten oder oben zum jeweils nächsten Quadrat. Die x-Werte laufen von oben nach unten, die y-Werte von links nach rechts. Der Fischer muss dabei jederzeit innerhalb der Begrenzungen des Sees bleiben, darf also nicht über die Ränder des Koordinatensystems hinausschippern. Ziel des Verfahrens ist es, den kürzesten Weg zu ermitteln, auf dem der Fischer alle Fische fängt.

Abbildung 1: Fische im digitalen See, die der Algorithmus angeln muss.

Dabei illustriert Abbildung 1 nur eine Möglichkeit. In der Praxis schwimmen Fische in beliebig vielen Quadraten und die Größe des Sees kann auch beliebige Werte für »m x n« annehmen. Kritische Extrapunkte erhält, wer den Algorithmus so entwirft, dass er auch bei weitläufigen Seen, also für große Werte für »m« und »n«, weder elend lange braucht, um die Fische zu finden, noch irre Mengen an Speicher verbraucht.

Garantiert keinen Preis gewinnt dabei Listing 1, das die Quadrate des Sees von links nach rechts und von oben nach unten abfährt und der Reihe nach alle gefundenen Fische meldet (Abbildung 2). Da der Fischer jeweils pro Schritt nur ein Quadrat weiterwandern darf, rudert er die erste Reihe von links nach rechts durch, in der zweiten dann von rechts nach links und so weiter, bis er dann am unteren Ende des Sees entweder links oder rechts anschlägt, abhängig davon, ob die Anzahl der Quadratzeilen gerade oder ungerade ist.

01 #!/usr/bin/python3
02 import fishing
03 
04 pond = fishing.Pond()
05 
06 def explore(pond):
07     x = 0
08     y = 0
09     ymax = pond.height - 1
10     xmax = pond.width - 1
11 
12     yield [x,y]
13 
14     while True:
15         if y % 2:
16             if x == 0:
17                 if y == ymax:
18                     return
19                 else:
20                     y += 1
21             else:
22                 x -= 1
23         else:
24             if x == ymax:
25                 if y == xmax:
26                     return
27                 else:
28                     y += 1
29             else:
30                 x += 1
31         yield [x,y]
32 
33 for coord in explore(pond):
34      x, y = coord
35       print("%d %d:%d" %
36        (pond.data[x][y], x, y)

Listing 1 nutzt die Funktion »explore()« ab Zeile 6 als Iterator, der in einer Endlosschleife ab Zeile 14 die Zeilen abwandert und in Zeile 31 nach der Ankunft an einem neuen Quadrat dessen Koordinaten mit »yield« meldet und die Kontrolle an den Aufrufer zurückgibt. Die For-Schleife ab Zeile 33 ruft den Iterator dann so lange auf, bis dieser keine weiteren Werte mehr liefert, ausgelöst durch eine der beiden »return«-Anweisungen im Iterator-Code. Die Ausgabe des Skripts zeigt Abbildung 2. Die Anzahl der abzuarbeitenden Schritte ist wenig überraschend konstant bei »m x n«.

Abbildung 2: Funktional, aber kaum preisverdächtig – ein Brute-Force-Algorithmus.

Als erste Optimierung des Brute-Force-Algorithmus könnte der Fischer zum Beispiel nach dem letzten gefangenen Fisch die Ausgabe der danach unsinnigerweise abgefahrenen Quadrate abbrechen. Die Anzahl der im See versteckten Fische könnte das Programm vorab bestimmen, was es treibt, bevor die Ausgabe startet, ist ihm schließlich selbst überlassen. Ruckzuck verkürzt sich so der Suchpfad um das letzte, unnütze Stück und der Programmierer rückt einen Schritt weiter in Richtung Preis. Aber Vorsicht, wenn das Verfahren bei einem 1000 mal 1000 Quadrate großen See hundert Jahre zur Ermittlung und Routenplanung braucht, gibt es auch wieder Punktabzug!

Vorgeschriebenes Format

Während es also fast immer garantiert bessere Verfahren als Listing 1 gibt, die das Puzzle knacken, soll es dennoch als Blaupause für eingesandte Lösungen dienen. Damit die Redaktion einfach prüfen kann, ob eine Lösung korrekt ist und die Anzahl der auf dem besten Pfad durchquerten Quadrate zur Bewertung summieren kann, muss das eingesandte Skript »explore.py« die Parameter

explore.py --size=MxN  --fish=x1:y1,x2:y2,x3:y3,...

verstehen und in seiner Ausgabe für jedes durchquerte, aber als leer befundene Quadrat mit den Koordinaten »x« und »y«

0 x:y

drucken, während die Ausgabezeilen mit

1 x:y

durchquerte, aber mit Fischen gefüllte Quadrate bezeichnen. So kann die Redaktion einfach mit »wc -l« prüfen, wie viele Schritte der Algorithmus gebraucht hat, und mit einem »awk«-Skript ermitteln, ob auch alle Fische im Netz zappeln.

Abbildung 3: Beispiel einer Fischverteilung, gezeichnet von Listing 2.

Damit die Teilnehmer sich nicht mit langweiligem Standardgeplänkel zur Analyse der Kommandozeilen-Parameter und dem Befüllen des Sees mit Fischen (Abbildung 3) aufhalten müssen, dürfen sie das Modul »fishing« in Listing 2 verwenden (verfügbar auf [1]).

01 #!/usr/bin/python3
02 import fishing
03 import terminaltables as termt
04 
05 pond = fishing.Pond()
06   
07   print("  ", end=' ')
08     for i in range(pond.width):
09       print("%3d" % i, end=' ')
10 print()   
11 
12 rows = [[" " for y in range(pond.width)]
13         for x in range(pond.height)]
14 
15 for x in range(pond.width):
16    for y in range(pond.height):
17        if(pond.data[x][y] != 0):
18       rows[y][x] = "*"
19 
20 table = termt.SingleTable(rows)
21 table.inner_row_border = True
22
23 idx=0
24 row=0
25 for line in table.table.split("\n"):
26    if idx % 2 == 1:
27          print("%2d" % row, end=' ')
28          row += 1
29    else:
30      print("  ", end=' ')
31        print(line)
32 idx += 1

Dazu nutzt Listing 2 das Modul »argparse«, das sich via »pip3 install argparse« installieren lässt. Die Klasse »Pond« analysiert in ihrem Konstruktor zunächst die als Kommandozeilen-Parameter hereingereichten Werte für die Dimensionen des Sees (»–size«) und setzt die Fische an den in »–fish« durch Kommas abgetrennte Koordinatenpaaren in den Teich. Anschließend kann ein am Wettbewerb teilnehmendes Fischer-Skript mit »import fishing« und »pond.Pond().data« auf einen Array von Arrays zugreifen, der an leeren Gewässerpositionen den numerischen Wert »0« aufweist und in Bereichen mit Fischen den Wert »1«.

Mehr als tausend Worte

Als praktische Applikation, die eifrigen Teilnehmern bei der Entwicklung helfen könnte und ebenfalls das Hilfsmodul »fishing.py« nutzt, zeichnet Listing 3 die Quadranten des Sees und malt die Stellen, an denen sich Fische aufhalten, mit einem »*« aus. Listing 3 nutzt das Python-Modul »terminaltables«, das sich ebenfalls mit »pip3 install« vom Netz holen lässt.

01 #!/usr/bin/python3
02 import argparse
03 import sys
04
05 class Pond:
06   def __init__(self):
07     parser = argparse.ArgumentParser()
08     group = \
09       parser.add_argument_group('required')
10     group.add_argument(
11       '--size', type=str, help='wxh')
12     group.add_argument('--fish',
13       type=str, help='x1:y1,x2:y2,...')
14
15     args = parser.parse_args()
16     if args.size == None or \
17        args.fish == None:
18       parser.print_help()
19       sys.exit(0)
20
21     width, height = args.size.split('x')
22     self.width=int(width)
23     self.height=int(height)
24
25     self.data = [
26       [0 for j in range(self.height)]
27            for i in range(self.width)]
28
29     for coord in args.fish.split(','):
30       x, y = coord.split(':')
31       self.data[int(x)][int(y)] = 1

Prüfverfahren

Damit die Redaktion eine Einsendung berücksichtigen kann, muss sie folgendem Format genügen: Sie enthält ein ausführbares Python-3-Skript namens »explore.py«, das die Library »fishing.py« nutzt, um die Kommandozeilen-Optionen »–size« und »–fish« entgegenzunehmen. Keine weiteren Libraries sind für die Aufgabe zugelassen, der Code muss mit einer Standardinstallation von Python 3 und den Anweisungen in »explore.py« laufen. Die Datei »explore.py« sollte lesbaren Code enthalten und nicht größer als etwa 10 KByte maximal sein. Es empfiehlt sich für die Teilnehmer auch, entworfene Algorithmen mit unterschiedlichen Seegrößen und Fischverteilungen auszuprobieren.

Die Redaktion wird alle eingehenden Lösungsvorschläge mit drei bis zur Preisvergabe streng geheim gehaltenen Seen und Fischverteilungen (Abbildung 4) ablaufen lassen, um so festzustellen, ob sie korrekt alle Fische finden, und dann zählen, wie viele Schritte durch das Quadratelabyrinth die Lösungen dazu brauchen. Die Code-Einsendungen mit der im Mittel kürzesten Strategie gewinnen. Bei der Ausgabe zu schummeln ist selbstredend strengstens untersagt, der Dieselskandal reicht. Also, an die Arbeit, und gutes Gelingen! (uba)

Abbildung 4: Auch so könnte die streng geheime Verteilung der Fische aussehen, die der Algorithmus fangen muss.