Advent of Code 2024

[Woy]

MueR schreef op vrijdag 6 december 2024 @ 10:19:
[...]

CPU go brrrrr is toch prima?

Mijn dag 6 doet ook redelijk brr.

spoiler:

Jouw implementatie doet nog wel iets meer brrrr, en ik kan mij voorstellen dat er inputs zijn waar hij uberhaupt niet werkt, want je detecteert niet echt of er een loop is, maar of er na 1000 stappen nog niet uit het veld gestapt is

Overigens wel een goed idee om al mijn cores brrr te laten doen, dat zou het weer zo'n factor 10 sneller moeten maken inderdaad

[MueR]

Woy schreef op vrijdag 6 december 2024 @ 10:25:
[...]

spoiler:

Jouw implementatie doet nog wel iets meer brrrr, en ik kan mij voorstellen dat er inputs zijn waar hij uberhaupt niet werkt, want je detecteert niet echt of er een loop is, maar of er na 1000 stappen nog niet uit het veld gestapt is

Overigens wel een goed idee om al mijn cores brrr te laten doen, dat zou het weer zo'n factor 10 sneller moeten maken inderdaad

spoiler:

True, ik doe een aanname dat er een finite aantal stappen is voordat er een loop is. Zou ik wel aan kunnen passen, maar ik moest het even snel afraffelen voor een meeting

[bakkerjangert]

Woy schreef op vrijdag 6 december 2024 @ 10:25:
[...]

spoiler:

Jouw implementatie doet nog wel iets meer brrrr, en ik kan mij voorstellen dat er inputs zijn waar hij uberhaupt niet werkt, want je detecteert niet echt of er een loop is, maar of er na 1000 stappen nog niet uit het veld gestapt is

Overigens wel een goed idee om al mijn cores brrr te laten doen, dat zou het weer zo'n factor 10 sneller moeten maken inderdaad

Nu ik daar zo over nadenk zou dat voor dit probleem moeten kunnen werken.

spoiler:

Ik zou dan wel de limiet op minimaal aantal rijen x aantal kolommen x 4 richtingen zetten, eventueel gereduceerd met het aantal blokkades x 4 richtingen. Dan is elke mogelijkheid binnen de loop mogelijk. Bij mijn input zou dat 67600 zijn.

[Mugwump]

Mijn input vindt brute forcen niet zo leuk. Dus voor wie wil testen, zie hier.

[MueR]

Mugwump schreef op vrijdag 6 december 2024 @ 10:35:
Mijn input vindt brute forcen niet zo leuk. Dus voor wie wil testen, zie hier.

Parsed input in 160ns
Part 1 output: xxx9 (394.091µs)
Part 2 output: xxx5 (301.092634ms)
Gaat prima?

[Mugwump]

MueR schreef op vrijdag 6 december 2024 @ 10:40:
[...]

Parsed input in 160ns
Part 1 output: xxx9 (394.091µs)
Part 2 output: xxx5 (301.092634ms)
Gaat prima?

Klopt je input dan nog wel aangezien je max 1000 steps doet?

Edit: je zou op 1915 uit moeten komen voor deel 2.

[ Voor 8% gewijzigd door Mugwump op 06-12-2024 11:21 ]

[MueR]

Mugwump schreef op vrijdag 6 december 2024 @ 10:44:
[...]


Klopt je input dan nog wel aangezien je max 1000 steps doet?

Edit: je zou op 1915 uit moeten komen voor deel 2.

Daar kwam ik op uit ja.

[Janoz]

Woy schreef op vrijdag 6 december 2024 @ 10:25:
Overigens wel een goed idee om al mijn cores brrr te laten doen, dat zou het weer zo'n factor 10 sneller moeten maken inderdaad

Verrek, helemaal niet aan gedacht. 1 stream() vervangen door een parallelStream() en inderdaad bijna 10x zo snel

[Mugwump]

MueR schreef op vrijdag 6 december 2024 @ 11:22:
[...]

Daar kwam ik op uit ja.

Hmm, dat is wel bijzonder als je na 1000 steps terminate. Want ik heb b.v. dit soort scenario's (0-based indexing ):

Exited grid with more than 1000 locations visited(6088) for obstacle placed at 73, 128
Exited grid with more than 1000 locations visited(6110) for obstacle placed at 73, 129

Als ik jouw oplossing goed lees zou dit een loop moeten opleveren, omdat de route meer dan 1000 stappen heeft. Of check je riching van de guard niet en gaat dat toevallig goed?

[Soultaker]

Voor wie wil benchmarken, hier wat extra grote invoer voor dag 6: aoc-2024-day-06-challenge-1-to-3.zip3

Antwoorden en referentietijden (in C++, mijn Python code is traag):

$ time ./solve < aoc-2024-day-06-challenge-1.txt
...18
...93

real    0m0.130s
user    0m0.124s
sys     0m0.006s

$ time ./solve < aoc-2024-day-06-challenge-2.txt
...13
...95

real    0m0.039s
user    0m0.037s
sys     0m0.002s

$ time ./solve < aoc-2024-day-06-challenge-3.txt
...261
...426

real    0m12.472s
user    0m12.419s
sys     0m0.017s

[Friits]

@Soultaker Met de hierboven besproken optimalisaties (en een klein extraatje):

data.txt (mijn puzzel-input)      50ms
aoc-2024-day-06-challenge-1.txt   3.5s
aoc-2024-day-06-challenge-1.txt   0.5s
aoc-2024-day-06-challenge-1.txt   ~10s

De code hiervoor is vreselijk lelijk; daar wil ik m'n naam niet bij hebben staan

[MueR]

Mugwump schreef op vrijdag 6 december 2024 @ 12:00:
[...]


Hmm, dat is wel bijzonder als je na 1000 steps terminate. Want ik heb b.v. dit soort scenario's (0-based indexing ):


[...]


Als ik jouw oplossing goed lees zou dit een loop moeten opleveren, omdat de route meer dan 1000 stappen heeft. Of check je riching van de guard niet en gaat dat toevallig goed?

Ik doe geen max 1000 stappen he, ik terminate na max 1000 previously visited tiles..

[Mugwump]

MueR schreef op vrijdag 6 december 2024 @ 13:01:
[...]

Ik doe geen max 1000 stappen he, ik terminate na max 1000 previously visited tiles..

Ah dan las ik het verkeerd. Dus dat zou alleen misgaan als er een loop in zit die meer dan 1000 tiles groot is.

Blijft bijzonder.

spoiler:

Ik heb echt een enorm performancehit zonder de optimalisatie om enkel de bezochte draaipunten vast te houden ipv de hele lijst van bezochte locatie+richting combinaties.

Had. nog een klein slordigheidje in de code zitten omdat ik voor het vaststellen van een loop heel lui gewoon domweg de size van een list vergeleek met de size van een set van die list (waarbij dubbelen wegvallen natuurlijk) en dat is niet bepaald efficiënt bij grotere hoeveelheden elementen.

Na dat even wat netter te doen blijft echter m'n ongeoptimaliseerde versie er pakweg 21 seconden over doen tegenover 500ms voor de geoptimaliseerde variant.

Go is natuurlijk wel iets sneller dan Kotlin voor dit soort dingen, maar toch.

[MueR]

Hmm, om de grote inputs te doen moet ik de hele boel op de schop gooien. Momenteel als ik die probeer te runnen slaat mn laptop vast op deel 2 Iets te veel goroutines die tegelijkertijd willen gaan lopen.

[Mugwump]

Soultaker schreef op vrijdag 6 december 2024 @ 12:40:
Voor wie wil benchmarken, hier wat extra grote invoer voor dag 6: aoc-2024-day-06-challenge-1-to-3.zip3

Antwoorden en referentietijden (in C++, mijn Python code is traag):

$ time ./solve < aoc-2024-day-06-challenge-1.txt
...18
...93

real    0m0.130s
user    0m0.124s
sys     0m0.006s

$ time ./solve < aoc-2024-day-06-challenge-2.txt
...13
...95

real    0m0.039s
user    0m0.037s
sys     0m0.002s

