@Manul: Theoretisch bin ich noch dabei, aber dieses Wochenende, genau wie letztes, hatte ich nicht so wirklich die Zeit/Ruhe.
Habe mir gerade die heutige Aufgabe angeschaut. So als erste Idee nach dem Lesen: Einfach so alle Wege ausprobieren dürfte laaaange dauern. Ich würde da auf Anhieb an einen Algorithmus denken, der in Spielen verwendet wird um den günstigsten Weg auf einer Karte von A nach B zu finden, wo es neben der Anzahl der Schritte noch unterschiedliche Kosten für die Bewegung auf ein Feld gibt. Da gibt's einen recht bekannten. Und da müsste man dann schauen die max-3-Schritte-in-die-gleiche-Richtung-Regel mit einzubauen. Das wäre mein Ansatz.
@kbr: `networkx` kann bei so etwas manchmal sehr hilfreich sein. Aber vielleicht nicht so sehr in diesem Fall. Den erwähnten Algorithmus gibt es dort zwar, aber da wäre dann die Frage ob man das mit der angebotenen API sinnvoll/einfach um die Zusatzregel mit den drei Schritten erweitern kann.
Advent of Code
-
__blackjack__
- User
- Beiträge: 13117
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
@Manul: Die Aufgabe heute ist eine Variation von einem Aufgabentyp, der eigentlich jedes Jahr drankommt. Bei mir war also Code Reuse angesagt. 
Die wichtige Optimierung für so eine Art von Aufgabe ist, nicht alle Pfade anzugucken, sondern möglichst viele davon möglichst früh auszusortieren. Oder einen der von __blackjack__ angesprochenen bekannten Algorithmen nachbauen.
Tag 10 hat mehrere interessante Lösungen. Mein erster Gedanke war „wenn die Aufgabenstellung sagt, dass man sich zwischen den Rohren durchzwängen kann, dann muss ich eben mehr Platz schaffen“. Ergo, alle Koordinaten verdoppeln und man hat zwischen jedem Feld ein neues Feld Platz, durch das ein Floodfill eingeschlossene äußere Bereiche erreichen kann. Damit muss man nicht darüber nachdenken, wie man aus dem Umriss ermittelt, ob etwas innen oder außen liegt.
Ein anderer sehr einfacher Ansatz ist, zeilenweise durch den Input zu gehen und mitzuzählen, wie oft man über den Umriss geht. Bei einer ungeraden Anzahl ist man innen, sonst außen.
Die wichtige Optimierung für so eine Art von Aufgabe ist, nicht alle Pfade anzugucken, sondern möglichst viele davon möglichst früh auszusortieren. Oder einen der von __blackjack__ angesprochenen bekannten Algorithmen nachbauen.
Tag 10 hat mehrere interessante Lösungen. Mein erster Gedanke war „wenn die Aufgabenstellung sagt, dass man sich zwischen den Rohren durchzwängen kann, dann muss ich eben mehr Platz schaffen“. Ergo, alle Koordinaten verdoppeln und man hat zwischen jedem Feld ein neues Feld Platz, durch das ein Floodfill eingeschlossene äußere Bereiche erreichen kann. Damit muss man nicht darüber nachdenken, wie man aus dem Umriss ermittelt, ob etwas innen oder außen liegt.
Ein anderer sehr einfacher Ansatz ist, zeilenweise durch den Input zu gehen und mitzuzählen, wie oft man über den Umriss geht. Bei einer ungeraden Anzahl ist man innen, sonst außen.
ich bin auch noch dabei und versuche die liegen gebliebenen Probleme aufzuholen. Aber irgendwie wird das so nichts: der erste Teil ist schnell hin geschmiert, aber beim zweiten Teil braucht es immer Stunden bis es bei mir Klick macht und der Groschen centweise fällt.
So, nun ist die Aufgabe vom 8. durch...
Ich fand's auf Dauer langweilig, immer irgendwelche Dinge mit Punkten und Rauten zu machen. War aber auch mein erstes AoC seit längerer Zeit, wo ich mal wieder ein paar Aufgaben mitgespielt habe. Ich weiß nicht warum, aber früher fand ich es spannender.
Ich bin noch dabei, wenn es die Zeit erlaubt.
MIr ist aufgefallen, dass die Aufgaben extrem verklausuliert erklärt werden, ganz anders als die Jahre vorher.
Ich gehe davon aus, dass dies gemacht wird, um die Nutzung von ChatGPT zu erschweren.
Ich weiß nicht, wie ich diejenigen im Leaderboard bewerten soll, die beide Aufgabenteile in einer Zeit lösen,
in der ich die Aufgabe noch nicht mal durchgelesen habe.
Supergenies oder GPT-Cheater?
MIr ist aufgefallen, dass die Aufgaben extrem verklausuliert erklärt werden, ganz anders als die Jahre vorher.
Ich gehe davon aus, dass dies gemacht wird, um die Nutzung von ChatGPT zu erschweren.
Ich weiß nicht, wie ich diejenigen im Leaderboard bewerten soll, die beide Aufgabenteile in einer Zeit lösen,
in der ich die Aufgabe noch nicht mal durchgelesen habe.
Supergenies oder GPT-Cheater?
Ich bin Pazifist und greife niemanden an, auch nicht mit Worten.
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
Weder noch (Zumindest nicht grundsätzlich). Genauso wie es Leute gibt, die in Hochgeschwindigkeit Zauberwürfel lösen oder Tetris durchspielen, gibt es eben auch Leute, die das "wettbewerbsmäßige Programmieren" zum Sport erhoben haben. (https://en.wikipedia.org/wiki/Competitive_programming). Wäre zwar nichts für mich, aber das kann man vermutlich wie jede andere Sportart auch üben und trainieren. Ich denke, das hat mit "regulärem" Programmieren, das man Hobby- oder Berufs-mäßig betreibt nicht so viel zu tun und deswegen sollte man sich mit den "Profis" – genau wie in jeder anderen Sportart – gar nicht vergleichen, finde ich.
Zuletzt geändert von nezzcarth am Montag 18. Dezember 2023, 17:05, insgesamt 1-mal geändert.
-
__blackjack__
- User
- Beiträge: 13117
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
@nezzcarth: Vielleicht auch ”Supergenies” + spezialisierte Unterstützung. Also nicht so etwas allgemeines wie Chat-GPT, sondern vielleicht was eigenes trainiertes mit den Aufgaben der vergangenen AoCs. Und da oft ähnliche Aufgaben wie aus den Vorjahren gestellt werden, haben die vielleicht auch schon vorbereitete Bibliotheken am Start wo sie geschaut haben was so die typischen Algorithmen und Hilfsfunktionen sind, die man schon vorgefertigt in der Schublade liegen haben sollte.
Das geht ja auch so in Richtung Sportler die das Training auf der Analyse von vorherigen Ereignissen aufbauen.
Das geht ja auch so in Richtung Sportler die das Training auf der Analyse von vorherigen Ereignissen aufbauen.
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
Zur 9. Aufgabe Teil 1: nach 2 Uhr nachts sollte ich wohl doch lieber nicht mehr programmieren. Da entfallen dann vielleicht solche überflüssigen Felher die sich dann erst am nächsten Morgen auflösen. Der Testfall 0 -1 -1 0 (erwartes Ergebnis: 2) war da sehr hilfreich. Musste ich bei Reddit sehr weiter runterscrollen um den zu finden.grubenfox hat geschrieben: ↑Montag 18. Dezember 2023, 00:52ich bin auch noch dabei und versuche die liegen gebliebenen Probleme aufzuholen. Aber irgendwie wird das so nichts: der erste Teil ist schnell hin geschmiert, aber beim zweiten Teil braucht es immer Stunden bis es bei mir Klick macht und der Groschen centweise fällt.
So, nun ist die Aufgabe vom 8. durch...
Und wieder lagen Stunden zwischen der Lösung 1 und der Lösung des zweiten Teils. Aber diesmal nicht weil ich lange nachdenken musste, am Montag kam mir dann das normale Wochentags-Leben (normale Einkäufe, Weihnachtseinkäufe, ....) dazwischen.
Und jetzt Aufgabe 10: 'Drums and Pipes'.. oder doch nur 'Pipes'? Das muss ich wohl zwei oder dreimal lesen um es zu verstehen...was will er da von mir? Aber hier im Forum habe ich weiter oben schon ein paar dazugehörige Kommentare überflogen.... sollte machbar sein.
Also, noch bin ich dabei!
@alle: Danke für die Hinweise zu Tag 17! Den von @__blackjack__ erwähnten Algorithmus habe ich - denke ich - identifiziert, aber noch nicht angeschaut, ich möchte erst noch mal ausprobieren, wie weit ich mit meinem eigenen Ansatz komme. Abbruchbedingungen, um nicht alle möglichen Wege untersuchen zu müssen, habe ich drin, und mit etwas draufgesetztem Caching läuft es mittlerweile relativ schnell durch. Nur das Ergebnis stimmt leider noch nicht, da muss ich noch etwas debuggen, denke aber, ich bin auf einem guten Weg.
Mein eigener Ansatz für Tag 10 war, zuerst vom Rand des Feldes aufzufüllen und dann den gefundenen Pfad abzugehen, bis ich auf einer Seite auf ein Feld stoße, das "außen" liegt. Anschließend dann alle weiteren Felder auf dieser Seite des Pfades nehmen, die noch nicht als "außen" markiert sind, und von denen aus aufzufüllen.
Gestern habe ich dann zum ersten mal attr verwendet, auch das war ein guter Tip, ich denke ebenfalls von @__blackjack__ - spart einem wirklich einiges an boiler plate-Code.
Heute bin ich allerdings wieder dicht am Aufgeben: Teil 1 war relativ trivial, auch wenn ich erst darüber gestolpert bin, daß die Beispiele eine Eigenschaft des Systems nahelegen, die zumindest meine Eingabedaten nicht aufweisen. Bei Teil 2 scheitere ich dagegen glorreich: Auch in über zwei Stunden Laufzeit bekomme ich kein Ergebnis. Ich nehme an, ich übersehe hier wieder eine Eigenschaft der Eingabedaten, habe auch ein grobes Gefühl, in welche Richtung das gehen könnte, komme aber selbst mit Ansätzen einer Visualisierung nicht dahinter. Hat von Euch jemand eine Lösung und kann darauf basierend einen Tip geben?
Diesen Ansatz habe ich für Tag 18 ausprobiert - und bin dabei noch auf einen Fallstrick gestossen, den ich nicht auf Anhieb gesehen hatte. Ließ sich aber lösen.narpfel hat geschrieben: ↑Sonntag 17. Dezember 2023, 19:34 Ein anderer sehr einfacher Ansatz ist, zeilenweise durch den Input zu gehen und mitzuzählen, wie oft man über den Umriss geht. Bei einer ungeraden Anzahl ist man innen, sonst außen.
Mein eigener Ansatz für Tag 10 war, zuerst vom Rand des Feldes aufzufüllen und dann den gefundenen Pfad abzugehen, bis ich auf einer Seite auf ein Feld stoße, das "außen" liegt. Anschließend dann alle weiteren Felder auf dieser Seite des Pfades nehmen, die noch nicht als "außen" markiert sind, und von denen aus aufzufüllen.
Gestern habe ich dann zum ersten mal attr verwendet, auch das war ein guter Tip, ich denke ebenfalls von @__blackjack__ - spart einem wirklich einiges an boiler plate-Code.
Heute bin ich allerdings wieder dicht am Aufgeben: Teil 1 war relativ trivial, auch wenn ich erst darüber gestolpert bin, daß die Beispiele eine Eigenschaft des Systems nahelegen, die zumindest meine Eingabedaten nicht aufweisen. Bei Teil 2 scheitere ich dagegen glorreich: Auch in über zwei Stunden Laufzeit bekomme ich kein Ergebnis. Ich nehme an, ich übersehe hier wieder eine Eigenschaft der Eingabedaten, habe auch ein grobes Gefühl, in welche Richtung das gehen könnte, komme aber selbst mit Ansätzen einer Visualisierung nicht dahinter. Hat von Euch jemand eine Lösung und kann darauf basierend einen Tip geben?
@Manul: Heute war echt nicht einfach, finde ich. Für Teil 2 hat es mir geholfen, mir die Eingabedaten genau anzugucken. Einen guten Tipp kann ich nicht geben, außer vielleicht, es mit weniger Eingabedaten zu probieren. Also entweder selbst einen Input schreiben, der interessant genug, aber gleichzeitig nicht zu aufwändig zu bruteforcen ist, oder den gegebenen Input so zu modifizieren, dass er einfacher wird. Und sich den Zustand des Systems über die Zeit hinweg anzugucken. Und guck dir das Verhalten der einzelnen Modul-Typen an. Was muss passieren, damit die jeweils ein bestimmtes Ausgabesignal erzeugen? Mit Brute Force wirst du nicht ans Ergebnis kommen: Mein (unoptimierter) Code schafft eine Million Knopfdrücke pro Sekunde, und damit würde es mehrere Jahre dauern, das Ergebnis zu finden.
Noch mal ein Zwischenstand meinerseits: Tag 17 habe ich mittlerweile gelöst - i.W. mit meinem ursprünglichen Code und ein paar zusätzlichen Abbruchbedingungen für die Suche. Damit läuft der Code für beide Teile in zwar immer noch recht langer aber für eine einmalige Lösung vertretbarer Zeit durch.
Tag 20 habe ich inzwischen auch, da habe ich wieder ein bisschen das gleiche Problem wie bei Tag 8: Die Lösung setzt eine Eigenschaft der Eingabedaten voraus, die weder in der Aufgabenstellung erwähnt noch anhand der Daten direkt ersichtlich ist. Nach (etwas mühsamer händischer) Analyse der Daten kommt man dann relativ schnell auf eine Lösung, die aber eben nur für Daten funktioniert, die eben diese Eigenschaft aufweisen.
Tag 21 fand ich etwas frustrierend: Teil 1 war relativ einfach, bei Teil 2 ist mir der Lösungsweg im Prinzip klar, ich habe aber das Gefühl, dabei so viele Spezialfälle betrachten zu müssen, daß ich eigentlich keine Lust darauf habe. Hier würde mich interessieren, ob jemand von Euch eine Lösung hat und wie die aussieht. Vielleicht übersehe ich ja wieder was Triviales.
Heute habe ich den ersten Teil noch mit brute force lösen können, für den 2. hat das dann nicht mehr funktioniert. Hier habe ich mich an den Tip zu Tag 17 erinnert und networkx verwendet, was relativ straightforward war. Auch damit läuft mein Code für die echten Eingabedaten noch knappe 5 Minuten, gibt die gefundenen Lösungen dafür aber graphisch in weihnachtlichen Farben aus.
Ansonsten hat sich die Verwendung von attr bei mir in den letzten Tagen etabliert, finde ich nach wie vor praktisch. Wobei ich nicht ausschließen kann, daß ich's derzeit noch etwas exzessiv einsetze - sieht halt allen nach Nagel aus, wenn man einen neuen Hammer hat.
Meinen Code teile ich natürlich gerne, wenn jemand Interesse hat, möchte das Forum aber nicht ungefragt damit überschwemmen.
Euch allen schöne Weihnachten!
Tag 20 habe ich inzwischen auch, da habe ich wieder ein bisschen das gleiche Problem wie bei Tag 8: Die Lösung setzt eine Eigenschaft der Eingabedaten voraus, die weder in der Aufgabenstellung erwähnt noch anhand der Daten direkt ersichtlich ist. Nach (etwas mühsamer händischer) Analyse der Daten kommt man dann relativ schnell auf eine Lösung, die aber eben nur für Daten funktioniert, die eben diese Eigenschaft aufweisen.
Tag 21 fand ich etwas frustrierend: Teil 1 war relativ einfach, bei Teil 2 ist mir der Lösungsweg im Prinzip klar, ich habe aber das Gefühl, dabei so viele Spezialfälle betrachten zu müssen, daß ich eigentlich keine Lust darauf habe. Hier würde mich interessieren, ob jemand von Euch eine Lösung hat und wie die aussieht. Vielleicht übersehe ich ja wieder was Triviales.
Heute habe ich den ersten Teil noch mit brute force lösen können, für den 2. hat das dann nicht mehr funktioniert. Hier habe ich mich an den Tip zu Tag 17 erinnert und networkx verwendet, was relativ straightforward war. Auch damit läuft mein Code für die echten Eingabedaten noch knappe 5 Minuten, gibt die gefundenen Lösungen dafür aber graphisch in weihnachtlichen Farben aus.
Ansonsten hat sich die Verwendung von attr bei mir in den letzten Tagen etabliert, finde ich nach wie vor praktisch. Wobei ich nicht ausschließen kann, daß ich's derzeit noch etwas exzessiv einsetze - sieht halt allen nach Nagel aus, wenn man einen neuen Hammer hat.
Meinen Code teile ich natürlich gerne, wenn jemand Interesse hat, möchte das Forum aber nicht ungefragt damit überschwemmen.
Euch allen schöne Weihnachten!
@Manul: Der Trick bei Tag 21 Teil 2 ist, dass sich das Muster immer wieder wiederholt. Man muss also nur weit genug simulieren, bis man den Rest extrapolieren (*hint* *hint*) kann. Spezialfälle muss man auch nicht wirklich beachten. Nimm dir einfach mal den Beispielinput und simulier den für ... ein paar hundert Schritte und guck dir die Werte an, die dabei rauskommen. Wenn du die Daten richtig massierst, sollte dir was bekanntes auffallen. 
@narpfel: Danke für den Hinweis! Daß die Wiederholung der Schlüssel ist, ist mir auch klar, ich habe nur noch nicht das passende Schloß dazu gefunden.
Für eine 19x19-fache Version des Beispielinputs sieht das bei mir so aus (Anzahl Schritte und Anzahl möglicher Positionen):
[fehlerhafte Ausgabe gelöscht]
Dann bin ich am Rand des großen Feldes. Ich erkenn da nix.
Interessant. Ich hätte gedacht, daß man die Asymmetrie, die die teilweise durch Felsen versperrten Wege erzeugen, berücksichtigen muss.
@edit: Das folgende ist Quatsch, hatte noch einen Fehler im Code zum Bilden des Mosaiks...
Für eine 19x19-fache Version des Beispielinputs sieht das bei mir so aus (Anzahl Schritte und Anzahl möglicher Positionen):
[fehlerhafte Ausgabe gelöscht]
Dann bin ich am Rand des großen Feldes. Ich erkenn da nix.
Mein aktueller Zwischenstand: Mir fehlen 2 Sterne.
Bei Tag 21, Teil 2, komme ich nach wie vor auf keinen grünen Zweig. Ich habe die Zahlen für die ersten paar hundert Schritte wirklich lange angestarrt, konnte bis jetzt aber kein Muster erkennen. Irgendwie stehe ich da auf dem Schlauch.
Tag 24, Teil 2, werde ich wohl ebenfalls nicht gelöst bekommen. Für eine analytische Lösung bin ich entweder zu doof oder nicht ausdauernd genug. Ein brute force-Ansatz, der für die Beispieldaten funktioniert, läuft noch, ich bezweifle aber, daß der zum Ziel führt. Interessehalber @diejenigen, die Teil 2 gelöst haben: Was sind bei Euch die Zeitpunkte der ersten beiden Kollisionen?
Für heute war wieder networkx recht praktisch, das liefert einem die Lösung quasi frei Haus.
Habt weiterhin schöne Weihnachten!
Bei Tag 21, Teil 2, komme ich nach wie vor auf keinen grünen Zweig. Ich habe die Zahlen für die ersten paar hundert Schritte wirklich lange angestarrt, konnte bis jetzt aber kein Muster erkennen. Irgendwie stehe ich da auf dem Schlauch.
Tag 24, Teil 2, werde ich wohl ebenfalls nicht gelöst bekommen. Für eine analytische Lösung bin ich entweder zu doof oder nicht ausdauernd genug. Ein brute force-Ansatz, der für die Beispieldaten funktioniert, läuft noch, ich bezweifle aber, daß der zum Ziel führt. Interessehalber @diejenigen, die Teil 2 gelöst haben: Was sind bei Euch die Zeitpunkte der ersten beiden Kollisionen?
Für heute war wieder networkx recht praktisch, das liefert einem die Lösung quasi frei Haus.
Habt weiterhin schöne Weihnachten!
@Manul: Zu Tag 21 Teil 2: Der Garten wiederholt sich mit einer bestimmten Frequenz, also sollte man das Muster in den Werten auch mit mit dieser Frequenz (oder einer ähnlichen Frequenz (? Wenn ja, welche und warum?)) suchen. Hast du dir das mal geplottet? Die Schrittanzahl auf der x-Achse, die Anzahl der erreichbaren Felder auf der y-Achse? Wonach sieht das aus? Und welche Eigenschaften hat so eine Funktion?
Tag 24 Teil 2 hat eine analytische Lösung, die man wahrscheinlich auch manuell finden kann (Hint: Wie viele Unbekannte hat das Gleichungssystem und wie viele Gleichungen braucht man dafür?), oder man benutzt ein Programm dafür, das automatisch Gleichungssysteme lösen kann. Oder, mit noch weniger Nachdenken, `z3`. Brute Force wird nicht funktionieren, der Zeitpunkt der ersten Kollision ist bei mir 57840424538.
Tag 24 Teil 2 hat eine analytische Lösung, die man wahrscheinlich auch manuell finden kann (Hint: Wie viele Unbekannte hat das Gleichungssystem und wie viele Gleichungen braucht man dafür?), oder man benutzt ein Programm dafür, das automatisch Gleichungssysteme lösen kann. Oder, mit noch weniger Nachdenken, `z3`. Brute Force wird nicht funktionieren, der Zeitpunkt der ersten Kollision ist bei mir 57840424538.
Tag 21 habe ich jetzt. Uff! EIn Fehler, den ich gemacht habe, war, mir erst die Entwicklung mit den Beispieldaten anzusehen. Die sind aber anders strukturiert als die wirklichen Inputdaten und weisen zusätzliche Asymmetrien auf. Dann habe ich mir das ganze visualisiert und dabei beim Abzählen der Parität einen Fehler gemacht. Und als ich dann schließlich sicher war, die richtige Lösung zu haben, kamen trotzdem noch nicht die richtigen Zahlen raus. Auf den letzten Fehler, den ich in meinen Annahmen gemacht hatte, kam ich dann nur durch Spicken bei Reddit...
Bei Tag 24 bin ich noch nicht weiter. Ich bin mit der analytischen Lösung so weit, daß ich glaube, die richtige Anzahl Gleichungen für die richtige Anzahl Variablen zu haben. Das von Hand zu lösen, ist mir allerdings zu mühsam (falls ich es überhaupt hinbekommen würde), und ein System, das die Gleichungen automatisch lösen kann, muss ich mir erst suchen.
Bei Tag 24 bin ich noch nicht weiter. Ich bin mit der analytischen Lösung so weit, daß ich glaube, die richtige Anzahl Gleichungen für die richtige Anzahl Variablen zu haben. Das von Hand zu lösen, ist mir allerdings zu mühsam (falls ich es überhaupt hinbekommen würde), und ein System, das die Gleichungen automatisch lösen kann, muss ich mir erst suchen.