[HaBo]

CDW

Anzeige

Es gibt sogenannte "perfekte" Labyrinthe - sie besitzen von einem beliebigen Punkt zum anderen genau einen Weg, es gibt also keine Schleifen oder unerreichbaren Stellen:

1.Euer Programm soll rechteckige, perfekte Labyrinthe beliebiger Größe erzeugen (möglichst zufällige und nicht nur "Schneckenlabyrinthe" ;) )


2. Damit es nicht so langweilig wird ;) , sollte das Programm sich noch 2 Punkte nehmen (zufällig oder vom Benutzer angeben lassen) und einen Lösungsweg dazwischen finden




3.Ein Output (Konsole oder grafisch) wäre zur Kontrolle ganz gut.

Lasst euch nicht abschrecken - so groß ist die Aufgabe nicht (ca. 300 Zeilen C, wobei bei mir noch Speichern/Laden in einem bestimmten Format und paar Aspekte mehr implementiert wurden).

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.

lagalopex

Ich würde folgende Darstellung bevorzugen, da sie imo besser zu lesen ist (zwei Zeichen für eine Breite, damit es in diesem Fall 10x10 auch in etwa quadratisch ist):

Außerdem würde mich das Format, in dem du die Daten speicherst interessieren, da große Labyrithe so bei 500x500 nicht gerade leicht zu überprüfen sind, und wohl kaum irgendjemand sowas ließt^^ und man dann so ein einheitliches Format hat...

CDW

Also Darstellung war nur ein Beispiel - mir war nichts besseres eingefallen und ich fand die Darstellung jeder einzelnen Zelle am einfachsten (und in der Console bzw. bei einem entsprechenden Font sieht das auch imho besser aus ). Außerdem kann man auch eine grafische Ausgabe machen - mit Bildchen oder gezeichneten Linien

hm, ich habe mir gedacht, dass es doch recht sprach und implementierungsspezifisch wäre.

Ich hatte die Vorgabe (ja, es war eine Übungsaufgabe ), die einzelnen Wände jeder Zelle mit jeweils einem gesetzten Bit zu kodieren, so dass ensprechend die Zellen verschiedene Werte hatten: 0 bis 15 (Binär eben 0001 bis 1111). Zusätzlich musste das Programm ein Labyrinth in "lesbarer" Form speichern: 1. Zeile wurde die Größe gespeichert:
3,3
weitere Zeilen war jeweils eine "Zeile" aus dem Labyrinth - die Zellen in Dezimaldarstellung.
Also z.B
3,3
11,9,3
10,10,10
12,6,14

Das wollte ich keinem antun .

Obwohl Textformat bei den ganzen genutzten Sprachen wohl am kompatibelsten wäre.



Wie wäre es damit:
Format: ASCII (Java &Co User können auch bei Unicode bleiben, nur dann kurz hinschreiben - die anschließende ASCII Konvertierung sollte jeder vernünftige Texteditor schaffen).

Darstellung einer einzelnen Zelle:
Dezimale Zahl.

Codierung:
(hab gerade etwas gegoogelt: die "gängigeren" Sprachen, die mir eingefallen sind, unterstützen bitweise Operatoren - c#/java/perl/PHP/pascal/c usw. - also gibt es keine Ausreden, sich nicht damit zu beschäftigen )
Für jede existierende Wand gibt es ein gesetztes Bit.
Wand oben gesetzt: 0001b
Wand rechts gesetzt: 0010b
Wand unten gesetzt: 0100b
Wand links gesetzt: 1000b

Damit repräsentiert z.B die Zahl 15 eine Zelle, dessen Wände noch alle "ganz" sind,
1 ist eine Zelle, die eine obere Wand hat, 3 ist eine Zelle, dessen obere und rechte Wand gesetzt sind usw. Wenn ich gerade keinen Denkfehler hab, sollte es auch OS/Plattformunabhängig sein.

Gesamtformat:

erste Zeile: eine Größenangabe (Dezimal, getrennt durch Komma)
folgende: jeweils eine Zeile aus dem Labyrinth, repräsentiert durch eine Zahl, getrennt durch Kommata. Beispiel (so sieht das Labfile in einem Texteditor aus)

3,3
11,9,3
10,10,10
12,6,14

was als Labyrinth so ausschaut:
Wie man eine Dezimalzahl erstellt bzw. aus der Zahl informationen ausliest:
Bitweise Operatoren - per "and" (bitweisem natürlich) kann man feststellen, ob eine Wand gesetzt ist. Per bitweisem "or" kann man einzelne Informationen reinschreiben:
Zahl=0
Zahl "bitweises or" 1 => obere Wand setzen
Zahl "bitweises or" 8 => linke Wand setzen

Zahl=lese Zahl aus Datei
Zahl "bitweises and" 1 ->ungleich 0 => obere Wand ist gesetzt
Zahl "bitweises and" 8 -> ungleich 0 => linke Wand ist gesetzt

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.

lagalopex

aha... was mich jetzt bloss wundert, ist dass du ja für alle inneren Wände je 2 bit hast... etwas überflüssig und dass immer außen immer Wände sind...

naja, ich hatte es so gemacht, dass sozusagen jede Zelle zwei bit hat: Wand links / Wand unten
sind zwar immernoch zuviele bits... :]

