Advent of Code 2022

[.oisyn]

Soultaker schreef op dinsdag 20 december 2022 @ 15:39:
Wat mij betreft tellen alleen geldige optimalisaties, niet cut-offs die toevallig op de beschikbare invoer werken Anders is natuurlijk het hek van de dam, dan kun je het optimale pad bij wijze van spreke wel hardcoden.

Duh

[Marcj]

Ik zie het nu, op een of andere manier mis ik het meeste optimale pad. Ik zou verwachten dat dit alleen kan liggen aan te agressief afkappen van paden. Zou iemand het beste pad voor large-1a met me kunnen delen (eventueel via DM)? Dan kan ik debuggen waarom die niet doorzocht wordt.

Het rare is dat voor de testinvoer en mijn opdracht op de site het prima werkt.

[.oisyn]

@Marcj AA -> EY -> WD -> BH -> FB -> VZ -> VI -> AD -> LY -> YC -> HY -> OQ -> IF -> JY -> FL

.edit: dit is trouwens niet per se hét beste pad, he. Er kunnen er meerdere zijn met dezelfde score.

[ Voor 35% gewijzigd door .oisyn op 20-12-2022 17:27 ]

[Marcj]

Heel erg bedankt voor deze input @.oisyn ! Ik heb het kunnen vinden. Het uiteindelijke probleem zat eigenlijk in het inlezen, waar een foutje in zat. Daardoor vielen er in een paar gevallen een enkele edge weg. En dit kwam niet voor in de kleinere sets. Helaas was dat ook een groot deel van de reden waarom het zo snel was

Day 16 from day16.txt:
    Part 1: 1923 in 0,027 seconds
    Part 2: 2594 in 0,045 seconds
Full run in 0,111 seconds

Day 16 from day16_big-1.txt:
    Part 1: 117949 in 0,230 seconds
    Part 2: 125937 in 0,357 seconds
Full run in 0,631 seconds

Day 16 from day16_big-2.txt:
    Part 1: 113928 in 0,267 seconds
    Part 2: 130572 in 0,348 seconds
Full run in 0,678 seconds

Day 16 from day16_big-3.txt:
    Part 1: 132860 in 0,166 seconds
    Part 2: 140630 in 0,294 seconds
Full run in 0,507 seconds

Day 16 from day16_big-4.txt:
    Part 1: 137838 in 0,403 seconds
    Part 2: 141648 in 0,443 seconds
Full run in 0,894 seconds

Day 16 from day16_big-5.txt:
    Part 1: 148452 in 5,716 seconds
    Part 2: 166998 in 7,024 seconds
Full run in 12,787 seconds

Day 16 from day16_big-6.txt:
    Part 1: 158683 in 6,397 seconds
    Part 2: 181585 in 63,713 seconds
Full run in 70,157 seconds

Day 16 from day16_big-7.txt:
    Part 1: 58361 in 0,004 seconds
    Part 2: 52131 in 0,003 seconds
Full run in 0,097 seconds

Nou ja, wel weer een hoop geleerd in ieder geval. Voor degene die de code willen bekijken, Day16 is de oplossing, met hier de hulpfuncties voor BFS, DFS en combinaties maken.

[Soultaker]

Omdat ik het niet kan laten, hier nog wat extra testdata voor dag 20: aoc_2022_day20_large.zip.

Oplossingen en referentie-tijden:

$ time pypy3 -O solve.py < large-1.txt 
...037
...357

2.149s

$ time pypy3 -O solve.py < large-2.txt 
...329
...383

9.982s

$ time pypy3 -O solve.py < large-3.txt 
...878
...634

1m14.715s

[HectorMalot]

poeh, mijn simpele oplossing (linked list + array) doet al 17 sec over de eerste. de 2e heb ik na 5 min maar gestopt

code:

$ go run main.go
Part 1: ...037
Part 2: ...357
Time:  17.88357825s

spoiler:

De pragmatische oplossingsrichting is om ook next100, next1000, next10000, next100000, prev100, etc. toe te voegen aan de nodes van de LL. Dan is het 1x iets meer werk met parsen, daarna veel sneller heen en weer springen.

[Soultaker]

HectorMalot schreef op dinsdag 20 december 2022 @ 23:48:

spoiler:

De pragmatische oplossingsrichting is om ook next100, next1000, next10000, next100000, prev100, etc. toe te voegen aan de nodes van de LL. Dan is het 1x iets meer werk met parsen, daarna veel sneller heen en weer springen.

Grappig, dat was ook mijn eerste gedachte, maar ik vond het erg lastig om de details correct te implementeren. Het lastigste is dat je

spoiler:

niet eenmalig die extra pointers kunt toevoegen, je moet ze ook (efficiënt!) updaten wanneer je nodes verplaatst.

Ik denk dat het wel moet kunnen, maar ik vond het persoonlijk lastig om het correct te implementeren, dus ik heb het uiteindelijk met een andere datastructuur opgelost. Misschien dat ik het later alsnog probeer; het is wel een elegante aanpak namelijk.

edit:
Hm, nu ik er wat langer over nagedacht heb weet ik niet of die aanpak wel haalbaar is. Als je b.v. een linkedlist hebt met elk tiende element, en je verwijdert 1 node, dan moet je alle volgende items in de linked list updaten wat nog steeds ongeveer lineair tijd kost. Dat is dus niet echt winst.

[ Voor 17% gewijzigd door Soultaker op 21-12-2022 12:55 ]

[tarlitz]

Python 3

Goed te doen vandaag, leuke puzzel!

spoiler:

Deel 1 zat ik vrijwel direct goed met een resursieve oplossing. Voor deel 2 dacht ik in eerste instantie dat dit weer een enorm gedoe zou worden, maar bleek vrij makkelijk aangezien de rechter aap altijd hetzelfde antwoord geeft. Het was voor mij logisch dat het antwoord sowieso een integer moest zijn en er zat een duidelijk patroon in. Toen heb ik in eerste instantie met de hand uitgerekend wat het andwoord moest zijn. Dit heb ik daarna maar geimplementeerd in de code 😅.

[MrHaas]

Dag 21 is een leuke en niet al te moeilijk.

spoiler:

Deel 2 initieel opgelost met een binary search, maar daarna nog even omgeschreven naar een lineaire vegelijking met wat operator overloading magic om hem direct in mn bestaande evaluate functie te kunnen gooien.

[bakkerjangert]

Leuke opdracht vandaag, aapjes kijken is altijd leuk .

spoiler:

Deel twee heb ik numeriek opgelast; ik merkte dat de ene aap altijd hetzelfde antwoord terug gaf en dat de andere aap voor een delta +1 ok circa hetzelfde verschil aan antwoord terug gaf (in mijn geval circa +2,83... per verhoging van 1). Een loop geschreven die het verschil / delta bij mijn initiële antwoord gooit om een nieuwe guess te doen. Werkte vrij goed voor mijn input; oplossing gevonden binnen 3 iteraties, maar geen idee of het ook voor andere input werkt. Code in python.

[RefleXion]

bakkerjangert schreef op woensdag 21 december 2022 @ 10:07:
Leuke opdracht vandaag, aapjes kijken is altijd leuk .

spoiler:

Deel twee heb ik numeriek opgelast; ik merkte dat de ene aap altijd hetzelfde antwoord terug gaf en dat de andere aap voor een delta +1 ok circa hetzelfde verschil aan antwoord terug gaf (in mijn geval circa +2,83... per verhoging van 1). Een loop geschreven die het verschil / delta bij mijn initiële antwoord gooit om een nieuwe guess te doen. Werkte vrij goed voor mijn input; oplossing gevonden binnen 3 iteraties, maar geen idee of het ook voor andere input werkt. Code in python.

spoiler:

Je kunt het antwoord ook volledig recursief beredeneren, je weet steeds van 1 branch wat het antwoord is, vervolgens kun je de omgekeerde operatie uitvoeren en voor de andere branch weer niveau dieper kijken. Zo heb ik het in ieder geval opgelost (< 1 s in python).

Python code dag 21 deel 1 en 2

[tarlitz]

spoiler:

Het zat me toch niet helemaal lekker dat ik niet direct het juiste antwoord kan berekenen voor part 2. Zou niet zo moeilijk moeten zijn aangezien het om een lineare functie gaat. Het is me nu gelukt om met redelijke precisie op het juiste antwoord te komen door de delta x (1e12) groot genoeg te maken.Linkje naar code.

[IWriteCode]

Leuk die advent of code. De oplossing vandaag snel in elkaar geklopt, met behulp van de fantastische exec functie van python:

