ioBroker Advent of Code
-
Das lief heute, Day 9 schon besser, auch wenn ich wieder einen selten dämlichen Fehler drin hatte.
Meine Ausstiegsbedingung war das die Summe(!!!) aller Werte einer Stufe 0 ist. Nun gab es natürlich 4 Zeilen in den Daten wo es auch einen Schritt gab der Zufällig 0 ergibt. Ich hatte mir alles ausgeben lassen, aber erst auf den 10. Blick gesehen das bei einigen Zeilen die 0 0 0 0 fehlte.Dafür war Part 2 mal ausgesprochen leicht ... es musste nur eine Zeile mit einem
ArrayReverseergänzt werden -
@bananajoe sagte in ioBroker Advent of Code:
Ich behaupte nicht es verstanden zu haben
aber eigentlich dann simpel. evtl denkt man nicht direkt gleich daran, das es so funktionieren könnte.
du hast 3 start-nodes. mit
bei 1 kommst du in 2 schritten durch,
bei 2 kommst du in 3 schritten durch
bei 3 kommst du mit 4 schritten durchdann musst du 234 machen, das ist die Anzahl der schritte wo zum ersten mal alle 3 startnodes zugleich am gleichen endpunkt ankommen. daher auch kgv=kleinster gemeinsamer vielfacher.
theoretisch kann man das auch in javascript rechnen. es kann da aber schnell zu überläufen kommen. ich denke die webseite nimmt eine andere bibliothek als die javascript eigenen rechenfunktionen zu verwenden. -
So, der ganze Sonntag ist nur für das Rätsel drauf gegangen ... also Teil B.
Ich hatte mir gleich am Anfang gebaut das er mir das ganze - mit richtigen Ecken und Linien - wieder als Text ausgibt (aka ASCII-Art).
Ich hatte dann zwar eine Lösung, die war aber nur nah dran und die letzten Fehler habe ich dann von Hand gezählt und abgezogen. Ich hatte alle Leerzeichen innerhalb des Pfades mit X markiert, es waren aber noch zu viele da einige ja nicht umschlossen wirklich waren. Aus dem ASCII ein png gemacht, im Malprogramm einmal das Füllwerkzeug genommen und die X die im bunten waren abgezogen.
Aber mich hatte natürlich mein Ehrgeiz gepackt das ich das mit dem Programm hinbekomme.Da habe ich jetzt 5h dran verschwendet, ich inzwischen wieder weiter weg von der Lösung wie am Anfang. und bei fast 600 Zeilen Code.
Und sieht man andere "Flitzpiepen" die das mit weniger als 100 Zeilen machen.
Ok, ich musste mir meinen "FloodFill" auch selbst schreiben, inklusive das ich immer wieder an das Limit bei den Rekursiven Aufrufen gestoßen bin.Hoffentlich ist morgen wieder einfach, eigentlich wollte ich heute doch ganz viel andere Sachen machen.
-
@bananajoe Dich hat der AoC Virus gefangen
Ich habe für den 2ten Teil auch was ziemlich komplexes geschrieben.In dem Moment wo sich dir Lösung hatte, fiel mir was viel einfacheres ein...
Man kann in in Polygonen sehr einfach bestimmen, was innen und was außen ist.
Du musst dir nur aus Teil eins alle Positionen der Strecke merken (damit du den ganzen anderen 'Müll' ignorieren kannst).
Dann einfach jede Zeile von links nach rechts wandern. Dabei zählst du nur, ob du die Strecke kreuzt. Hast du sie einmal gekreuzt: bist du 'innen', zweimal gekreuzt wieder 'außen' und sie weiter. Also testest du, ob du eine gerade oder ungerade Anzahl Wege gekreuzt hast und je nachdem die leeren Felder an denen du vorbeikommst zählen oder nicht. Bei den Ecken nur bestimmte Ecke zählen, damit einen waagerechte Wände die Rechnung nicht kaputt machen.
Schau mal hier unter 'Raycasting' :
https://en.m.wikipedia.org/wiki/Point_in_polygonDas ist hier relativ einfach weil alles schön gerade ist.
Andere haben das Labyrinth 'aufgeplustert'. Aus Jedem Punkt eine 3x3 Fläche machen., dann lässt sich der FloodFill auf der größeren Fläche einsetzen, weil er sich dann gut zwischen den Wänden durchschlängeln kann.
-
@bluegaspode sagte in ioBroker Advent of Code:
Andere haben das Labyrinth 'aufgeplustert'. Aus Jedem Punkt eine 3x3 Fläche machen., dann lässt sich der FloodFill auf der größeren Fläche einsetzen, weil er sich dann gut zwischen den Wänden durchschlängeln kann.
genau das hatte ich auch zuletzt gemacht, mir fiel nichts besseres ein.
-
@bananajoe Man hätte das Labyrinth auch Lasercutten können, um dann manuell zu zählen:
https://www.reddit.com/r/adventofcode/comments/18fjhb9/2023_day_10_laser_cut_solution/
-
Ok, Tag 12 Teil 1 ging ja noch. Wie üblich bin ich bei einer "Brute Force" Lösung gelandet mit Logausgaben.
Für Teil 2 ist das - wie üblich - viel zu langsam. Ich habe mir schon diversen Code anderer angesehen und wie ich es verstehe ist bei denen die Lösung das "in Memory cached" zu machen ... die Möglichkeit fehlt mir irgendwie ..
Edit: und komme in die Limits von AutoIt.
Blöd das die 5 Gruppen per ? verbunden werden ... -
Als Cache brauchst du eigentlich nur etwas was in diversen Programmiersprachen "Map / HashMap / Dictionary" heißt.
Du nimmst weiterhin AutoIt?
Dann ist das hier dein Freund: https://www.autoitscript.com/wiki/Associative_ArraysIm Grunde geht es darum, Berechnungsergebnisse, die man schon hatte, zwischenzuspeichern.
Ich finde dieses hier ist ein schönes 'einfaches' Beispiel:
.??..??...?##. 1,1,3Du machst dort irgendwann eine Berechnung, wo du '1,1' 'schon untergebracht hast, z.B.: so:
.#...#.und dann bist du an der nächsten Stelle im String und fragst dich: passt hier dann irgendwo noch ein 3er Block rein. Beim ersten Mal, wenn du dich das fragst, musst du es berechnen.
In deinen Cache schreibst du dann aber z.B. rein "wenn du je wieder an der 10ten Stelle bist und nur noch den 3er Block unterbringen willst -> dann gibt es dafür noch eine Möglichkeit."Dann suchst du nach weiteren Möglichkeiten und findest z.B. dann eine zweite Verteilung für den (1,1) Block:
..#..#. statt
.#...#.tja - und jetzt hilft dir der Cache - weil wieder musst du dich fragen: hey ich bin an Stelle 10 - wie viele Möglichkeiten gibt es für den verbleibenden 3er Block ... und die Antwort weißt du dann schon.
Der Cache füllt sich dann auch sehr schnell, z.B. mit der Antwort für "ich bin an Stelle 4 im String -> wie viele Möglichkeiten gibt es eigentlich noch einen (1,3) er Block unterzubringen. Und in deinem Cache steht drinne, dass es aber der 4ten Position nur noch 2 Möglichkeiten gibt.
Dadurch verkürzen sich sehr schnell viele Berechnungsergebnisse.
-
by the way: ich selbst hatte auch einen eher simplen Weg für Part 1, der natürlich vorne und hinten nicht gut genug für Part 2 war.
Dann habe ich was neues für den 2ten Part geschrieben, dass hat die Demo korrekt berechnet, aber dann selbst für Teil 1 nicht mehr die richtigen Ergebnisse.
Dadurch dass ich über Teil1 aber richtig viele 'Testcases' hatte, konnte ich mir sehr schnell die kaputten Fälle raussuchen, und dann Stück für Stück 3 Bugs noch fixen.
-
@bluegaspode Prinzipiell verstehe ich deine Erklärung mit dem Cache ... ich habe nur keinen Schimmer wie ich das umsetzen könnte. Noch nicht. Bisher habe ich mir Teillösungen noch nicht gemerkt.
Woran teile ich zum merken? Oder schreibe ich mir jede Lösung weg und merke mir wieviel ich davon schon gelöst habe?Mhh, stimmt, wenn ich von Links nach rechts gehe:
.??..??...?##. 1,1,3wenn ich die erste 1 gelöst habe merke ich mir das. Und das es 2 Lösungen dafür gibt und probiere alles danach vorne nur mit den beiden Varianten?
Dann bin ich bei 1,1 und weis das es 4 Möglichkeiten gibt und teste den letzten Block bei dem es nur noch ein Treffer gibt.
Ach ist auch Müll, das wird spätestens bei?#?#?#?#?#?#?#? 1,3,1,6scheitern wenn da
?#?#?#?#?#?#?#???#?#?#?#?#?#?#???#?#?#?#?#?#?#???#?#?#?#?#?#?#???#?#?#?#?#?#?#? 1,3,1,6,1,3,1,6,1,3,1,6,1,3,1,6,1,3,1,6draus wird ...
-
Es wird meist mit einem rekursiven Ansatz gemacht, der teilt das Problem in kleinere Probleme.
Mal ein ganz einfaches Beispiel, mit nur 4 Stellen
##.# 2,1Du schreibst eine Funktion:
'anzahlLoesungenFuer(text, gruppen)'Du guckst dir in der Funktion immer nur den Start an, hier also Stelle 0 im Text und findest das '#' - und denkst 'super - ich suche einen 2er Block, hier ist eine #, das passt doch super zusammen'.
Jetzt stell dir vor, du hättest ein Funktion, die dir beantwortet, wie viele Lösungen es für das Beispiel:
#.# 1,1
gibt (das ist der hintere Teil von deinem Text).Aber hey - so eine Funktion hast du schon, die hast du gerade angefangen zu schreiben - du musst dich also nur selbst (mit manipuliertem verkürzten String und manipulierten verkürzten Gruppen) aufrufen.
Und so hangelst du dich durch einige Fälle durch.
Das nächste was du für
#.# 1,1
brauchst ist die Frage:- ich habe auf Position 0 die '#' gefunden. Das passt zu dem '1' er Block, der gesucht wird.
- ABER: der 1er Block wird nur erfüllt, wenn nach der '#' auch ein '.' (oder '?') kommt. Wenn es hier zwei '##' gibt, gibt es keine Lösung mehr, und ich liefere als Funktion einfach '0 Lösungen für diesen Fall' zurück.
Hier passt es, also kannst du deinen String jetzt um 2 Zeichen kürzen ('#.'). Da die eine Gruppe 'fertig' rufst du dich jetzt auf mit "anzahlLoesungenFuer('#', '1')" und hierfür liefert dir die Funktion zurück, dass es eine passende Lösung gibt.
Wenn du das so geschrieben hast, sollte es dir Teil 1 weiterhin korrekt ausrechnen, dein Code ist nur etwas länger geworden.
ABER: jetzt kannst du den Cache einbauen (einfach als weiteren Parameter der überall durchgeschleift wird).
Am Anfang der Funktion fragst du den Cache "gibt es schon eine Lösung für '#.# 1,1'" und kannst sofort zurückkehren falls ja.Falls nein, machst du deine Berechnung und packst am Ende der Funktion den Wert in den Cache.
Dieser Text ist dafür da, dass es (hoffentlich?) anschaulich wird, wie sich die Funktion immer wieder selbst mit einem verkleinerten String aufrufen kann.
Ich selbst habe es (subtil) anders gemacht. Damit ich nicht immer Strings kopieren kürzen muss, heißt meine Funktion "zaehleLoesungen(text, startPosition, gruppen).
Ich gebe also immer den gleichen Text rein und erhöhe immer nur die startPosition, kommt dann aber aufs gleiche hinaus. -
Vielleicht noch das Beispiel:
?#?#?#?#?#?#?#?du rufst die Funktion natürlich zuerst mit dem vollen String auf:
anzahlLoesungen('?#?#?#?#?#?#?#?', '1,3,1,6')deine Funktion ruft sich in kleinen Schritten aber erstmal so lange selber auf, bis du bei der Frage gelandet bist (das hintere Ende vom Text):
anzahlLoesungen('#?#?#?', '6')
und selbst das wird immer kleiner, bis du bei der Frage
anzahlLoesungen ('?', 1)
angelangt bist (das allerletzte Ende mit verkleinerter Restgruppe).
Und dieses Problem ist soooo klein, dass du sagen kannst "passt, es gibt für dieses kleine Problem genau eine Lösung").
Das ist tatsächlich das erste was in deinem Cache landet, die Rekursion sorgt also subtil dafür, dass das Problem eigentlich 'von hinten' gelöst wirst.Aber dann arbeitet sich das Programm Stück für Stück in die höheren Ebenen zurück, irgendwann wird der Cache für
anzahlLoesungen('#?#?#?', '6') gefüllt sein (auch nur 1 Lösung)und dann tobt sich das Programm an den ganzen Fragezeichen noch weiter vorne aus.
-
@bluegaspode Ich danke dir für deine Erklärungen, mal schauen was ich da bauen kann.
AutoIt Skaliert ja "schlecht", Rekursion maximal 3850 mal, mir fiel dann aber eine Methode ein es doch zu skalieren, hatte ich schon mal so gemacht.AutoIt ist schlecht in "parallel machen".
Eine Zeile abzukopfen ist von der CPU quasi nicht messbar, aber ich kann mit einem Trick dann doch einfach alle 1000 Zeilen gleichzeitig berechnen bzw. zumindest in Teilen.
Mein Programm wird kompiliert und mit Parametern aufgerufen. Der erste Aufruf liest die Textdatei ein und startet sich einfach 10, 100, 500 oder 1.000 mal mit je einer Zeile als Aufgabe. Ich kann dabei sogar die Zeilen Aufteilen, das ein Prozess die Möglichkeiten 1 bis 100.000 rechnet und der nächste 100.001 bis 200.000Aber da haben wir das nächste Problem, die Möglichkeiten sind inzwischen so groß das er die mir z.B. als
$i_possibilitiesTotal: 6.04462909807315e+23darstellt (2 hoch 79), das passt leider nicht zu meinem Prüfalgorithmus der auf der binären Darstellung der Möglichkeit basiert.Mal schauen ob ich den Stern noch schaffe.
-
@bananajoe hhhmm - also die Gesamtsumme an Lösungen ist im Bereich:
4.500.100.000.000das müsstest du irgendwie in eine Zahl abgespeichert bekommen.
der 'Long' Dateintyp (was auch immer das bei AutoIT ist, reicht in der Regel dafür aus)Auch die Rekursionstiefe passt.
Der längste String im Input ist zu 20Zeichen lang, den machst du 5mal größer, sind 100 Zeichen.
Das ist deine maximale Rekursionstiefe (pro Zeichen = 1x Rekursion)Ich habe es auch anders gemacht, auf jeder Rekursionsstufe prüfe ich immer eine komplette Gruppe.
6 Gruppen * 5 = 30Das heißt ich bin bei Rekursionstiefe von 'nur' 30.
Der Algorithmus geht dann so
sucheLoesungen(pattern, startposition, gruppen[]) { // ab der Startposition, finde alle Positionen wo die allerste Gruppe von der Länge hinpassen könnte // für alle diese Positionen // neueStartPosition = ersteGruppeStartPositon + ersteGruppeLaenge+1 // neueGruppen = alteGruppen (ohne die erste, die wir gerade festgelegt haben) // ergebnis += sucheLoesungen (pattern, neueStartPosition, neue Gruppen) }und noch den Cache dazu, dass es für Teil2 passt.
-
@bluegaspode ich habe halt noch Brute Force ... Ich errechne die Anzahl der Möglichkeiten = 2 hoch Anzahl der Fragezeichen, z.B. 2 hoch 3 = 8
Davon ziehe ich einen ab weil es dann von 0 bis 7 geht. Dann also eine Schleife von 0 nach 7.
Anhand des Wertes erstelle ich die Binärdaten:0 = 000 1 = 001 2 = 010 3 = 011 usw.Und die Fragezeichen habe ich dann jeweils durch
.= 0 oder#= 1 ersetzt und dann geprüft ob das Ergebnis stimmt (als Stringvergleich )Skaliert halt extrem schlecht da komplett ohne Abkürzungen.
Das mit dem Cache leuchtet ja ein, wie ich den nutzen soll erschließet sich mir im Moment nicht und auch nicht woran ich bei?#?#?#?#?#?#?#???#?#?#?#?#?#?#???#?#?#?#?#?#?#???#?#?#?#?#?#?#???#?#?#?#?#?#?#? 1,3,1,6,1,3,1,6,1,3,1,6,1,3,1,6,1,3,1,6Gruppen setze.
Das muss im Moment auch geistig erst einmal bei mir sacken, so manches habe ich erst im 2 oder 3. Anlauf verstanden.
Das mit den Gruppen schein fast alle so gemacht zu haben und ich hab auch schon versucht es nach zu programmieren (dann hätte ich mir den Stern vielleicht noch gegönnt), stoße dabei auf an die Limits von AutoItDeine Beschreibungen waren nicht umsonst, es wurmt mich ja und will gelöst werden
-
Für alle, die in den letzten Tagen nicht so viel Spaß hatten. Teil 1 des heutigen Rätsels (Tag 14) ist sehr sehr sehr gut machbar.
aber bei Part2
-
doppelt
-
Ich weiß, das klingt jetzt ein bisschen nach Mimimi, aber mir kann keiner erzählen, dass SimonFischer04 die Lösung heute selbst programmiert hat. Teil 2 ist einfach ganz anders als Teil 1, so dass man nicht in 11 Sekunden zu einer Lösung kommen kann.
-
@ignis-draco naja, manchmal hat man noch fertigen Code aus einem anderen Projekt liegen der 1:1 passt. Ich schreibe im Grunde auch ständig wieder bei mir selber ab.
Und mein Ursprungscode ist ja auch ein Sammelsurium aus Fundstücken der letzten Jahrzehnte -
@BananaJoe 11 Sekunden um alten Code zu verwenden ???
Wenn es 3 Min oder so wären dann ja. Aber 11 Sekunden ?Ich habe konnte auch ein der einer Stelle Code von 2015 verwendenden aber auch da habe ich bestimmt 30 sek benötigt nur um die Datei zu finden in der das steht.
