Linux-Magazin_-_Januar_2019

fen von oben nach unten, die y-Werte

von links nach rechts. Der Fischer muss

dabei jederzeit innerhalb der Begrenzun-

gen des Sees bleiben, darf also nicht über

die Ränder des Koordinatensystems hin-

ausschippern. Ziel des Verfahrens ist es,

den kürzesten Weg zu ermitteln, auf dem

der Fischer alle Fische fängt.

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

Der schnellste Algorithmus gewinnt also

den Preis. Als zugelassene Programmier-

sprache kommt das im Snapshot häufig

genutzte Python zum Einsatz. Preise,

Einsendemöglichkeiten und die Regula-

rien im Detail finden sich nochmals im

Kasten „Wettbewerb“ wieder.

Das Ganze Unterfangen als harmlose

Spielerei abzutun könnte sich als Bume-

rang 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 Rahmenbedingun-

gen 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 bestim-

menden Reihenfolge ab. Angestrebtes

Ziel ist es, auf schnellstem Wege alle

im See zufällig verteilten Fische einzu-

fangen, 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 je-

weils nächsten Quadrat. Die x-Werte lau-

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. Michael Schilli

Programmier-Wettbewerb: Wer knackt die Rätselfrage des Programmiermeisters?

Beißt was an?

Programmieren

98

http://www.linux-magazin.de

Snapshot

© ANTONIO BALAGUER SOLER, 123RF

Im Screencast demonstriert Michael

Schilli das Beispiel: [http:// http://www.

linux-magazin.de/ videos/]

Online PLUS

Die Teilnehmer schicken ihre Lösung an die

Adresse [snapshot@linux‑magazin. de]. Die

Redaktion prüft das Skript gemäß den Regu‑

larien, die Mike Schilli im Artikel formuliert.

Das schnellste Skript gewinnt. Zu gewinnen

gibt es drei Bücher zur Java‑Programmierung

von Arnold Willemer.

Einsendeschluss ist der 31. Dezember. Es gel‑

ten die Gewinnspiel‑Bedingungen [http://www.

computec. de/ pdf/ Allge meineGewinnspiel bedin‑

gungen.pdf] und die Datenschutzerklärung

von Computec. Die Mail‑Adressen werden nur

verwendet, um die Gewinner zu kontaktieren.

Wettbewerb