Programmieren Sie ein Ruby-Programm, das ein Labyrinth von folgendem Format vom STDIN einliest:

6
+---+---+---+---+---+---+
|   |           |       |
+   +   +   +   +---+   +
|   |   |   |           |
+   +   +---+---+---+   +
|   |       |       |   |
+   +   +---+   +   +   +
|               |   |   |
+   +---+   +---+---+   +
|   |               |   |
+---+   +   +---+---+   +
|       |           |   |
+---+---+---+---+---+---+

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 Punkte 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:

+---+---+---+---+---+---+
| v | >   >   v |       |
+   +   +   +   +---+   +
| v | ^ |   | >   >   v |
+   +   +---+---+---+   +
| v | ^     |       | v |
+   +   +---+   +   +   +
| >   ^         |   | v |
+   +---+   +---+---+   +
|   |               | v |
+---+   +   +---+---+   +
|       |           | X |
+---+---+---+---+---+---+

1. 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.
2. Ü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.
3. Programmieren Sie dann Ihre Hilfsfunktionen und testen Sie diese auf korrektes Funktionieren.
4. Programmieren Sie dann Ihren Lösungsalgorithmus

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.

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)}
o = [1,n]
while c.max>0
  d = rand(2)
  p = rand(n-d)*n+rand(n-1+d)
  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}
  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+"+"

Das Programm wird mit zwei Argumenten gestartet: Grösse des Labyrinths und die Initialisierung des Zufallsgenerators:

ruby labgen.rb 10 394

Damit wird ein Labyrinth der Grösse 10×10 mit dem Seed 394 generiert.

instances.txt

5 1
5 2
5 3
6 1
6 485
6 1152
7 1
7 112
7 554
8 1
8 9
8 515
9 13
9 66
10 0
10 4
10 394
11 136
11 1
11 483
12 17
12 250
12 467
13 44
13 170
14 46
14 122
14 442
15 115
15 341
16 222
16 3522
20 33
20 58
20 504

Generieren aller Instanzen:

generator.rb

while l=gets
  cmd = "ruby labgen.rb #{l.chomp} > lab-#{l.chomp.gsub(/ /,"-"}.txt"
  puts cmd
  `#cmd`
end