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

+---+---+---+---+---+---+
| 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)}
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+"+"

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 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 3833
30 80
30 258

Generieren aller Instanzen mit

ruby generator.rb < instances.txt

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