Font
Wiki:Tipp zum Debugging: use Data::Dumper; local $Data::Dumper::Useqq = 1; print Dumper \@var;
[thread]6495[/thread]

RDW #6 - Rätsel der Woche 6

Tags: Similar Threads

Readers: 2


<< |< 1 2 3 >| >> 22 entries, 3 pages
Crian
 2004-08-13 15:11
#49254 #49254
User since
2003-08-04
5826 articles
ModeratorIn
[Homepage]
user image
Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 RDW #6 - Raetsel der Woche Nummer 6
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Regeln:  * Bitte nicht vor Ablauf der ersten 72 Stunden ( = drei Tage ) nach
~~~~~~~    Veroeffentlichung Hinweise (Spoiler) oder Loesungen veroeffent-
           lichen!

         * Wenn diese Zeit abgelaufen ist, werde ich einen Thread mit passen-
           dem Titel erstellen, in dem die Loesungen gepostet werden und dis-
           kutiert werden koennen.

         * Die Loesungen sollten nicht nur gepostet, sondern auch an mich ge-
           mailt werden, damit ich sie testen, "bewerten"  und zusammenfassen
           kann. Die Adrese dafuer lautet:

           crian <---AT---> perl <---MINUS---> community <---DOT---> de

           Im Betreff sollte 'RDW' und die Nummer des Raetsels stehen. Hilf-
           reich waere neben dem Quellcode der Username im Forum sowie Perl-
           und OS-Version, falls Du diese kennst.

         * Verstaendnisfragen duerfen in diesem Thread gestellt werden, aber
           Tipps und (Teil-) Loesungen sind hier unerwuenscht.

         * Ich werde die eingeschickten Programme im Netz zur Verfuegung
           stellen, so dass gerade lange Quellcodes nicht (komplett)
           gepostet werden muessen.

         * Zur Verwendung von Modulen: Ich moechte diese nicht generell aus-
           schliessen, aber wenn quasi die komplette Aufgabe durch die Ver-
           wendung eines Moduls ersetzt werden kann, ist dies vielleicht nicht
           der Sinn der Aufgabe gewesen.



Aufgabe: Ausgehend von der Loesung zu Raetsel RDW #4 (welches die folgende
~~~~~~~~ Aufgabenstellung hatte:

                                   -----

         Gegeben sei ein rechteckiges Spielfeld F mit n x m Feldern.
         
         Desweiteren gibt es eine Menge S mit Steinen auf diesem Spielfeld.
         Jeder dieser Steine ist rechteckig und belegt p x q Felder (die
         Steine koennen verschieden gross sein).

         Die Steine duerfen sich auf dem Feld nicht ueberlappen. (Das heisst
         jedes Feld von F darf von hoechstens einem Stein aus S belegt sein.)

         Schaffe eine interne Darstellung von F und S und Funktionen (oder
         Methoden), um den Stein S_i in eine der vier Himmelsrichtungen auf
         dem Spielfeld zu verschieben.

         Ist es nicht moeglich, den gegebenen Stein in die gegebene Richtung
         zu verschieben, so soll dies dem Aufrufer auf irgend eine Weise mit-
         geteilt werden.

                                   -----

         ) soll eine Moeglichkeit geschaffen werden, zu gegebenen Ausgangs-
         stellungen und Zielvorgaben Loesungen zu finden. Dabei sollte nach
         Moeglichkeit eine Loesung mit der kleinsten Anzahl an Zuegen gefun-
         den werden.

         Beispiel:

            +---+---+---+        Der Stein "1" soll aus dem Feld unten
          2 | 1 | 0 | 2 |        rechts aus dem Spielfeld herausgescho-
            +---+---+---+        ben werden, d.h., dass er auf dem Feld
          1 | 0 | 3 | 0 |        unten rechts landen soll.
            +---+---+---+        Eine minimale Loesung ist:
          0 | 4 | 0 | 0 | ->         3-l, 1-r, 1-u, 1-u, 1-r
            +---+---+---+        Dann steht der Stein vor dem Ausgang
              0   1   2          und kann herausgezogen werden.
       
        Die Zielvorgaben werden in Form von Koordinaten für einen bestimmten
        Stein (im Beispiel Stein 1) angeben, hier etwa
            (0,2) == 1
        (Stein 1 auf Zeile Null, Spalte Zwei)

        Ev. laesst sich diese Zielvorgabe elegant als Funktionsreferenz mit-
        geben, aber da kann sich jeder selbst etwas ausdenken.


        Wenn das Programm die Loesung gefunden hat, sollte es sie in der oben
        angegebenen Form (d.h. jeder Zug besteht aus X-Y, wobei X die
        Steinnummer angibt und Y die Richtung, in der dieser Stein einen
        Schritt weit bewegt wird, mit Y ist Element der Menge {r, l, o, u})
        ausgeben und optional auch Schritt fuer Schritt darstellen.


        Bei den bisherigen Betrachtungen wurde davon ausgegangen, dass sich
        jeder Stein prinzipiell in alle vier Himmelsrichtungen bewegen
        laesst. Eine Variante des Spiels waere es, wenn nichtquadratische
        Steine nur in Richtung ihrer laengsten Ausdehnung verschoben werden
        duerfen. (Es gibt solche Spielvarianten, da gilt es, ein bestimmtes
        Auto aus einem Gewirr anderer Autos zu befreien, dafuer waere diese
        Variante notwendig.)

        Die Unterstuetzung dieser Spielvariante sehe ich als optional an.
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
Crian
 2004-08-13 15:15
