Matthias Reitinger
ɐɯıǝɹ
Quiz #9
Zeichenbegabte Schildkröten
Regeln
Die Regeln und der Ablauf der Quizrunde können in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält. Lösungsansätze können und dürfen auch schon vorab untereinander ausgetauscht und diskutiert werden, allerdings nicht öffentlich im Forum. Verwendet stattdessen bitte private Nachrichten oder schaut im Chat vorbei.
Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist voraussichtlich Sonntag, der 26. Juli 2009 um ca. 20 Uhr. Update: Verlängert bis Samstag, den 1. August 2009 um ca. 20 Uhr.
Das Problem
Ziel ist es diesmal, eine "zeichnende Schildkröte" zu implementieren. Die Aufgabe ist sehr umfangreich, deshalb habe ich sie auch in zwei Teilaufgaben aufgeteilt. Je nach Lust und Laune, Zeit und der individuellen Fähigkeiten könnt ihr entweder nur Teilaufgabe A oder beide bearbeiten (A ist Voraussetzung für B). Zu beiden Teilaufgaben gibt es auch Erweiterungen, die wie immer optional sind. Ihr habt vorbehaltlich wieder eine volle Woche Zeit zur Bearbeitung. Wenn es aber genügend Rückmeldungen gibt, dass mehr Zeit benötigt wird, wird die Abgabefrist entsprechend nach hinten verschoben.
Grafikausgabe
Dieses Problem beinhaltet die Ausgabe von einfachen Liniengrafiken. Wenn die verwendete Programmiersprache keine einfache Möglichkeit bietet, solche zu erzeugen, empfehle ich euch die Ausgabe von SVG. Ihr könnt dazu folgendes Template verwenden (Platzhalter in eckigen Klammern):
Als [Inhalt] könnt ihr z.B. Strecken oder Streckenzüge verwenden:
Achtung: die Koordinatenangaben in SVG beziehen sich auf ein Koordinatensystem, in dem die y-Achse nach unten zeigt. In den Beispielen verwende ich allerdings das aus der Schule bekannte karthesische Koordinatensystem (y-Achse nach oben). Um zwischen den beiden Systemen umzuwandeln, könnt ihr die Anweisung y = Höhe - y verwenden.
Teilaufgabe A
Eine Schildkröte kennt ihre aktuelle Position in der Zeichenebene und ihre Blickrichtung (Winkel gegenüber der x-Achse). Sie kennt außerdem eine Liste von Aktionen, die sie einmalig nacheinander ausführt. In der einfachsten Form unterstützt die Schildkröte drei Aktionen:
Das zu schreibende Programm soll den Weg, den die Schildkröte durchläuft, grafisch darstellen.
Eingabeformat A
Beispiel
Erklärung: Die Schildkröte startet an Position (15, 10) und blickt zunächst in Richtung der x-Achse. Sie läuft 100 Schritte vorwärts (F), dreht sich dann um 120 Grad nach links (+), läuft wieder 100 Schritte vorwärts, dreht sich weitere 120 Grad nach links und läuft abschließend nochmal 100 Schritte vorwärts. Der resultierende Weg ist ein Dreieck. Er wird in ein Bild mit Breite 130 und Höhe 110 eingezeichnet:
![dreieck.png dreieck.png](https://www.tutorials.de/data/attachments/37/37383-c6b294ddc9177c4cb6fdacd5667b47e9.jpg?hash=xrKU3ckXfE)
Erweiterung
Die Schildkröte soll nun ein Gedächtnis erhalten. Sie kann sich ihre aktuelle Position merken und später wieder dorthin zurückkehren. Dazu kennt sie zusätzlich diese Aktionen:
Teilaufgabe B
Jetzt soll die Schildkröte dazu gebracht werden, dass sie selbstähnliche Gebilde (Fraktale) zeichnet. Dazu erhält das Programm eine Startliste von Aktionen, zusätzlich eine Ersetzungsliste und eine Iterationsanzahl n. Die Ersetzungliste ist wieder eine Liste von Aktionen. Dadurch ergibt sich das...
Eingabeformat B
Beispiel
Die Startliste ist F++F++F und die Ersetzungsliste lautet F-F++F-F. Für n = 0 soll die Schildkröte einfach nur die Startliste ablaufen. Ist n = 1, so wird zuerst jedes F in der Startliste durch die Ersetzungsliste ersetzt und dann die resultierende Liste abgelaufen:
Anders formuliert: die Schildkröte läuft die Startliste ab, führt aber bei jedem F die Ersetzungsliste aus, anstatt vorwärts zu laufen. Bei n = 2 werden zwei "Ersetzungsrunden" durchgeführt. Die sich ergebende Liste wäre also
Für höhere n lässt sich dieses Verfahren beliebig fortführen. Die Liste der Aktionen wächst dabei allerdings exponentiell, man sollte n also nicht zu groß wählen (einstelliger oder sehr kleiner zweistelliger Bereich).
Für n = 5 ergibt sich dieses Bild (die Kochsche Schneeflocke):
![koch.png koch.png](https://www.tutorials.de/data/attachments/37/37384-d818d4609a01cae81e26aa0dc562c01e.jpg?hash=2BjUYJoByu)
Erweiterung I
Um noch komplexere Fraktale zeichnen zu können, soll anstatt der Ersetzungsliste eine Reihe von Ersetzungsregeln angegeben werden können. Eine Ersetzungsregel hat zwei Bestandteile: das zu ersetzende Symbol (beliebiger lateinischer Großbuchstabe) und die Ersetzungsliste (Liste von Aktionen + Symbolen).
Beispiel
sind zwei Ersetzungsregeln. Das zu ersetzende Symbol in der ersten Regel ist X, die Ersetzungsliste XF+F. Die zweite Regel beschreibt die Ersetzung von F durch FF.
Jedes Symbol darf in höchstens einer Ersetzungsregel als zu ersetzendes Symbol auftauchen. In jeder Iteration sollen jetzt sämtliche Ersetzungsregeln angewandt werden. Achtung: das soll für alle Regeln simultan
geschehen!
Beispiel
Es sollen die Ersetzungsregeln aus dem letzten Beispiel auf die Aktionsliste
angewendet werden. Das Ergebnis nach einer Iteration ist
und nicht
Wenn die Schildkröte eine Aktionsliste abläuft, in der auch andere Symbole als F auftauchen, dann werden diese einfach ignoriert.
Eingabeformat B I
Beispiel
erzeugt die Hilbert-Kurve:
![hilbert.png hilbert.png](https://www.tutorials.de/data/attachments/37/37385-97ca1ef086f2d12a4f1d789a5136acde.jpg?hash=l8oe8Iby0S)
Erweiterung II
Die Beschränkung, dass jedes Symbol nur in einer Ersetzungregel auftauchen darf, fällt weg. Stattdessen wird jeder Ersetzungsregel eine Wahrscheinlichkeit zugeordnet, dass diese gewählt wird. Für jedes Vorkommen eines zu ersetzenden Symbols wird also anhand der angegebenen Wahrscheinlichkeiten eine Regel ausgewählt, die für dieses Vorkommen angewandt wird. In der Eingabe könnte die Wahrscheinlichkeit einfach zwischen Symbol und Ersetzungsliste notiert werden.
Erweiterung III
Wer immer noch nicht genug hat, kann vielleicht mit den folgenden Stichworten was anfangen: kontextsensitive Ersetzungsregeln, anpassbare Farbgebung, GUI zur interaktiven Einstellung der Parameter, Erweiterung auf 3D, ...
Zusätzliche Beispiele/Tests
Im Eingabeformat A:
Ergebnis:
![tutorials.png tutorials.png](https://www.tutorials.de/data/attachments/37/37386-9b16512ea33c952bdffa4a8f9c557884.jpg?hash=mxZRLqM8lS)
Im Eingabeformat A, mit Erweiterung:
Ergebnis:
![tutorials2.png tutorials2.png](https://www.tutorials.de/data/attachments/37/37387-66a7724a75a203952879594fa3528b1d.jpg?hash=ZqdySnWiA5)
Im Eingabeformat B:
Ergebnis:
![tree.jpg tree.jpg](https://www.tutorials.de/data/attachments/37/37388-d15c719d2a1b2ab004e981f1e3de4635.jpg?hash=0VxxnSobKr)
Im Eingabeformat B I:
Ergebnis:
![tree2.png tree2.png](https://www.tutorials.de/data/attachments/37/37389-eb07c48455d634f09209650db51c5886.jpg?hash=6wfEhFXWNP)
Im Eingabeformat B I:
Ergebnis:
![dragon.png dragon.png](https://www.tutorials.de/data/attachments/37/37455-3933b9a8cd83b7f8066b645014e0d54a.jpg?hash=OTO5qM2Dt_)
Im Eingabeformat B II (Je höher die Zahl desto wahrscheinlicher wird die Regel auswählt. Hier haben alle eine Wahrscheinlichkeit von 1:4, also 25%):
Mögliche Ergebnisse:
![nondet1.png nondet1.png](https://www.tutorials.de/data/attachments/37/37456-88d31ec3e8df77435b12ff0ffed0d005.jpg?hash=iNMew-jfd0)
![nondet2.png nondet2.png](https://www.tutorials.de/data/attachments/37/37457-fbf0b601d5d220e618ad90c63293f1c2.jpg?hash=-_C2AdXSIO)
![nondet3.png nondet3.png](https://www.tutorials.de/data/attachments/37/37458-940d51a3ab594765e49fdf65fe335379.jpg?hash=lA1Ro6tZR2)
![nondet4.png nondet4.png](https://www.tutorials.de/data/attachments/37/37459-cc2e92fa4bf48325f4b41817a3dfecf6.jpg?hash=zC6S-kv0gy)
![nondet5.png nondet5.png](https://www.tutorials.de/data/attachments/37/37460-25cf8783f98b968068109900c58a6b12.jpg?hash=Jc-Hg_mLlo)
Wenn du weitere Beispiele hast, dann nur her damit.
Im Anhang nochmals sämtliche Beispiele in den jeweiligen Eingabeformaten, inkl. Logdateien und SVG-Ausgabe.
Zeichenbegabte Schildkröten
Regeln
Die Regeln und der Ablauf der Quizrunde können in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält. Lösungsansätze können und dürfen auch schon vorab untereinander ausgetauscht und diskutiert werden, allerdings nicht öffentlich im Forum. Verwendet stattdessen bitte private Nachrichten oder schaut im Chat vorbei.
Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist voraussichtlich Sonntag, der 26. Juli 2009 um ca. 20 Uhr. Update: Verlängert bis Samstag, den 1. August 2009 um ca. 20 Uhr.
Das Problem
Ziel ist es diesmal, eine "zeichnende Schildkröte" zu implementieren. Die Aufgabe ist sehr umfangreich, deshalb habe ich sie auch in zwei Teilaufgaben aufgeteilt. Je nach Lust und Laune, Zeit und der individuellen Fähigkeiten könnt ihr entweder nur Teilaufgabe A oder beide bearbeiten (A ist Voraussetzung für B). Zu beiden Teilaufgaben gibt es auch Erweiterungen, die wie immer optional sind. Ihr habt vorbehaltlich wieder eine volle Woche Zeit zur Bearbeitung. Wenn es aber genügend Rückmeldungen gibt, dass mehr Zeit benötigt wird, wird die Abgabefrist entsprechend nach hinten verschoben.
Grafikausgabe
Dieses Problem beinhaltet die Ausgabe von einfachen Liniengrafiken. Wenn die verwendete Programmiersprache keine einfache Möglichkeit bietet, solche zu erzeugen, empfehle ich euch die Ausgabe von SVG. Ihr könnt dazu folgendes Template verwenden (Platzhalter in eckigen Klammern):
XML:
<?xml version="1.0" ?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg xmlns="http://www.w3.org/2000/svg" version="1.1"
width="[Breite]" height="[Höhe]" stroke="black" fill="none">
[Inhalt]
</svg>
XML:
<line x1="[Startpunkt x]" y1="[Startpunkt y]" x2="[Endpunkt x]" y2="[Endpunkt y]" />
XML:
<polyline points="[Punkt 1 x] [Punkt 1 y], [Punkt 2 x] [Punkt 2 y], [usw.], [Punkt n x] [Punkt n y]" />
Teilaufgabe A
Eine Schildkröte kennt ihre aktuelle Position in der Zeichenebene und ihre Blickrichtung (Winkel gegenüber der x-Achse). Sie kennt außerdem eine Liste von Aktionen, die sie einmalig nacheinander ausführt. In der einfachsten Form unterstützt die Schildkröte drei Aktionen:
- +: Linksdrehung (gegen den Uhrzeigersinn)
- -: Rechtsdrehung (im Uhrzeigersinn)
- F: Vorwärtsbewegung in Blickrichtung (Forward)
Das zu schreibende Programm soll den Weg, den die Schildkröte durchläuft, grafisch darstellen.
Eingabeformat A
Code:
Breite Höhe
x-Position y-Position
Schrittweite
Drehwinkel
Liste der Aktionen
Beispiel
Code:
130 110
15 10
100
120
F+F+F
![dreieck.png dreieck.png](https://www.tutorials.de/data/attachments/37/37383-c6b294ddc9177c4cb6fdacd5667b47e9.jpg?hash=xrKU3ckXfE)
Erweiterung
Die Schildkröte soll nun ein Gedächtnis erhalten. Sie kann sich ihre aktuelle Position merken und später wieder dorthin zurückkehren. Dazu kennt sie zusätzlich diese Aktionen:
- [: Merken der aktuellen Position und Blickrichtung
- ]: Zurücklaufen zur gemerkten Position und Drehung in gemerkte Blickrichtung
Teilaufgabe B
Jetzt soll die Schildkröte dazu gebracht werden, dass sie selbstähnliche Gebilde (Fraktale) zeichnet. Dazu erhält das Programm eine Startliste von Aktionen, zusätzlich eine Ersetzungsliste und eine Iterationsanzahl n. Die Ersetzungliste ist wieder eine Liste von Aktionen. Dadurch ergibt sich das...
Eingabeformat B
Code:
Breite Höhe
x-Position y-Position
Schrittweite
Drehwinkel
Startliste
Iterationsanzahl
Ersetzungsliste
Beispiel
Code:
260 300
10 80
1
60
F++F++F
5
F-F++F-F
![48003d1248012886-ersetzung.png](/proxy.php?image=http%3A%2F%2Fwww.tutorials.de%2Fforum%2Fattachments%2Fdiskussion%2F48003d1248012886-ersetzung.png&hash=48647d362477d8f9ed03f268f0a96c9f)
Anders formuliert: die Schildkröte läuft die Startliste ab, führt aber bei jedem F die Ersetzungsliste aus, anstatt vorwärts zu laufen. Bei n = 2 werden zwei "Ersetzungsrunden" durchgeführt. Die sich ergebende Liste wäre also
Code:
F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F
Für n = 5 ergibt sich dieses Bild (die Kochsche Schneeflocke):
![koch.png koch.png](https://www.tutorials.de/data/attachments/37/37384-d818d4609a01cae81e26aa0dc562c01e.jpg?hash=2BjUYJoByu)
Erweiterung I
Um noch komplexere Fraktale zeichnen zu können, soll anstatt der Ersetzungsliste eine Reihe von Ersetzungsregeln angegeben werden können. Eine Ersetzungsregel hat zwei Bestandteile: das zu ersetzende Symbol (beliebiger lateinischer Großbuchstabe) und die Ersetzungsliste (Liste von Aktionen + Symbolen).
Beispiel
Code:
X XF+F
F FF
Jedes Symbol darf in höchstens einer Ersetzungsregel als zu ersetzendes Symbol auftauchen. In jeder Iteration sollen jetzt sämtliche Ersetzungsregeln angewandt werden. Achtung: das soll für alle Regeln simultan
Beispiel
Es sollen die Ersetzungsregeln aus dem letzten Beispiel auf die Aktionsliste
Code:
XF
Code:
XF+FFF
Code:
XFF+FFFF
Wenn die Schildkröte eine Aktionsliste abläuft, in der auch andere Symbole als F auftauchen, dann werden diese einfach ignoriert.
Eingabeformat B I
Code:
Breite Höhe
x-Position y-Position
Schrittweite
Drehwinkel
Startliste
Interationsanzahl
Ersetzungsregel 1
...
Ersetzungsregel k
Beispiel
Code:
340 340
10 10
5
90
X
6
X +YF-XFX-FY+
Y -XF+YFY+FX-
![hilbert.png hilbert.png](https://www.tutorials.de/data/attachments/37/37385-97ca1ef086f2d12a4f1d789a5136acde.jpg?hash=l8oe8Iby0S)
Erweiterung II
Die Beschränkung, dass jedes Symbol nur in einer Ersetzungregel auftauchen darf, fällt weg. Stattdessen wird jeder Ersetzungsregel eine Wahrscheinlichkeit zugeordnet, dass diese gewählt wird. Für jedes Vorkommen eines zu ersetzenden Symbols wird also anhand der angegebenen Wahrscheinlichkeiten eine Regel ausgewählt, die für dieses Vorkommen angewandt wird. In der Eingabe könnte die Wahrscheinlichkeit einfach zwischen Symbol und Ersetzungsliste notiert werden.
Erweiterung III
Wer immer noch nicht genug hat, kann vielleicht mit den folgenden Stichworten was anfangen: kontextsensitive Ersetzungsregeln, anpassbare Farbgebung, GUI zur interaktiven Einstellung der Parameter, Erweiterung auf 3D, ...
Zusätzliche Beispiele/Tests
Im Eingabeformat A:
Code:
460 100
30 10
20
90
+FF+F--F+FF--FF+F--F+FF+FF+FF--FF+FF+FF--FF+FF+FF+F--F+FF--FF+F--F+FF+FFFF+FF+FF+FF+FFF+FF-F--F+FF+FF+FF--FF+FFF+FF-F++FFF+FF+FFFF+FFFF++FFFF+FFF+F+FF-F-FF
![tutorials.png tutorials.png](https://www.tutorials.de/data/attachments/37/37386-9b16512ea33c952bdffa4a8f9c557884.jpg?hash=mxZRLqM8lS)
Im Eingabeformat A, mit Erweiterung:
Code:
460 100
30 10
20
90
[+FF[FF][+F][-F]]FF[+FF]FF[+FF]FF[+FF[FF][+F][-F]]FFFF[+FF+FF+FF]F[+FF-F]FF[+FF]FFF[+FF[-F]+FF+FF]FF[+FFFF]FFF+F+FF-F-FF
![tutorials2.png tutorials2.png](https://www.tutorials.de/data/attachments/37/37387-66a7724a75a203952879594fa3528b1d.jpg?hash=ZqdySnWiA5)
Im Eingabeformat B:
Code:
400 600
130 10
5
22.5
++++F
5
FF-[-F+F+F]+[+F-F-F]
![tree.jpg tree.jpg](https://www.tutorials.de/data/attachments/37/37388-d15c719d2a1b2ab004e981f1e3de4635.jpg?hash=0VxxnSobKr)
Im Eingabeformat B I:
Code:
290 430
190 10
5
22.5
++++X
5
X F-[[X]+X]+F[+FX]-X
F FF
![tree2.png tree2.png](https://www.tutorials.de/data/attachments/37/37389-eb07c48455d634f09209650db51c5886.jpg?hash=6wfEhFXWNP)
Im Eingabeformat B I:
Code:
490 340
380 120
5
90
FX
12
X X+YF+
Y -FX-Y
![dragon.png dragon.png](https://www.tutorials.de/data/attachments/37/37455-3933b9a8cd83b7f8066b645014e0d54a.jpg?hash=OTO5qM2Dt_)
Im Eingabeformat B II (Je höher die Zahl desto wahrscheinlicher wird die Regel auswählt. Hier haben alle eine Wahrscheinlichkeit von 1:4, also 25%):
Code:
300 500
150 10
3
30
+++F
6
F 1 F[+F]F[-F]F
F 1 F[+F]F
F 1 F[-F]F
F 1 FF
![nondet1.png nondet1.png](https://www.tutorials.de/data/attachments/37/37456-88d31ec3e8df77435b12ff0ffed0d005.jpg?hash=iNMew-jfd0)
![nondet2.png nondet2.png](https://www.tutorials.de/data/attachments/37/37457-fbf0b601d5d220e618ad90c63293f1c2.jpg?hash=-_C2AdXSIO)
![nondet3.png nondet3.png](https://www.tutorials.de/data/attachments/37/37458-940d51a3ab594765e49fdf65fe335379.jpg?hash=lA1Ro6tZR2)
![nondet4.png nondet4.png](https://www.tutorials.de/data/attachments/37/37459-cc2e92fa4bf48325f4b41817a3dfecf6.jpg?hash=zC6S-kv0gy)
![nondet5.png nondet5.png](https://www.tutorials.de/data/attachments/37/37460-25cf8783f98b968068109900c58a6b12.jpg?hash=Jc-Hg_mLlo)
Wenn du weitere Beispiele hast, dann nur her damit.
Im Anhang nochmals sämtliche Beispiele in den jeweiligen Eingabeformaten, inkl. Logdateien und SVG-Ausgabe.
Anhänge
Zuletzt bearbeitet von einem Moderator: