Knobelspaß - Der Kreisring

Übersicht

Sonstiges

Smalltalk

Gehe zu Seite Zurück 1, 2, 3, 4, 5 Weiter

	Xeres Moderator	So, Okt 13, 2013 17:10 Antworten mit Zitat
@biggicekey: Ja, die Aufgabenstellung ist etwas suboptimal gestellt worden. Eigentlich hat es nichts mit Snake zu tun - es geht nur darum, die Anzahl der Kombinationen eines sich nicht kreuzenden Pfades zu finden, der über alle Felder eines n mal n Gitters verläuft. Ich versuche mich an einer Version, die kleinere Vierecke zuerst ausrechnet und falls die Schlange eines von der Ecke her betritt, den gecachten Wert einsetzt. Mal sehen, ob ich das auch hin bekomme.
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

So, Okt 13, 2013 17:10
Antworten mit Zitat

@biggicekey: Ja, die Aufgabenstellung ist etwas suboptimal gestellt worden. Eigentlich hat es nichts mit Snake zu tun - es geht nur darum, die Anzahl der Kombinationen eines sich nicht kreuzenden Pfades zu finden, der über alle Felder eines n mal n Gitters verläuft.

Ich versuche mich an einer Version, die kleinere Vierecke zuerst ausrechnet und falls die Schlange eines von der Ecke her betritt, den gecachten Wert einsetzt. Mal sehen, ob ich das auch hin bekomme.

Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

	Tobchen	So, Okt 13, 2013 17:54 Antworten mit Zitat
Ich kann mir nicht vorstellen, dass das mit den Rechtecken viel bringt. Man müsste immerzu gucken, ob jetzt nur noch ein Rechteck bleibt und wenn es einmal Erfolg hat, spart man gewiss nicht so viel Zeit wie man überhaupt erst durch die erfolglosen Prüfungen verloren hat. Aber in diese Richtung geht auch mein jüngstes Scheitern: Ich habe bei mir noch eingebaut, dass er alle paar Wegvoranschreitungen Floodfill vom Kopf aus ausführt und dann checkt, ob noch freie Felder (= niemals betretbare) existieren, aber das hat alles eher langsamer gemacht...
Tobchen - die Welt von Tobi!

Tobchen

So, Okt 13, 2013 17:54
Antworten mit Zitat

Ich kann mir nicht vorstellen, dass das mit den Rechtecken viel bringt. Man müsste immerzu gucken, ob jetzt nur noch ein Rechteck bleibt und wenn es einmal Erfolg hat, spart man gewiss nicht so viel Zeit wie man überhaupt erst durch die erfolglosen Prüfungen verloren hat.

Aber in diese Richtung geht auch mein jüngstes Scheitern:
Ich habe bei mir noch eingebaut, dass er alle paar Wegvoranschreitungen Floodfill vom Kopf aus ausführt und dann checkt, ob noch freie Felder (= niemals betretbare) existieren, aber das hat alles eher langsamer gemacht...

Tobchen - die Welt von Tobi!

	Noobody	So, Okt 13, 2013 20:19 Antworten mit Zitat
@CO2: Durch schnelles Ausprobieren komme ich auf 8 Moeglichkeiten bei 3x3, aber ist moeglich, dass noch mehr existieren:
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

So, Okt 13, 2013 20:19
Antworten mit Zitat

@CO2: Durch schnelles Ausprobieren komme ich auf 8 Moeglichkeiten bei 3x3, aber ist moeglich, dass noch mehr existieren:
user posted image

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

	BladeRunner Moderator	So, Okt 13, 2013 20:40 Antworten mit Zitat
Ab davon wären laut deiner Formel nicht 90 Möglichkeiten gegeben, sondern (100²)-100, also 99900. Aber auch das ist definitiv falsch, du kannst sicherlich von mehreren Milliarden Lösungen ausgehen. EDIT: Argh, sorry, ich hatte 100*100 im Kopf als Größe. Dennoch sind es deutlich mehr Möglichkeiten die zu erwarten stehen.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

So, Okt 13, 2013 20:40
Antworten mit Zitat

Ab davon wären laut deiner Formel nicht 90 Möglichkeiten gegeben, sondern (100²)-100, also 99900. Aber auch das ist definitiv falsch, du kannst sicherlich von mehreren Milliarden Lösungen ausgehen.
EDIT: Argh, sorry, ich hatte 100*100 im Kopf als Größe.
Dennoch sind es deutlich mehr Möglichkeiten die zu erwarten stehen.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	Xeres Moderator	Mo, Okt 14, 2013 0:14 Antworten mit Zitat
Die aktuellen Ergebnisse: Mit Tobchens Optimierungen ergeben sich diese Ergebnisse: Code: [AUSKLAPPEN] [EINKLAPPEN] n v t ============================== 2 2 <1ms 3 8 <1ms 4 52 <1ms 5 824 2ms 6 22144 120ms 7 1510446 15 Sekunden 8 180160012 1 Stunde, 19 Minuten, 12 Sekunden 9 ? ? 10 ? ? (mit Hardware siehe Signatur) Wir können ziemlich sicher sein, dass die Ergebnisse richtig sind (thx Tennisball). Meine Idee für weitere Optimierungen: Um zwei getrennte Bereiche zu finden, die man abbrechen kann, könnte man alle Zeilen/Spalten AND verknüpfen (sowas wie ein Schattenwurf?); Code: [AUSKLAPPEN] [EINKLAPPEN] ######=# #_##_#=_ #_##_#=_ #_##_#=_ ######=# ====== #_##_# <- Unterbrechung signalisiert zwei getrennte Bereiche Einsprüche? Bessere Ideen? Nur zu! Edit: Noch eine Quelle von Tennisball: On Maximal Self-Avoiding Walks
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Mo, Okt 14, 2013 0:14
Antworten mit Zitat

Die aktuellen Ergebnisse:
Mit Tobchens Optimierungen ergeben sich diese Ergebnisse:
Code: [AUSKLAPPEN]

n v t
==============================
2 2 <1ms
3 8 <1ms
4 52 <1ms
5 824 2ms
6 22144 120ms
7 1510446 15 Sekunden
8 180160012 1 Stunde, 19 Minuten, 12 Sekunden
9 ? ?
10 ? ?

(mit Hardware siehe Signatur)
Wir können ziemlich sicher sein, dass die Ergebnisse richtig sind (thx Tennisball).

Meine Idee für weitere Optimierungen:
Um zwei getrennte Bereiche zu finden, die man abbrechen kann, könnte man alle Zeilen/Spalten AND verknüpfen (sowas wie ein Schattenwurf?);
Code: [AUSKLAPPEN]

######=#
#_##_#=_
#_##_#=_
#_##_#=_
######=#
======
#_##_# <- Unterbrechung signalisiert zwei getrennte Bereiche

Einsprüche? Bessere Ideen? Nur zu!

Edit:
Noch eine Quelle von Tennisball: On Maximal Self-Avoiding Walks

	ZEVS	Mo, Okt 14, 2013 21:07 Antworten mit Zitat
So, mein C-Programm ist fertig. Meine Ursprungsidee, deckungsgleiche Pfade wiederzuverwenden scheitert an der Tatsache, dass ich sämtliche bisher erzeugten Pfade im RAM halten müsste, das wären zu viele. Stattdessen habe ich mich für eine andere Optimierung entschieden: Ein "Ende" ist ein Feld, das leer ist und drei nicht leere Nachbarn hat (hier mit einer Null markiert). Code: [AUSKLAPPEN] [EINKLAPPEN] xxx 0x xxx Wenn nur ein Ende existiert, ist das in Ordnung, denn da kann der Pfad dann beendet werden. Wenn zwei Enden existieren, das eine aber mit vom Schlangenkopf eingeschlossen wird, z.B. Code: [AUSKLAPPEN] [EINKLAPPEN] xxxxxx h0 0x xxxxxx (h ist der Schlangenkopf, 0 die Enden) ist das in Ordnung, sofern sich die Schlange als nächstes dieses Ende füllt. Wenn zwei Enden existieren und der Schlangenkopf ganz woanders ist, braucht dieser Pfad nicht weiterprobiert zu werden. Wenn drei Enden existieren, geht das ebenfalls nicht. Weil ich in C ohne Weiteres nur auf Sekunden genau messen kann, kann ich nur einen Messwert präsentieren: 5 Sekunden für das 7x7-Quadrat (Win XP 32 Professional mit AMD Athlon 64 [2.19GHz]). Das Programm findet ihr hier. Für eine 8x8-Messung habe ich noch nicht die Zeit gefunden. ZEVS edit 18.10.: Link verweist auf Version 1.1.

ZEVS

Mo, Okt 14, 2013 21:07
Antworten mit Zitat

So, mein C-Programm ist fertig. Meine Ursprungsidee, deckungsgleiche Pfade wiederzuverwenden scheitert an der Tatsache, dass ich sämtliche bisher erzeugten Pfade im RAM halten müsste, das wären zu viele.
Stattdessen habe ich mich für eine andere Optimierung entschieden: Ein "Ende" ist ein Feld, das leer ist und drei nicht leere Nachbarn hat (hier mit einer Null markiert).
Code: [AUSKLAPPEN]

xxx
0x
xxx

Wenn nur ein Ende existiert, ist das in Ordnung, denn da kann der Pfad dann beendet werden. Wenn zwei Enden existieren, das eine aber mit vom Schlangenkopf eingeschlossen wird, z.B.
Code: [AUSKLAPPEN]

xxxxxx
h0 0x
xxxxxx

(h ist der Schlangenkopf, 0 die Enden)
ist das in Ordnung, sofern sich die Schlange als nächstes dieses Ende füllt. Wenn zwei Enden existieren und der Schlangenkopf ganz woanders ist, braucht dieser Pfad nicht weiterprobiert zu werden. Wenn drei Enden existieren, geht das ebenfalls nicht.

Weil ich in C ohne Weiteres nur auf Sekunden genau messen kann, kann ich nur einen Messwert präsentieren: 5 Sekunden für das 7x7-Quadrat (Win XP 32 Professional mit AMD Athlon 64 [2.19GHz]). Das Programm findet ihr hier.
Für eine 8x8-Messung habe ich noch nicht die Zeit gefunden.

ZEVS

edit 18.10.: Link verweist auf Version 1.1.

Zuletzt bearbeitet von ZEVS am Fr, Okt 18, 2013 21:34, insgesamt einmal bearbeitet

	Tobchen	Mo, Okt 14, 2013 22:49 Antworten mit Zitat
Geile Scheiße, ZEVS. 8x8 in 527sek berechnet. Mag deine Idee (und sie funktioniert ja offensichtlich bestens), aber wie testest du auf diese Enden? (Sorry, dein C-Code ist mir zu lang.) Die immerzu zu prüfen, kann doch nicht billig sein.
Tobchen - die Welt von Tobi!

Tobchen

Mo, Okt 14, 2013 22:49
Antworten mit Zitat

Geile Scheiße, ZEVS.
8x8 in 527sek berechnet.

Mag deine Idee (und sie funktioniert ja offensichtlich bestens), aber wie testest du auf diese Enden? (Sorry, dein C-Code ist mir zu lang.) Die immerzu zu prüfen, kann doch nicht billig sein.

Tobchen - die Welt von Tobi!

	DAK	Di, Okt 15, 2013 11:05 Antworten mit Zitat
Bin soweit mit rekursivem Aufruf und 2 Threads aber sonst ohne Optimierungen auf 142 ms auf 6x6 gekommen. Ich werd mal versuchen, das Ganze nicht-rekursiv zu machen, da in Java Funktionsaufrufe ja auch nicht gratis sind. @ZEVS: Deine Lösung ist ja echt genial schnell.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Di, Okt 15, 2013 11:05
Antworten mit Zitat

Bin soweit mit rekursivem Aufruf und 2 Threads aber sonst ohne Optimierungen auf 142 ms auf 6x6 gekommen.

Ich werd mal versuchen, das Ganze nicht-rekursiv zu machen, da in Java Funktionsaufrufe ja auch nicht gratis sind.

@ZEVS: Deine Lösung ist ja echt genial schnell.

