{{backlinks>.}}
===== Labyrinth =====
  * [[efinf:blc2016:students:labyrinth|Pseudocodes und Lösungen der Schülerinnen und Schüler]]
==== Aufgabenstellung ====
Programmieren Sie ein Ruby-Programm, das ein Labyrinth von folgendem Format vom STDIN einliest:
<code txt>
6
+---+---+---+---+---+---+
|   |           |       |
+   +   +   +   +---+   +
|   |   |   |           |
+   +   +---+---+---+   +
|   |       |       |   |
+   +   +---+   +   +   +
|               |   |   |
+   +---+   +---+---+   +
|   |               |   |
+---+   +   +---+---+   +
|       |           |   |
+---+---+---+---+---+---+
</code>
Die erste Zeile enthält die Grösse vom (quadratischen) Labyrinth. Danach folgt das Labyrinth als ASCII-Grafik. Das Labyrinth ist so aufgebaut, dass es zwischen zwei Punkten immer **genau einen Weg** gibt. Gesucht der (eindeutige) Weg von oben links nach unten rechts. Die Ausgabe des Programms soll das Labyrinth mit gekennzeichnetem Weg wieder ausgeben:
<code txt>
+---+---+---+---+---+---+
| v | >   >   v |       |
+   +   +   +   +---+   +
| v | ^ |   | >   >   v |
+   +   +---+---+---+   +
| v | ^     |       | v |
+   +   +---+   +   +   +
| >   ^         |   | v |
+   +---+   +---+---+   +
|   |               | v |
+---+   +   +---+---+   +
|       |           | X |
+---+---+---+---+---+---+
</code>

==== Vorgehen ====
  - Formulieren Sie zuerst einen Lösungssalgorithmus auf Papier. Dieser soll aber noch nicht auf technische Details eingehen, wie z.B. der String analysiert wird etc. Dieser Algorithmus soll z.B. einer Person erlauben, diesen Weg systematisch zu finden.
  - Überlegen Sie sich dann, welche "Datenzugriffe" Sie in Ihrem Algorithmus häufig machen. Überlegen Sie sich dann, wie Sie diese Zugriffe direkt auf dem String machen können, der das Labyrinth darstellt. 
  - Programmieren Sie dann Ihre Hilfsfunktionen für die Datenzugriffe und testen Sie diese auf korrektes Funktionieren.
  - Programmieren Sie dann Ihren Lösungsalgorithmus.

==== Instanzen ====
Die Instanzen werden von folgendem Rubyprogramm generiert. Hinweis: Das Programm ist absichtlich kurz und damit unleserlich gehalten. Die Funktionsweise des Programms wird später erläutert.  
<code ruby labgen.rb>
n = ARGV[0].to_i
srand ARGV[1].to_i
c = (0...(n*n)).to_a
f = Array.new(2){Array.new(n*n, 0)}
todo = (Array.new(n*(n-1)) {|i| [0,i+i/(n-1)]}+Array.new(n*(n-1)) {|i| [1,i]}).shuffle
o = [1,n]
ec,tp = n*n-1,0
while ec>0
  d,p,tp = *(todo[tp]),tp+1
  if c[p]!=c[p+o[d]]
    f[d][p]=1
    a = [c[p],c[p+o[d]]].sort
    c.map!{|e| e==a[1] ? a[0] : e}
    ec-=1
  end
end
puts n
puts "+---"*n+"+"
n.times{|i|
  puts "|   "+f[0][(i*n)...(i*n+n-1)].map{|e| "| "[e]+"   "}.join+"|"
  puts "+" +f[1][(i*n)...(i*n+n)].map{|e| ["---+","   +"][e]}.join if i<n-1
}
puts "+---"*n+"+"
</code>
Das Programm wird mit zwei Argumenten gestartet: Grösse des Labyrinths und die Initialisierung des Zufallsgenerators:
<code bash>
ruby labgen.rb 10 394
</code>
Damit wird ein Labyrinth der Grösse 10x10 mit dem Seed 394 generiert.

=== Test-Instanzen (Grössen und Seeds) ===
<code text instances.txt>
5 1
5 107
5 266
6 6
6 54
6 2432
7 0
7 112
7 819
8 6
8 2
8 801
9 4
9 67
9 535
10 0
10 275
10 447
15 23
15 845
15 2060
20 83
20 131
20 1306
30 7074
30 80
30 258
</code>

