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.
Listing 1 nutzt die Funktion »explore()«
ab Zeile 6 als Iterator, der in einer Endlos-
schleife ab Zeile 14 die Zeilen abwandert
und in Zeile 31 nach der Ankunft an ei-
nem 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«.
Als erste Optimierung des Brute-Force-
Algorithmus könnte der Fischer zum Bei-
spiel 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 star-
tet, 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 U
‑‑fish=x1:y1,x2:y2,x3:y3,...verstehen und in seiner Ausgabe für je-
des 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 Redak-
tion 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.
Damit die Teilnehmer sich nicht mit lang-
weiligem Standardgeplänkel zur Analyse
der Kommandozeilen-Parameter unddem Befüllen des Sees mit Fischen (Ab-
bildung 3) aufhalten müssen, dürfen sie
das Modul »fishing« in Listing 2 verwen-
den (verfügbar auf [1]).
Dazu nutzt Listing 2 das Modul »arg-
parse«, das sich via »pip3 install argparse«
installieren lässt. Die Klasse »Pond« ana-
lysiert in ihrem Konstruktor zunächst die
als Kommandozeilen-Parameter herein-
gereichten Werte für die Dimensionen
des Sees (»--size«) und setzt die Fische
an den in »--fish« durch Kommas abge-
trennte Koordinatenpaaren in den Teich.
Anschließend kann ein am Wettbewerb
teilnehmendes Fischer-Skript mit »import
fishing« und »pond.Pond().data« auf ei-
nen Array von Arrays zugreifen, der an
leeren Gewässerpositionen den numeri-
schen Wert »0« aufweist und in Bereichen
mit Fischen den Wert »1«.Mehr als tausend Worte
Als praktische Applikation, die eifrigen
Teilnehmern bei der Entwicklung helfen01 #!/usr/bin/python3
02 import fishing
03
04 pond = fishing.Pond()
05
06 def explore(data):
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: »explore.py«Abbildung 2: Funktional, aber kaum preisverdächtig- ein Brute-Force-Algorithmus.
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9Abbildung 1: Fische im digitalen See, die der Algo-
rithmus angeln muss.
99http://www.linux-magazin.deProgrammierenSnapshot