$ time ./solve < aoc-2024-day-06-challenge-3.txt
...261
...426

real    0m12.472s
user    0m12.419s
sys     0m0.017s

M'n Kotlincode komt tot:
0.45s
0.12s
1m49s

[breew]

Ik loop ff vast op deel 2.
Deel 1 correct.

mijn denkwijze (ik ga het proberen uit te leggen):

spoiler:

deel 1:
1. Begin te lopen in de startrichting
2. Houd elke stap bij welke richting (up, right, down, left) je beweegt en kijk wat de eerstvolgende barrier is (geen barrier, dan loop je het veld uit en klaar) in de looprichting (gebaseerd op rij/kolom positie in een matrix)
3. kom je een barrier tegen, verander de looprichting up > right > down > left > up, herhaal 2+3 tot je het veld uit bent

deel 2
1. doe eerst alle stappen van deel 1, om alle stappen van een pad te maken
2. kijk bij elke stap 90 graden naar rechts (loop je dus "up", kijk dan naar "right".. loop je "left" kijk dan naar "up").ga na of je in de kijkrichting een barrier ziet (neem alleen de eerste die je ziet, niet die daarachter).
3. kijk in alle voorgaande stappen al stappen zijn die in de richting van die barrier gaan (dus kijk je "left", dan moeten er ook eerder stappen naar die barrier met richting "left" zijn gemaakt.
4. zo ja (bij 3), dan kan je 1 stapje verder een nieuw obstakel plaatsen, om ene loop te maken
5. sla de positie van het nieuwe obstakel op
6. neem alleen de unieke posities van het obstakel

voor de testinvoer klopt dit

maar dan krijg ik een te laag getal voor deel 2....
Klopt mijn logica wel? Of mis ik iets?

[Janoz]

breew schreef op vrijdag 6 december 2024 @ 15:13:
Ik loop ff vast op deel 2.
Deel 1 correct.

mijn denkwijze (ik ga het proberen uit te leggen):

spoiler:

deel 1:
1. Begin te lopen in de startrichting
2. Houd elke stap bij welke richting (up, right, down, left) je beweegt en kijk wat de eerstvolgende barrier is (geen barrier, dan loop je het veld uit en klaar) in de looprichting (gebaseerd op rij/kolom positie in een matrix)
3. kom je een barrier tegen, verander de looprichting up > right > down > left > up, herhaal 2+3 tot je het veld uit bent

deel 2
1. doe eerst alle stappen van deel 1, om alle stappen van een pad te maken
2. kijk bij elke stap 90 graden naar rechts (loop je dus "up", kijk dan naar "right".. loop je "left" kijk dan naar "up").ga na of je in de kijkrichting een barrier ziet (neem alleen de eerste die je ziet, niet die daarachter).
3. kijk in alle voorgaande stappen al stappen zijn die in de richting van die barrier gaan (dus kijk je "left", dan moeten er ook eerder stappen naar die barrier met richting "left" zijn gemaakt.
4. zo ja (bij 3), dan kan je 1 stapje verder een nieuw obstakel plaatsen, om ene loop te maken
5. sla de positie van het nieuwe obstakel op
6. neem alleen de unieke posities van het obstakel

voor de testinvoer klopt dit

maar dan krijg ik een te laag getal voor deel 2....
Klopt mijn logica wel? Of mis ik iets?

Een nieuwe route hoeft niet gelijk op de bestaande route uit te komen. Hou zou best nog één of meer keer kunnen botsen op bestaande obstakels.

[TrailBlazer]

Janoz schreef op vrijdag 6 december 2024 @ 15:42:
[...]

Een nieuwe route hoeft niet gelijk op de bestaande route uit te komen. Hou zou best nog één of meer keer kunnen botsen op bestaande obstakels.

ah crap ik heb dezelfde fout inderdaad

code:

          if data[(pos[0]+next_dir[direction][0]*j,pos[1]+next_dir[direction][1]*j)] == "#":
            break

ik moet dit dus gewoon verder uitwerken.

[deboder]

MueR schreef op vrijdag 6 december 2024 @ 10:26:
[...]

spoiler:

True, ik doe een aanname dat er een finite aantal stappen is voordat er een loop is. Zou ik wel aan kunnen passen, maar ik moest het even snel afraffelen voor een meeting

Ja, M*N max lijkt me ( min een aantal minimale blokkades )

[Soultaker]

deboder schreef op vrijdag 6 december 2024 @ 16:20:
Ja, M*N max lijkt me ( min een aantal minimale blokkades )

4×hoogte×breedte is de voor de hand liggende bovengrens, aangezien je elke cel van vier kanten kunt binnenkomen, maar een test case waarbij je (bijna) zoveel stappen kunt zetten is lastig te constructeren. Meer dan hoogte×breedte is wel mogelijk.

[ Voor 7% gewijzigd door Soultaker op 06-12-2024 17:42 ]

[Satom]

Bedankt voor de heads up @Soultaker. In eerste instantie had ik ook hoogte x breedte gedaan en ergens voelde dat wel "geluk hebben dat het werkt". Het antwoordt werd geaccepteerd, dus daar bij gelaten. Ik heb voor de zekerheid zojuist nog de x4 toegevoegd en dan duurt nu +- 1,2 sec ipv 0,7.

---

Moet wel zeggen dat ik wat liep te stuntelen met het bepalen van, wanneer is het een loop? Wellicht als je de O meerdere keren tegenkomt, maar na hoevaak is het dan een loop? Uiteindelijk ben ik bij gaan houden hoeveel stappen er zijn gezet en daaruit mijn conclusie (is het een loop?) gehaald

Al met al erg tevreden dat dag 6 klaar is!

[Soultaker]

Satom schreef op vrijdag 6 december 2024 @ 18:32:
Moet wel zeggen dat ik wat liep te stuntelen met het bepalen van, wanneer is het een loop?

spoiler:

De meeste mensen houden drie variabelen bij: (rij, kolom, richting). Wanneer die drie exact hetzelfde zijn als de drie waarden die je eerder hebt gehad, dan zit je in een lus. Om dat te herkennen kun je elke tripel (rij, kolom, richting) die je tegenkomt in een set/dictionary/hashtable stoppen, zodat je kunt zien wanneer je in herhaling valt.

Dit kost een hoeveelheid geheugen die proportioneel is aan het aantal stappen tot je in een lus beland. Het is ook mogelijk om zonder extra geheugen (O(1)) cykels te detecteren, met behulp van een cycle detection algoritme, maar dat is wat lastiger te implementeren, en in de praktijk vaak niet eens sneller (mits je voldoende geheugen hebt).

[FCA]

Friits schreef op vrijdag 6 december 2024 @ 13:00:
@Soultaker Met de hierboven besproken optimalisaties (en een klein extraatje):

data.txt (mijn puzzel-input)      50ms
aoc-2024-day-06-challenge-1.txt   3.5s
aoc-2024-day-06-challenge-1.txt   0.5s
aoc-2024-day-06-challenge-1.txt   ~10s

De code hiervoor is vreselijk lelijk; daar wil ik m'n naam niet bij hebben staan

Dan ben ik toch benieuwd wat jij nog anders doet. Ik zit met (geparalleliseerde code) op:

day06.txt                                        30ms
aoc-2024-day-06-challenge-1.txt   0.67s
aoc-2024-day-06-challenge-2.txt   0.06s
aoc-2024-day-06-challenge-3.txt   ~16s

Nu verwacht ik dat parallelisatie niet heel veel gaat doen bij de kleinere gevallen, maar zeker gezien jouw score bij challenge 3 verwacht ik dat ik nog iets mis.

spoiler:

Ik houd nu per rij + kolom bij waar de obstakels staan in een geordende lijst, en jump steeds van obstakel naar obstakel, zonder iets met tussenliggende velden te doen. Het volgende obstakel zoek ik dan met een binary search weer in de betreffende rij/kolom informatie.
Ik doe nog steeds wel een loop over alle punten van het oorspronkelijke pad, en die loop is parallel nu

[Friits]

spoiler:

Ik doe preprocessing op de graaf en bereken daar per (positie, richting) wat de volgende (positie, richting) wordt. Die gebruiken we tijdens de "wandelingen" om naar het volgende obstakel te "springen", behalve als we op de rij/kolom van het extra obstakel zitten. Geen binary search nodig.

Verder begin ik de wandeling niet iedere keer opnieuw vanaf de startpositie, maar pas vanaf het punt waar ik het obstakel plaats. Het eerdere deel is toch iedere keer gelijk.

[Soultaker]

Friits schreef op vrijdag 6 december 2024 @ 19:55:

spoiler:

Ik doe preprocessing op de graaf en bereken daar per (positie, richting) wat de volgende (positie, richting) wordt. Die gebruiken we tijdens de "wandelingen" om naar het volgende obstakel te "springen", behalve als we op de rij/kolom van het extra obstakel zitten. Geen binary search nodig.

Slim bedacht. Voor het “behalve” deel zou je eventueel nog binary search kunnen gebruiken (maar in Python is dat lastig omdat er geen native ondersteuning is voor geordende containers zoals C++'s std::set<> of Java's TreeSet<>).

spoiler:

Verder begin ik de wandeling niet iedere keer opnieuw vanaf de startpositie, maar pas vanaf het punt waar ik het obstakel plaats. Het eerdere deel is toch iedere keer gelijk.

Ah, dat had ik ook bedacht maar nog niet geïmplementeerd. Nu even gedaan, en dat levert wel een forse tijdsbesparing op:

$ time OMP_NUM_THREADS=1 ./solve < aoc-2024-day-06-challenge-3.txt 
...261
...426

real    0m2.309s
user    0m2.271s
sys     0m0.022s

(Met 4 cores kan ik deze case onder de 900 ms krijgen maar ik vind multithreading een beetje flauw dus bovenstaande timings zijn met 1 thread.)

edit: voor de liefhebbers van Duff's device levert dit wel een leuke for-in-een-switch situatie op: https://github.com/maksve.../day06/solve.cc#L139-L168

[ Voor 9% gewijzigd door Soultaker op 06-12-2024 20:27 ]

[mbe81]

Het tijdsverschil tussen mijn code van vanochtend:

code:

Result Day 6, Part 1: 5269, Duration: 1.302375ms
Result Day 6, Part 2: 1957, Duration: 4.452888167s

en vanavond:

code:

Result Day 6, Part 1: 5269, Duration: 60.375µs
Result Day 6, Part 2: 1957, Duration: 226.244083ms

Ik heb het algoritme zelf niet aangepast en ga, voor deel 2, nog steeds alle posities af om te kijken of een obstakel voor een loop zorgt.

Verschillen zijn dat ik eerder overal een eigen Point{Y,X} type met 64-bits integers gebruikte, zowel voor de richting als de positie en deze heb vervangen door 4 16-bits integers: posY, posX, dirY, dirX. Dit leverde ca. 1,2 seconde op. Ook hield ik in de visits bij in een map[Point, Dir] waarbij er elk bezoek een element werd toegevoegd. Dit heb ik aangepast naar een vooraf geïnitialiseerde slice [][]int8 waarin ik met bitwise operators de bezochte richtingen bijhoud. Dit leverde de volgende 2 seconden op.

Voor wie de verschillen wil zien; hier mijn code van vanochtend en vanavond.

Overigens zijn op deze manier de inputbestanden van @Soultaker nog steeds niet binnen een redelijke tijd te parsen. Deel 3 duurt bijna 5 minuten... Om daar een beetje knap voor de dag te komen moet ik dus het aantal obstakels gaan beperken.

[Robbinb1993]

Soultaker schreef op vrijdag 6 december 2024 @ 12:40:
Voor wie wil benchmarken, hier wat extra grote invoer voor dag 6: aoc-2024-day-06-challenge-1-to-3.zip3

Antwoorden en referentietijden (in C++, mijn Python code is traag):

$ time ./solve < aoc-2024-day-06-challenge-1.txt
...18
...93

real    0m0.130s
user    0m0.124s
sys     0m0.006s

$ time ./solve < aoc-2024-day-06-challenge-2.txt
...13
...95

real    0m0.039s
user    0m0.037s
sys     0m0.002s

$ time ./solve < aoc-2024-day-06-challenge-3.txt
...261
...426

real    0m12.472s
user    0m12.419s
sys     0m0.017s

Ik heb mijn idee van vanochtend geïmplementeerd door lege cellen over te slaan en direct naar de eerstvolgende cel te springen die vlak voor het volgende obstakel ligt. Hierdoor wordt het proces efficiënter, maar de code is wat langer geworden: https://github.com/Robbinb1993/AoC24/blob/main/day6/day6.cc.

Hierbij heb ik ook de optimalisatie toegepast dat we alleen maar de obstakels hoeven te plaatsen op de cellen waar de guard in part 1 langs is geweest, anders heeft zo'n nieuw obstakel geen invloed en zal hij hetzelfde pad weer bewandelen en ontsnappen.

Ik haal hiermee de volgende tijden op deze test cases:

originele input: 3ms.
aoc-2024-day-06-challenge-1.txt: 36ms.
aoc-2024-day-06-challenge-2.txt: 9ms.
aoc-2024-day-06-challenge-3.txt: 1397ms.

[ Voor 9% gewijzigd door Robbinb1993 op 06-12-2024 22:14 ]

[Satom]

Soultaker schreef op vrijdag 6 december 2024 @ 19:45:
[...]

spoiler:

De meeste mensen houden drie variabelen bij: (rij, kolom, richting). Wanneer die drie exact hetzelfde zijn als de drie waarden die je eerder hebt gehad, dan zit je in een lus. Om dat te herkennen kun je elke tripel (rij, kolom, richting) die je tegenkomt in een set/dictionary/hashtable stoppen, zodat je kunt zien wanneer je in herhaling valt.

Dit kost een hoeveelheid geheugen die proportioneel is aan het aantal stappen tot je in een lus beland. Het is ook mogelijk om zonder extra geheugen (O(1)) cykels te detecteren, met behulp van een cycle detection algoritme, maar dat is wat lastiger te implementeren, en in de praktijk vaak niet eens sneller (mits je voldoende geheugen hebt).

Bedankt voor de uitgebreide uitleg! Dit was grotendeels mijn eerste oplossing voor deel 2, maar waar het bij mis is gegaan:

spoiler:

ik hield alleen de rij en kolom bij en liep daardoor tegen het probleem aan, dat een kruising al werd gezien als loop. Stom, als ik daar de richting aan toe had gevoegd, was ik er mogelijk al geweest!

[Creepy]

Deel 1 was eenvoudig. Deel 2 ben ik nog niet aan uit. Ik heb een oplossing die werkt in de testcase maar veel te lang duurt voor de echte input.

spoiler:

Bruteforce is niet de oplossing blijkbaar

Morgen eens verder prutsen.

[ Voor 6% gewijzigd door Creepy op 06-12-2024 23:27 ]

[MatHack]

Deel 1 was zo klaar, maar deel 2 liep ik tegen een probleempje aan:

spoiler:

Om een of andere reden werkt mijn HasLoop methode wel als ik vanaf de start positie begin (met bijbehorende richting omhoog), maar niet als ik begin vanaf de plek precies voor het tijdelijke obstakel dat ik net geplaatst heb (met de richting naar het obstakel)... Ik heb geen idee waarom niet, en heb ook de puf niet meer om het uit te zoeken. Jammer genoeg levert dit dubbele runtime op (1.2s ipv 600ms).
In de code zou dat dus "HasLoop(grid, current, direction)" zijn ipv "HasLoop(grid, start, Coords.OffsetUp)"

https://github.com/realma...de.Y2024/Solvers/Day06.cs

[Creepy]

En ondertussen wel een manier gevonden om deel 2 sneller op te lossen, maar ergens nog een bug waardoor ik te hoog uit kom. De test input gaat uiteraard goed, maar de echte input nog niet.

[.oisyn]

Ik probeer een inhaalslag te maken maar ik blijf hangen op een stomme bug op deel 2 van dag 2, maar gewoon mijn brute force antwoord is ook fout
.edit: oh jezus ik ben dom. Next.

[ Voor 60% gewijzigd door .oisyn op 07-12-2024 03:00 ]

[Robbinb1993]

Friits schreef op vrijdag 6 december 2024 @ 19:55:

spoiler:

Ik doe preprocessing op de graaf en bereken daar per (positie, richting) wat de volgende (positie, richting) wordt. Die gebruiken we tijdens de "wandelingen" om naar het volgende obstakel te "springen", behalve als we op de rij/kolom van het extra obstakel zitten. Geen binary search nodig.

Verder begin ik de wandeling niet iedere keer opnieuw vanaf de startpositie, maar pas vanaf het punt waar ik het obstakel plaats. Het eerdere deel is toch iedere keer gelijk.

Met deze laatste optimalisatie is de runtime van test case aoc-2024-day-06-challenge-3.txt verder verlaagd naar 506 ms.

[Corniel]

Note to self: wees geduldig!

Mijn niet geoptimalizeerde (lompe) implementatie van deel 2 deed er vandaag 1.6 minuten over. Maar ipv dat ik geduldig ging wachten heb ik een aantal keer zitten k#t-en om te kijken of er niet ergens een rare infinite loop zat.Toch zo'n 20 minuten verprutst...

[mbe81]

1,6 minuut? Ik ben benieuwd wat je dan allemaal doet! Ik kom op net geen 1,4 seconden voor deel 2.

https://github.com/mbe81/.../main/days/day07/day07.go

[Soultaker]

mbe81 schreef op zaterdag 7 december 2024 @ 07:44:
1,6 minuut? Ik ben benieuwd wat je dan allemaal doet! Ik kom op net geen 1,4 seconden voor deel 2.

https://github.com/mbe81/.../main/days/day07/day07.go

Ik zit op 1,9 seconde in Python, of 1,5 seconde als ik gebruik maak van het feit dat alle invoerwaarden

spoiler:

positief zijn, dus als je tussentotaal groter is dan je doeltotaal, kun je de zoekoperatie afbreken.

Corniel schreef op zaterdag 7 december 2024 @ 07:37:
Note to self: wees geduldig!

Mijn niet geoptimalizeerde (lompe) implementatie van deel 2 deed er vandaag 1.6 minuten over. Maar ipv dat ik geduldig ging wachten heb ik een aantal keer zitten k#t-en om te kijken of er niet ergens een rare infinite loop zat.Toch zo'n 20 minuten verprutst...

Mijn aanpak in dit soort situaties is om de oplossing te laten draaien op de achtergrond terwijl ik ondertussen doorwerk aan het optimaliseren van m'n code. Als je mazzel hebt dan is het script halverwege toch opeens klaar, en zoniet, dan heb je geen tijd verspild met wachten.

(Onder Windows moet je dan misschien eerst een kopie maken van je script/executable omdat je 'm anders niet kunt overschrijven. Onder Linux kun je gewoon je bestaande script editen/binaries hercompileren zonder dat het effect heeft op het proces dat al loopt.)

Wat bij problemen zoals die van vandaag, waarbij elke regel onafhankelijk opgelost wordt, ook helpt is om voor elke regel het antwoord te debug-printen. Dan kun je aan de uitvoer zien hoeveel regels/seconde 'ie ongeveer doet en dus inschatten hoe lang het ongeveer gaat duren, en als 'ie bijvoorbeeld vastloopt op 1 specifieke testcase kun je dat ook zien.

(Ook zou je zo'n buitenste loop in theorie vrij makkelijk kunnen paralelliseren maar meestal is dat niet eens nodig.)

[ Voor 3% gewijzigd door Soultaker op 07-12-2024 08:48 ]

[Remcoder]

Meer dan een seconde?

Mijn deel 2 draait in 30ms...

https://github.com/remcos...er/adventofcode/Day7.java

[CrossProd]

370ms voor een rechttoe rechtaan oplossing voor deel 2 in Swift met de aanname

spoiler:

dat er geen negatieve getallen zijn en dat de samenvoegingen nog steeds valide int64s zijn

[ Voor 14% gewijzigd door CrossProd op 07-12-2024 09:02 ]

[mbe81]

Remcoder schreef op zaterdag 7 december 2024 @ 08:47:
Meer dan een seconde?

Mijn deel 2 draait in 30ms...

https://github.com/remcos...er/adventofcode/Day7.java

Slim! Jij beperkt het aantal opties wat je doorrekent.

[CrossProd]

Hoe denken jullie eigenlijk over meerdere threads gebruiken? Als ik de equations over meerdere threads verdeel kom ik op 186ms vs 370ms. Tot nu toe heb ik dit voor alle voorgaande jaren van AoC niet gedaan maar dit jaar probeer ik het wel te gebruiken.

[mbe81]

Kan, maar dan heb ik dan liever de oplossing in 370 ms. Het toepassen van meerdere threads is geen optimalisatie van je algoritme.

Ik zou dat zelf pas doen als ik anders niet binnen een acceptabele tijd tot een oplossing kom.

[Hagdos]

Eerste oplossing voor vandaag (dag 7) was in ~5.5 seconde. Na wat optimalisatie in ~2.5 seconde. Nog wat meer klooien, en het teruggebracht naar 22 milliseconden (in Python).

spoiler:

Eerste optimalizatie: Afbreken als het resultaat groter wordt dan het eindresultaat. Tweede optimalizatie: Achteraan beginnen, dan is delen door of samenvoegen heel vaak überhaupt niet mogelijk omdat je dan niet op een integer uit komt.

Leuke puzzel, eigenlijk zouden er wat langere vergelijkingen in de input moeten zitten.

[ Voor 11% gewijzigd door Hagdos op 07-12-2024 09:22 ]

[Friits]

Ik heb het idee hierboven ook geïmplementeerd: 12 LoC.

Ik weet alleen niet of ik trots moet zijn of me juist moet schamen voor dit trucje:

Python:

class int(int):
    __or__ = lambda x, y: (x-y) / (10 ** int(log10(y)+1))

waarmee ik dit kan doen:

code:

>>> print(int(123)|int(3))
12.0
>>> print(int(123)|int(23))
1.0

[Corniel]

[quote]mbe81 schreef op zaterdag 7 december 2024 @ 07:44:
1,6 minuut? Ik ben benieuwd wat je dan allemaal doet! Ik kom op net geen 1,4 seconden voor deel 2.

Na mijn fixes kom ik op 1.5s.

spoiler:

Snel aanpassen van mijn deel 1 code deed ik door ipv 1 << l, 1 << (l *2). Te doen, en als de (&==3) exit. Dat typte supersnel, maar ja, dan heb je natuurlijk een heel groot deel van je permutaties die exit doen. Maar het was wel in een keer het goede antwoord.

[Hagdos]

Friits schreef op zaterdag 7 december 2024 @ 09:42:

Ik weet alleen niet of ik trots moet zijn of me juist moet schamen voor dit trucje:

Python:

class int(int):
    __or__ = lambda x, y: (x-y) / (10 ** int(log10(y)+1))

waarmee ik dit kan doen:

code:

>>> print(int(123)|int(3))
12.0
>>> print(int(123)|int(23))
1.0

Haha, waarom zou je dat in de int-class doen, en niet gewoon een aparte functie voor maken? De wiskunde an-sich is best oké toch?

[Friits]

Zodat ik de | operator op ints kan overloaden

[Corniel]

Friits schreef op zaterdag 7 december 2024 @ 09:51:
Zodat ik de | operator op ints kan overloaden

Eval or Evil?

[Mugwump]

CrossProd schreef op zaterdag 7 december 2024 @ 09:08:
Hoe denken jullie eigenlijk over meerdere threads gebruiken? Als ik de equations over meerdere threads verdeel kom ik op 186ms vs 370ms. Tot nu toe heb ik dit voor alle voorgaande jaren van AoC niet gedaan maar dit jaar probeer ik het wel te gebruiken.

Ach ja, waarom niet. Het maakt natuurlijk sowieso al uit op wat voor hardware je de boel draait.

Grappig genoeg wordt mijn oplossing trager als ik er een parallelStream() in stop. Zonder parallelisme komt deel 2 op ongeveer 90ms, met op ongeveer 130ms. Levert kennelijk meer overhead op dan snelheidswinst.

[KabouterSuper]

Ik was vanochtend lui, heel lui. Voor deel 2 alle mogelijkheden doorgerekend en zelfs elke operator met een eval uitgevoerd. Toen aangezet (2GHz, single core) en gaan douchen... niet eens aan gedacht om pypy te gebruiken. 36 minuten later had ik het goede antwoord. Nu maar even optimaliseren.

[FCA]

Vanochtend vooral veel tijd kwijt met het genereren van alle opties. Alle binaire strings van een bepaalde lengte genereren was iets wat ik niet eerder in Rust had gedaan. De risico's van AoC in een (voor mij dan) relatief nieuwe taal doen. Maar goed, AoC is er natuurlijk ook vooral om nieuwe dingen te leren

spoiler:

Deel 2 was dan weer een eitje, omdat ik met mijn suffe hoofd wel dat kon bedenken, maar voor deel 1 mooi bit-shifts wilde gebruiken...

Eerste instantie brute-force, deel 2 deed er ~2,5 seconden over, later netjes van de achterkant afpellen zoals door Hagdos boven beschreven, alles onder de 2ms nu

Met wat extra optimalisaties het totaal onder de 1ms, goed genoeg voor het weekend

[ Voor 11% gewijzigd door FCA op 07-12-2024 12:00 ]

[ProAce]

Initieel voor deel 1 een simpele iterator gemaakt op van wat bit shiften, ging dat bij deel 2 niet op. Leuk om eens te spelen met de nieuwe Iterators in Go. Runt in respectievelijk 10 en 465 ms, misschien nog eens kijken wat parallel brute forcen doet met die laatste (edit: gaat naar 69ms)

https://github.com/ysmild...lutions/2024/day7/day7.go

[ Voor 3% gewijzigd door ProAce op 07-12-2024 11:54 ]

[Mugwump]

mbe81 schreef op zaterdag 7 december 2024 @ 08:59:
[...]


Slim! Jij beperkt het aantal opties wat je doorrekent.

Ik moest dat ook gewoon doen, want domweg door alle permutaties van operators heenlopen was gewoon traag. Ben nog een beetje zoekende waarom dat nou precies het geval is, want natuurlijk is Go (en al helemaal Rust) sneller dan Kotlin, maar na een minuut ratelen zat ie bij mij op regel 80 van de 850 ofzo voor deel 1.

[rengeltje]

Hagdos schreef op zaterdag 7 december 2024 @ 09:45:
[...]


Haha, waarom zou je dat in de int-class doen, en niet gewoon een aparte functie voor maken? De wiskunde an-sich is best oké toch?

Oei, Python brengt duidelijk het meeste luie in mij naar boven. Ik had gewoon:

code:

return int(str(a)+str(b))

gedaan

[Soultaker]

Wat extra data voor dag 7:
aoc-2024-day-07-challenge-1-to-3.zip.

Referentietijden en antwoorden:

$ time python3 07.py < aoc-2024-day-07-challenge-1.txt 
...841
...981

real	0m0.076s
user	0m0.062s
sys	0m0.012s

$ time python3 07.py < aoc-2024-day-07-challenge-2.txt 
...558
...254

real	0m0.288s
user	0m0.273s
sys	0m0.013s

$ time pypy3 07.py < aoc-2024-day-07-challenge-3.txt 
...032
...719

real	0m33.456s
user	0m32.902s
sys	0m0.415s

[FCA]

Soultaker schreef op zaterdag 7 december 2024 @ 12:15:
Wat extra data voor dag 7:
aoc-2024-day-07-challenge-1-to-3.zip.

Referentietijden en antwoorden:

$ time python3 07.py < aoc-2024-day-07-challenge-1.txt 
...841
...981

real	0m0.076s
user	0m0.062s
sys	0m0.012s

$ time python3 07-fast-memoized.py < aoc-2024-day-07-challenge-2.txt 
...558
...254

real	0m0.288s
user	0m0.273s
sys	0m0.013s

$ time pypy3 07-fast-memoized.py < aoc-2024-day-07-challenge-3.txt 
...032
...719

real	0m33.456s
user	0m32.902s
sys	0m0.415s

Volgens mij loopt het antwoord bij de laatste over een u64 heen, want de antwoorden kloppen niet meer, maar geen zin om alles om te zetten naar u128.
edit: Ik doe een specifieke edge case fout, weet welke, maar zo snel geen oplossing.

Voor challenge 1:

Day 7 - Part 1 - recurse : ...2841
        generator: 300ns,
        runner: 802.3µs

Day 7 - Part 2 - recurse :. ..5981
        generator: 300ns,
        runner: 1.4716ms

Challenge 2:

Day 7 - Part 1 - recurse : ...6558
        generator: 500ns,
        runner: 1.498ms

Day 7 - Part 2 - recurse : ...8254
        generator: 400ns,
        runner: 2.9452ms

En voor challenge 3 krijg ik in ~1,5 seconde het foute antwoord

[ Voor 3% gewijzigd door FCA op 07-12-2024 13:12 ]

[Soultaker]

FCA schreef op zaterdag 7 december 2024 @ 12:35:
Volgens mij loopt het antwoord bij de laatste over een u64 heen, want de antwoorden kloppen niet meer, maar geen zin om alles om te zetten naar u128.

Alle getallen passen in 48 bits. Dit is ook eenvoudig te verifiëren door de eerste getallen van elke regel op te tellen, want dat is het maximaal mogelijke antwoord. Ik denk dat je iets gemist hebt in de invoer

[KabouterSuper]

spoiler:

Ter overweging, is het niet veel sneller om het achterstevoren te berekenen? Je kunt dan gelijk bepalen of je dieper moet of kunt afbreken. Bijv
7290: 6 8 6 15
7290 eindigt niet op 15 - > stop
7290 is wel deelbaar door 15 - > door met 486
- - 486 eindigt op 6 - > door met 48
- - - - Enz
- - 486 is deelbaar door 6 - > door met 81
- --- Enz
7290-15 is positief-> door met 7275
--Enz

[Daos]

KabouterSuper schreef op zaterdag 7 december 2024 @ 14:05:

spoiler:

Ter overweging, is het niet veel sneller om het achterstevoren te berekenen? Je kunt dan gelijk bepalen of je dieper moet of kunt afbreken. Bijv
7290: 6 8 6 15
7290 eindigt niet op 15 - > stop
7290 is wel deelbaar door 15 - > door met 486
- - 486 eindigt op 6 - > door met 48
- - - - Enz
- - 486 is deelbaar door 6 - > door met 81
- --- Enz
7290-15 is positief-> door met 7275
--Enz

Zo heb ik het opgelost.

[.oisyn]

Zo, t/m 6.1 nu af, vanavond even 6.2 en 7 en dan ben ik weer bij. Heb nog niet heel veel moeite gedaan om optimale oplossingen te bedenken. Denk dat ik 6.2 ook maar even ga brute forcen zodat ik 'm iig af kan vinken, maar ik kan vandaag iig nog even broeden op een betere oplossing

[Marcj]

Dag 7 ook opgelost, met een paar van dezelfde optimalisaties waar anderen het ook over hadden.

Met de grote input van Soultaker:

code:

$ day7 < big_inputs/aoc-2024-day-07-challenge-1.txt
Executing
 ├── Input parsed in 1,103µs
 ├── Part 1 calculated in 370µs: …2841
 ├── Part 2 calculated in 166µs: …5981
 └── Total time: 1,664µs

day7 < big_inputs/aoc-2024-day-07-challenge-2.txt
Executing
 ├── Input parsed in 1,499µs
 ├── Part 1 calculated in 668µs: …6558
 ├── Part 2 calculated in 715µs: …8254
 └── Total time: 2,932µs

$ day7 < big_inputs/aoc-2024-day-07-challenge-3.txt
Executing
 ├── Input parsed in 2,022µs
 ├── Part 1 calculated in 73,997µs: …3273
 ├── Part 2 calculated in 128,878µs: …5132
 └── Total time: 204,934µs

Wel multi-threaded toegepast, wat best snel is op een Apple M1 Pro processor Single-threaded deed deel 3 er 1,3 seconden over.

ps. Voor die derde input moest ik nog wel even een edge-case toevoegen. Best gemeen om nullen toe te voegen Soultaker!

[ Voor 8% gewijzigd door Marcj op 07-12-2024 15:41 ]

[Soultaker]

Marcj schreef op zaterdag 7 december 2024 @ 14:37:
ps. Voor die derde input moest ik nog wel even een edge-case toevoegen. Best gemeen om nullen toe te voegen Soultaker!

Het is een challenge, hè Je krijgt overigens een ander antwoord eruit dan ik.

Ik zal eens debuggen om te zien of ik kan uitvinden of de fout bij mij of bij jou zit...

edit:
Jij zit fout. Als je een hint wil:

spoiler:

31435833265: 7 691 3 754 14 56 8 59 81 950 923 1 530 3 35 233 514 1 92 44 0 168 31 4 268 47 23 6 4 3 318 9 41 0 6 2 28 1 98 1 8 443 8 54 41 4 25 729 7 82 341 2 5 825

is oplosbaar voor deel 1 (en dus ook deel 2)

[ Voor 25% gewijzigd door Soultaker op 07-12-2024 15:14 ]

[Janoz]

Ik doe het ook achterstevoren, maar ben wel benieuwd naar de edgecase van @Soultaker Ik krijg er na 7.5 seconden 121983015304067 uit bij het 3e voorbeeld.

Bij voorbeeld 2 krijg ik het juiste antwoord in 51ms en voorbeeld 1 in 36ms

Ik heb de spoiler van hierboven er ook even door gegooid, maar die gaat bij mij gewoon goed.

[ Voor 24% gewijzigd door Janoz op 07-12-2024 15:43 ]

[Marcj]

Soultaker schreef op zaterdag 7 december 2024 @ 14:59:
[...]

Het is een challenge, hè Je krijgt overigens een ander antwoord eruit dan ik.

Ik zal eens debuggen om te zien of ik kan uitvinden of de fout bij mij of bij jou zit...

edit:
Jij zit fout. Als je een hint wil:

spoiler:

31435833265: 7 691 3 754 14 56 8 59 81 950 923 1 530 3 35 233 514 1 92 44 0 168 31 4 268 47 23 6 4 3 318 9 41 0 6 2 28 1 98 1 8 443 8 54 41 4 25 729 7 82 341 2 5 825

is oplosbaar voor deel 1 (en dus ook deel 2)

Aargh, ik bedenk net de fout. Maar ben nu niet meer thuis, dus kan het bugfix niet testen. Heeft met mijn oplossing voor de edge case te maken volgens mij, er is een andere mogelijke oplossing!

[Soultaker]

Janoz schreef op zaterdag 7 december 2024 @ 15:34:
Ik doe het ook achterstevoren, maar ben wel benieuwd naar de edgecase van @Soultaker Ik krijg er na 7.5 seconden 121983015304067 uit bij het 3e voorbeeld.

Is dat deel 1 of deel 2? Het is te hoog voor deel 1 maar te laag voor deel 2.

Als je de getallen die je opsomt kunt debug-printen (1 per regel b.v.) dan kan ik checken welke er verkeerd zijn.

[Bolukan]

Bij alle comments op day 7 mis ik nog het woord "recursief".

[Soultaker]

Ik heb recusie uitgelegd in deze deze comment.

[Gropah]

Eerst heel dom alle permutaties van operators zitten verzinnen. Voor deel 3 maar naar

spoiler:

een heap gegaan, waarbij ik an te voren check of het nog het toevoegen waard is.

Ben wel van voren begonnen. Mijn hersenen waren van ochtend duidelijk nog niet helemaal wakker

Bolukan schreef op zaterdag 7 december 2024 @ 16:43:
Bij alle comments op day 7 mis ik nog het woord "recursief".

Dit kan inderdaad best goed recursief, hoewel je dat bij verschillende niet-functionele talen wellicht tot problemen mbt heap space kan gaan aanlopen.

[Janoz]

Bolukan schreef op zaterdag 7 december 2024 @ 16:43:
Bij alle comments op day 7 mis ik nog het woord "recursief".

Niet in mijn comment, wel in mijn code

[Janoz]

Soultaker schreef op zaterdag 7 december 2024 @ 16:11:
[...]

Is dat deel 1 of deel 2? Het is te hoog voor deel 1 maar te laag voor deel 2.

Als je de getallen die je opsomt kunt debug-printen (1 per regel b.v.) dan kan ik checken welke er verkeerd zijn.

Deel 2, dit zijn mijn resultaten: https://gist.github.com/J...b8dedbc50dd88b2c2b8146ade

[MueR]

Dag 7 ook weer klaar.

[MueR]

ProAce schreef op zaterdag 7 december 2024 @ 11:51:
Initieel voor deel 1 een simpele iterator gemaakt op van wat bit shiften, ging dat bij deel 2 niet op. Leuk om eens te spelen met de nieuwe Iterators in Go. Runt in respectievelijk 10 en 465 ms, misschien nog eens kijken wat parallel brute forcen doet met die laatste (edit: gaat naar 69ms)

https://github.com/ysmild...lutions/2024/day7/day7.go

Die concatenate functie van je jat ik even Helemaal niet aan gedacht

[Soultaker]

Janoz schreef op zaterdag 7 december 2024 @ 17:07:
Deel 2, dit zijn mijn resultaten: https://gist.github.com/J...b8dedbc50dd88b2c2b8146ade

Daarin ontbreekt 31435833265 die ik hier noemde toch al? (Ik dacht dat je eerder zei dat je die wel accepteerde, maar misschien begreep ik je verkeerd?)

[Janoz]

oh , weird. Als ik die los draai gaat hij wel goed.

--edit---
Oh wacht, dacht dat hij goed ging, maar blijkbaar nu niet..

[ Voor 42% gewijzigd door Janoz op 07-12-2024 17:50 ]

[Janoz]

Yup, nu doet hij deel 2 in 5 seconden met de juiste antwoorden.

spoiler:

Ik had eerder al de /0 fout opgelost aangezien die een stuk duidelijker naar voren kwam, maar blijkbaar moest 0/0 weer anders afgehandeld worden.

[ Voor 57% gewijzigd door Janoz op 07-12-2024 18:13 ]

[ProAce]

MueR schreef op zaterdag 7 december 2024 @ 17:19:
[...]

Die concatenate functie van je jat ik even Helemaal niet aan gedacht

Die heb ik dan weer geleend van stack overflow

[Robbinb1993]

Soultaker schreef op zaterdag 7 december 2024 @ 12:15:
Wat extra data voor dag 7:
aoc-2024-day-07-challenge-1-to-3.zip.

Referentietijden en antwoorden:

$ time python3 07.py < aoc-2024-day-07-challenge-1.txt 
...841
...981

real	0m0.076s
user	0m0.062s
sys	0m0.012s

$ time python3 07.py < aoc-2024-day-07-challenge-2.txt 
...558
...254

real	0m0.288s
user	0m0.273s
sys	0m0.013s

$ time pypy3 07.py < aoc-2024-day-07-challenge-3.txt 
...032
...719

real	0m33.456s
user	0m32.902s
sys	0m0.415s

Mijn code draait de derde test case nu in 2419ms. Ik cache eerder bezochte states, maar alleen voor lagere waarden van het resterende getal: https://github.com/Robbinb1993/AoC24/blob/main/day7/day7.cc.

Edit: na het omdraaien van de volgorde van operations (eerst ||, dan / en daarna -) is de runtime nog maar 755ms.

[ Voor 17% gewijzigd door Robbinb1993 op 07-12-2024 19:58 ]

[Creepy]

Zo, dag 7 ook weer gefixt. Als ik morgen puf heb fix ik deel 6.2
https://github.com/CodeEn...er/aoc/aoc2024/Day07.java

[.oisyn]

Net even 6.2 ingetypt, simpele brute force, doet er 14ms over op mijn machine. Prima

Alle code hier trouwens: https://github.com/oisyn/Advent2024. @ElkeBxl mag in de TS . Alles in Rust.

[HannoOttens]

Leuk om dit allemaal te lezen! Heb zelf gewoon alles brute force gedaan. Door gebruik te maken de binaire representatie van getallen alle mogelijkheden gegenereerd 😁

https://github.com/HannoO...er/2024/day07/src/main.rs

[Hagdos]

Soultaker schreef op zaterdag 7 december 2024 @ 12:15:
Wat extra data voor dag 7:
aoc-2024-day-07-challenge-1-to-3.zip.

Referentietijden en antwoorden:

$ time python3 07.py < aoc-2024-day-07-challenge-1.txt 
...841
...981

real	0m0.076s
user	0m0.062s
sys	0m0.012s

$ time python3 07.py < aoc-2024-day-07-challenge-2.txt 
...558
...254

real	0m0.288s
user	0m0.273s
sys	0m0.013s

$ time pypy3 07.py < aoc-2024-day-07-challenge-3.txt 
...032
...719

real	0m33.456s
user	0m32.902s
sys	0m0.415s

Ik snap niet waarom; voor challenge 1 heb ik alleen part1 goed, challenge 2 heb ik beide goed, bij challenge 3 heb ik beide fout.

Ik denk dat ik weet wat ik fout doe bij challenge 3, maar ik heb geen idee wat ik fout doe bij 1b. Kun je een hint geven?

Code staat hier: https://github.com/Hagdos...de/tree/main/2024/Day%207

[.oisyn]

Janoz schreef op zaterdag 7 december 2024 @ 15:34:
Ik doe het ook achterstevoren, maar ben wel benieuwd naar de edgecase van @Soultaker Ik krijg er na 7.5 seconden 121983015304067 uit bij het 3e voorbeeld.

Grappig, dat antwoord heb ik dus ook voor deel 2, en voor deel 1 heb ik hetzelfde antwoord als @Marcj

Tijden resp. 530.1µs, 1711.3µs en 1234427.0µs

.edit: haha, bug gevonden, maar nog steeds niet het goede antwoord: ...022 en ...565

@Soultaker Kun je eens een variant van challenge3 releasen waarbij alleen maar de regels zitten die daadwerkelijk kunnen?

.edit: oh nvm, ik heb een early out die niet helemaal correct was. Nu wel goed. De totale tijd voor challenge 3 gaat wel naar beneden: 884605.7µs . Kan nog wel sneller door de stappen van part1 en part2 te combineren.

[ Voor 40% gewijzigd door .oisyn op 08-12-2024 01:42 ]

[Janoz]

Weird, ik krijg bij dag 8 de melding bij deel 1 dat ik het foute antwoord heb, maar dat het het goede antwoord van een andere set is. Op de input gaat alles wel goed...

hmm, een bug en een interpretatie fout die elkaar ophieven en vervolgens een resultaat wat gelijk was aan een andere set maakten mij wat paranoïde . Deel 2 was eigenlijk een eitje met de manier waarop ik deel 1 al gedaan had.

[ Voor 41% gewijzigd door Janoz op 08-12-2024 07:05 ]

[FCA]

Haha.. voor mij was het vandaag Advent of Casting: heb welgeteld 32x expliciet een variabele moeten casten. .

En daarna bleek ook nog eens dat ik 'isize' standaard als 'isze' type

[ Voor 26% gewijzigd door FCA op 08-12-2024 06:55 ]

[mbe81]

Best tevreden vandaag. Moest wel 3 keer lezen voordat ik de opdracht echt snapte.

code:

Result day 8, part 1: xxx - duration: 173.042µs
Result day 8, part 2: xxx - duration: 339.625µs

[Soultaker]

Dag 8: Ik denk dat mensen die een punt/vector klasse hadden geïmplementeerd daar vandaag weer hun voordeel mee hebben kunnen doen.

Ik zat nog half te slapen... er gingen zoveel kleine dingen mis (if ipv while, verkeerde sample invoer, etc.) dat ik geen goede tijd heb kunnen neerzetten, maar dat brengt wel wat meer spanning in het Tweakers leaderboard.

Voor dag 7 extra challenges:

Hagdos schreef op zaterdag 7 december 2024 @ 22:54:
Ik snap niet waarom; voor challenge 1 heb ik alleen part1 goed, challenge 2 heb ik beide goed, bij challenge 3 heb ik beide fout.

Ik denk dat ik weet wat ik fout doe bij challenge 3, maar ik heb geen idee wat ik fout doe bij 1b. Kun je een hint geven?

Speciaal voor jou en andere mensen die hier nog mee bezig zijn, de referentie-oplossingen met per onderdeel welke uitkomsten goed zijn en hoe ze geconstrueerd kunnen worden:
aoc-2024-day-07-challenge-1-to-3-solutions.zip

Wat betreft de bug in je code, neem een voorbeeld als:

1: 2 1

die kan niet, maar jouw code denkt van wel. De reden is dat (spoilers!)

spoiler:

je er ten onrechte vanuit gaat dat je met 0 begint; je construeert voor bovenstaande voorbeeld dus eigenlijk 0*2+1, maar die 0 bestaat helemaal niet.

Is eigenlijk een zwakte van mijn testdata (en van de officiële data, maar dat verbaasd me niet) dat je daar in challenge 1 part 1 niet al op nat gaat. Het is een zwakte van de manier waarop ik onmogelijke cases genereer helaas.

[ Voor 7% gewijzigd door Soultaker op 08-12-2024 07:08 ]

[Friits]

Soultaker schreef op zondag 8 december 2024 @ 07:07:
Dag 8: Ik denk dat mensen die een punt/vector klasse hadden geïmplementeerd daar vandaag weer hun voordeel mee hebben kunnen doen.

Of complexe getallen gebruiken (misbruiken?)

Mijn oplossing voor vandaag. Leuk puzzeltje, maar ik had inmiddels wel wat ingewikkelders verwacht!

[CrossProd]

Ik zat te slapen en had voor part 1 de oplossing geschreven die je voor part 2 nodig had

[Mugwump]

Hij was uiteindelijk heel makkelijk, maar ik vond dit stukje van de tekst wat verwarrend:

but only when one of the antennas is twice as far away as the other. In particular, an antinode occurs at any point that is perfectly in line with two antennas of the same frequency - This means that for any pair of antennas with the same frequency, there are two antinodes, one on either side of them.

In mijn ogen klopt het eerste deel niet helemaal met het tweede. Als een antinode optreedt op een plek die exact in de lijn van 2 punten ligt en de afstand van punt A 2 keer zo groot is als de afstand van punt B, dan heb je in mijn ogen in potentie 4 antinodes in plaats van 2. Er kunnen namelijk ook twee punten tussen A en B zijn waarvoor geldt dat de afstand tot A 2x de afstand tot B is en vice versa.

En ja, ik had natuurlijk met m'n slaperige kop over het tweede deel van de alinea heengelezen.

[TrailBlazer]

De afgelopen 2 dagen lopen vechten nu alles straightforwards
Python

ik heb wel het idee dat de omschrijving steeds lastiger wordt om AI's om de tuin te leiden.

spoiler:

In fact, the three T-frequency antennas are all exactly in line with two antennas, so they are all also antinodes! This brings the total number of antinodes in the above example to 9.

dit vond ik echt vaag.

[ Voor 33% gewijzigd door TrailBlazer op 08-12-2024 08:59 ]

[HannoOttens]

Het was echt even een paar keer lezen vandaag, maar best makkelijk.

Rust

[FCA]

Friits schreef op zondag 8 december 2024 @ 07:27:
[...]

Of complexe getallen gebruiken (misbruiken?)

Mijn oplossing voor vandaag. Leuk puzzeltje, maar ik had inmiddels wel wat ingewikkelders verwacht!

Inderdaad, ik bleek achteraf zelfs nog met teveel subtiliteiten rekening te houden

spoiler:

Zo kun je bijvoorbeeld 2 antenne's met een verschil van (4,2) hebben, maar dan moet je elk gridpoint op een lijn van (2,1) natuurlijk invullen, dus ik een gcd functie erin knallen.

Komt dus helemaal niet voor in de input data

Verder zijn er nog steeds onsubtiele "AI enthousiasts" die gewoon een oplossing in 14 seconden voor deel 1 insturen. " Improving my Python skills using AI." Nee dus, je laat gewoon AI het werk voor je doen. Daar leer je niks van . Niet dat ik ooit op het leaderboard terecht kom, maar ik word daar toch een beetje pissig van.
Zeker als je deze reddit thread leest, er zijn dus mensen die dit bewust doen om de boel te fucken

[Ghehe]

Kan iemand (in spoilers) deel 2 uitleggen zodat de opdracht begrijpelijk is? Ik snap echt niets van dat voorbeeld...

[FCA]

Ghehe schreef op zondag 8 december 2024 @ 10:00:
Kan iemand (in spoilers) deel 2 uitleggen zodat de opdracht begrijpelijk is? Ik snap echt niets van dat voorbeeld...

"Read the problem statement carefully" (sorry, kon even niet nalaten het oude standaardantwoord van alle programming contests te herbruiken).

spoiler:

I.p.v. dus alleen enkele "antinodes", maak je in beide richtingen de lijn af (waaronder dus ook de antennes zelf)

[Mugwump]

Ghehe schreef op zondag 8 december 2024 @ 10:00:
Kan iemand (in spoilers) deel 2 uitleggen zodat de opdracht begrijpelijk is? Ik snap echt niets van dat voorbeeld...

spoiler:

Vandaag blinkt inderdaad niet uit in helderheid.

Voor opdracht 1 had je vast bedacht dat je de afstand tussen punt A en B respectievelijk van punt A moest aftrekken en bij B moest optellen.

Voor opdracht 2 geldt min of meer het zelfde, alleen is het niet enkel 1x de afstand eraf halen of erbij op tellen, maar ook voor 0x de afstand, 2x de afstand, 3x de afstand, enz.

edit: dit maakt natuurlijk wel misbruik van de structuur van de input zoals @FCA in z'n eerdere post aanhaalt.

[ Voor 8% gewijzigd door Mugwump op 08-12-2024 10:06 ]

[Ghehe]

FCA schreef op zondag 8 december 2024 @ 10:04:
[...]

"Read the problem statement carefully" (sorry, kon even niet nalaten het oude standaardantwoord van alle programming contests te herbruiken).

Ik was de opdracht al 15 minuten aan het bekijken en herlezen. Het zal wel aan mijn niveau van de Engelse taal liggen

Mugwump schreef op zondag 8 december 2024 @ 10:04:
[...]

spoiler:

Voor opdracht 2 geldt min of meer het zelfde, alleen is het niet enkel 1x de afstand eraf halen of erbij op tellen, maar ook voor 0x de afstand, 2x de afstand, 3x de afstand, enz.

Met deze uitleg was het op 2 minuutjes gepiept.

[Marcj]

.oisyn schreef op zondag 8 december 2024 @ 01:25:
[...]


Grappig, dat antwoord heb ik dus ook voor deel 2, en voor deel 1 heb ik hetzelfde antwoord als @Marcj

Tijden resp. 530.1µs, 1711.3µs en 1234427.0µs

.edit: haha, bug gevonden, maar nog steeds niet het goede antwoord: ...022 en ...565

@Soultaker Kun je eens een variant van challenge3 releasen waarbij alleen maar de regels zitten die daadwerkelijk kunnen?

.edit: oh nvm, ik heb een early out die niet helemaal correct was. Nu wel goed. De totale tijd voor challenge 3 gaat wel naar beneden: 884605.7µs . Kan nog wel sneller door de stappen van part1 en part2 te combineren.

Ik kon het niet los laten en heb eerst alle edge-cases opgelost voor dag 7. Ik geloof dat het nu wel klopt!

code:

$ day7 < big_inputs/aoc-2024-day-07-challenge-1.txt
Executing
 ├── Input parsed in 1,467µs
 ├── Part 1 calculated in 357µs: ...2841
 ├── Part 2 calculated in 241µs: ...5981
 └── Total time: 2,088µs

$ day7 < big_inputs/aoc-2024-day-07-challenge-2.txt
Executing
 ├── Input parsed in 1,443µs
 ├── Part 1 calculated in 421µs: ...6558
 ├── Part 2 calculated in 516µs: ...8254
 └── Total time: 2,410µs

$ day7 < big_inputs/aoc-2024-day-07-challenge-3.txt
Executing
 ├── Input parsed in 2,261µs
 ├── Part 1 calculated in 48,898µs: ...5032
 ├── Part 2 calculated in 91,670µs: ...7720
 └── Total time: 142,873µs

Na de lunch kan ik pas naar vandaag kijken helaas, eerst andere verplichtingen...

[Soultaker]

Mugwump schreef op zondag 8 december 2024 @ 08:38:
Er kunnen namelijk ook twee punten tussen A en B zijn waarvoor geldt dat de afstand tot A 2x de afstand tot B is en vice versa.

Dat was mijn eerste interpretatie ook. Maar dat blijkt niet voor te komen. Gerelateerd:

FCA schreef op zondag 8 december 2024 @ 09:42:

spoiler:

Zo kun je bijvoorbeeld 2 antenne's met een verschil van (4,2) hebben, maar dan moet je elk gridpoint op een lijn van (2,1) natuurlijk invullen, dus ik een gcd functie erin knallen.

Ik vermoedde op basis van de problem statement dat dat niet voor zou komen, dus ik had een statement:

spoiler:

assert gcd(dr, dc) == 1

erin gestopt om dat te garanderen, en dan is de ambiguïteit die Mugwump noemde ook gelijk opgelost.

[MatHack]

Zoals @Soultaker al aangaf, was dit een makkie omdat ik vanuit de vorige jaren al een toolset had voor grid-based solutions. Mijn oplossing is het langst bezig met het lezen van de file. Het parsen van de input en verwerken naar de antinodes is supersnel.

Ik kon deel 2 overigens goed begrijpen aan de hand van het grid-voorbeeld dat eronder stond, maar de tekst was inderdaad niet de helderheid zelve.

https://github.com/realma...de.Y2024/Solvers/Day08.cs

[Devilfish]

Ik kan wat hulp gebruiken bij dag 6, deel 2... Het voorbeeld gaat goed en kleine voorbeelden die ik kan bedenken ook, toch gaat de input fout...

spoiler: Stappenplan

Loop door de locaties uit deel 1
Als de volgende locatie vrij is (en niet al bezocht) zet daar dan een tijdelijk obstakel neer
Draai de guard naar rechts
Start de check op een loop

Code:

https://github.com/antonr.../tree/main/puzzles/2024/6

Dus als je een voorbeeld kan vinden dat fout gaat, dan kan ik verder checken .

[mbe81]

Devilfish schreef op zondag 8 december 2024 @ 10:51:
Ik kan wat hulp gebruiken bij dag 6, deel 2... Het voorbeeld gaat goed en kleine voorbeelden die ik kan bedenken ook, toch gaat de input fout...

spoiler: Stappenplan

Loop door de locaties uit deel 1
Als de volgende locatie vrij is (en niet al bezocht) zet daar dan een tijdelijk obstakel neer
Draai de guard naar rechts
Start de check op een loop

Code:

https://github.com/antonr.../tree/main/puzzles/2024/6

Dus als je een voorbeeld kan vinden dat fout gaat, dan kan ik verder checken .

Op basis van je beschrijving is je fout denk ik al een paar keer langsgekomen in dit topic:

spoiler:

Op de richting waar je uitkomt kan all een blokkade staan en dan moet je nog een keer draaien.