Zum Inhalt springen
01 — Was damit geht

Die Sprache ist einfach.
Die Programme müssen es nicht sein.

Einfach zu lernen heißt nicht, dass man damit nur einfache Programme schreiben kann. Die Sätze bleiben dieselben wie in Lektion 1 — was daraus entsteht, muss nicht klein bleiben. Zwei Programme, die das zeigen: eines, das man sich selbst überlässt, und eines, das rechnet.

Werkstück 01

Das Spiel des Lebens

John Conway, 1970. Ein Gitter aus Zellen, vier Regeln, kein Spieler — und trotzdem entstehen Formen, die wandern, blinken, sich gegenseitig auffressen und manchmal für immer stehen bleiben. 352 Zellen, dreißig Generationen, jede aus der vorherigen gerechnet.

Die Regeln, wie sie im Programm stehen
Wenn Nachbarn gleich 3 ist, füge 1 zur Neu hinzu.
Sonst wenn Nachbarn gleich 2 und Element i von Feld gleich 1 ist, füge 1 zur Neu hinzu.
Sonst füge 0 zur Neu hinzu.

Das ist das ganze Spiel. Darüber steht ein einziger Satz, der die acht Nachbarn zusammenzählt, darunter kein weiterer. Der Rest des Programms — gut hundert Zeilen — beantwortet die Fragen, die jedes ernsthafte Programm stellt: Wie bringt man ein Gitter in einer Liste unter? Wie zählt man Nachbarn, ohne an jeder Kante zu fragen, ob es dort noch weitergeht? Und wie wird aus Zahlen ein Bild, das stillsteht, während sich darin alles bewegt?

Liste als Gitter 22 mal 16 Zellen, flach in einer einzigen Liste, Nummer statt Koordinaten.

Toter Rand Eine Reihe nie lebender Zellen ringsum — dadurch braucht das Nachbarzählen keine einzige Kantenabfrage.

Feste Leinwand Nimm die Leinwand 440 mal 320. hält den Maßstab still. Ohne diesen Satz springt das Gitter bei jeder Generation.

Aufgabe gibt eine Liste zurück Jede Generation entsteht als neue Liste — nichts wird an Ort und Stelle verändert, deshalb rechnet keine Zelle mit halb aktualisierten Nachbarn.

Im Spielplatz unter 21 Spiel des Lebens, im Archiv als programme/21_spiel_des_lebens.klar.

Werkstück 02

Der Routenplaner

Zwölf Orte in Niederösterreich und Wien, neunzehn Straßen mit gerundeten Kilometern. Zwei Orte werden ausgewürfelt, und der Algorithmus von Edsger Dijkstra sucht die kürzeste Verbindung — dieselbe Rechnung, die im Navigationsgerät steckt.

Der Kern: Lohnt der Umweg über diesen Ort?
Merke Kuerzeste plus Wert für Strecke in Strecken als Ueber.
Wenn Ueber kleiner als Wert für Nachbar in Weite ist:
    Trage Nachbar mit Ueber in Weite ein.
    Trage Nachbar mit Hier in Vorher ein.
Ende.

Dijkstras Einfall von 1959 steht in einem Satz: Nimm immer den nächstgelegenen Ort, der noch offen ist — für den kann kein Umweg mehr kürzer sein. Was das Programm dabei mitschreibt, ist nicht der Weg, sondern zu jedem Ort nur der Vorgänger. Der fertige Weg entsteht erst am Schluss, rückwärts vom Ziel.

Tabelle als Straßennetz Der Schlüssel "Krems|Tulln" nennt beide Enden, der Wert die Kilometer. Befahren wird jede Straße in beide Richtungen.

Drei Tabellen als Gedächtnis Entfernung, Vorgänger, erledigt — mehr braucht der Algorithmus nicht.

Karte aus Koordinaten Jeder Ort hat einen Ost- und einen Nordwert; eine Aufgabe zieht daraus Linien, Richtung und Länge rechnet sie mit Wurzel und Arkustangens selbst aus.

Beschriftete Karte Beschrifte "Wien". schreibt den Namen an die Stelle, an der der Stift steht — auch das kann die Sprache jetzt.

Im Spielplatz unter 22 Routenplaner, im Archiv als programme/22_routenplaner.klar. Die Kilometer sind gerundete Straßenkilometer — für die Urlaubsplanung bitte trotzdem eine echte Karte.