Differences

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

--- jumpin [2023/11/28 08:22]
Ivo Blöchliger created
+++ jumpin [2023/12/14 15:06] (current)
Ivo Blöchliger [Kurzbeschreibung der Videos]
@@ Line 44: / Line 44: @@
 Eine andere Variante wäre die Koordinaten der Figuren zu speichern (bis zu 4 Hasen und 2 Füchse). Bei 25 Feldern, nummeriert von 0-24 werden also 5 Bits pro Figur benötigt, d.h. maximal 30 Bits.
-Um eine eindeutige Codierung zu erreichen, werden die Hasen nach aufsteigenden Feldnummern sortiert abgespeichert (und dann ebenso die Füchse). Für die Füchse würde sogar eine Koordinate reichen (die andere ist schliesslich fix), wobei die Positionen nur von 0-3 gehen, d.h. für die Füchse reichen schon je 2 Bits, was die Anzahl Bits auf total 20 Bits reduziert.
+Um eine eindeutige Codierung zu erreichen, werden die Hasen nach aufsteigenden Feldnummern sortiert abgespeichert (und dann ebenso die Füchse). Für die Füchse würde sogar eine Koordinate reichen (die andere ist schliesslich fix), wobei die Positionen nur von 0-3 gehen, d.h. für die Füchse reichen schon je 2 Bits, was die Anzahl Bits auf total 24 Bits reduziert.
-$2^{20} \approx 10^6$, was sehr wenig ist. Damit liesse sich eine Menge von Positionen als Bitstring mit $2^{20}$ Bits schreiben, was im Speicher $2^{17}$ Bytes (130kB) belegt, was sicherlich kein Problem ist.
+$2^{24} \approx 1.8*10^7$, was eher wenig ist. Damit liesse sich eine Menge von Positionen als Bitstring mit $2^{24}$ Bits schreiben, was im Speicher $2^{21} Bytes (2MB) belegt, was sicherlich kein Problem ist.
 Damit lassen sich Positionen in konstanter Zeit markieren und abfragen, besser geht's nicht. Konkret lässt sich das mit einem
@@ Line 52: / Line 52: @@
+===== Grössere Felder =====
+Für grössere Felder werden mehr Bits pro Position benötigt und ein Bit-Array ist nicht mehr praktikabel.
+Werden alle besuchten Positionsnummern als Zahl oder String in einem Array gespeichert, ist die Überprüfung, ob eine Position schon vorhanden ist sehr ineffizient, weil mit allen Positionen verglichen werden muss.
+Man könnte das Array sortieren und dann einen binary search darauf machen. Allerdings ist das Sortieren sehr aufwendig. Selbst das Einfügen in ein sortieres Array ist aufwendig, weil etwa die Hälfte aller Element umplatziert werden müssen.
+Eine Möglichkeit besteht darin, die Zahlen «halbsortiert» in einem [[https://en.wikipedia.org/wiki/Binary_heap|Binary Heap]], ([[https://de.wikipedia.org/wiki/Bin%C3%A4rer_Heap|Binärer Heap]]) zu speichern.
+Damit lassen sich alle Operationen in $\log(n)$ durchführen.
+===== Video-Serie =====
+Verfolgen Sie die komplette Entwicklung des Programm mit Erklärungen:
+  * https://fginfo.ksbg.ch/~ivo/videos/ffprog/gumpine/ oder via [[https://bldsg-my.sharepoint.com/:f:/g/personal/ivo_bloechliger_ksbg_ch/EtC8QNI8hwFPlKMzPTLDpagBbJxqBnycaozJQ8fz9613dg?e=uF5HBs|OneDrive]]
+  * Die Codes gibt es als git-Repo, für jeden einzeln Video gibt es einen Tag, dem man auch einzeln auschecken kann. https://github.com/techlabksbg/gumpine
+<code bash>
+git clone https://github.com/techlabksbg/gumpine.git
+</code>
+Einen gegebenen Tag (z.B. v0) kann man wie folgt aus-checken und daran in einem eigenen Branch (z.B. dev) weiterarbeiten:
+<code bash>
+git fetch --all --tags
+git checkout tags/v0
+git switch -c dev
+</code>
+==== Kurzbeschreibung der Videos ====
+  * **v0**: «Einrichtung» von NodeJS, package.json, die fixen Teile eines Spielfelds als Klasse ''Fix'', Ausgabe eines Spielfelds.
+    * Wie bringt man emojis in die git-bash? Vieleicht so: https://www.reddit.com/r/git/comments/ih4frz/how_to_get_emojis_in_git_bash_prompt_on_windows/
+  * **v1**: Klasse ''Moving'' für bewegliche Teile des Spielfelds.
+  * **v2**: Codierung und Dekodierung der beweglichen Teile als Zahl.
+  * **v3**: Generierung aller möglichen Hasenzüge als Generator-Funktion.
+  * **v4**: Generierung aller möglichen Fuchszüge als Generator-Funktion.
+  * **v5**: ''explore'': Sämtliche erreichbare Spielpositionen ab einer Startposition generieren.
+  * **v6**: Aufräumen (aka refactoring) der Funktion ''explore''.
+  * **v7**: Generator aller möglichen Hasen-Endposition.
+  * **v8**: Generator aller möglichen Pilzposition als rekursive Funktion (sollte zwar besser iterativ als Generatorfunktion gemacht werden).
+  * **v9**: Erste Generierung von puzzles (inkl. Lösungen). Noch ohne Füchse.
+  * **v10**: Generator aller möglichen Platzierunge für die Füchse (muss dann später überarbeitet werden, weil gar nicht alle Positionen benötig werden).
+  * **v11**: Kleiner bugfix in der ''explore''-Funktion, die zu unnötigen Fuchs-Bewegungen am Ende einer Lösung geführt hat (obwohl die Hasen schon in den Löchern waren).
+  * **v12**: ''makePuzzle''-Funktion als Generator-Funktion, Serialisierung der Fix- und Moving-Instanzen (wird für die Dekodierung der Lösungen benötigt).
+  * **v13**: ''fuchsPlaetze''-Funktion liefert nur noch nötige Platzierungen, nicht mehr alle. Damit muss nicht mehrmals das gleiche Puzzle gelöst werden.
+  * **v14**: ''toMiniObj()'' etc. für ''Fix'' und ''Moving'': Schlankere Codierung, so dass alle Puzzles gespeichert werden können.
+  * **v15**: Parallelisierter Puzzle-Generator mit Threads.
+  * **v16**: Puzzles in eine JSON-Datei speichern.
+  * **v17**: Alle puzzles generiert.
+  * **v18**: Triviale Puzzle gefiltert.
+  * **v19**: Full width Canvas. (Start der GUI-Programmierung)
+  * **v20**: Koordinatensystem (0,0) bis (4,4)
+  * **v21**: Maus und Touch Interaktion (langes Video, viel Debugging)