Aber sonst ist das Format gut... werds wohl mal aufnehmen... muss nur noch(tm) einen Weg S zu E berechnen...
Wie groß kann dein Labyrinth eigentlich werden?

CDW

Naja, das Format war Vorgabe (man musste alle Wände mit einem Bit kodieren ).

Anderseits erscheint es logischer bei der Konstruktion oder Wegsuche: z.B
zwei Zellen:
linke Zelle hat keine obere und keine rechte Wand, die rechte Zelle keine linke und keine untere Wand und bildet damit eine "Eckdurchgang" (Zugang von oben, dann nach rechts gehen und nach unten.
Wie willst Du diese Situation mit nur 2 Bits informationen abspeichern?
ich hab festgestellt, dass es sehr Compilerabhängig ist:
gcc unter Windows: irgendwo knapp über 100x100 ist Schluss
lcc32: irgendwo nach 300x300
gcc unter Knoppix 3.4: imho ging es bis 1000x1000 - was ich sehr erfreulich fand

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.

merker

Wie kommt das ?!? Gab es irgendwelche Fehlermeldungen ?

CDW

Lcc32 Kompilat: "Software Fehlercode 0xFD" aufgetreten (im Olly kann man "StackOverflow" Excetion" bewundern). Der Gcc kompilat unter Windows (DJGPP) beendet sich entweder komplett ohne Meldung oder reagiert nicht mehr.Die Meldung unter Knoppix weiß ich nicht mehr - afaik ging das auch Richtung Stackoverflow.

Je nach Compiler werden afaik auch per Default unterschiedliche Stack-Größen reserviert. Man könnte hier ein wenig mit den Einstellungen spielen. Aber sowohl die Erstellung wie auch die Lösung des Labyrinths sind bei mir rekursiver Natur - da geht irgendwann eben der Speicher aus.

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.

merker

Das ist die einzig saubere Lösung.

Hier eine unsaubere (für Leute die keine Zeit haben :-) :
Allerdings lässt sich das Labyrinthproblem auch ohne Rekursion lösen. Ich zumindest habe lieber einen "OutOfMemory" anstatt den in jeder Hinsicht fatalen "StackOverflow".

lagalopex

Also ich hab nichts am Programm geändert (auch rekursiver Ansatz) und kann Labyrinthe von 7000x7000 erstellen (dauert eine knappe halbe Minute, wird mit Schleifen nicht ganz so schnell gehen, imo [oder es braucht auch Unmengen an Speicher]). Zeitweise braucht das Programm dann zwar fast ein GB, aber egal...

Unter Linux kann es sein, dass mit "ulimit -s" eine Stack-Beschränkung gesetzt wurde.
Bei Gentoo war das standardmäßig bei 8MB ... Softlimit kann mit "ulimit -S -s 300000" auf 300 MB gesetzt werden...

Die Konsolen-Ausgabe ist auch knapp 370 MB groß... (wenn das einer haben will^^ gepackt wirds wohl nichtmehr soooo groß sein)

und da ich die letzten Tage unter anderem knapp 550 km weiter im Süden war, bin ich erst heute wieder hierzu gekommen ...

CDW

Ok, hab ein bisschen in der DJGPP Dokumentation gelesen. Die Stackgröße kann man per globalvariable ändern.
unsigned _stklen = 1048576;
Denn standardmäßig soll sie auf 512KB beschränkt sein. Auf "sichere" 100 MB erhöht, konnte ich 4000x4000 Labyrinthe testen (größere dauern mit zu lange - da ich sofort das erstellte Labyrinth erstmal ausgebe ).

So, hier ist erstmal eine Lösung. Sollte mit Lcc32 bzw. gcc auf Windows kompilierbar sein.
Zusätzlich auf Knoppix 3.4 getestet. Wer ein anders OS nutzt, muss eventuell zuerst die Headerdatei anpassen (die OS spezifischen Definitionen um ein einheitliches Clearscreen zu implementieren )
Wer "übergroße" Labyrinthe testen mag, sollte selbst für die nötigen Stackeinstellungen sorgen.
Dass C nicht meine Lieblingssprache ist, merkt man wahrscheinlich schnell
Der Codestil ist etwas gewöhnungsbedürftig - aus mir inzwischen unerklärlichen Gründen habe ich die Namensgebung der Funktions/Variablennamen auf den deutschen Sprachraum beschränkt.

Edit: die Binarys drangehängt: einmal eine Exe für Windows und einmal einen "ELF", der unter Knoppix 3.4 erstellt wurde

Angehängte Dateien

	Lab.zip (3,1 KB, 108x aufgerufen)
	binarys.zip (15,6 KB, 82x aufgerufen)

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.

merker

Ich hoffe doch, dass die Programmieraufgabe mit dem Posten einer Lösung noch nicht als gelöst gilt. Schliesslich besitzt sie einen interessanten Nebenaspekt.

Offenbar ist die maximale Labyrinthgrösse plattform- und / oder kompilerabhängig.

Das kann aber nicht sein, da Algorithmen immer plattform- und kompilerunabhängig arbeiten.

Was also muss geändert werden um Labyrinthe zu generieren, die 100.000 * 100.000 Felder gross sind ?

CDW

Nein, ist sie nicht - eine Lösung kann allerdings einige Denkansätze liefern, falls jemand nicht weiterkommt.

Die Implementierungen dieser Algorithmen sind aber plattform/kompilerabhängig, da sie letzendlich darauf laufen müssen, ich sehe hier keinen Widerspruch

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.

lagalopex

Mittlerweile kann ich auch ein Labyrinth lösen und speichern... fehlt nur noch das laden...


@merker: Und vom Algorithmus her. Der ist an sich durch die Speichergröße der verwendeten Datentypen und dem zur Verfügung stehenden Speicher begrenzt. An sich also wie CDW sagte, keine Beschränkung des Algorithmus. Allerhöchstens eine Beschränkung der Implementierung / Betriebssystems...
Hast du eigentlich schon eine Lösung mit Schleifen? Im Grunde geht es, klar, aber bei großen Labyrinthen hatte mein Algorithmus ein Problem: Wie finde ich noch nicht zugängliche Zellen, und das möglichst zufällig...

@CDW: Diese Schleife "while (nachbar_versuche!=NORD+WEST+OST+SUED)" wird manchmal doppelt so häufig durchlaufen, wie nötig. (nachbar_versuche wird geändert, wenn der nachbar nichtmehr frei ist, also bei dem zweiten versuch) . Und manchmal ziemlich oft^^ (je nach dem, was rand()%4 liefert...)
Das bei mir mehr Speicher gebraucht wird, könnte an den 64bit liegen denn wieviele pointer müssen gesichert werden?!...

xsheep

Hier ein Labyrinth von meinem Programm:

Mein Programm beherrscht das Speichern/Laden, Generieren und Lösen von Labyrinthen. Das einzige Problem: nach 300x300 macht es schlapp, kA wieso.

cya xsheep

merker

Huch ! (Teil 1)

Ihr seid mir alle zu schnell :-).

Deshalb hier ein Test für den Algorithmus :


@lagalopex

Das geht in dem man sich bei "step_forward" sämtliche freien Richtungen merkt. Dann liegen sie bei "step_back" wieder vor.


+E+D+I+T+1+


Huch ! (Teil 2)

Hoffentlich ist das Interesse an dieser Aufgabe noch nicht verschwunden. Deshalb erst mal ein bischen angeben (siehe Anhang :-).

Meine nichtrekursive Lösung schafft ohne besondere Linkereinstellungen locker 8000 * 8000 grosse Labyrinthe. Allerdings braucht mein Rechner (Celeron,350MHz,RAM 64MB, FP 6 GB) dafür bereits mehrere Minuten.
Die Maximalgrösse ist nur begrenzt durch folgenden Ausdruck : ((4,75 * x_sz * y_sz) < 4 GB).

Und hier wird die Aufgabe wieder interessant :

Wie lässt sich beweisen, dass ein "sehr" grosses Labyrinth auch wirklich "ok" ist ?

Ausdrucken läuft nicht. Nur Vertrauen haben in die eigene Implementation ist inakzeptabel. Irgendwelche Ideen ?