Gewinner der 6. und der 68. BlitzCodeCompo

	ZEVS	Di, Okt 15, 2013 18:55 Antworten mit Zitat
Freut mich, dass euch mein Programm gefällt . @Xeres: Deine Optimierung findet nichts, was Tobchens nicht auch finden würde. @Tobchen: Die Implementierung gestaltetet sich in der Tat kompliziert und bugfreudig. Es ist nicht nötig, jedes mal das ganze Spielfeld auf Enden zu untersuchen, da sich 90% ja sowieso nicht ändert. Man speichert einfach die bisher gefundenen Enden und schaut nur in den Feldern direkt neben dem Schlangenkopf, ob diese nun zum Ende würden. Das Programm verwaltet ein "allgemeines" Ende (in den globalen Variablen endX und endY) und zu jedem Schlangensegment (genannt step) auch ein eigenes Ende (path->endX, path->endY). Wenn bereits ein Ende gefunden wurde (gespeichert in endX/endY) und ein neues hinzukommt (gespeichert in path->endX/path->endY), muss die Schlange im nächsten Schritt das Feld (path->endX / path->endY) füllen, sonst kommt es irgendwann zwangsläufig zu drei Enden (Z. 294). Diese Regel hat eine Ausnahme: Es kann sein, dass bisher kein Ende gefunden wurde. Nun kommen mit einem weiteren Schritt zwei Enden dazu, das eine wird in endX/endY und das andere in path->endX/path->endY (bzw. die Zwischenwerte ex/ey) gespeichert. Dies ist ja eine legitime Situation. Wenn die Schlange nun aber in das Ende weitergeht, das in endX/endY gespeichert wurde, werden diese beiden Werte einfach getauscht (Z. 277). Wenn der Pfad ein zugehöriges Ende hat (path->endX/path->endY) und die Schlange dies füllt, ist alles super. Entscheidet sie sich dagegen, wird dieses Pfad-Ende nur noch ganz zum Schluss ausgefüllt werden können und daher zum allegemeinen Ende (endX/endY). Dies ist aber natürlich nur dann zulässig, wenn vorher kein allgemeines Ende gefunden wurde (Z. 303). Kompliziert wird es dann, wenn der momentane Pfad verworfen wird und die Schlange ein Stück zurück gezogen wird (Z. 180). Dann muss man irgendwie die passenden Werte der End-Variablen wiederherstellen... 527 Sekunden für das bekannte Maximum ist wirklich nicht schlecht. Ich spiele mit dem Gedanken, dass wir über distributed computing mit den Leuten hier im Forum das 9x9 berechnen (die Berechnung lässt sich ja sehr gut aufteilen). Damit wären wir die ersten, die den Wert kennen. ZEVS

ZEVS

Di, Okt 15, 2013 18:55
Antworten mit Zitat

Freut mich, dass euch mein Programm gefällt Very Happy

.

@Xeres: Deine Optimierung findet nichts, was Tobchens nicht auch finden würde.

@Tobchen: Die Implementierung gestaltetet sich in der Tat kompliziert und bugfreudig. Es ist nicht nötig, jedes mal das ganze Spielfeld auf Enden zu untersuchen, da sich 90% ja sowieso nicht ändert. Man speichert einfach die bisher gefundenen Enden und schaut nur in den Feldern direkt neben dem Schlangenkopf, ob diese nun zum Ende würden.
Das Programm verwaltet ein "allgemeines" Ende (in den globalen Variablen endX und endY) und zu jedem Schlangensegment (genannt step) auch ein eigenes Ende (path->endX, path->endY). Wenn bereits ein Ende gefunden wurde (gespeichert in endX/endY) und ein neues hinzukommt (gespeichert in path->endX/path->endY), muss die Schlange im nächsten Schritt das Feld (path->endX / path->endY) füllen, sonst kommt es irgendwann zwangsläufig zu drei Enden (Z. 294).
Diese Regel hat eine Ausnahme: Es kann sein, dass bisher kein Ende gefunden wurde. Nun kommen mit einem weiteren Schritt zwei Enden dazu, das eine wird in endX/endY und das andere in path->endX/path->endY (bzw. die Zwischenwerte ex/ey) gespeichert. Dies ist ja eine legitime Situation. Wenn die Schlange nun aber in das Ende weitergeht, das in endX/endY gespeichert wurde, werden diese beiden Werte einfach getauscht (Z. 277).
Wenn der Pfad ein zugehöriges Ende hat (path->endX/path->endY) und die Schlange dies füllt, ist alles super. Entscheidet sie sich dagegen, wird dieses Pfad-Ende nur noch ganz zum Schluss ausgefüllt werden können und daher zum allegemeinen Ende (endX/endY). Dies ist aber natürlich nur dann zulässig, wenn vorher kein allgemeines Ende gefunden wurde (Z. 303).
Kompliziert wird es dann, wenn der momentane Pfad verworfen wird und die Schlange ein Stück zurück gezogen wird (Z. 180). Dann muss man irgendwie die passenden Werte der End-Variablen wiederherstellen...

