Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
efinf:blc2016:ruby:labyrinth [2016/09/25 20:48] Ivo Blöchliger [Instanzen] |
efinf:blc2016:ruby:labyrinth [2016/10/21 17:39] (current) Ivo Blöchliger |
||
---|---|---|---|
Line 1: | Line 1: | ||
{{backlinks> | {{backlinks> | ||
===== Labyrinth ===== | ===== Labyrinth ===== | ||
+ | * [[efinf: | ||
+ | ==== Aufgabenstellung ==== | ||
Programmieren Sie ein Ruby-Programm, | Programmieren Sie ein Ruby-Programm, | ||
<code txt> | <code txt> | ||
Line 18: | Line 20: | ||
+---+---+---+---+---+---+ | +---+---+---+---+---+---+ | ||
</ | </ | ||
- | 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 | + | 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 |
<code txt> | <code txt> | ||
+---+---+---+---+---+---+ | +---+---+---+---+---+---+ | ||
Line 38: | Line 40: | ||
- 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. | - 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 " | - Überlegen Sie sich dann, welche " | ||
- | - Programmieren Sie dann Ihre Hilfsfunktionen und testen Sie diese auf korrektes Funktionieren. | + | - Programmieren Sie dann Ihre Hilfsfunktionen |
- | - Programmieren Sie dann Ihren Lösungsalgorithmus | + | - Programmieren Sie dann Ihren Lösungsalgorithmus. |
==== Instanzen ==== | ==== Instanzen ==== | ||
Line 48: | Line 50: | ||
c = (0...(n*n)).to_a | c = (0...(n*n)).to_a | ||
f = Array.new(2){Array.new(n*n, | f = Array.new(2){Array.new(n*n, | ||
+ | todo = (Array.new(n*(n-1)) {|i| [0, | ||
o = [1,n] | o = [1,n] | ||
- | while c.max>0 | + | ec,tp = n*n-1,0 |
- | d = rand(2) | + | while ec>0 |
- | | + | d,p,tp = *(todo[tp]),tp+1 |
if c[p]!=c[p+o[d]] | if c[p]!=c[p+o[d]] | ||
f[d][p]=1 | f[d][p]=1 | ||
a = [c[p], | a = [c[p], | ||
c.map!{|e| e==a[1] ? a[0] : e} | c.map!{|e| e==a[1] ? a[0] : e} | ||
+ | ec-=1 | ||
end | end | ||
end | end | ||
Line 72: | Line 76: | ||
Damit wird ein Labyrinth der Grösse 10x10 mit dem Seed 394 generiert. | Damit wird ein Labyrinth der Grösse 10x10 mit dem Seed 394 generiert. | ||
- | === Test-Instanzen === | + | === Test-Instanzen |
<code text instances.txt> | <code text instances.txt> | ||
5 1 | 5 1 | ||
- | 5 2 | + | 5 107 |
- | 5 3 | + | 5 266 |
- | 6 1 | + | 6 6 |
- | 6 485 | + | 6 54 |
- | 6 1152 | + | 6 2432 |
- | 7 1 | + | 7 0 |
7 112 | 7 112 | ||
- | 7 554 | + | 7 819 |
- | 8 1 | + | 8 6 |
- | 8 9 | + | 8 2 |
- | 8 515 | + | 8 801 |
- | 9 13 | + | 9 4 |
- | 9 66 | + | 9 67 |
+ | 9 535 | ||
10 0 | 10 0 | ||
- | 10 4 | + | 10 275 |
- | 10 394 | + | 10 447 |
- | 11 136 | + | 15 23 |
- | 11 1 | + | 15 845 |
- | 11 483 | + | 15 2060 |
- | 12 17 | + | 20 83 |
- | 12 250 | + | 20 131 |
- | 12 467 | + | 20 1306 |
- | 13 44 | + | 30 7074 |
- | 13 170 | + | 30 80 |
- | 14 46 | + | 30 258 |
- | 14 122 | + | |
- | 14 442 | + | |
- | 15 115 | + | |
- | 15 341 | + | |
- | 16 222 | + | |
- | 16 3522 | + | |
- | 20 33 | + | |
- | 20 58 | + | |
- | 20 504 | + | |
</ | </ | ||
- | Generieren aller Instanzen | + | === Generieren aller Instanzen |
+ | Mit Hilfe des untenstehenden Ruby-Programms, | ||
<code bash> | <code bash> | ||
ruby generator.rb < instances.txt | ruby generator.rb < instances.txt | ||
Line 117: | Line 114: | ||
<code ruby generator.rb> | <code ruby generator.rb> | ||
while l=gets | while l=gets | ||
- | cmd = "ruby labgen.rb #{l.chomp} > lab-#{l.chomp.gsub(/ | + | |
+ | | ||
puts cmd | puts cmd | ||
`#{cmd}` | `#{cmd}` | ||
end | end | ||
</ | </ | ||
+ | |||
+ | === 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 | ||
+ | </ | ||
+ | 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 | ||
+ | </ | ||
+ | liefert: | ||
+ | <code text md5sums.txt> | ||
+ | 49c7657bfe8761c500d64da6aef9629d | ||
+ | 7a428a06291dc483540b1b8df3611196 | ||
+ | 81befe6e57446e91f7843dd4e9c7daed | ||
+ | e34dfb8c4475ebe498012e82e9cb2fc8 | ||
+ | fd5e5eeb2d925c975f77dc5f6cdf3f9e | ||
+ | b95a2a8105868cb3c7ae8ae8eaf57c88 | ||
+ | fbe21f8638c9464e0ccffdba5b629ed1 | ||
+ | f933e2a752cc4258521ceff75b1c3595 | ||
+ | 4345500ad8888b4c944acd37a414f57e | ||
+ | bbb7046a19697fc4aba892ff336e8457 | ||
+ | a25f29d82fcce1cd8b512f0d7c7d4b38 | ||
+ | e6bb18eaa21b7810da70f42b2616b105 | ||
+ | 9705d2dca3e6df15f9d2540b3e73bd44 | ||
+ | cee3c78b6fc9c9f749d3ca9858ea3bf8 | ||
+ | f818ab0d4189da824b942d9daa8f8980 | ||
+ | 14e552e98eb85da3a6c99107c542992a | ||
+ | 58d85d3d27988f153c4d448a2849e7c4 | ||
+ | b09e6fa42f5e7f2a0a08e9f9d5b11cef | ||
+ | 1833edb9bb81d2cad6859809186e16a3 | ||
+ | 88bc9d1b03df36dd52bbc161379dd020 | ||
+ | 79d6eefdae4f65a75a3b0a9cb2cb4654 | ||
+ | a3b3020050f0c695bb803c6a54629a6a | ||
+ | 9f9792a25a7655428f8751ac699d1016 | ||
+ | 71ceb615f5647d468cff17f970dc4c5a | ||
+ | e55c391b926d43a60df1b4b736a3674e | ||
+ | 40d83072656c633ae468f1d5cd428bba | ||
+ | 3ed6049c2c245bc0344e0728a77727a0 | ||
+ | </ | ||
+ | |||
+ | ==== Hilfestellungen ==== | ||
+ | Einlesen der Grösse und des Labyrinths. Markieren einer Position x,y, testen, ob dabei nach rechts gegangen werden kann. Starten mit | ||
+ | < | ||
+ | ruby labsolve.rb < lab.txt | ||
+ | </ | ||
+ | oder | ||
+ | < | ||
+ | ruby labgen.rb 7 123 | ruby labsolve.rb | ||
+ | </ | ||
+ | |||
+ | <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 " | ||
+ | end | ||
+ | </ | ||
+ |