spoiler:

monkeys = [x.replace(":", " = ") for x in open("input.txt", "r").read().split("\n")]
while (len(monkeys) > 0):
for i, monkey in enumerate(monkeys):
try:
exec(monkey)
del monkeys[i]
except: pass
print(int(root))

En deel 2 met 'het handje' gedaan in excel, na het uitrekenen na 2 waardes voor humn :-)

[ Voor 10% gewijzigd door IWriteCode op 21-12-2022 11:49 ]

[Diderikdm]

Leuke dag vandaag!

spoiler:

Liep in eerste instantie meerdere keren door de monkeys en wanneer bekend, zette ik hun waarde in een dict. Deel twee eerst met de hand gedaan.

Daarna geoptimaliseerd door elke monkey een lambda te geven naar ofwel hun int, ofwel op metaniveau de berekening.

Deel twee opgelost met een lineaire vergelijking

Dag 21 - Python

[ Voor 12% gewijzigd door Diderikdm op 21-12-2022 17:30 ]

[IWriteCode]

En nu ik dan toch in de draad ben aangehaakt, wil ik graag nog mijn oplossing voor dag 19 delen.

Ik gebruik een genetisch algoritme om de oplossing te vinden. Nadat ik eerst zelf bedacht had hoe zo'n algoritme zou moeten werken, tot een oplossing gekomen, maar dat kostte wel een x aantal pogingen.

Daarna ingelezen hoe zo'n genetisch algoritme echt zou moeten werken en daar m'n code mee verbeterd. Nu vindt ie sneller (en vaker ) het juiste antwoord:

https://topaz.github.io/p...BkKO0LQ7IlIuv7br/+ARlnA==

[RangedNeedles]

Uuugh, al de zoveelste dag waarbij part 2 niet werkt met de echte input

spoiler:

Mijn idee was soortgelijk aan dat van @RefleXion. Ik zoek eerst een pad van 'root' naar 'humn'. Daarna begin ik opnieuw bij root, en kijk ik welke branch ik kan/moet aanpassen, namelijk die waarin 'humn' zit.

Aangezien beide branches dezelfde waarde moeten geven, reken je dan uit wat de branch, waarin 'humn' zit, eigenlijk zou moeten teruggeven. Ga een niveautje lager en rinse en repeat.