527 Sekunden für das bekannte Maximum ist wirklich nicht schlecht. Ich spiele mit dem Gedanken, dass wir über distributed computing mit den Leuten hier im Forum das 9x9 berechnen (die Berechnung lässt sich ja sehr gut aufteilen). Damit wären wir die ersten, die den Wert kennen.

ZEVS

	BladeRunner Moderator	Di, Okt 15, 2013 19:14 Antworten mit Zitat
Wenn Du das Programm dafür machst stelle ich gern Rechenzeit zur Verfügung.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Di, Okt 15, 2013 19:14
Antworten mit Zitat

Wenn Du das Programm dafür machst stelle ich gern Rechenzeit zur Verfügung.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	PhillipK	Mi, Okt 16, 2013 22:22 Antworten mit Zitat
Dito. Das wäre doch mal ein schönes problem was behandelt wird Aber bitte nicht 100% cpu zwacken.. dann lass ichs dauerhaft nebenher laufen (und wenn du ganz viele böcke hast, mit multithreading. Es gibt kaum noch wen mit singlecore cpus )

PhillipK

Mi, Okt 16, 2013 22:22
Antworten mit Zitat

Dito. Das wäre doch mal ein schönes problem was behandelt wird Smile

Aber bitte nicht 100% cpu zwacken.. dann lass ichs dauerhaft nebenher laufen Smile

(und wenn du ganz viele böcke hast, mit multithreading. Es gibt kaum noch wen mit singlecore cpus Smile

)

	ZEVS	Fr, Okt 18, 2013 21:32 Antworten mit Zitat
So, ich habe ein Programm geschrieben, mit dem man aus der Gesamtheit der zu berechnenden Pfade verschiedene mit bestimmten Anfängen herauspicken kann und sie einzeln berechnet. Die ausführlichen Ergebnisse speichere bitte jeder selbst und teile den anderen hier nur die Zusammenfassung (d.h. von - bis, Anzahl perfekte Zustände) mit. Außerdem hatte meine Implementierung noch eine ziemlich unnötige Bremse mit drin. Ich hatte die Pfadschritte alle in unabhängigen Speicherbereichen zu je 12 Byte gespeichert und dann so einen (prinzipiell unendlich großen) Stack geschaffen. Da ich für ein Feld der Länge n maximal n^2 Pfadschritte habe, ist es aber viel sinnvoller, mit einem größenbeschränkten Stack zu arbeiten, was dafür sorgt, dass man nicht immer vom OS neue Speicherbereiche anfragen muss, nur um sie z.T. kurz darauf wieder freizugeben. Aktueller Rekord: 7x7 in 1s! Ich habe mein Programm kuzzeitig so umgebaut, dass es auch das 8x8 berechnen kann, das hat 243.991 Sekunden gedauert (und das Programm nimmt sich nur 90% CPU). Die Version 1.1 von meinem Originalprogramm findet ihr hier (9.83 KB). Das ZIP-Archiv aller benötigter Dateien für die verteilte Berechnung nebst Readme findet ihr hier (1.46 MB). Multicore-Menschen dürfen das Programm auch mehrmals parallel ausführen, die beißen sich nicht. ZEVS edit: Um deutlich zu machen, was sich hinter den Pfadangaben verbirgt, habe ich ein Beispiel gemalt: (Der Pfad heißt EESSWWSSE)