=== Generieren aller Instanzen ===
Mit Hilfe des untenstehenden Ruby-Programms, direkt auf der Kommandozeile:
<code bash>
ruby generator.rb < instances.txt
</code>
<code ruby generator.rb>
while l=gets
  l = l.chomp.split(" ").map{|e| e.to_i}
  cmd = "ruby labgen.rb #{l[0]} #{l[1]} > lab-#{"%02d" % l[0]}-#{"%05d" % l[1]}.txt"
  puts cmd
  `#{cmd}`
end
</code>

=== Lösen aller Instanzen ===
Annahme: Ihr Lösungsprogramm heisst labsolv.rb. Dann direkt auf der Kommandozeile:
<code bash>
for a in lab-*txt
do 
  echo $a
  ruby labsolv.rb < $a > solution-$a
done
</code>
Alternativ dazu könnte auch das generator.rb Ruby-Programm erweitert werden, so dass die Lösungen gleich miterstellt werden.

=== Überprüfen der Lösungen ===
Die Lösungen können mittels MD5-Hash überprüft werden (**ACHTUNG!** Diese Hashfunktion nie für sicherheitsrelevante Zwecke einsetzen!)
<code bash>
md5sum solution-lab*.txt
</code>
liefert:
<code text md5sums.txt>
49c7657bfe8761c500d64da6aef9629d  solution-lab-05-00001.txt
7a428a06291dc483540b1b8df3611196  solution-lab-05-00107.txt
81befe6e57446e91f7843dd4e9c7daed  solution-lab-05-00266.txt
e34dfb8c4475ebe498012e82e9cb2fc8  solution-lab-06-00006.txt
fd5e5eeb2d925c975f77dc5f6cdf3f9e  solution-lab-06-00054.txt
b95a2a8105868cb3c7ae8ae8eaf57c88  solution-lab-06-02432.txt
fbe21f8638c9464e0ccffdba5b629ed1  solution-lab-07-00000.txt
f933e2a752cc4258521ceff75b1c3595  solution-lab-07-00112.txt
4345500ad8888b4c944acd37a414f57e  solution-lab-07-00819.txt
bbb7046a19697fc4aba892ff336e8457  solution-lab-08-00002.txt
a25f29d82fcce1cd8b512f0d7c7d4b38  solution-lab-08-00006.txt
e6bb18eaa21b7810da70f42b2616b105  solution-lab-08-00801.txt
9705d2dca3e6df15f9d2540b3e73bd44  solution-lab-09-00004.txt
cee3c78b6fc9c9f749d3ca9858ea3bf8  solution-lab-09-00067.txt
f818ab0d4189da824b942d9daa8f8980  solution-lab-09-00535.txt
14e552e98eb85da3a6c99107c542992a  solution-lab-10-00000.txt
58d85d3d27988f153c4d448a2849e7c4  solution-lab-10-00275.txt
b09e6fa42f5e7f2a0a08e9f9d5b11cef  solution-lab-10-00447.txt
1833edb9bb81d2cad6859809186e16a3  solution-lab-15-00023.txt
88bc9d1b03df36dd52bbc161379dd020  solution-lab-15-00845.txt
79d6eefdae4f65a75a3b0a9cb2cb4654  solution-lab-15-02060.txt
a3b3020050f0c695bb803c6a54629a6a  solution-lab-20-00083.txt
9f9792a25a7655428f8751ac699d1016  solution-lab-20-00131.txt
71ceb615f5647d468cff17f970dc4c5a  solution-lab-20-01306.txt
e55c391b926d43a60df1b4b736a3674e  solution-lab-30-00080.txt
40d83072656c633ae468f1d5cd428bba  solution-lab-30-00258.txt
3ed6049c2c245bc0344e0728a77727a0  solution-lab-30-07074.txt
</code>

==== Hilfestellungen ====
Einlesen der Grösse und des Labyrinths. Markieren einer Position x,y, testen, ob dabei nach rechts gegangen werden kann. Starten mit
<code>
   ruby labsolve.rb < lab.txt
</code>
oder
<code>
   ruby labgen.rb 7 123 | ruby labsolve.rb
</code>

<code ruby labsolve.rb>
n = gets.to_i
lines = STDIN.readlines
x = 2
y = 4
lines[y*2+1][x*4+2] = "#"
puts lines

if lines[y*2+1][x*4+4]==" "
    puts "Ich kann nach rechts"
else
    puts "Rechts ist zu!"
end
</code>