This is an old revision of the document!
Labyrinth
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 | +---+---+---+---+---+---+
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 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.
- 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.
Test-Instanzen
- 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 mit
ruby generator.rb < instances.txt
- generator.rb
while l=gets cmd = "ruby labgen.rb #{l.chomp} > lab-#{l.chomp.gsub(/ /,"-"}.txt" puts cmd `#cmd` end