Maar door die delingen kom ik soms een kommagetal uit. Ik had verwacht dat alles altijd netjes deelbaar zou zijn En als ik hier dan naar sommige mensen hun (Python-)oplossingen kijk, zie ik ook dat jullie int division doen (door die // operator). Waar staat er gespecifieerd dat dit mag? Of wat mis ik nu net?

Oké, gevonden! Oef... rust in het hoofd opnieuw Blijkbaar moest ik dus...

spoiler:

... in het geval dat de tweede branch de 'humn'-branch is, de volgorde van m'n termen omdraaien. Best 'n domme fout wel.

[ Voor 12% gewijzigd door RangedNeedles op 21-12-2022 12:29 ]

[Diderikdm]

RangedNeedles schreef op woensdag 21 december 2022 @ 12:19:
Uuugh, al de zoveelste dag waarbij part 2 niet werkt met de echte input

spoiler:

Mijn idee was soortgelijk aan dat van @RefleXion. Ik zoek eerst een pad van 'root' naar 'humn'. Daarna begin ik opnieuw bij root, en kijk ik welke branch ik kan/moet aanpassen, namelijk die waarin 'humn' zit.

Aangezien beide branches dezelfde waarde moeten geven, reken je dan uit wat de branch, waarin 'humn' zit, eigenlijk zou moeten teruggeven. Ga een niveautje lager en rinse en repeat.

Maar door die delingen kom ik soms een kommagetal uit. Ik had verwacht dat alles altijd netjes deelbaar zou zijn En als ik hier dan naar sommige mensen hun (Python-)oplossingen kijk, zie ik ook dat jullie int division doen (door die // operator). Waar staat er gespecifieerd dat dit mag? Of wat mis ik nu net?

Je hebt gelijk!

spoiler:

Had bij de division monkeys gekeken naar de uitkomst, welke altijd x.0 was voor mijn input en daarom een int() eromheen gegooid, of intdiv. In theorie kan het inderdaad wel dat er kommagetallen voorkomen.. Ik heb mn code aangepast, thanks

[Varienaja]

Dag 21 in Java.

Voor deel twee doe ik hetzelfde als @RefleXion: kijken welke kant van 'root' uitrekenbaar is, dan een som dieper kijken welke kant uitrekenbaar is, etc, todat 'humn' overblijft.

[Varienaja]

Soultaker schreef op dinsdag 20 december 2022 @ 21:41:
Omdat ik het niet kan laten, hier nog wat extra testdata voor dag 20: aoc_2022_day20_large.zip.

Ik heb het mezelf gemakkeljik gemaakt en gebruik 'teveel' .indexOf operaties op LinkedList.
Bij de eerste reken ik al 90 seconden. De rest heb ik maar niet uitgeprobeerd.

[Soultaker]

Dag 21 was een leuk concept. Zelfde aanpak als de anderen hierboven; volgens mij is er ook niet veel anders mogelijk. Niet super moeilijk maar wel de meeste code die ik heb moeten schrijven door het implementeren van alle operators etc.

RangedNeedles schreef op woensdag 21 december 2022 @ 12:19:

spoiler:

Maar door die delingen kom ik soms een kommagetal uit. Ik had verwacht dat alles altijd netjes deelbaar zou zijn En als ik hier dan naar sommige mensen hun (Python-)oplossingen kijk, zie ik ook dat jullie int division doen (door die // operator). Waar staat er gespecifieerd dat dit mag?

spoiler:

Ik zou er nooit vanuit gaan dat het mag. Ik probeer eventuele aannamen altijd te checken in de code. Bijvoorbeeld in plaats van direct te delen kun je dit doen:

assert a % b == 0
return a // b

Het voordeel daarvan is dat als je aanname niet klopt, je een duidelijk foutmelding krijgt, in plaats van dat je domweg het verkeerde antwoord krijgt.

Als er niet-geheeltallige delingen zouden voorkomen dan zou je in Python vrij makkelijk kunnen overschakelen op Fractions, maar daar zou ik in eerste instantie niet vanuit gaan; het is vrij waarschijnlijk dat de invoer zo geconstrueerd is dat het op te lossen is met alleen gehele getallen, en dat was hier dus ook het geval.

[ Voor 3% gewijzigd door Soultaker op 21-12-2022 14:27 ]

[Ghehe]

spoiler:

Ik dacht eerst deel 2 met z3 te doen maar uiteindelijk een domme brute-force gedaan richting "root: a - b == 0". Getal humn gaat omhoog zolang ik onder 0 zit en weer omlaag als ik erboven zit. Initieel met stapjes van 10 miljard en dan steeds kleiner richting de 0.

Geen idee of alle inputs een lineare correlatie hebben tussen humn en root maar in mijn geval wel (anders zou ik niet hoger-lager kunnen doen?)

[RefleXion]

RangedNeedles schreef op woensdag 21 december 2022 @ 12:19:
En als ik hier dan naar sommige mensen hun (Python-)oplossingen kijk, zie ik ook dat jullie int division doen (door die // operator). Waar staat er gespecifieerd dat dit mag? Of wat mis ik nu net?

Inderdaad, gewoon met // geprobeerd en het werkte, niet verder over nagedacht. Als je in mijn code de // door / vervangt werkt hij ook voor floats.

[Janoz]

Deel 1 van vandaag was zo af, maar voor deel 2 ben ik een rabbit hole ingedoken met een complete polynoom implementatie, totdat ik doorhad dat het antwoord van een monkey maar door 1 andere monkey werd gebruikt. Dat maakte alles heel simpel.

spoiler:

itt de eerdere oplossingen in dit topic heb ik gewoon mijn boom laten berekenen zoals bij part 1, alleen liet ik de kant van de operatie leeg waar humn in zat. Vervolgens zit in root 1 antwoord en ben ik gewoon weer naar beneden de boom in gegaan waarbij ik inverse van de operaties gebruikte icm het antwoord wat ik moest hebben en de waarde uit de andere tak.

Code

[Soultaker]

Ghehe schreef op woensdag 21 december 2022 @ 14:43:
[spoiler]
Ik dacht eerst deel 2 met z3 te doen maar uiteindelijk een domme brute-force gedaan richting "root: a - b == 0". Getal humn gaat omhoog zolang ik onder 0 zit en weer omlaag als ik erboven zit. Initieel met stapjes van 10 miljard en dan steeds kleiner richting de 0.

Aha, dat is feitelijk een exponential search gecombineerd met een binary search, behalve dat je het niet in binaire stappen doet.

Geen idee of alle inputs een lineare correlatie hebben tussen humn en root maar in mijn geval wel (anders zou ik niet hoger-lager kunnen doen?)

In z'n algemeenheid niet, denk bijvoorbeeld aan

spoiler:

1/(10 - x), die discontinu is rond x=10.

Maar het lijkt er op dat in de gegenereerde invoer

spoiler:

geen berekeningen met negatieve getallen voorkomen. Dan is het vrij eenvoudig te concluderen dat de uitkomst ofwel strict stijgt ofwel strict daalt, immers geldt dat voor alle operaties afzonderlijk: voor a + b en a * b geldt dat de uitkomst stijgt met a en b, en voor a - b en a / b geldt dat de uitkomst stijgt met a en daalt met b.

Sterker nog, er lijkt een strict lineair verband te zijn tussen de waarde van humn en het resultaat van de expressie waar die in voorkomt (laten we zeggen, x en f(x)). Dat betekent dat je zelfs geen binary search nodig hebt.

Als je de invoer omzet naar een expressie (met x voor de humn variabele) dan kun je het zo uitrekenen met de Python interpreter. Voor de voorbeeldinvoer is de expressie b.v. ((4+(2*(x-3)))/4) == 150.

En voor mijn testinvoer:

(5*(40172078470474-((427+(87+(((((2*((((11*(((399+((((((356+(2*((10*(610+(((((2*(516+((((((((((3*(((611+(((((((((((((857+((425+((((7*((((9*(x+446))-308)/11)-306))+797)/2)-910))/3))*14)+759)+984)/7)-910)*14)-937)+180)+345)/2)+907)*2))/9)-185))-539)*3)+872)/11)-404)+467)/10)+362)*85)))-655)/7)-783)/2)))-159)))/2)-137)*2)+818)/2))/10)-479))-339)/10)+289))-155)/9)+677)*19)))/2))) == 90565407195785

Als ik dan even experimenteer met Python:

>>> f = lambda x: (5*(40172078470474-((427+(87+(((((2*((((11*(((399+((((((356+(2*((10*(610+(((((2*(516+((((((((((3*(((611+(((((((((((((857+((425+((((7*((((9*(x+446))-308)/11)-306))+797)/2)-910))/3))*14)+759)+984)/7)-910)*14)-937)+180)+345)/2)+907)*2))/9)-185))-539)*3)+872)/11)-404)+467)/10)+362)*85)))-655)/7)-783)/2)))-159)))/2)-137)*2)+818)/2))/10)-479))-339)/10)+289))-155)/9)+677)*19)))/2)))
>>> ff = lambda x: f(Fraction(x))

>>> ff(1) - ff(0)
Fraction(-2261, 66)

>>> ff(2) - ff(1)
Fraction(-2261, 66)

>>> ff(100) - ff(99)
Fraction(-2261, 66)

>>> ff(123456789) - ff(123456788)
Fraction(-2261, 66)

Hmmmm!!! Het verschil is altijd hetzelfde!

>>> (90565407195785 - ff(0)) / (ff(1) - ff(0))
Fraction(3219579395609, 1)

Tadaa! 3219579395609 is mijn antwoord.

Concluderend: voor de gegeven testinvoer hoef je alleen maar de expressie te evalueren voor humn=0 en humn=1 (met breuken) en dan kun je het correcte antwoord zo uitlezen. Maar pas op: floating point getallen hebben niet genoeg precisie!

[Jern_97]

dag 21 runtime 5ms
https://github.com/Jeroen...22/blob/main/src/day21.rs

Ik heb deel 2 opgelost door telkens als ik een variabele nodig had die niet voorkwam in de rechterlid van een vergelijking, de vergelijking om te draaien en verder te rekenen.
Totdat uiteindelijk (na 72 aanpassingen voor mijn input) alle variabelen die ik nodig heb om "humn" te berekenen in het rechterlid staan.

Ben benieuwd welke alternatieve aanpakken er zijn die eleganter zijn, want mijn oplossing is niet meteen de meest compacte naar mijn aanvoelen.

EDIT: indien ik de variabelen gewoon zou representeren met een index ipv een string kan de rekentijd zeker nog heel veel naar beneden... maar had weinig tijd vandaag

[ Voor 13% gewijzigd door Jern_97 op 21-12-2022 20:25 ]

[DeadLock]

Soultaker schreef op woensdag 21 december 2022 @ 14:24:
Dag 21 was een leuk concept. Zelfde aanpak als de anderen hierboven; volgens mij is er ook niet veel anders mogelijk. Niet super moeilijk maar wel de meeste code die ik heb moeten schrijven door het implementeren van alle operators etc.


[...]

spoiler:

Newton's approximation was ook een optie vandaag!

[Varienaja]

Wat een slachtveld vandaag. Temeer daar de layout van het voorbeeld anders is dan de echte input. Ik heb hier een bos if-elsen waar je eng van wordt. (niks generiek geïmplementeerd, gewoon een vouwsel gemaakt en nageprogrammeerd.)

[user109731]

Varienaja schreef op donderdag 22 december 2022 @ 08:41:
Wat een slachtveld vandaag. Temeer daar de layout van het voorbeeld anders is dan de echte input. Ik heb hier een bos if-elsen waar je eng van wordt. (niks generiek geïmplementeerd, gewoon een vouwsel gemaakt en nageprogrammeerd.)

spoiler:

Ik hard-code voor de voorbeeld kubus en mijn input kubus een "cubeInfo" struct met daarin de size van de kubus en voor elke kant de (x, y) van de top-left corner (in de input) + de 4 edges (per edge de target face + direction).

Daarmee kun je de 'echte' code generiek implementeren. Ik vond part 2 wel de minst leuke puzzel dit jaar omdat het veel handmatig uitzoeken vereist - het is vast mogelijk om te automatiseren, maar dat wordt me te tijdrovend...

edit: nu ik er over nadenk.. het is misschien niet eens zo moeilijk om de input te transformeren naar mijn representatie, misschien als ik vanavond tijd heb

[ Voor 13% gewijzigd door user109731 op 22-12-2022 13:11 ]

[Diderikdm]

Was een leuke dag Wel veel gepriegel..

spoiler:

Wil als ik nog tijd over hou ergens deze maand een 3d grid aan 2d coords koppelen (en vice versa). Dan zou in theorie elke variant van een uitgevouwde kubus moeten werken /denk/ ik.

Voor nu semi-hardcoded variant op basis van de vorm van de kubus uit mijn input (zie code) -> wel schaalbaar op formaat (nu 50 per kant).

Dag 22 - Python

[RefleXion]

Varienaja schreef op donderdag 22 december 2022 @ 08:41:
Wat een slachtveld vandaag. Temeer daar de layout van het voorbeeld anders is dan de echte input. Ik heb hier een bos if-elsen waar je eng van wordt. (niks generiek geïmplementeerd, gewoon een vouwsel gemaakt en nageprogrammeerd.)
[Afbeelding]

Fijn om te zien dat ik niet de enige ben die met papier en schaar aan de slag is gegaan!

Erg lastig debuggen. Heeft even geduurd voordat ik door had dat ik mijn lokale coördinaten moest corrigeren naar totale uitgevouwen kaart.

Heb hem inmiddels af:
Dag 22 - deel 2 (Python)

[Asgardian28]

Was weer een hele lastige vandaag. Ben benieuwd wat vrijdag en zaterdag nog in petto hebben. Ik gok morgen wel te doen en zaterdag nog een kraker?

[Soultaker]

Zo, dag 22 ook af (Python code). Ik zou mensen die nog achter lopen met de opdrachten wel aanraden om dag 22 voorlopig over te slaan; dat is echt een tijdrovend klusje.

Zoals anderen heb ik de topologie van de invoer min of meer gehardcode, wat niet heel elegant is. Ik zal nog eens proberen dat te verbeteren.

Overigens lijkt het erop dat bij iedereen de testinvoer dezelfde vorm heeft.

[Diderikdm]

Soultaker schreef op donderdag 22 december 2022 @ 19:57:
Zo, dag 22 ook af (Python code). Ik zou mensen die nog achter lopen met de opdrachten wel aanraden om dag 22 voorlopig over te slaan; dat is echt een tijdrovend klusje.

Zoals anderen heb ik de topologie van de invoer min of meer gehardcode, wat niet heel elegant is. Ik zal nog eens proberen dat te verbeteren.

Overigens lijkt het erop dat bij iedereen de testinvoer dezelfde vorm heeft.

Ik denk dat je gelijk hebt qua gelijke invoer: https://www.reddit.com/r/...tm_medium=web2x&context=3

Asgardian28 schreef op donderdag 22 december 2022 @ 18:51:
Was weer een hele lastige vandaag. Ben benieuwd wat vrijdag en zaterdag nog in petto hebben. Ik gok morgen wel te doen en zaterdag nog een kraker?

Zeker! Vermoed stiekem dat ze beiden nog flink pittig zullen zijn, wellicht nog iets VM/reverse engineering/simuation - igs?

[Remcoder]

spoiler:

Ik ben veel te lang bezig geweest om erachter te komen dat mijn edge detection ook rekening moest houden met de richting waarin ik aan het lopen was.

Ik kwam met mijn input blijkbaar op een hoekpunt uit waarbij ik daarna een verkeerde edge terug gaf, en daarna ging uiteraard de rest compleet de mist ging.

Nadat ik een paar stukken code van anderen vergeleken had en tijdens verschillende debug sessies niet duidelijk zag waar het nu precies mis ging viel het kwartje dat rekening houden met de richting nodig is voor de juiste edge te bepalen in een hoek.

[bakkerjangert]

RefleXion schreef op donderdag 22 december 2022 @ 15:38:
[...]


Fijn om te zien dat ik niet de enige ben die met papier en schaar aan de slag is gegaan!

Erg lastig debuggen. Heeft even geduurd voordat ik door had dat ik mijn lokale coördinaten moest corrigeren naar totale uitgevouwen kaart.

Heb hem inmiddels af:
Dag 22 - deel 2 (Python)

Held, ik snapte maar niet waarom mijn code niet het juiste antwoord gaf. Straks maar even implementeren.

[Soultaker]

Ik heb dag 22 ook nog generiek geïmplementeerd, dus zonder de grootte of de configuratie van de kubus te hardcoden.

Het is niet eens meer code (al is mijn implementatie verre van compact). Het idee erachter is dit:

spoiler:

je kunt de ruimte modelleren als een graaf. De punten van de graaf corresponderen met de '.' en '#' karakters in de invoer. Voor deel 1 zijn de punten verbonden met edges in de vier richtingen met wraparound.

Voor deel 2 kun je een kubus bouwen en vervolgens het grid erop projecteren.

[Diderikdm]

Soultaker schreef op donderdag 22 december 2022 @ 22:51:
Ik heb dag 22 ook nog generiek geïmplementeerd, dus zonder de grootte of de configuratie van de kubus te hardcoden.

Het is niet eens meer code (al is mijn implementatie verre van compact). Het idee erachter is dit:

spoiler:

je kunt de ruimte modelleren als een graaf. De punten van de graaf corresponderen met de '.' en '#' karakters in de invoer. Voor deel 1 zijn de punten verbonden met edges in de vier richtingen met wraparound.

Voor deel 2 kun je een kubus bouwen en vervolgens het grid erop projecteren.

Nice work! Dit staat nog op mn lijstje

[Janoz]

Zo, veel te lang mee bezig geweest, en eigenlijk pas opgelost toen ik daadwerkelijk een kartonnen doosje gepakt had om te zien hoe welke edge aan welke edge geknoopt werd.

Qua oplossing had ik gelijk aan het begin al de oplossingsrichting gekozen die @Soultaker ook al noemde, alhoewel ik het stitchen van de edges nog wel hardcoded heb. Ik ging heel erg de mist in met de verandering van de draaiing waardoor ik het gewoon maar uitgetekend heb, en ook dat hardcoded gedaan heb.

Code

[Diderikdm]

Was prima te doen vandaag vergeleken met gisteren. Code runt in ~10s dus daar valt vast nog iets aan te doen.

Dag 23 - Python

[Janoz]

Inderdaad, door de juiste keuzes in deel 1 had ik deel 2 ook met 2 regeltjes klaar.


Code

[tarlitz]

Best wel tevreden met vandaag na het slachtveld van gisteren. In eerste instantie ging ik volledig de mist in, want ik had de opdracht niet goed gelezen.

spoiler:

Blijkbaar schaalt de grootte met het veld mee met de elven. Hier had ik natuurlijk volledig overheen gelezen en mijn numpy implementatie werkte prima met de test input waar dit niet in voorkwam. Toen maar even herschreven naar een implementatie met sets zoals gebruikelijk is bij dit soort puzzels en dat ging eigenlijk direct goed.

Python code

[Remcoder]

spoiler:

Vandaag was mijn vermoeden over deel 2 juist. We hadden nog geen "game of life" achtige opdracht gehad waarbij je een end state moet bepalen.

Mijn deel 1 oplossing was dus met een paar kleine wijzigingen geschikt te maken voor deel 2.

Het is niet de meest efficiente oplossing, het duurt ~1,5 seconde om ~1000 iteraties te simuleren om deel 2 op te lossen.

[Varienaja]

Dag 23 in Java.

Ik zit overigens op 2,2s voor deel 2. Middelmoot dus, lijkt het.

[Asgardian28]

Dag 23 kan je ook zo oplossen:

spoiler:

Alleen de elfjes tracken in een set van coordinaten.
Werkt vaak gemakkelijker dan een lijst van lijsten of np array bijhouden met padding enzo.
Nog niet opgeschoonde code Denk dat ik vooral wat meer op het goed benoemen van m'n variabelen moet gaan letten

Nu even mentaal voorbereiden op morgen

[Soultaker]

Asgardian28 schreef op vrijdag 23 december 2022 @ 13:58:
Dag 23 kan je ook zo oplossen:

spoiler:

Alleen de elfjes tracken in een set van coordinaten.

Ik denk dat de meeste mensen het juist op die manier hebben opgelost

[tarlitz]

Dag 23 ging prima, dus ik ben nog maar even voor dag 22 gaan zitten. Gister was echt zwaar frustrerend voor mij met debuggen. Ik zat er echt volledig naast met mijn eerste implementatie. Dus ik had het even gelaten voor wat het was. Vandaag was goed te doen, dus ik had wat tijd over om er nog eens in te duiken. Opnieuw begonnen en toen viel het eigelijk allemaal wel mee. Een dag te laat, maar wilde toch graag mijn oplossing delen.

spoiler:

Net als iedereen heb ik ook gewoon alle regeltjes ge-handcode, veel simpeler. 😅

Dag 22 deel 2

[Remcoder]

Soultaker schreef op vrijdag 23 december 2022 @ 14:07:
[...]

Ik denk dat de meeste mensen het juist op die manier hebben opgelost

spoiler:

Zoiets heb ik dus ook gedaan, en dan gecombineerd met mijn Grid.

De lijst van elfjes gebruik ik om het volgende gewenste coördinaat te bepalen, op basis van de huidige beschikbaarheid op de Grid. Daardoor hoef ik niet voor elk elfje aan alle andere elfjes te vragen of die plek beschikbaar is, maar vraag ik dat aan mijn Grid die onderwater een HashMap gebruikt.

Per coördinaat houd ik dan een telling bij van hoeveel elfjes daarheen willen gaan. Weer gebaseerd op een HashMap.

In de move fase kijkt elk elfje dan of die de enige is die naar dat coördinaat wil en gaat erheen.

[joppybt]

Soultaker schreef op donderdag 22 december 2022 @ 19:57:
Zoals anderen heb ik de topologie van de invoer min of meer gehardcode, wat niet heel elegant is. Ik zal nog eens proberen dat te verbeteren.

Overigens lijkt het erop dat bij iedereen de testinvoer dezelfde vorm heeft.

De testinvoer is toch altijd voor iedereen identiek?

[Varienaja]

joppybt schreef op vrijdag 23 december 2022 @ 16:46:
De testinvoer is toch altijd voor iedereen identiek?

Je moet altijd oppassen met aannames. Deze is fout. En ik schrijf te vlug. Ja de testinvoer is volgens mij voor iedereen gelijk. De echte invoer verschilt doorgaans.

[ Voor 22% gewijzigd door Varienaja op 23-12-2022 16:59 ]

[Mschamp]

Varienaja schreef op vrijdag 23 december 2022 @ 16:47:
[...]

Je moet altijd oppassen met aannames. Deze is fout.

Dat wist ik ook niet, ik nam ook aan dat enkel de 'echte' input gebruikersafhankelijk was.
De test-input kan je ook zien zonder ingelogd te zijn en die was altijd hetzelfde.
Ik ging er dus ook van uit dat die voor iedereen hetzelfde was.

[joppybt]

Mschamp schreef op vrijdag 23 december 2022 @ 16:50:
[...]
Dat wist ik ook niet, ik nam ook aan dat enkel de 'echte' input gebruikersafhankelijk was.
De test-input kan je ook zien zonder ingelogd te zijn en die was altijd hetzelfde.
Ik ging er dus ook van uit dat die voor iedereen hetzelfde was.

Even gecontroleerd en mijn test-input is bijvoorbeeld altijd gelijk aan die van een anonieme gebruiker. Volgens mij is dat gewoon altijd zo.

[Soultaker]

De voorbeeld-invoer die in de tekst genoemd wordt is inderdaad voor iedereen gelijk, maar ik bedoelde de officiële invoer die je alleen kunt zien als je inlogt. Die kan veranderen van persoon tot persoon (v.z.i.w. is er een pool van mogelijke invoeren, dus niet iedereen heeft een unieke invoer) maar voor deze dag leek het erop dat de uitgevouwen kubussen in ieder geval allemaal dezelfde vorm hadden (waarschijnlijk waren de muren/instructies wel verschillend).

[FCA]

Ik vond vandaag toch best een lastige, maar vooral begrijpend lezen dan. Ik heb 4 verschillende implementaties van "Finally, at the end of the round, the first direction the Elves considered is moved to the end of the list of directions." geimplementeerd.

spoiler:

Eerst genegeerd , daarna per elf gekeken of ze uberhaupt probeerden te bewegen en dan de move-check order updaten, daarna per elf of ze daadwerkelijk bewogen en dan de move-check updaten, en daarna pas gerealiseerd dat ik te moeilijk dacht en dus de move-check order voor alle elven altijd hetzelfde was, maar per stap verschilde.

Ondertussen zat ik 4 dicts/hashmaps de hele tijd te updaten, wat de foutloosheid ook niet ten goede kwa

[CrossProd]

Erg goed te doen na enkele wat lastigere van de laatste dagen.

spoiler:

Ik heb ook een set gebruikt voor de posities van de elven ipv een grid, maakt alles zoveel makkelijker.

Oplossing in Swift.

[Soultaker]

Ik heb voor de grap dag 23 ook nog met numpy geïmplementeerd (valt nog van alles aan te optimaliseren). Het is conceptueel wel leuk, aangezien je elke simulatie-stap met een constant aantal array-operaties kunt uitvoeren, maar voor de officiële invoer niet heel veel sneller.

Het valt me trouwens tegen dat we nog niet van @.oisyn of andere figuren die ervaring hebben met graphics programming gehoord hebben; de bitmap-aanpak is behoorlijk goed te optimaliseren. B.v. het tellen van buren kan met een convolutie-matrix.

[ Voor 14% gewijzigd door Soultaker op 23-12-2022 21:36 ]

[Soultaker]

Voor wie z'n implementatie wil testen, hier nog wat extra invoer: aoc_2022_day23_large.zip.

Antwoorden en referentie-tijden:

$ time python3 solve-numpy-experiment.py < large-1.txt 
***08
**10

5.428s

$ time python3 solve-numpy-experiment.py < large-2.txt 
***66
**26

35.534s

$ time python3 solve-numpy-experiment.py < large-3.txt 
**90
**23

1m3.877s

$ time python3 solve-numpy-experiment.py < large-4.txt 
***37
**64

2m9.684s

$ time python3 solve-numpy-experiment.py < large-5.txt 
***12
***50

5m39.157s

Dat moet sneller kunnen!

[.oisyn]

Soultaker schreef op vrijdag 23 december 2022 @ 21:32:
Ik heb voor de grap dag 23 ook nog met numpy geïmplementeerd (valt nog van alles aan te optimaliseren). Het is conceptueel wel leuk, aangezien je elke simulatie-stap met een constant aantal array-operaties kunt uitvoeren, maar voor de officiële invoer niet heel veel sneller.

Het valt me trouwens tegen dat we nog niet van @.oisyn of andere figuren die ervaring hebben met graphics programming gehoord hebben; de bitmap-aanpak is behoorlijk goed te optimaliseren. B.v. het tellen van buren kan met een convolutie-matrix.

Ik heb het deze week een beetje druk gehad en heb sinds dag 16 eigenlijk helemaal niet meer naar de opdrachten gekeken

[Asgardian28]

Leuke vandaag! Nu relaxed morgen in voor de laatste alweer!

spoiler:

Wel heel veel tijd verloren omdat ik in mn bfs er vanuit ging dat je altijd kon wachten. Klopt natuurlijk niet als er een storm aankomt. Ging daardoor m'n stormberekeningen helemaal checken en uiteindelijk het gelopen pad vergelijken met het voorbeeld. Doh!

[tarlitz]

Inderdaad een leuke vandaag!

spoiler:

Ik heb best lang lopen knoeien om de data in een `numpy` array te lezen, maar ik dacht dat `np.roll` echt ideaal voor dit probleem zou zijn (spoiler, dat is het ook). Toen een BFS gedaan en een set met veilige posities bijgehouden. Deel 2 was simpelweg deel 1 3x aanroepen.

Python

[Remcoder]

spoiler:

Mijn eerste poging met pathfinding werkte goed voor het voorbeeld, maar met de echte input kwam die niet tot een resultaat binnen een acceptabele tijd...

Daarna maar domweg per minuut alle mogelijke posities bij gaan houden, en zodra de exit in de lijst met posities zit ben ik er.

Ik was wel nog even bang voor deel 2, maar die viel reuze mee.

[Marcj]

Ik heb het ook wat druk gehad, maar ondertussen een paar dagen extra gemaakt.
Day 17 in Kotlin
Day 18 in Kotlin
Day 19 in Kotlin
Day 20 in Kotlin
Day 21 in Kotlin

Alleen dag 19 was nog erg interessant en het duurde een tijd voordat ik voldoende optimalisaties in het zoeken had om het snel genoeg te maken.

spoiler:

- Voor de heuristic heb ik gekeken wat het maximale aantal geodes was dat je mogelijk kon produceren. Deze overschat het nog steeds een stuk, maar beter kreeg ik het niet.
- Ik ga nooit meer een bot bouwen als ik al het maximaal aantal productie heb wat ik kan gebruiken van die resource
- Ik ga ook geen bot bouwen als in de vorige ronde ik geen bot heb gebouwd en deze wel kon betalen

Eens kijken wanneer ik de tijd heb voor 22 - 25...

[Varienaja]

Dag 24 in Java.

[Varienaja]

Soultaker schreef op vrijdag 23 december 2022 @ 22:01:
Voor wie z'n implementatie wil testen, hier nog wat extra invoer: aoc_2022_day23_large.zip.
Dat moet sneller kunnen!

Dan heb ik nog flink wat te sleutelen:

large-1.txt 20s
large-2.txt 184s

Verder probeer ik niet eens.

[RefleXion]

Weer erg leuke opdracht vandaag.

spoiler:

Eerst geprobeerd om met een agent alle opties te volgen, dit werkt voor het voorbeeld, maar is veel te traag voor daadwerkelijke puzzel input. Daarom bij gaan houden wat allemaal mogelijk is per tijdspunt. Hierna is deel twee van de puzzel ook een eitje.

Day 24 (Python)

[user109731]

Dag 24 in JS. Zo'n 170 ms voor deel 1 en 430 ms voor deel 2.

spoiler:

Standaard BFS oplossing. Ik was eerst bang dat ik moest gaan prunen, maar het aantal oude/nieuwe states voor elke iteratie (minuut) is maximaal 25 * 120 (= 3000) dus dat was niet nodig. De positie van de blizzards update ik aan het begin van elke iteratie.

[ Voor 217% gewijzigd door user109731 op 24-12-2022 15:47 ]

[Janoz]

Pff, ik doe nog veel te veel. In 15 seconden heb ik alles ingelezen en een datastructuur gemaakt waarbij ik van elk punt op elk moment in de tijd weet in hoeveel minuten ik bij het begin en in hoeveel minuten ik bij het eind kan komen. Uiteindelijke heen en weer lopen is vervolgens een simpele lookup in een hashmap.

Ben tussendoor af en toe nog ff aan het kijken of ik ook minder kan berekenen..


code

[Soultaker]

Dag 24 oplossing in Python

Ik zie trouwens veel mensen moeilijk doen met het simuleren van blizzards en vervolgens de resultaten te cachen; dat is helemaal niet nodig

spoiler:

je kunt met de originele kaart in vier stappen checken of je op tijdstip `t` op positie (r, c) door een blizzard geraakt wordt; je weet immers dat een blizzard die van rechts komt `t` stappen naar rechts heeft gedaan, dus die moet dan `t` stappen links van jou begonnen zijn, wat betekent dat je alleen van rechts geraakt kan worden als op positie (r, c - t) in de invoer een '>' staat. Dan datzelfde voor elk van de vier richtingen, en een modulo operatie voor de wraparound. (code)

Janoz schreef op zaterdag 24 december 2022 @ 15:52:
Pff, ik doe nog veel te veel. In 15 seconden heb ik alles ingelezen en een datastructuur gemaakt waarbij ik van elk punt op elk moment in de tijd weet in hoeveel minuten ik bij het begin en in hoeveel minuten ik bij het eind kan komen. Uiteindelijke heen en weer lopen is vervolgens een simpele lookup in een hashmap.

Ja, je bent ook knettergek als je de hele graaf expliciet gaat instantiëren terwijl je kunt aanvoelen dat je de meeste nodes waarschijnlijk nooit bezoekt. Heeft je framework geen support voor een breadth-first-search over een impliciete graaf, waarbij je alleen de punten berekent die bezocht worden of gegenereerd worden als buren?

edit:
Ik zie dat je daar inderdaad ondersteuning voor hebt.

Overigens kun je de graaf nog iets kleiner maken door

spoiler:

voor het aantal lagen lcm(height, width) te gebruiken i.p.v. (height * width); scheelt toch weer een factor 5, voor mijn testinvoer tenminste

maar ook dat zou niet nodig moeten zijn. Ik precompute helemaal niets en het loopt binnen 1 seconde.

[ Voor 9% gewijzigd door Soultaker op 24-12-2022 16:25 ]

[user109731]

Soultaker schreef op zaterdag 24 december 2022 @ 16:15:
Dag 24 oplossing in Python

Grappig om te zien dat jij ook hebt gekeken of er verticale blizzards in de start/finish kolom zaten Ik was bang dat dit een instinker was maar gelukkig zat het niet in de invoer.

[Soultaker]

user109731 schreef op zaterdag 24 december 2022 @ 14:38:
Zo'n 170 ms voor deel 1 en 430 ms voor deel 2.

Hoe run jij je code zo snel? Als ik m'n eigen testinput er in copy/paste is 'ie ruim 10 keer zo traag:

$ time node test.js 
Part 1: *** (2106 ms)
Part 2: *** (6173 ms)

real    0m8.483s
user    0m8.721s
sys     0m0.052s

[user109731]

Soultaker schreef op zaterdag 24 december 2022 @ 16:38:
Hoe run jij je code zo snel?

Is dat de laatste versie? Ik had mijn code/post bijgewerkt om de blizzards ook in een Set op te slaan zodat ik ze niet allemaal hoef te doorlopen en dat scheelde behoorlijk.

Dit is op macOS, M1. Nog even gekeken en ik zie < 450 ms voor deel 2 ook in de browser (Chrome en Firefox).

[ Voor 3% gewijzigd door user109731 op 24-12-2022 16:44 ]

[Janoz]

Soultaker schreef op zaterdag 24 december 2022 @ 16:15:
Ja, je bent ook knettergek als je de hele graaf expliciet gaat instantiëren terwijl je kunt aanvoelen dat je de meeste nodes waarschijnlijk nooit bezoekt.

Klopt, maar ik zat te lang te kutten met mijn initiele oplossing (waarschijnlijk meerdere off by one errors ed) dat ik vervolgens maar eens aan het kijken ben gegaan hoe lang de debiele oplossing duurde. En toen ik alles in 15 sec berekende vond ik het nog niet eens zo heel debiel.

Heeft je framework geen support voor een breadth-first-search over een impliciete graaf, waarbij je alleen de punten berekent die bezocht worden of gegenereerd worden als buren?
edit:
Ik zie dat je daar inderdaad ondersteuning voor hebt.

Overigens kun je de graaf nog iets kleiner maken door

spoiler:

voor het aantal lagen lcm(height, width) te gebruiken i.p.v. (height * width); scheelt toch weer een factor 5, voor mijn testinvoer tenminste

maar ook dat zou niet nodig moeten zijn. Ik precompute helemaal niets en het loopt binnen 1 seconde.

Weet ik, maar voor de puzzelinput maakte dat niet uit.

[Soultaker]

user109731 schreef op zaterdag 24 december 2022 @ 16:43:
Is dat de laatste versie?

Aha, wist niet dat je de code nog geüpdate had. De laatste versie loopt inderdaad vrij rap:

$ time node test.js 
Part 1: *** (314 ms)
Part 2: *** (823 ms)

real    0m1.372s
user    0m1.591s
sys     0m0.051s

Nog wel iets minder snel op mijn laptop dan bij jou, maar het verschil is minder dan een factor 2. edit: kan ook aan de testinvoer liggen natuurlijk.

Overigens lijkt dit topic een soort van verkapte reclame voor Apple's M1 CPU's te zijn. Die blijken verdraait snel te zijn voor een laptop CPU.

[ Voor 8% gewijzigd door Soultaker op 24-12-2022 16:56 ]

[Diderikdm]

Prima dagje vandaag, leuke puzzel! Op naar morgen.

~ 2.5s

Dag 24 - Python

[ Voor 3% gewijzigd door Diderikdm op 24-12-2022 20:12 ]

[Diderikdm]

Fijne afsluiter. Vond het weer een leuk jaar dit jaar!

Dag 25 - Python

[MrHaas]

Yes, leuke afsluiter idd. Fijne dagen en tot volgend jaar allemaal!

[RefleXion]

Laatste dag was mijn inziens wel erg simpel in vergelijking met eerdere puzzels.

Had helaas pas op dag 17 door dat deze puzzels weer online stonden, geen punten verdiend dus de eerste dagen, alles daarna op de dag zelf opgelost en de eerdere puzzels nog voor vandaag in kunnen halen. Veel plezier aan gehad.

Oplossing day 25 (Python)

[ Voor 44% gewijzigd door RefleXion op 25-12-2022 10:59 ]

[Varienaja]

Dag 25 in Java.

Ik ben er nog even voor gaan zitten en heb een oplossing gebouwd die helemaal geen conversie naar decimaal nodig heeft. (hoewel.. de per-macht-van-5 optelling is nog decimaal, maar ik had toch geen zin om die vele mogelijkheden van 1 snafu + nog een safu + een carry in een lookup-table te stoppen. )

De puzzles waren weer leuk. Al heb ik echte krakers zoals dag 20 in 2020 wel gemist. Maar misschien ben ik gewoon in de loop der jaren wat pragmatischer geworden.

[tarlitz]

Dag 25 Python

Leuke afsluiter inderdaad! Bedankt iedereen voor het posten van jullie oplossingen! Net als vorig jaar heb ik er weer veel van opgestoken :-)

[Soultaker]

Varienaja schreef op zondag 25 december 2022 @ 11:47:
Dag 25 in Java.

Ik ben er nog even voor gaan zitten en heb een oplossing gebouwd die helemaal geen conversie naar decimaal nodig heeft.

Heb ik ook zo gedaan (de implementatie is ook bijna letterlijk hetzelfde). Blij te zien dat ik niet de enige was die zich realiseerde dat conversie naar integers helemaal niet nodig is; om twee decimale getallen op te tellen ga je ze toch ook niet eerst naar binair omzetten?

Are you trying to tell me I can convert between SNAFUs and decimal numbers?
— No, Neo, I'm telling you, when you're ready, you won't have to.

De puzzles waren weer leuk. Al heb ik echte krakers zoals dag 20 in 2020 wel gemist. Maar misschien ben ik gewoon in de loop der jaren wat pragmatischer geworden.

Mee eens. Het equivalent voor Jurassic Jigsaw was dit jaar Day 22: Monkey Map, en ik vond Day 19: Not Enough Minerals ook wel een leuke uitdaging.

[KabouterSuper]

Varienaja schreef op zondag 25 december 2022 @ 11:47:

De puzzles waren weer leuk. Al heb ik echte krakers zoals dag 20 in 2020 wel gemist. Maar misschien ben ik gewoon in de loop der jaren wat pragmatischer geworden.

Ik ben dit jaar behoorlijk afgehaakt op de optimalisatie-opgaven (Dijkstra-achtige algo's). Dag 16 deel 2 was echt niet leuk omdat een generieke methode te langzaam bleek. En de helft van de python oplossing op internet die ik bekeken heb (ter inspiratie) gaven bij mij niet eens het goede antwoord. En dag 19 was weer een hel waar je je in bochten moest wringen om je antwoord te krijgen, in de hoop dat je niet te kort door de bocht was gegaan....pfft.

[Asgardian28]

Oe vond het vanochtend toch heel lastig, meer dan uur mee bezig geweest, zag het niet meer.

Maarrrr wel voor het eerst keer op global leaderboard gekomen bij een puzzel! Hoewel dat natuurlijk in het niets valt bij eerste plek op tweakers lb 🤪

Tot volgend jaar!

[Remcoder]

Waarom stoppen als je nog door kan met puzzels van voorgaande jaren?

Op naar de 400 sterren!

Ik moet er nog 54.

[vDorst]

Day25 was leuk.
Jammer dat ik nog niet genoeg sterren heb voor part 2.
Tevens ook geleerd dat in Rust conversie van u64/i64 naar f64 niet op de nette manier, "try_from", kan.
Nu maar cast gebruikt met wat extra check zodat het veilig is.

[Daanoz]

Nog wat statistieken van dit jaar:







Thx @ElkeBxl voor het organiseren dit jaar!

[ElkeBxl]

Leuke grafieken @Daanoz ! Het organiseren was graag gedaan

Ik loop nog achter dit jaar, ben nu pas aan dag 16 aan het starten Ooit krijg ik het af, als ik de tijd vind

[MatHack]

Helaas ergens halverwege flink in de ban van een griepvirus dat ik ergens gratis kreeg... binnenkort maar eens proberen alles af te ronden. Is zeker een leuk event.

[Soultaker]

Voor het geval men zich verveelt deze laatste dagen van het jaar nu er geen dagelijkse nieuwe puzzel meer gepost wordt, wilde ik een reminder plaatsen dat een aantal van mijn custom AOC inputs nog niet opgelost zijn. Van makkelijk naar moeilijk (denk ik):

• Voor Day 23: Unstable Diffusion: alle invoer (vooral een optimalisatie-uitdaging)
• Voor Day 18: Boiling Boulders: alle invoer
• Voor Day 20: Grove Positioning System: large-2 en large-3
• Voor Day 11: Monkey in the Middle: large-2.txt (alleen deel 1) (vooral een wiskundige uitdaging)

Daarnaast zag ik dat @Asgardian28 een blog post met statistieken had gepost: Advent of Code analysis through the years. Leuk om te lezen!

[Asgardian28]

Dank je! Was leuk om eens in de stats te duiken

[sjorsjuhmaniac]

Diderikdm schreef op donderdag 15 december 2022 @ 10:08:
Al was het een bruteforce in 1m19s voor deel 2, wel blij met 9 min tussen part 1 en 2 completion time

Nu tijd om (in ieder geval part 2) te refactoren.
Dag 15 - Python

Mooie oplossing! Voor part 2 zat ik zelf ook aan hetzelfde te denken maar heb hem niet uitgewerkt omdat ik er niet op kwam om te stellen:

spoiler:

https://github.com/Jeroen...09da933d/src/day15.rs#L48
[quote]
its distance must be exactly r+1 from at least 2 sensors
[/quote]

Ik begrijp dat het punt voor meer dan 1 sensor op (>r, >r) moet liggen, maar begrijp niet waarom het precies op (r+1, r+1) moet ligen. Maar waarom kan het punt niet op (r+1, r+2) voor een van de (2) sensoren liggen?
De >r zat namelijk in mijn hoofd. In dat geval is het niet meer zo eenvoudig om de snijpunten te bepalen.

[Diderikdm]

sjorsjuhmaniac schreef op zondag 1 januari 2023 @ 16:15:
[...]


Mooie oplossing! Voor part 2 zat ik zelf ook aan hetzelfde te denken maar heb hem niet uitgewerkt omdat ik er niet op kwam om te stellen:

spoiler:

https://github.com/Jeroen...09da933d/src/day15.rs#L48
[quote]
its distance must be exactly r+1 from at least 2 sensors
[/quote]

Ik begrijp dat het punt voor meer dan 1 sensor op (>r, >r) moet liggen, maar begrijp niet waarom het precies op (r+1, r+1) moet ligen. Maar waarom kan het punt niet op (r+1, r+2) voor een van de (2) sensoren liggen?
De >r zat namelijk in mijn hoofd. In dat geval is het niet meer zo eenvoudig om de snijpunten te bepalen.

Thanks!

spoiler:

De enige reden waarom dit punt op precies (r + 1, r + 1) moet liggen is omdat er precies 1 punt binnen het gegeven vlak (but the distress beacon must have x and y coordinates each no lower than 0 and no larger than 4000000.) niet bedekt wordt door sensor(s) + r (Find the only possible position for the distress beacon. What is its tuning frequency?)

In het geval van (r + 1, r + 2) heb je in het allerbeste geval al twee punten die niet geraakt worden (r + 1, r + 1) en (r + 1, r + 2). Er moet dus een snijpunt zijn van 2+ (r + 1) lijnen om te garanderen dat slechts 1 punt binnen dit vlak niet geraakt wordt door sensor + r. Het punt kan wel op r + 2 van een sensor liggen, al liggen er dan ook meerdere sensors wel op r + 1.

In mijn geval zijn dit 288 snijpunten in de volgende vorm (gesimplificeerd):



Met bovenstaande kun je zelf nog een stapje verder gaan. Om precies 1 leeg punt te vinden, kan je twee evenwijdige lijnen vinden (r en r + 2), en deze checken tegen twee aan deze lijnen kruisende evenwijdige (r en r + 2) lijnen:

[ Voor 19% gewijzigd door Diderikdm op 02-01-2023 10:32 ]

[sjorsjuhmaniac]

Thanks @Diderikdm voor de gedetailleerde uitleg!

Door je laatste opm. wel een nieuwe vraag

spoiler:

Ik kon de betreffende logica van de pallellen lijnen r en r+2 nog niet plaatsen.

Ik heb het gegeven puzzlevoorbeeld met [code]visualize.py[/code] geplot. Daarna heb ik met dezelfde input alleen r en r + 2 geplot.
Groen met r
Blauw met r + 1
Geel met r + 2

Ik zie er nog geen verband tussen
er zijn meerdere posities waar r + 1 voor 2 sensoren waar is waarbij dan ook r en r + 2 dubbelzijdig ...
Het enige wat me wel opvalt is dat de r + 2 lijnen (geel) alleen bij het lege punt elkaar volledig doorkruizen. Bij de omcirkelde punten raken/overlappen ze elkaar wel maar lopen ze op tenminste 1 hoek niet door.

Wat is het verband waar je op doelt?


https://tweakers.net/i/UG...reyXGnHI.png?f=user_large

https://tweakers.net/i/4o...lYzf37gG.png?f=user_large

[ Voor 17% gewijzigd door sjorsjuhmaniac op 02-01-2023 21:51 ]

[.oisyn]

Diderikdm schreef op maandag 2 januari 2023 @ 10:20:

spoiler:

Met bovenstaande kun je zelf nog een stapje verder gaan. Om precies 1 leeg punt te vinden, kan je twee evenwijdige lijnen vinden (r en r + 2), en deze checken tegen twee aan deze lijnen kruisende evenwijdige (r en r + 2) lijnen:

spoiler:

Hiermee maak je het jezelf wel ingewikkelder dan nodig. Want waarom zou je per se kijken naar evenwijdige lijnen r en r+2, als je ook gewoon de lijn r+1 kunt pakken? Twee sensoren met range A en B die precies rA+rB+1 van elkaar afliggen delen zo'n lijn.

[Diderikdm]

sjorsjuhmaniac schreef op maandag 2 januari 2023 @ 21:24:
Thanks @Diderikdm voor de gedetailleerde uitleg!

Door je laatste opm. wel een nieuwe vraag

spoiler:

Ik kon de betreffende logica van de pallellen lijnen r en r+2 nog niet plaatsen.

Ik heb het gegeven puzzlevoorbeeld met [code]visualize.py[/code] geplot. Daarna heb ik met dezelfde input alleen r en r + 2 geplot.
Groen met r
Blauw met r + 1
Geel met r + 2

Ik zie er nog geen verband tussen
er zijn meerdere posities waar r + 1 voor 2 sensoren waar is waarbij dan ook r en r + 2 dubbelzijdig ...
Het enige wat me wel opvalt is dat de r + 2 lijnen (geel) alleen bij het lege punt elkaar volledig doorkruizen. Bij de omcirkelde punten raken/overlappen ze elkaar wel maar lopen ze op tenminste 1 hoek niet door.

Wat is het verband waar je op doelt?


https://tweakers.net/i/UG...reyXGnHI.png?f=user_large

https://tweakers.net/i/4o...lYzf37gG.png?f=user_large

.oisyn schreef op maandag 2 januari 2023 @ 21:54:
[...]

spoiler:

Hiermee maak je het jezelf wel ingewikkelder dan nodig. Want waarom zou je per se kijken naar evenwijdige lijnen r en r+2, als je ook gewoon de lijn r+1 kunt pakken? Twee sensoren met range A en B die precies rA+rB+1 van elkaar afliggen delen zo'n lijn.

Ah yes..

spoiler:

Ik had dit zelf nog niet verder uitgewerkt, maar mijn vermoeden is dat wanneer je alleen de (r + 1) van de evenwijdige lijnen pakt (r en r + 2), je met de methode van het eerdere voorbeeld nog een stuk sneller (dan alle (r + 1) kruispunten vergelijken t.o.v. alle scanners) tot het antwoord komt. Ik weet nu inderdaad alleen niet of je door de extra vergelijking evenwijdig/niet echt veel runtime opschiet

[.oisyn]

@Diderikdm

spoiler:

Ik zie niet helemaal hoe jou methode voorkomt dat je snijpunten moet testen op overlap met andere sensoren.

[Diderikdm]

.oisyn schreef op maandag 2 januari 2023 @ 22:57:
@Diderikdm

spoiler:

Ik zie niet helemaal hoe jou methode voorkomt dat je snijpunten moet testen op overlap met andere sensoren.

spoiler:

Ik denk dat ik niet duidelijk genoeg was in mijn uitleg, je zou voor deze selectie ook een vergeliking moeten doen; In bovenstaand geval test je niet álle (r + 1) snijpunten die te vinden zijn zoals in het eerste voorbeeld, maar alleen de snijpunten van de (r + 1) lijnen binnen de evenwijdige (r en r + 2) lijnen. Vermoedelijk hoef je dan niet 200+ snijpunten te vergelijken met alle sensors, maar (naar schatting) onder de 50-100.

[.oisyn]

Diderikdm schreef op dinsdag 3 januari 2023 @ 00:02:
[...]

spoiler:

Ik denk dat ik niet duidelijk genoeg was in mijn uitleg, je zou voor deze selectie ook een vergeliking moeten doen; In bovenstaand geval test je niet álle (r + 1) snijpunten die te vinden zijn zoals in het eerste voorbeeld, maar alleen de snijpunten van de (r + 1) lijnen binnen de evenwijdige (r en r + 2) lijnen. Vermoedelijk hoef je dan niet 200+ snijpunten te vergelijken met alle sensors, maar (naar schatting) onder de 50-100.

spoiler:

Maar dan mis je de kern van mijn post. Namelijk, als je eerst naar paren van sensoren kijkt en alleen die paren pakt die rA+rB+1 uit elkaar liggen, dan hou je nog maar een handjevol potentiele lijnen over.

[Diderikdm]

.oisyn schreef op dinsdag 3 januari 2023 @ 00:04:
[...]

spoiler:

Maar dan mis je de kern van mijn post. Namelijk, als je eerst naar paren van sensoren kijkt en alleen die paren pakt die rA+rB+1 uit elkaar liggen, dan hou je nog maar een handjevol potentiele lijnen over.

spoiler:

Right, het is exact de conclusie van wat ik bedoel alleen beter uitgewerkt

[quote]maar mijn vermoeden is dat wanneer je alleen de (r + 1) van de evenwijdige lijnen pakt (r en r + 2)[/quote]

^ Welke natuurlijk overlappen.

[Janoz]

Aangezien de AoC afgelopen is lijkt het me niet meer perse noodzakelijk om alles in spoiler tags te zetten. Vanaf nu mogen wat mij betreft de discussies gewoon open gevoerd worden. Komt de leesbaarheid van het topic ook ten goede.

[sjorsjuhmaniac]

Diderikdm schreef op maandag 2 januari 2023 @ 22:53:
[...]


[...]


Ah yes..

Ik had dit zelf nog niet verder uitgewerkt, maar mijn vermoeden is dat wanneer je alleen de (r + 1) van de evenwijdige lijnen pakt (r en r + 2), je met de methode van het eerdere voorbeeld nog een stuk sneller (dan alle (r + 1) kruispunten vergelijken t.o.v. alle scanners) tot het antwoord komt. Ik weet nu inderdaad alleen niet of je door de extra vergelijking evenwijdig/niet echt veel runtime opschiet

Aah yes, ik snap nu wat je bedoelde

[Marcj]

Marcj schreef op dinsdag 20 december 2022 @ 18:19:
...

Day 16 from day16.txt:
    Part 1: 1923 in 0,027 seconds
    Part 2: 2594 in 0,045 seconds
Full run in 0,111 seconds

Day 16 from day16_big-1.txt:
    Part 1: 117949 in 0,230 seconds
    Part 2: 125937 in 0,357 seconds
Full run in 0,631 seconds

Day 16 from day16_big-2.txt:
    Part 1: 113928 in 0,267 seconds
    Part 2: 130572 in 0,348 seconds
Full run in 0,678 seconds

Day 16 from day16_big-3.txt:
    Part 1: 132860 in 0,166 seconds
    Part 2: 140630 in 0,294 seconds
Full run in 0,507 seconds

Day 16 from day16_big-4.txt:
    Part 1: 137838 in 0,403 seconds
    Part 2: 141648 in 0,443 seconds
Full run in 0,894 seconds

Day 16 from day16_big-5.txt:
    Part 1: 148452 in 5,716 seconds
    Part 2: 166998 in 7,024 seconds
Full run in 12,787 seconds

Day 16 from day16_big-6.txt:
    Part 1: 158683 in 6,397 seconds
    Part 2: 181585 in 63,713 seconds
Full run in 70,157 seconds

Day 16 from day16_big-7.txt:
    Part 1: 58361 in 0,004 seconds
    Part 2: 52131 in 0,003 seconds
Full run in 0,097 seconds

...

Ik ben de laatste tijd met Rust bezig geweest om toch eens een taal te leren die wat dichter op de machine zat. Hiermee kan ik de meeste runtimes met ongeveer een factor 4 - 6 versnellen. Wat resultaten voor deze use-case, ik vond het leuk om dag 16 opnieuw te implementeren.

$ target/release/day16 < 2022/big_inputs/day16_big-1.txt
Executing
 ├── Input parsed in 706µs
 ├── Part 1 calculated in 76,496µs: 117949
 ├── Part 2 calculated in 117,812µs: 125937
 └── Total time: 195,060µs

$ target/release/day16 < 2022/big_inputs/day16_big-2.txt
Executing
 ├── Input parsed in 1,057µs
 ├── Part 1 calculated in 92,986µs: 113928
 ├── Part 2 calculated in 77,699µs: 130572
 └── Total time: 171,778µs

$ target/release/day16 < 2022/big_inputs/day16_big-3.txt
Executing
 ├── Input parsed in 637µs
 ├── Part 1 calculated in 71,237µs: 132860
 ├── Part 2 calculated in 100,572µs: 140630
 └── Total time: 172,493µs

$ target/release/day16 < 2022/big_inputs/day16_big-4.txt
Executing
 ├── Input parsed in 647µs
 ├── Part 1 calculated in 112,746µs: 137838
 ├── Part 2 calculated in 161,786µs: 141648
 └── Total time: 275,218µs

$ target/release/day16 < 2022/big_inputs/day16_big-5.txt
Executing
 ├── Input parsed in 684µs
 ├── Part 1 calculated in 1,742,271µs: 148452
 ├── Part 2 calculated in 2,056,727µs: 166998
 └── Total time: 3,799,795µs

$ target/release/day16 < 2022/big_inputs/day16_big-6.txt
Executing
 ├── Input parsed in 1,069µs
 ├── Part 1 calculated in 2,139,708µs: 158683
 ├── Part 2 calculated in 6,206,188µs: 181585
 └── Total time: 8,347,046µs

$ target/release/day16 < 2022/big_inputs/day16_big-7.txt
Executing
 ├── Input parsed in 2,799µs
 ├── Part 1 calculated in 50µs: 58361
 ├── Part 2 calculated in 99µs: 52131
 └── Total time: 2,972µs

Of het waard is? Ik vind de Kotlin versie wel een stuk leesbaarder, maar de Rust versie kun je wel dingen doen die dichter op de hardware zitten en nog behoorlijk wat performance vinden...

ps. Deze code is gerund op een M1 macBook Pro