===== Aufgaben Serie C =====

{{gem/mgr}}{{gem/pageinfo}}

==== 1 X-Mas Tree ======

Erstelle einen Algorithmus der aus der folgenden Eingabe eine entsprechenden Weihnachtsbaum zeichnet:

  ; Eingabe
  : <code>
ooooooo
</code>
  ; Ausgabe
  : <code>
   o 
  ooo
 ooooo
ooooooo
   o
</code>

  * Die Grösse des Baumes ist abhängig von der Eingabe.
  * Erweiterung 1: Baumstrunk
  * Erweiterung 2: Baumschmuck

 {{gem/plain#d419758672dd4212}}

++++ Lösung von Roli | <code text>
/^(\s*)(o*)oo/ $1$2\n$&/
/^( *o)((\n *o*)*)$/$1$2\n$1/!
</code> ++++

++++ Lösung von Tscherter| <code text>
/^( *oo?)\n[o\s]*/$&\n$1/!
/^( *o*)oo/ $1\n$&/</code> ++++

==== 2 Pascalsche Dreieck =====

Erstelle einen Algorithmus der aus der folgenden Eingabe eine entsprechendes binäres Pascalsche Dreieck zeichnet.

Eingabe <code>
oooooooooooooooooooooooooooooooooooooooo
o
o
o
o
o
o
o
o
o
o
</code>

Ausgabe <code>
oooooooooooooooooooooooooooooooooooooooo
o o o o o o o o o o o o o o o o o o o o 
oo  oo  oo  oo  oo  oo  oo  oo  oo  oo  
o   o   o   o   o   o   o   o   o   o   
oooo    oooo    oooo    oooo    oooo    
o o     o o     o o     o o     o o     
oo      oo      oo      oo      oo      
o       o       o       o       o       
oooooooo        oooooooo        oooooooo
o o o o         o o o o         o o o o 
oo  oo          oo  oo          oo  oo  
</code>

 {{gem/plain#f983e5a38d8e7023}}

++++ Lösung (TSC) | <code>
/αo([o \n]*)βo/oα$1oβ /
/αo([o \n]*)β /oα$1 βo/
/α ([o \n]*)βo/ α$1oβo/
/α ([o \n]*)β / α$1 β /
/α\no(.*)β(.)\no/\noα$1$2\nβo/
/α\n(.*)β(.)/\n$1$2/ !
/^o(o*)\no/oα$1\nβo/
</code> ++++

==== 3 Häufigste Wort in einem Text ======

Erstelle einen Algorithmus der jenes Wort aus einem Text herausliest, das am häufigsten vorkommt.

  ; Eingabe
  : <code>Allein sitzen, allein ruhen, allein gehen. Indem er sich selbst zaehmt, wird er gluecklich allein - allein im Wald.</code>
  ; Ausgabe
  : <code>allein</code>

 {{gem/plain#57189171ba8425d3}}

++++ Lösung| <code text>
/\W+$//g
/ξ(\w+)\b(.*?)(ξ+)\1\b/ξ$3$1$2/g
/(ξ+)(ξ+)(\w+)\1(\w+)/$1$2$3/g
/.*ξ//!
/\W+|^/ξ/g
</code> ++++

==== 4 Zahlenreihe =====

Eine Zahlenreihe ist folgend aufgebaut: Man beginnt mit einer beliebigen Zahl.
  - Ist die Zahl gerade, kann sie durch zwei geteilt werden
  - Ist die Zahl ungerade, wird sie mit drei multipliziert und eins wird dazu addiert
  - Ist die Zahl 1 stoppt die Reihe

Beispiel: 6, 3, 10, 5, 16, 8, 4, 2, 1

Programmiere die Zahlenreihe als Markow Algorithmus für eine beliebige Eingabe in unärer Form. Beispiel:

  ; Eingabe
  : <code>111</code>
  ; Ausgabe
  : <code>111
1111111111
11111
1111111111111111
11111111
1111
11
1</code>

 {{gem/plain#f8e4233bf03072ef}}

++++ Lösung | <code text>
/(^|\n)1$/$&/!              stopt bei 1
/(^|\n)(1+)\2$/$&\n$2/      halbiert die zeile
/(^|\n)(1+)$/$&\n$2$2$21/   verdreifacht die zeile +1
</code> ++++

==== 5 Römische Zahlen II =====

Schreibe einen Algorithmus der eine Dezimalzahl römisch darstellt. Bespiel:

  ; Eingabe
  : <code>42</code>
  ; Ausgabe
  : <code>XXXXII</code>

 {{gem/plain#0285cb446a1ded53}}

++++ Lösung | <code>
/IIIII/V/g
/VV/X/g
/XXXXX/L/g
/LL/C/g
/CCCCC/D/g
/DD/M/g
/^α(.*)β//!
/9α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1$1$1$1$1$1/
/8α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1$1$1$1$1/
/7α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1$1$1$1/
/6α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1$1$1/
/5α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1$1/
/4α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1/
/3α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1/
/2α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1/
/1α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1/
/0α(.*)β/α$1$1$1$1$1$1$1$1$1$1β/
/$/αIβ/</code>++++

==== 6 Römische Zahlen III =====

Schreibe einen Algorithmus der zwei römische Zahlen addiert.  Bespiel:

  ; Eingabe
  : <code>LIII + CLXIII</code>
  ; Ausgabe
  : <code>CCXVI</code>
  

 {{gem/plain#4e4967079acf84be}}

++++ Lösung | <code>
- Filtern
/[^MDCLXVI]//g
- Sortieren
/(I)([MDCLXV])/$2$1/g
/(V)([MDCLX])/$2$1/g
/(X)([MDCL])/$2$1/g
/(L)([MDC])/$2$1/g
/(C)([MD])/$2$1/g
/(D)(M)/$2$1/g
- Verdichten
/I{5}/V/
/V{2}/X/
/X{5}/L/
/L{2}/C/
/C{5}/D/
/D{2}/M/
</code>

Bemerkung: Der Algrithmus prüft nicht ob eine syntaktisch korrekte Addition vorliegt. Er addiert lediglich sämtliche vorhandene Zahlensymbole ''M'', ''D'', ''C'', ''L'', ''X'', ''V'' und ''I'' zu einer einzigen römischen Zahl.
++++

==== 7 Towers of Hanoi ======

{{http://upload.wikimedia.org/wikipedia/commons/0/07/Tower_of_Hanoi.jpeg?200}}
\\ cf. [[wpde>Türme von Hanoi]]

 
Wir haben Scheiben, der Markow-Algorithmus arbeitet aber mit Buchstaben. Um die Lage der Scheiben zu beschreiben, braucht es eine geeignete Codierung:

  * {{:markow:tvh1.png|}}
  * {{:markow:tvh2.png|}}
  * {{:markow:tvh3.png|}}

 {{gem/plain#05058d36af3ff8ff}}

=== Lösungen ====

++++ Lösung von Sandro Ackermann | <code text>
/α(.*)#([-]+)([bc].*)-\2(c|$)/$1-$2$3#$2$4/
/^(a.*)#([bc][#-]+)-(c|$)/α$1-$2#$3/
/^(a.*)-(b[#-]+-c)([#-]+)#/α$1#$2$3-/
/α(.*)-([-]+)([bc].*)#\2(c|$)/$1#$2$3-$2$4/
/α//!
</code>++++

++++ Lösung von Vincent Tscherter | <code text>
/ξ(\w.*)(\w.*)#(-+)(\w.*)-\3$/$1$2-$3$4#$3/
/ξ(\w.*)(\w.*)-(-+)(\w.*)#\3$/$1$2#$3$4-$3/
/^(\w.*)#(\w.*)-(\w.*)$/ξ$2#$3$1-/
/ξ//!
</code>

Regeln 0 oder 1 wechseln sich mit Regel 2 ab. Regel 2 dient dazu, die kleinste Scheibe eins weiterzugeben (mod 3). Regel 0 resp. Regel 1 führen geweils den einzigen legalen Zug, der die kleinste Scheibe nicht betrifft, aus. ++++

==== 8 Vokalen  und Konsonantentrenner ======

Erstelle einen Algorithmus, der die Buchstaben in einem Text nach Vokalen und Konsonanten auftrennt.

  ; Eingabe
  : <code>
guten morgen liebe sorgen
</code>
  ; Ausgabe
  : <code>
Vokale      : ueoeieeoe
Konsonanten : gtnmrgnlbsrgn
</code>

 {{gem/plain#630d637f08f44a9e}}

++++ Lösung| <code text>
/ //g
/([^aeiou])([aeiou])/$2$1/g
/([aeiou]+)([^aeiou])/Vokale      : $1\nKonsonanten : $2/ !</code> ++++

==== 9 Conway Folge  ======

  ; Problemstellung
  : Prüfe ob eine Zahl zur Conway-Folge ''1'', ''11'', ''21'', ''1211'', ''111221'', ''312211'', ''13112221'', ''1113213211'', ...  gehört (''✔'') oder nicht (''✘'').
  ; Beispiele
  : ''111221''→ ''111221 ✔''
  : ''111222''→ ''111222 ✘''
  ; Idee
  : Erstelle beginnend mit ''1'' solange das Folgeelement der Conway-Folge bis dieses der Eingabe entspricht. Falls dabei ein Folgeelement länger als die Eingabe wird kann die Berechnung abgebrochen werden. \\ Da die Länge von Zeichenketten in Markov-Algorithmen nicht direkt verglichen werden kann, wird diese mit dem Hilfssysmbol '':'' in unärer Schreibweise laufend ermittelt. ''1211'' → ''::::1211'' (entspricht der Textlänge 4)

 {{gem/plain#4a6f10fd886b308f}}

++++Antwortzugng| <code>/^1$/$& ✔/
/^\d+$/α1βγ$&/

/γ(\d)/:$1γ/
/(\d)(:+)/$2$1/g

/α(\d)\1\1/::3$1α/
/α(\d)\1/::2$1α/
/α(\d)/::1$1α/

/:+(\d+)αβ:+\1γ/$1 ✔/
/(:+):+.*β\1(\d+)γ/$2 ✘/
/:+(\d+)α/α$1/g</code>

==Erläuterungen ==
  ; A Initialisierung
  : Die erste Regeln prüften den Trivialfall ''1''. Ansonsten kommt die zweite Regel zum Zug welche den eigentlichen Algorithmus initialisiert: \\ ''**111221**'' -> ''//α//**1**//βγ//**111221**''
  ; B Eingabelänge
  : Über Regel 4 und 5 werden solange '':'' eingefügt und umplatziert bis die Länge der Eingabe unär feststeht. Dabei wandert ''γ'' ans Ende. \\ ''//α//**1**//βγ//**111221**'' -> ''//α//**1**//β//**::::::111221**//γ//''
  ; C Folgeelement
  : Es folgt über die Regeln 7 bis 9 die Bestimmung des Folgeelements und dessen unären Länge zwischen ''α'' und ''β''. Dabei wandert ''α'' zu ''β''. \\ ''//α//**1**//β//**::::::111221**//γ//'' -> ''::**11**//αβ//**::::::111221**//γ//''
  ; D Inhaltsvergleich
  : Über Regel 11 wird geprüft ob die beiden Elemente links von ''α'' und ''γ'' identisch sind und ein Element der Conwey-Folge konnte gefunden werden (STOP ✔): \\ ''::::::**111221**//αβ//::::::**111221**//γ//'' -> ''**111221** ✔'' 
  : Über Regel 12 prüft der Algorithmus ob das letzte berechnete Folgeelement bereits mehr Zeichen als die zu prüfende Eingabe hat (STOP ✘). \\ ''::::::::**13112221**//αβ//::::::**111222**//γ//'' -> ''**111222** ✘''
  : Über Regel 13 wird der nächste Iterationsschritt eingeleitet, so dass anschliessend das nächste Folgeelement berechnet werden kann (WEITER BEI C): \\ ''::::**1211**//αβ//::::::**111221**//γ//'' -> ''//α//**1211**//β//::::::**111221**//γ//''
  
++++