Zum Jahresende hat sich die Redaktion diesmal etwas Besonderes ausgedacht: Eifrige Leser des Programmier-Snapshots haben über die vergangenen Jahre sicher genug Tipps gesammelt, um einen Algorithmus zum Lösen eines mathematischen Puzzles zu entwerfen. Aus allen Einsendungen belohnen wir den schnellsten, der das Problem vollständig löst. Als zugelassene Programmiersprache kommt das im Snapshot häufig genutzte Python zum Einsatz.
Das Ganze als harmlose Spielerei abzutun könnte sich als Bummerang 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 heutigen 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. 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.
Als Beispiel liegt in Abbildung 1 ein See mit den Abmessungen 10x10 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 hinausfahren. 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 von vielen Möglichkeiten. In der Praxis schwimmen Fische in beliebig vielen Quadraten und die Größe des Sees kann 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.
01 #!/usr/bin/env 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 == xmax:
25 if y == ymax:
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))
Garantiert keinen Preis gewinnt 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 weiter wandern 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.
Listing 1 nutzt die Funktion explore() ab Zeile 6 als Iterator, die 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 solange 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 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 Preisgeld. Aber Vorsicht, wenn das Verfahren bei einem 1000x1000 Quadrate großen See hundert Jahre zur Ermittlung und Routenplanung braucht, gibt's Punktabzug!
 |
| Abbildung 2: Funktional, aber kaum preisverdächtig: Ein Brute-Force-Algorithmus |
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 aufsummieren 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:ydrucken, während Ausgabezeilen mit
1 x:ydurchquerte aber mit Fischen befüllte Quadrate bezeichnen. So kann die Redaktion einfach mit wc -l prüfen, wieviele Schritte der Algorithmus gebraucht hat und mit einem awk-Skript ermitteln, ob auch alle Fische im Netz zappeln.
Damit die Teilnehmer sich nicht mit langweiligem Standardgeplänkel zur Analyse der Kommandozeilenparameter und dem Befüllen des Sees mit Fischen aufhalten müssen, dürfen sie das Modul fishing in Listing 2 verwenden (verfügbar auf [1]).
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
Dazu nutzt Listing 2 das Modul argparse, das sich mittels pip3 install argparse installieren lässt. Die Klasse Pond analysiert in ihrem Konstruktor zunächst die als Kommandozeilenparameter 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.
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 an 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/env 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
 |
| Abbildung 3: Ein Beispiel einer Fischverteilung, gezeichnet von Listing 2. |
Damit die Redaktion eine Einsendung berücksichtigen kann, muss sie folgendem Format genügen: Sie enthält ein ausführbares Python3-Skript explore.py, das die Library fishing.py nutzt, um die Kommandozeilenoptionen --size und --fish entgegenzunehmen. Keine weiteren Libraries sind zugelassen, aller Code muss mit einer Standardinstallation von Python3 und den Anweisungen in explore.py laufen. explore.py sollte lesbaren Code enthalten und nicht größer als etwa 10kbyte maximal sein. Es empfiehlt sich, entworfene Algorithmen mit verschiedenen Seegrößen und Fischverteilungen auszuprobieren.
 |
| Abbildung 4: Auch so könnte die streng geheime Verteilung der Fische aussehen, die der Algorithmus fangen muss. |
Die Redaktion wird alle eingehenden Lösungsvorschläge mit drei bis zur Preisvergabe streng geheimgehaltenen Seen und Fishverteilungen ablaufen lassen, um festzustellen, ob sie korrekt alle Fische finden und dann zählen, wieviele Schritte durch das Quadratenlabyrinth sie dazu brauchen. Die Lösung mit der im Mittel kürzesten Strategie gewinnt. Bei der Ausgabe zu schummeln ist selbstredend streng untersagt, wir wollen keinen zweiten Dieselskandal. Also, an die Arbeit, und gutes Gelingen!
Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2019/01/snapshot/
Michael Schilli, "Herausgekegelt": Linux-Magazin 12/09, S.XXX, <U>http://www.linux-magazin.de/ausgaben/2009/12/herausgekegelt/<U>
 |
Michael Schilliarbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |
Hey! The above document had some coding errors, which are explained below:
Unknown directive: =desc