efinf:blc2016:ruby:labyrinth

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
efinf:blc2016:ruby:labyrinth [2016/09/25 18:45] – [Instanzen] Ivo Blöchligerefinf:blc2016:ruby:labyrinth [2016/10/21 15:39] (current) – Ivo Blöchliger
Line 1: Line 1:
 +{{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>