#49255 #49255
User since
2003-08-04
5826 articles
ModeratorIn
[Homepage]
user image
Anmerkung: Wer bei RDW04 nicht teilgenommen hat und jetzt gern mitmachen möchte, kann natürlich gern eine der dort vorgestellten Lösungen als Basis verwenden.


Folgende Aufgabendateien sollten eingelesen werden können:

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#
# Test 1
#

columns = 5
rows = 3

stone 1 = (0, 0), (0, 1)
stone 2 = (1, 0), (1, 1)
stone 3 = (1, 2), (0, 2)
stone 4 = (2, 2), (2, 1)

goal = 1, (2, 3), (2, 4)

# Koordinaten beginnen links unten mit 0,0
# Die erste Koordinate ist die Zeile, die
# zweite die Spalte.


Ergebnis:

Code: (dl )
1
2
3
4
5
6
7
+---+---+---+---+---+
| 0 | 4 | 4 | 0 | 0 | ->
+---+---+---+---+---+
| 2 | 2 | 3 | 0 | 0 |
+---+---+---+---+---+
| 1 | 1 | 3 | 0 | 0 |
+---+---+---+---+---+
\n\n

<!--EDIT|Crian|1092447291-->
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
Crian
 2004-08-14 05:50
#49256 #49256
User since
2003-08-04
5826 articles
ModeratorIn
[Homepage]
user image
So ... meine Lösung ist (bis auf die optionale Spielvariante) fertig. Hier sind zwei Aufgabendateien zum Testen:

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#
# Test 1
#

columns = 5
rows = 3

stone 1 = (0, 0), (0, 1)
stone 2 = (1, 0), (1, 1)
stone 3 = (1, 2), (0, 2)
stone 4 = (2, 2), (2, 1)

goal = 1, (2, 3), (2, 4)

# Koordinaten beginnen links unten mit 0,0
# Die erste Koordinate ist die Zeile, die
# zweite die Spalte.
#
# +---+---+---+---+---+
# 2 | 4 | 4 | 0 | 0 | 0 | ->
# +---+---+---+---+---+
# 1 | 2 | 2 | 3 | 0 | 0 |
# +---+---+---+---+---+
# 0 | 1 | 1 | 3 | 0 | 0 |
# +---+---+---+---+---+
# 0 1 2 3 4
#
# Eine minimale Loesung ist 4-l, 3-u, 1-r, 1-r, 1-r, 1-u, 1-u


und

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#
# Test 1
#

columns = 3
rows = 3

stone 1 = (2, 0)
stone 2 = (2, 2)
stone 3 = (1, 1)
stone 4 = (0, 0)

goal = 1, (0, 2)