ZEVS

Fr, Okt 18, 2013 21:32
Antworten mit Zitat

So, ich habe ein Programm geschrieben, mit dem man aus der Gesamtheit der zu berechnenden Pfade verschiedene mit bestimmten Anfängen herauspicken kann und sie einzeln berechnet. Die ausführlichen Ergebnisse speichere bitte jeder selbst und teile den anderen hier nur die Zusammenfassung (d.h. von - bis, Anzahl perfekte Zustände) mit. Außerdem hatte meine Implementierung noch eine ziemlich unnötige Bremse mit drin. Ich hatte die Pfadschritte alle in unabhängigen Speicherbereichen zu je 12 Byte gespeichert und dann so einen (prinzipiell unendlich großen) Stack geschaffen. Da ich für ein Feld der Länge n maximal n^2 Pfadschritte habe, ist es aber viel sinnvoller, mit einem größenbeschränkten Stack zu arbeiten, was dafür sorgt, dass man nicht immer vom OS neue Speicherbereiche anfragen muss, nur um sie z.T. kurz darauf wieder freizugeben. Aktueller Rekord: 7x7 in 1s! Ich habe mein Programm kuzzeitig so umgebaut, dass es auch das 8x8 berechnen kann, das hat 243.991 Sekunden gedauert (und das Programm nimmt sich nur 90% CPU).
Die Version 1.1 von meinem Originalprogramm findet ihr hier (9.83 KB).
Das ZIP-Archiv aller benötigter Dateien für die verteilte Berechnung nebst Readme findet ihr hier (1.46 MB).

Multicore-Menschen dürfen das Programm auch mehrmals parallel ausführen, die beißen sich nicht.

ZEVS

edit: Um deutlich zu machen, was sich hinter den Pfadangaben verbirgt, habe ich ein Beispiel gemalt:
user posted image

(Der Pfad heißt EESSWWSSE)

	Tennisball	Fr, Okt 18, 2013 23:24 Antworten mit Zitat
Hi, Ich habe mal angefangen zu berechnen von SE bis W. Log Letzte Zeile: SWSSENESSESEEENNWSWNWNENWWNEEESSENNEESWSESWSESWSWS; SWSSENESSESWWNWSSSSENNESSEENWNENESSSENNESSENNNNNWWWNENESENNWWWSWNWWSES; 11342461;9310 Insgesamt berechnete Pfade bis dahin: 4607207568 Gruß, Tennisball

Tennisball

Fr, Okt 18, 2013 23:24
Antworten mit Zitat

Hi,

Ich habe mal angefangen zu berechnen von SE bis W.
Log
Letzte Zeile: SWSSENESSESEEENNWSWNWNENWWNEEESSENNEESWSESWSESWSWS;
SWSSENESSESWWNWSSSSENNESSEENWNENESSSENNESSENNNNNWWWNENESENNWWWSWNWWSES;
11342461;9310
Insgesamt berechnete Pfade bis dahin: 4607207568

Gruß,
Tennisball

	Jamagin	Sa, Okt 19, 2013 7:06 Antworten mit Zitat
@Teennisball wie kommt es das bei dir die Sekunden angezeigt werden? Bei mir kommt immer eine 0;9730 zB raus. Die erste Stelle ist immer 0; komisch oder? @zevs; kannst du das Fenster bitte größer machen oder zumindest, das man die größe selbst verändern kann? lg. Jamagin
Bevor du etwas neues beginnst, erledige das alte

Jamagin

Sa, Okt 19, 2013 7:06
Antworten mit Zitat

@Teennisball

wie kommt es das bei dir die Sekunden angezeigt werden? Bei mir kommt immer eine 0;9730 zB raus. Die erste Stelle ist immer 0; komisch oder?

@zevs;

kannst du das Fenster bitte größer machen oder zumindest, das man die größe selbst verändern kann?

lg. Jamagin

Bevor du etwas neues beginnst, erledige das alte

	DAK	Sa, Okt 19, 2013 9:42 Antworten mit Zitat