# Koordinaten beginnen links unten mit 0,0
# Die erste Koordinate ist die Zeile, die
# zweite die Spalte.
#
# +---+---+---+ Der Stein "1" soll aus dem Feld unten
# 2 | 1 | 0 | 2 | rechts aus dem Spielfeld herausgescho-
# +---+---+---+ ben werden, d.h., dass er auf dem Feld
# 1 | 0 | 3 | 0 | unten rechts landen soll.
# +---+---+---+ Eine minimale Loesung ist:
# 0 | 4 | 0 | 0 | -> 3-l, 1-r, 1-u, 1-u, 1-r
# +---+---+---+ Dann steht der Stein vor dem Ausgang
# 0 1 2 und kann herausgezogen werden.


Weitere werden eventuell folgen. Ich werde diese Dateien auch gleich schonmal auf den Server hochladen und im Wiki verlinken, siehe http://wiki.perl-community.de/bin/view/Wissensbasis/RaetseL20040813

Edit: done, zu finden hier:

http://www.perl-community.de/rdw/rdw06/f1.field
http://www.perl-community.de/rdw/rdw06/f2.field\n\n

<!--EDIT|Crian|1092448496-->
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
Crian
 2004-08-14 17:44
#49257 #49257
User since
2003-08-04
5826 articles
ModeratorIn
[Homepage]
user image
So, meine Lösung kann jetzt auch mit der Variante umgehen. Beispieldatei hierzu:

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#
# Test 1
#

columns = 5
rows = 5

stone 1 = (2, 0), (2, 1)
stone 2 = (2, 2), (3, 2)
stone 3 = (4, 1), (4, 2)
stone 4 = (0, 2), (1, 2)
stone 5 = (3, 3), (4, 3)
stone 6 = (1, 3), (2, 3)
stone 7 = (0, 3), (0, 4)

goal = 1, (2, 3), (2, 4)

type = car

# Koordinaten beginnen links unten mit 0,0
# Die erste Koordinate ist die Zeile, die
# zweite die Spalte.
#
# +---+---+---+---+---+
# 4 | 0 | 3 | 3 | 5 | 0 |
# +---+---+---+---+---+
# 3 | 0 | 0 | 2 | 5 | 0 |
# +---+---+---+---+---+
# 2 | 1 | 1 | 2 | 6 | 0 | ->
# +---+---+---+---+---+
# 1 | 0 | 0 | 4 | 6 | 0 |
# +---+---+---+---+---+
# 0 | 0 | 0 | 4 | 7 | 7 |
# +---+---+---+---+---+
# 0 1 2 3 4
#
# Eine minimale Loesung ist
# 3-l, 2-u, 4-u, 7-l, 7-l, 7-l, 4-d, 6-d, 1-r, 1-r, 1-r


Zu finden hier:
http://www.perl-community.de/rdw/rdw06/f3.field

Wie man sieht, habe ich die Zeile type = car hinzugefuegt, um diese Variante zu spezifizieren. Fehlt die type Information oder ist sie auf 'standard' gesetzt, so wird das normale Verhalten spezifiziert.

Mein Programm findet dazu die Lösung 3-l, 2-u, 4-u, 7-l, 7-l, 6-d, 7-l, 4-d, 1-r, 1-r, 1-r (also auch 11 Schritte).

Im Moment habe ich eine Ausgabeklasse, die das Ergebnis auf der Konsole anzeigt. Ich hab aber auch schon Rümpfe für eine Tk-Präsentation des Ergebnisses. Wenn ich noch genug Lust habe, programmiere ich die noch bis Montag, sonst liefer ich das mal später nach.


Ich hoffe es trügt der Eindruck, dass dieses Rätsel ausser mir niemanden interessiert?!
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
esskar
 2004-08-14 18:07
#49258 #49258
User since
2003-08-04
7321 articles
ModeratorIn

user image
[quote=Crian,14.08.2004, 15:44]Ich hoffe es trügt der Eindruck, dass dieses Rätsel ausser mir niemanden interessiert?![/quote]
naja, ich muss zugegeben, dass es teilweise schon aufwenig ist. dazu kommt, dass ich momentan etwas faul und urlaubsreif bin!
Crian
 2004-08-14 18:11