Wir sollten eine Liste machen, wo die ganze Karte in die passenden Pfade zerhackt wird, so dass man weiß, wo man weitersuchen soll. Ich mach grad von EE bis SE, werde posten, wenn es ein Ergebnis gibt. Aja, eins noch: es wäre nett, wenn man in der GUI einstellen könnte, wie viele Threads man haben will. Edit: Fertig. Log findet sich unter https://www.blitzforum.de/upload/file.php?id=12613. Ergebnis ist: 19.850.432.269 Hat jetzt gute siebeneinhalb Stunden gebraucht.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Sa, Okt 19, 2013 9:42
Antworten mit Zitat

Wir sollten eine Liste machen, wo die ganze Karte in die passenden Pfade zerhackt wird, so dass man weiß, wo man weitersuchen soll.

Ich mach grad von EE bis SE, werde posten, wenn es ein Ergebnis gibt.

Aja, eins noch: es wäre nett, wenn man in der GUI einstellen könnte, wie viele Threads man haben will.

Edit: Fertig. Log findet sich unter https://www.blitzforum.de/upload/file.php?id=12613.
Ergebnis ist: 19.850.432.269

Hat jetzt gute siebeneinhalb Stunden gebraucht.

Gewinner der 6. und der 68. BlitzCodeCompo

	Holzchopf Meisterpacker	So, Okt 20, 2013 22:26 Antworten mit Zitat
Habe SWSE-SWSS gemacht. Ergebnis: 7'642'913'203 Logs: 1. Teil, 2. Teil Wenn ich mich nicht irre, fehlt jetzt nur noch SSE-SSS
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf CC BY ♫ BinaryBorn - Yogurt ♫ (31.10.2018) Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

Holzchopf

Meisterpacker

So, Okt 20, 2013 22:26
Antworten mit Zitat

Habe SWSE-SWSS gemacht.
Ergebnis: 7'642'913'203
Logs: 1. Teil, 2. Teil

Wenn ich mich nicht irre, fehlt jetzt nur noch SSE-SSS

Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BY ♫ BinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

	ZEVS Betreff: Version 1.1	Mo, Okt 21, 2013 20:12 Antworten mit Zitat
OK, das geht echt wesentlich schneller als ich erwartet hatte. Auf den (hoffentlich) letzten Metern gibt es jedenfalls noch ein Update: changelog.txt hat Folgendes geschrieben: Version 1.1 (21.10.13) ====================== - Die Anwendung legt selbstständig Logdateien an. Hierzu kann sie über eine Konfigurationsdatei gesteuert werden. Die Logs sind nicht mehr im Fenster sichtbar. - Das Fenster kann beliebig vergrößert und verkleinert werden (mittels SetGadgetLayout EDGE_RELATIVE implementiert). - Man kann in mehreren worker-Tabs mehrere Prozesse in einem Fenster parallel ausführen. - Das Programm stellt seine eigenen Abstürze fest und informiert darüber beim nächsten Start und vermerkt sie im Log. - WICHTIG: Das Programm kann nicht mehrmals parallel ausgeführt werden! Beide Versionen würden versuchen, gleichzeitig schreibenden Zugriff auf die zentrale Logdatei zu erhalten -> geht nicht. Aber es ist ja inzwischen auch unnötig, dies zu tun. - Das Programm showPath wurde hinzugefügt, um die Pfade veranschaulichen zu können (BlitzMax-Compiler benötigt). Übersicht des bisher untersuchten: DAK: EE-SE Tennisball: SE-SWSSENESSESWWNWSSSSENNESSEENWNENESSSENNESSENNNNNWWWNENESENNWWWSWNWWSES Holzchopf: SWSE-SWSS => es fehlt SWSS-W und die Schnittstelle Tennisball-Holzchopf muss ausgebessert werden. Download (1.41 MB) ZEVS P.S: Habe einen Bug gefixt.

ZEVS

Betreff: Version 1.1

Mo, Okt 21, 2013 20:12
Antworten mit Zitat

OK, das geht echt wesentlich schneller als ich erwartet hatte. Auf den (hoffentlich) letzten Metern gibt es jedenfalls noch ein Update:
changelog.txt hat Folgendes geschrieben:

Version 1.1 (21.10.13)
======================
- Die Anwendung legt selbstständig Logdateien an. Hierzu kann sie über eine Konfigurationsdatei gesteuert werden. Die Logs sind nicht mehr im Fenster sichtbar.
- Das Fenster kann beliebig vergrößert und verkleinert werden (mittels SetGadgetLayout EDGE_RELATIVE implementiert).
- Man kann in mehreren worker-Tabs mehrere Prozesse in einem Fenster parallel ausführen.
- Das Programm stellt seine eigenen Abstürze fest und informiert darüber beim nächsten Start und vermerkt sie im Log.
- WICHTIG: Das Programm kann nicht mehrmals parallel ausgeführt werden! Beide Versionen würden versuchen, gleichzeitig schreibenden Zugriff auf die zentrale Logdatei zu erhalten -> geht nicht. Aber es ist ja inzwischen auch unnötig, dies zu tun.
- Das Programm showPath wurde hinzugefügt, um die Pfade veranschaulichen zu können (BlitzMax-Compiler benötigt).

Übersicht des bisher untersuchten:
DAK: EE-SE
Tennisball: SE-SWSSENESSESWWNWSSSSENNESSEENWNENESSSENNESSENNNNNWWWNENESENNWWWSWNWWSES
Holzchopf: SWSE-SWSS
=> es fehlt SWSS-W und die Schnittstelle Tennisball-Holzchopf muss ausgebessert werden.

Download (1.41 MB)

ZEVS

P.S: Habe einen Bug gefixt.

Zuletzt bearbeitet von ZEVS am Mo, Okt 21, 2013 21:42, insgesamt einmal bearbeitet

	DAK	Mo, Okt 21, 2013 20:56 Antworten mit Zitat
Ich rechne gerade an SWSS -> W Kleine Frage dazu, weil ich die Pfadangaben nicht wirklich behirne. Es war doch so, dass man links oben beginnt, oder? Das heißt, von Start an, kann man eigentlich nur nach Süden und Osten gehen, oder? Wie kann man dann den Weg SWSS gehen? Wäre man da nicht nach dem ersten W im Aus?
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Mo, Okt 21, 2013 20:56
Antworten mit Zitat

Ich rechne gerade an SWSS -> W

Kleine Frage dazu, weil ich die Pfadangaben nicht wirklich behirne. Es war doch so, dass man links oben beginnt, oder? Das heißt, von Start an, kann man eigentlich nur nach Süden und Osten gehen, oder?
Wie kann man dann den Weg SWSS gehen? Wäre man da nicht nach dem ersten W im Aus?

Gewinner der 6. und der 68. BlitzCodeCompo

	ZEVS	Mo, Okt 21, 2013 21:00 Antworten mit Zitat
Das erste "nach Osten" ist nicht erwähnt, da redundant. ZEVS

ZEVS

Mo, Okt 21, 2013 21:00
Antworten mit Zitat

Das erste "nach Osten" ist nicht erwähnt, da redundant.

ZEVS

	Tennisball	Mo, Okt 21, 2013 21:00 Antworten mit Zitat
Man geht am Anfang immer einmal nach rechts. Würde man das nicht tun, müsste man doppelt so viele Wege ausrechnen (nämlich die, bei denen man am Anfang nach unten geht). So kann man aber alle Wege einfach "spiegeln", d.h. die Anzahl der errechneten Wege verdoppeln, und man erhält die wirkliche Anzahl. Edit: ZEVS war schneller

Tennisball

Mo, Okt 21, 2013 21:00
Antworten mit Zitat

Man geht am Anfang immer einmal nach rechts. Würde man das nicht tun, müsste man doppelt so viele Wege ausrechnen (nämlich die, bei denen man am Anfang nach unten geht). So kann man aber alle Wege einfach "spiegeln", d.h. die Anzahl der errechneten Wege verdoppeln, und man erhält die wirkliche Anzahl.

Edit: ZEVS war schneller

Gehe zu Seite Zurück 1, 2, 3, 4, 5 Weiter

Übersicht

Sonstiges

Smalltalk

Nach Oben

BlitzBasic Portal

Knobelspaß - Der Kreisring

Betreff: Version 1.1