#49259 #49259
User since
2003-08-04
5826 articles
ModeratorIn
[Homepage]
user image
Kein Problem, ich hab auch gemerkt, dass es nicht wirklich eine Aufgabe für Anfänger ist ;)

Ich werd zusehen, dass es beim nächsten Mal wieder etwas überschaubarer und ev. Golfbar wird, da ist die Resonanz doch irgendwie größer.

Aber vielleicht reicht der Rest-Elan, Dir Montag die (oder das?) Ergebnis(se) anzusehen =)
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
[E|B]
 2004-08-14 18:16
#49260 #49260
User since
2003-08-08
2561 articles
HausmeisterIn
[Homepage] [default_avatar]
Ich wäre nochmal für RDW #7 für was mathematisches.
Die Permutationen waren z.B. cool. :)
Gruß, Erik!

s))91\&\/\^z->sub{}\(\@new\)=>69\&\/\^z->sub{}\(\@new\)=>124\&\/\^z->sub{}\(\@new\)=>);
$_.=qq~66\&\/\^z->sub{}\(\@new\)=>93~;for(@_=split(/\&\/\^z->sub{}\(\@new\)=>/)){print chr;}

It's not a bug, it's a feature! - [CGI-World.de]
Crian
 2004-08-16 21:58
#49261 #49261
User since
2003-08-04
5826 articles
ModeratorIn
[Homepage]
user image
Ich habe leider keine Lösungen erhalten, das Thema war wohl dann für eine Wochenendaufgabe doch zu komplex. Vielleicht interessiert den einen oder anderen aber trotzdem meine Lösung, ich stelle ein Zwischenergebnis mit rudimentärer Tk-Oberfläche (per Option --gui) oder Textausgabe (im defaultfall) auf den Server. Geplant ist eine schönere Ausgabe und eine Scrollmöglichkeit durch die Schritte der Lösung und vielleicht noch das ein oder andere Goodie.

Eigentlich wollte ich irgendwann nochmal als weiteren Aufgabenteil eine Eingabemöglichkeit für menschliche Spieler stellen, aber das lasse ich dann besser. Falls ich das mal für mich schreibe, kann ich es ja in diesem Thread kundtun.

Es sei denn, es kommen jetzt laute Protestschreie ;)

Lösung ist etwas lang um sie hier zu posten, auf dem Wiki ist sie aber zu sehen und hier herunterladbar:

http://www.perl-community.de/rdw/rdw06/rdw06_crian.pl



Interessant ist, dass schon diese wirklich übersichtliche Aufgabe:

http://www.perl-community.de/rdw/rdw06/rdw06_crian...
(roter Stein nach links oben)

auch auf meinem recht neuen Rechner deutlich länger braucht, als man als Mensch für die Lösung überlegen muss.\n\n

<!--EDIT|Crian|1092679955-->
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
Ronnie
 2004-08-16 22:15
#49262 #49262
User since
2003-08-14
2022 articles
BenutzerIn
[default_avatar]
Sorry Crian, Ich finde es durchaus sehr interessant. Leider bekomme ich zur Zeit nur wenig auf die Reihe, deshalb habe ich die letzten RDWs ausgesetzt. Und das obwohl ich von einem eigenen Tetris träume *g*. Aber im Moment wächst mir alles über den Kopf, ich bekomme meinem Job im Moment nicht gebacken (weil ich organisatorisch 'ne Niete bin und meine Aufgaben zur Zeit zu wenig technisch und zuviel administrativ sind), vom Rest will ich gar nicht sprechen. Du machst mit den RDWs einen Superjob, lass dich durch kurzzeitige Flauten nicht aus dem Konzept bringen.

Gruß,
Ronnie
renee
 2004-08-17 01:13
#49263 #49263
User since
2003-08-04
14367 articles
ModeratorIn
[Homepage] [default_avatar]
*ronnie_zustimm*
OTRS-Erweiterungen (http://feature-addons.de/)
Frankfurt Perlmongers (http://frankfurt.pm/)
--

Unterlagen OTRS-Workshop 2012: http://otrs.perl-services.de/workshop.html
Perl-Entwicklung: http://perl-services.de/
<< |< 1 2 3 >| >> 22 entries, 3 pages



View all threads created 2004-08-13 15:11.