Advent of Code 2024

[Janoz]

Zo, even een animated gif van mijn connectedsets in elkaar kunnen hacken.

[KabouterSuper]

breew schreef op donderdag 12 december 2024 @ 15:13:

spoiler:

- per blok, per polylijn, kijk uit hoeveel punten de polylijn bestaat. (aantal punten - 1) is aantal lijndelen.

spoiler:

Heb je geen last van polygonen met overlappende punten?
________
|.. _____ |__
|.. |_____|.....|
|................... |
|__________|

[breew]

KabouterSuper schreef op donderdag 12 december 2024 @ 18:34:
[...]

spoiler:

Heb je geen last van polygonen met overlappende punten?
________
|.. _____ |__
|.. |_____|.....|
|................... |
|__________|

spoiler:

Ik denk dat dat goed gaat. Ik beschouw de grenzen van ieder blok van letters als een individuele grens; die kunnen zichzelf niet overlappen. Pas aan het eind tel ik de lijnen bij elkaar op.
Jouw voorbeeld hierboven zou dus in eerste instantie bestaan uit 2polygonen, daarna uit twee linestrings. Pas aan het eind tel ik de lijnsegmenten bij elkaar op; overlap is dan volgens mij geen issue.

[.oisyn]

Soultaker schreef op donderdag 12 december 2024 @ 13:08:

Extra testdata voor dag 12: aoc-2024-day-12-challenge-1-and-2.zip

PS|main#2|D:\Projects\Advent2024>cargo r -p day12 --release -- -i .\extra\day12\combined-1.txt
    Finished `release` profile [optimized] target(s) in 0.05s
     Running `target\release\day12.exe -i .\extra\day12\combined-1.txt`
Time spent: 27379.3µs
57718154044 - 40605118790

PS|main#2|D:\Projects\Advent2024>cargo r -p day12 --release -- -i .\extra\day12\combined-2.txt
    Finished `release` profile [optimized] target(s) in 0.05s
     Running `target\release\day12.exe -i .\extra\day12\combined-2.txt`
Time spent: 245599.9µs
3591315362592 - 2549457500666

spoiler:

Ik loop 1x linear over de grid, van links naar rechts, van boven naar onder. Elke grid cell krijgt een region id. Als alleen links of boven hetzelfde is, dan voegt hij zichzelf aan de region. Als links én boven hetzelfde is met verschillende ids, dan merget hij die regions en krijgt een van de twee ids een verwijzijng naar de andere (dus ik hoef de grid met ids niet te updaten).

Verder bereken ik een mask adhv of { links-boven, boven, rechts-boven, links } hetzelfde zijn, en dat geeft dus in totaal 16 combinaties. Voor elk van die combinaties heb ik een tabelletje wat dat doet met de perimeter en sides als ik in die combinatie een grid-cell toevoeg aan de region.

Daarna is het een kwestie van regions optellen.

[ Voor 31% gewijzigd door .oisyn op 13-12-2024 01:29 ]

[Soultaker]

Ik had het voor deel 1 te ingewikkeld gemaakt:

spoiler:

een dynamic programming oplossing geschreven, wat natuurlijk overkill is want de volgorde waarin je knop A en B drukt doet er helemaal niet toe, alleen het aantal, dus een simpele for lus van 1 tot 100 (het maximaal aantal knopdrukken) had volstaan.

Python code hier, maar dit werkt dus alleen voor deel 1.

Voor wie een hint wil voor deel 2:

spoiler:

De verhouding dx/dy verschilt voor knop A en B voor elke testcase.

Een grotere hint:

spoiler:

Laten we de verplaatsing bij indrukken van knop A (ax, ay) noemen, en bij B (bx, by). Als je knop A n keer indrukt, dan heb je nog (x - ax*n, y - ay*n) over. Dat is een oplossing als (x - ax*n) / (y - ay*n) = bx / by. Het aantal keer dat je B moet indrukken is dan m = (x - ax*n) / bx = (y - ay*n) / by.

En de oplossing:

spoiler:

Neem w.l.o.g aan dat ax/ay ≤ x/y ≤ bx/by. Die situatie kun je desnoods creëeren door A en B om te draaien (kosten niet vergeten!), en zoniet, dan is het probleem onoplosbaar. Dan wordt de ratio r = (x - ax*n) / (y - ay*n) groter naarmate n groter wordt. Je kunt dan een binary search uitvoeren om de waarde van n te vinden waarbij r = bx/by, en dan m berekenen zoals hierboven beschreven.

Python code

edit:
Overigens denk ik dat er ook wel een O(1) closed form oplossing is. Even over nadenken...

[ Voor 8% gewijzigd door Soultaker op 13-12-2024 07:04 ]

[Robbinb1993]

Soultaker schreef op vrijdag 13 december 2024 @ 07:00:
Ik had het voor deel 1 te ingewikkeld gemaakt:

spoiler:

een dynamic programming oplossing geschreven, wat natuurlijk overkill is want de volgorde waarin je knop A en B drukt doet er helemaal niet toe, alleen het aantal, dus een simpele for lus van 1 tot 100 (het maximaal aantal knopdrukken) had volstaan.

Python code hier, maar dit werkt dus alleen voor deel 1.

Voor wie een hint wil voor deel 2:

spoiler:

De verhouding dx/dy verschilt voor knop A en B voor elke testcase.

Een grotere hint:

spoiler:

Laten we de verplaatsing bij indrukken van knop A (ax, ay) noemen, en bij B (bx, by). Als je knop A n keer indrukt, dan heb je nog (x - ax*n, y - ay*n) over. Dat is een oplossing als (x - ax*n) / (y - ay*n) = bx / by. Het aantal keer dat je B moet indrukken is dan m = (x - ax*n) / bx = (y - ay*n) / by.

En de oplossing:

spoiler:

Neem w.l.o.g aan dat ax/ay ≤ x/y ≤ bx/by. Die situatie kun je desnoods creëeren door A en B om te draaien (kosten niet vergeten!), en zoniet, dan is het probleem onoplosbaar. Dan wordt de ratio r = (x - ax*n) / (y - ay*n) groter naarmate n groter wordt. Je kunt dan een binary search uitvoeren om de waarde van n te vinden waarbij r = bx/by, en dan m berekenen zoals hierboven beschreven.

Python code

edit:
Overigens denk ik dat er ook wel een O(1) closed form oplossing is. Even over nadenken...

spoiler:

Cramer's Rule: an explicit formula for the solution of a system of linear equations with as many equations as unknowns. Werkt alleen als er een unieke oplossing is. Als je lineaire algebra wil vermijden dan is binary search inderdaad een goed alternatief, aangezien er maximaal maar één mogelijke oplossing voor de gegeven invoer is. Alhoewel dat niet gelijk duidelijk was, ik ging er in eerste instantie vanuit dat er vele mogelijke oplossingen konden zijn en we n moesten minimaliseren om n*3+m minimaal te houden.

In het geval er wel meer dan één oplossing kan zijn, wordt het probleem een stuk complexer. Er zal dan met behulp van lineaire algebra of misschien Extended Euclidean algorithm alsnog wel een manier bestaan, maar dat is toch wel wat uitzoekwerk.

https://github.com/Robbin.../blob/main/day13/day13.cc

[ Voor 16% gewijzigd door Robbinb1993 op 13-12-2024 09:09 ]

[KabouterSuper]

Soultaker schreef op vrijdag 13 december 2024 @ 07:00:

edit:
Overigens denk ik dat er ook wel een O(1) closed form oplossing is. Even over nadenken...

Het is gewoon lineaire algebra.

spoiler:

Getallen van a en b in een 2x2-matrix stoppen, inverse berekenen en vermenigvuldigen met de prijslocatie.
Dan checken of deze geheeltallig is.

Voor mij was het sneller om de inverse en vermenigvuldiging uit te schrijven dan om numpy te pakken.

Edit: matrices zijn voor de data altijd inverteerbaar. Anders kom je met een eigenwaarde decompositie waarschijnlijk wel een eind.

Leuke edge case:

code:

A: X+5, Y+5
B: X+1, Y+1
P: X=102, Y=102

[ Voor 17% gewijzigd door KabouterSuper op 13-12-2024 08:29 ]

[Janoz]

Pff, heel lang op papier lopen kloten maar deel 2 draait in 2ms . Uiteindelijk heel lang gedaan over een + welke een - had moeten zijn ..

[Soultaker]

Robbinb1993 schreef op vrijdag 13 december 2024 @ 07:39:

spoiler:

Cramer's Rule [..]
https://github.com/Robbin.../blob/main/day13/day13.cc

Informatief Het is minstens 10 jaar geleden dat ik daar voor het laatst van gehoord heb. Ik heb de vergelijkingen gewoon met de hand uitgeschreven, en dan kom ik (in essentie) op hetzelfde uit: 13-alt.py (waarschijnlijk gaat dit niet zo makkelijk met meer dan 2 variabelen).

KabouterSuper schreef op vrijdag 13 december 2024 @ 08:16:
Leuke edge case:

code:

A: X+5, Y+5
B: X+1, Y+1
P: X=102, Y=102

Of deze:

Button A: X+1, Y+1
Button B: X+3, Y+2
Prize: X=10, Y=11

Helaas zaten die niet in de invoer. Had wat mij betreft best gemogen, aangezien je redelijk eenvoudig je antwoorden kunt checken en dan debuggen waar je fout gaat.

[KabouterSuper]

Soultaker schreef op vrijdag 13 december 2024 @ 09:10:
[...]
Of deze:

Button A: X+1, Y+1
Button B: X+3, Y+2
Prize: X=10, Y=11

Helaas zaten die niet in de invoer. Had wat mij betreft best gemogen, aangezien je redelijk eenvoudig je antwoorden kunt checken en dan debuggen waar je fout gaat.

Verrek, die check ik niet eens.

Ook deze zit er trouwens niet in:

Button A: X+1, Y+1
Button B: X-1, Y+0
Prize: X=10, Y=11

[Soultaker]

KabouterSuper schreef op vrijdag 13 december 2024 @ 09:19:
Ook deze zit er trouwens niet in:

Button A: X+1, Y+1
Button B: X-1, Y+0
Prize: X=10, Y=11

Da's niet helemaal compatibel met de probleemstelling:

With a little experimentation, you figure out that each machine's buttons are configured to move the claw a specific amount to the right (along the X axis) and a specific amount forward (along the Y axis) each time that button is pressed.

(Interpreteer ik als: zowel dx als dy moeten strict positief zijn.) Had wel gekund als de probleemstelling net wat anders geformuleerd was. Dan kun je ook nog dingen verzinnen als:

Button A: X+0, Y+0
Button B: X+0, Y+0
Prize: X=0, Y=0

Button A: X+0, Y+0
Button B: X+1, Y+1
Prize: X=123, Y=123

[ Voor 16% gewijzigd door Soultaker op 13-12-2024 09:25 ]

[KabouterSuper]

Robbinb1993 schreef op vrijdag 13 december 2024 @ 07:39:
[...]

spoiler:

Cramer's Rule: an explicit formula for the solution of a system of linear equations with as many equations as unknowns. Werkt alleen als er een unieke oplossing is. Als je lineaire algebra wil vermijden dan is binary search inderdaad een goed alternatief, aangezien er maximaal maar één mogelijke oplossing voor de gegeven invoer is. Alhoewel dat niet gelijk duidelijk was, ik ging er in eerste instantie vanuit dat er vele mogelijke oplossingen konden zijn en we n moesten minimaliseren om n*3+m minimaal te houden.

In het geval er wel meer dan één oplossing kan zijn, wordt het probleem een stuk complexer. Er zal dan met behulp van lineaire algebra of misschien Extended Euclidean algorithm alsnog wel een manier bestaan, maar dat is toch wel wat uitzoekwerk.

https://github.com/Robbin.../blob/main/day13/day13.cc

spoiler:

Nooit van Cramer's Rule gehoord (en dat met een doctorsgraad in wiskunde). Maar het blijkt gewoon de formule te zijn die de codeterminanten gebruikt, daar ben ik goed mee bekend. Het is precies wat ik heb gedaan om de 2x2 matrices te inverteren.

Bij een niet-inverteerbare matrix zou ik kijken of ik met de Jordan vorm iets kan doen of ik ga voor mijn favoriete methode, namelijk eigenwaarde-decompositie. Anyway, de input data was vandaag erg netjes, dus geen complicaties.

[mbe81]

KabouterSuper schreef op vrijdag 13 december 2024 @ 08:16:
[...]

Het is gewoon lineaire algebra.

spoiler:

Getallen van a en b in een 2x2-matrix stoppen, inverse berekenen en vermenigvuldigen met de prijslocatie.
Dan checken of deze geheeltallig is.

Voor mij was het sneller om de inverse en vermenigvuldiging uit te schrijven dan om numpy te pakken.

Edit: matrices zijn voor de data altijd inverteerbaar. Anders kom je met een eigenwaarde decompositie waarschijnlijk wel een eind.

Leuke edge case:

code:

A: X+5, Y+5
B: X+1, Y+1
P: X=102, Y=102

Hier moet ik me vanavond maar eens in verdiepen dan... Ben niet zo (of eigenlijk helemaal niet) wiskundig onderlegd als sommige van jullie hier. Mooi om te zien maar ik moet dan echt wel een paar keer kijken wat jullie precies doen en waarom.

[KabouterSuper]

mbe81 schreef op vrijdag 13 december 2024 @ 09:28:
[...]


Hier moet ik me vanavond maar eens in verdiepen dan... Ben niet zo (of eigenlijk helemaal niet) wiskundig onderlegd als sommige van jullie hier. Mooi om te zien maar ik moet dan echt wel een paar keer kijken wat jullie precies doen en waarom.

spoiler:

Ik gebruik deze formule die ik vrijwel blind heb getypt.

def linalgsolve(a,b,p):
det=a[0]*b[1]-a[1]*b[0]
return ( (b[1]*p[0]-b[0]*p[1])/det, (-a[1]*p[0]+a[0]*p[1])/det)

logica is:

inverse van A = 1/determinant * matrix van codeterminanten

determinant van 2x2 matrix is m00*m11-m01*m10

elk element i,j van de codeterminantenmatrix is (-1)^(i+j)*determinant van de matrix zonder rij i en kolom j (geteld vanaf 0). Bij een 2x2 matrix is een matrix zonder een rij en kolom maar één getal, dus eenvoudig.
Dus de codeterminantenmatrix wordt:
m11 -m10
-m01 m00

[bakkerjangert]

Moest wel even nadenken vandaag, maar uiteindelijk is het vrij simpel. Code in python.

spoiler:

Het zijn twee vergelijkingen met 2 onbekende dus is per machine maar één oplossing mogelijk. Uitschrijven en checken of de a en b waarden positieve integers zijn. Ik doe dat door te checken of waarden afgerond naar de dichtstbijzijnde int het juiste antwoord geeft. Uitwerking van de vergelijking:

[.oisyn]

KabouterSuper schreef op vrijdag 13 december 2024 @ 09:27:

spoiler:

Bij een niet-inverteerbare matrix zou ik kijken of ik met de Jordan vorm iets kan doen of ik ga voor mijn favoriete methode, namelijk eigenwaarde-decompositie. Anyway, de input data was vandaag erg netjes, dus geen complicaties.

spoiler:

Bij een niet-inverteerbare matrix (determinant = 0) zijn de assen colinear of minstens een van de twee is [0, 0], en wordt de oplossing vrij triviaal als die bestaat

[Soultaker]

.oisyn schreef op vrijdag 13 december 2024 @ 10:18:

spoiler:

Bij een niet-inverteerbare matrix (determinant = 0) zijn de assen colinear of minstens een van de twee is [0, 0], en wordt de oplossing vrij triviaal als die bestaat

Dan is het een 1-dimensionaal probleem geworden en dan is een reële oplossing eenvoudig te vinden (of eenvoudig aan te tonen dat er geen oplossing is), maar een geheeltallige oplossing is een stuk lastiger.

Bijvoorbeeld: 123n + 456m = 5877 is helemaal niet triviaal om op te lossen als n en m niet-negatieve integers moeten zijn, zeker niet als je ook nog 3n + m moet minimaliseren.

Dit soort problemen komen wel vaker voor bij Advent of Code, dus wie zich wil voorbereiden kan zich alvast een beetje inlezen op Wikipedia: Diophantine equation en Bézout's identity.

[Janoz]

Was ik helemaal met latex aan het kutten om mijn hanepoten op papier netjes te krijgen, zie ik dat @bakkerjangert dat ook al gedaan had . Maar hier dan toch mijn O(1) oplossing:

spoiler:

(1) herschrijf het issue naar 2 lineaire vergelijkingen
(2) los de 2e formule op voor a
(3) vul in bij de eerste en los op voor b


Nu is het gewoon een kwestie van kijken of de oplossing van b uit (3) een geheel getal oplevert, en dan a bepalen door (2) in te vullen.

https://github.com/Janoz-...2024/day13/Day13.java#L49

Wel grappig trouwens dat de uiteindelijke oplossing voor b van mij en @bakkerjangert relatief verschillend zijn (in vorm, niet in uitkomst)

[ Voor 30% gewijzigd door Janoz op 13-12-2024 10:42 ]

[.oisyn]

Soultaker schreef op vrijdag 13 december 2024 @ 10:35:
Dit soort problemen komen wel vaker voor bij Advent of Code, dus wie zich wil voorbereiden kan zich alvast een beetje inlezen op Wikipedia: Diophantine equation en Bézout's identity.

Triviaal dus

[Hagdos]

spoiler:

Had vandaag direct door dat twee variabelen en twee vergelijkingen maar één oplossing kunnen geven, dus vrij snel wiskundig opgelost, en deel 1 af. Deel 2 zou dan simpel moeten zijn, maar ik kwam in de knoop door float/integer-problemen.

Iets te lang naar gestaard, toen bedacht dat ik vrij eenvoudig mijn formule kon omschrijven zodat er nog maar één deling in zit aan het eind, en die kun je dan makkelijk checken op modulo.

[.oisyn]

Ugh. Voor alle moeite die ze doen om te zeggen dat je misschien per ongeluk het antwoord van iemand ander's input hebt gegeven, mogen ze ook weleens een check inbouwen of je het antwoord van het voorbeeld geeft

[Friits]

Heeft er hier iemand veel ervaring van NumPy en meerdimensionale matrices in het bijzonder?

Ik heb nu een werkende oplossing die een 3-dimensionale matrix neemt van alle parameters van alle machines, en het hele stelsel van vergelijkingen in één keer oplost. Vermenigvuldig met de kosten-vector, en we zijn klaar.

Dit is natuurlijk best cool (al zeg ik het zelf), maar het zit me een beetje dwars dat ik alsnog twee berekeningen uitvoer: eentje voor de posities van deel 1, en eentje voor deel 2. De hele boel kan volgens mij ook in één keer als ik een extra dimensie toevoeg aan de positie-matrix. Zoiets:

Python:

P = np.stack([P, P+10**13])

Alleen heeft mijn hoofd een beetje moeite met 4-dimensionale data; normaal werk ik alleen maar met 1- en 2-dimensionale data voor wat statistiek, dus al deze algebra in hogere dimensies is best een uitdaging. Heeft iemand suggesties?

Mijn werkende 3-dimensionale implementatie staat hier.

[gedonie]

.oisyn schreef op vrijdag 13 december 2024 @ 12:13:
Ugh. Voor alle moeite die ze doen om te zeggen dat je misschien per ongeluk het antwoord van iemand ander's input hebt gegeven, mogen ze ook weleens een check inbouwen of je het antwoord van het voorbeeld geeft

Vond het ook al raar dat inderdaad bij deel 2 geen antwoord stond gegeven bij het voorbeeld. Dat betekend dat je inderdaad alleen kunt controleren of je wijzigingen kloppen door de echte input door te rekenen, en nog een keer en nog een keer en nog een keer .

[KabouterSuper]

Friits schreef op vrijdag 13 december 2024 @ 12:19:
Heeft er hier iemand veel ervaring van NumPy en meerdimensionale matrices in het bijzonder?

Ik heb nu een werkende oplossing die een 3-dimensionale matrix neemt van alle parameters van alle machines, en het hele stelsel van vergelijkingen in één keer oplost. Vermenigvuldig met de kosten-vector, en we zijn klaar.

Dit is natuurlijk best cool (al zeg ik het zelf), maar het zit me een beetje dwars dat ik alsnog twee berekeningen uitvoer: eentje voor de posities van deel 1, en eentje voor deel 2. De hele boel kan volgens mij ook in één keer als ik een extra dimensie toevoeg aan de positie-matrix. Zoiets:

Python:

P = np.stack([P, P+10**13])

Alleen heeft mijn hoofd een beetje moeite met 4-dimensionale data; normaal werk ik alleen maar met 1- en 2-dimensionale data voor wat statistiek, dus al deze algebra in hogere dimensies is best een uitdaging. Heeft iemand suggesties?

Mijn werkende 3-dimensionale implementatie staat hier.

Ik ga eens kijken. Het lijkt me ietswat overkill om een meer-dimensionale matrix te gebruiken. Als je een reguliere 2-dimensionale sparse matrix gebruikt, dan kom je er ook (maar minder cool).

Ik zou zelf gaan voor de volgende oplossing (waarbij jij je magie gebruikt om de distributiehal van de albert heijn in een schoenendoos kunt proppen):

spoiler:

De functie per setje van a,b,p (de data die jij in M gestopt hebt) die per setje het getal geeft is:
def linalgsolve(a,b,p):
det=a[0]*b[1]-a[1]*b[0]
return 3*(b[1]*p[0]-b[0]*p[1])//det+ (-a[1]*p[0]+a[0]*p[1])//det if (b[1]*p[0]-b[0]*p[1])%det==0 and (-a[1]*p[0]+a[0]*p[1])%det==0 else 0
Dan simpelweg de som nemen over alle setjes.
Met deze oplossing heb je geen numpy meer nodig en ook geen solver.

Update: met de functie kan je natuurlijk deel1 en deel2 tegelijkertijd teruggeven.

Update: zoiets misschien?? Het zou mooi zijn om numpy helemaal te vermijden

spoiler:

import numpy as np

M = np.fromregex(file, r'\d+', [('', int)]*6).view(int).reshape(-1,6)

def linalgsolve(a,b,p):
det=a[0]*b[1]-a[1]*b[0]
return 3*(b[1]*p[0]-b[0]*p[1])//det+ (-a[1]*p[0]+a[0]*p[1])//det if (b[1]*p[0]-b[0]*p[1])%det==0 and (-a[1]*p[0]+a[0]*p[1])%det==0 else 0

print([sum([linalgsolve(M[i][0:2],M[i][2:4],M[i][4:6]+1e13*p) for i in range(len(M))]) for p in [0,1]])

[ Voor 9% gewijzigd door KabouterSuper op 13-12-2024 13:33 ]

[Friits]

@KabouterSuper: Ja, maar die overkill is juist het punt. We doen dit omdat het kan, niet omdat het nodig is

Een "normale" oplossing heb ik al.

[.oisyn]

gedonie schreef op vrijdag 13 december 2024 @ 13:09:
[...]


Vond het ook al raar dat inderdaad bij deel 2 geen antwoord stond gegeven bij het voorbeeld.

Dat was idd ook waarom ik per ongeluk het verkeerde antwoord opgaf. En dat was bij dag 11 dus ook al, toen had ik exact hetzelfde probleem. Antwoord invullen voor deel 2, niet goed. Code goed nakijken, alles nalopen. Nee moet toch goed zijn. Op GoT vragen of zij misschien het antwoord voor het voorbeeld willen posten. Dan bedenken dat het misschien handig is als je je eigen antwoord er even bij zet. En dan ineens realizeren dat dat antwoord degene is die je had ingevuld. Had me een hoop tijd gespaard als ófwel het antwoord van het voorbeeld er al stond, ófwel ze hadden gezegd dat dat het antwoord van het voorbeeld was .

[Janoz]

gedonie schreef op vrijdag 13 december 2024 @ 13:09:
[...]


Vond het ook al raar dat inderdaad bij deel 2 geen antwoord stond gegeven bij het voorbeeld. Dat betekend dat je inderdaad alleen kunt controleren of je wijzigingen kloppen door de echte input door te rekenen, en nog een keer en nog een keer en nog een keer .

Maar misschien had 875318608908 ook wel een beetje veel weggegeven (als dat al niet gebeurt was doordat de waarde die er bij opgeteld moest worden niet in een int32 past).

[Soultaker]

.oisyn schreef op vrijdag 13 december 2024 @ 13:40:
Had me een hoop tijd gespaard als ófwel het antwoord van het voorbeeld er al stond, ófwel ze hadden gezegd dat dat het antwoord van het voorbeeld was .

Dat tweede is best een goed idee. Je zou 't naar Eric Wastl kunnen mailen, misschien implementeert 'ie het dan (waarschijnlijk niet dit jaar, maar misschien voor volgend jaar).

Voor deze dag specifiek vond ik het prima dat het voorbeeld niet verder uitgelegd werd voor deel 2, want als je deel 1 opgelost hebt, kun je makkelijk je eigen antwoorden checken. Gisteren (dag 12) was dat een heel stuk lastiger, en toen was het antwoord voor het voorbeeld voor deel 2 wel gegeven. Op dag 11 had je het voorbeeld weer niet nodig en was het antwoord ook niet gegeven. Dus al met al doet 'ie dat best goed vind ik.

Janoz schreef op vrijdag 13 december 2024 @ 15:17:
Maar misschien had 875318608908 ook wel een beetje veel weggegeven (als dat al niet gebeurt was doordat de waarde die er bij opgeteld moest worden niet in een int32 past).

Da's een van de redenen waarom ik bij mijn challenges meestal alleen de laatste paar cijfers van het antwoord weggeef

[Janoz]

Eigenlijk best leuk om te spelen met wat animaties. Hieronder mijn connectedSets algoritme van dag 12 waarbij ik de punten in willekeurige volgorde afhandel en in het midden begin (compleet onnodig, maar een leukere animatie dan de vorige)

[Satom]

Dag 12: deel 2 lang mee zitten prutsen. Kwam er lang niet uit totdat ik met wat pen, papier en Excel aan de slag ging.

spoiler:

Uiteindelijke oplossing was om de buren te markeren, door te kijken of je boven je geen buur had én zowel links of rechts wel en vervolgens linksboven en rechtsboven niet, dan kreeg de buur links en/of rechts een markering. Dit riedeltje herhalen voor alle richtingen, uiteindelijk deed ik 4 - markeringen - buren en dat gaf mij het gewenste resultaat

Dag 13: deel 1 was prima, maar ik voelde de bui al hangen toen ik zo goed als klaar was met deel 1. Met deel 2 heel lang zitten prutsen, heb nog gekeken of ik iets met log kon doen. Uiteindelijk, ergens tijdens de lunchpauze, kwam ik tot de volgende conclusie:

spoiler:

a*ax + b*bx = px is a*ay +b*by = py en alleen de 'a' en 'b' zijn onbekende waarden. Deze met 'simple elimination' weggewerkt. Nadat ik de controle op een heel getal na het delen had gefixt werkte het perfect! (het zijn immers hele knoppen waar je op drukt

[Soultaker]

Janoz schreef op vrijdag 13 december 2024 @ 16:38:
Eigenlijk best leuk om te spelen met wat animaties. Hieronder mijn connectedSets algoritme van dag 12 waarbij ik de punten in willekeurige volgorde afhandel en in het midden begin (compleet onnodig, maar een leukere animatie dan de vorige)

[Afbeelding]

Ik vind het heel mooie plaatjes maar ik snap geen bal van hoe je algoritme werkt. Kun je dat uitleggen?

Wat ik meestal doe is een floodfill per regio, maar jij lijkt een beetje alles tegelijk te doen en dan af en toe regio's te mergen (ik zie wat gebieden van kleur verschieten)?

[Janoz]

Soultaker schreef op vrijdag 13 december 2024 @ 17:09:
[...]

Ik vind het heel mooie plaatjes maar ik snap geen bal van hoe je algoritme werkt. Kun je dat uitleggen?

Wat ik meestal doe is een floodfill per regio, maar jij lijkt een beetje alles tegelijk te doen en dan af en toe regio's te mergen (ik zie wat gebieden van kleur verschieten)?

Het algoritme is relatief simpel.
Ik begin met een punt en ken daar een regio aan toe en druk deze in een stack.

Vervolgens herhaal ik totdat de stack leeg is:

- haal een punt van de stack en bekijk zijn buren:

- - als een buur dezelfde waarde heeft:
- - - heeft de buur nog geen regio dan krijgt het dezelfde regio ID en wordt ie op de stack gedrukt
- - - heeft de buur al een regio, dan worden de regio's samengevoegd
- - heeft de buur een andere waarde en nog geen regio dan krijgt het een nieuwe regio en wordt hij op de stack gepushed

Het samenvoegen lijkt duur, maar daarvoor hou ik gewoon een map bij.


De echte werking is goed te zien aan mijn eerder geplaatste animatie. Voor dit plaatje heb ik een priority queue gebruikt ipv een stack die vervolgens random sorteert om de animatie juist interessant te maken.

Hier staat de 'normale' code die gewoon linksboven begint:
https://github.com/Janoz-...noz/aoc/geo/Grid.java#L83

(frameConsumer zit er bij om de animaties te maken)

[Robbinb1993]

Janoz schreef op vrijdag 13 december 2024 @ 17:24:
[...]


Het algoritme is relatief simpel.
Ik begin met een punt en ken daar een regio aan toe en druk deze in een stack.

Vervolgens herhaal ik totdat de stack leeg is:

- haal een punt van de stack en bekijk zijn buren:

- - als een buur dezelfde waarde heeft:
- - - heeft de buur nog geen regio dan krijgt het dezelfde regio ID en wordt ie op de stack gedrukt
- - - heeft de buur al een regio, dan worden de regio's samengevoegd
- - heeft de buur een andere waarde en nog geen regio dan krijgt het een nieuwe regio en wordt hij op de stack gepushed

Het samenvoegen lijkt duur, maar daarvoor hou ik gewoon een map bij.


De echte werking is goed te zien aan mijn eerder geplaatste animatie. Voor dit plaatje heb ik een priority queue gebruikt ipv een stack die vervolgens random sorteert om de animatie juist interessant te maken.

Hier staat de 'normale' code die gewoon linksboven begint:
https://github.com/Janoz-...noz/aoc/geo/Grid.java#L83

(frameConsumer zit er bij om de animaties te maken)

Worden de regio's samengevoegd met een Union-Find datastructuur? Oftewel als je een buur tegenkomt die al tot een ander regio behoort maar dezelfde waarde heeft, dat je de twee regio's op die manier samenvoegt (union van de twee) en daardoor de kleur van het ene regio in de animatie ook gelijk wordt aan de kleur van het regio waarmee hij samengevoegd wordt?

[Janoz]

Robbinb1993 schreef op vrijdag 13 december 2024 @ 17:29:
[...]


Worden de regio's samengevoegd met een Union-Find algorithm? Oftewel als je een buur tegenkomt die al tot een ander regio behoort maar dezelfde waarde heeft, dat je de twee regio's op die manier samenvoegt (union van de twee) en daardoor de kleur van het ene regio in de animatie ook gelijk wordt aan de kleur van het regio waarmee hij samengevoegd wordt?

Nou, eigenlijk heb ik gewoon een map waarin ik opsla dat de twee regio Id's bij dezelfde regio horen. Dat is een O(1) operatie.

https://github.com/Janoz-...llections/MergingMap.java

[Robbinb1993]

Janoz schreef op vrijdag 13 december 2024 @ 17:35:
[...]


Nou, eigenlijk heb ik gewoon een map waarin ik opsla dat de twee regio Id's bij dezelfde regio horen. Dat is een O(1) operatie.

https://github.com/Janoz-...llections/MergingMap.java

Het heeft veel weg van UFDS (Union-Find Disjoint Set). Je kan nog path compression toepassen, oftewel als je in getActual een actuele set 'leader' ID opvraagt, ook gelijk op de weg terug in de function calls dit toe te kennen aan de backingMap voor de ID's op het pad. Dan heb je voor al die ID's de volgende keer een shortcut, waardoor de opvolgende calls sneller bij de leader ID zijn. Als je het nog sneller wil maken, kan je naar 'rank' kijken op de wiki van UFDS.

Het is inderdaad een unieke manier van floodfillen. Meestal wordt het regio voor regio gedaan door bij te houden of een cell al gezien is, en dan als het niet gezien is weer eerst die hele regio af te gaan en een nieuw ID toe te kennen.

[ Voor 14% gewijzigd door Robbinb1993 op 13-12-2024 18:02 ]

[Soultaker]

Janoz schreef op vrijdag 13 december 2024 @ 17:35:
Nou, eigenlijk heb ik gewoon een map waarin ik opsla dat de twee regio Id's bij dezelfde regio horen. Dat is een O(1) operatie.

https://github.com/Janoz-...llections/MergingMap.java

Aha, maar dit is in het algemeen niet correct. Als je y hernoemt naar z, moet je ook alle keys x die al gemapt zijn naar y updaten, anders heb je niet door dat x en z dezelfde groep zijn.

Een workaround is om getActual() het if-statement in een while-loop te veranderen, maar dan is je oplossing niet meer O(1).

Met een klein beetje moeite kun je van je MergingMap een echte disjoint set implementatie maken. Die heeft praktisch O(1) performance (in theorie iets met de inverse Ackermann functie, maar geen hond die het verschil merkt).

[KabouterSuper]

Friits schreef op vrijdag 13 december 2024 @ 13:38:
@KabouterSuper: Ja, maar die overkill is juist het punt. We doen dit omdat het kan, niet omdat het nodig is

Een "normale" oplossing heb ik al.

Mmm, het is een beetje gekunsteld, maar dit geeft volgens mij het goede antwoord. Ik herhaal S in de eerste dimensie en breid P op dezelfde manier uit. Het moet in de eerste dimensie, omdat de solver het anders niet slikt. Ik moest nog wel even expliciet naar np.int64 casten omdat ik anders een foutmelding kreeg.

spoiler:

S=np.zeros(shape=(2,4,2,2))
S[0,:,:,:]=M[..., :2]
S[1,:,:,:]=M[..., :2]
P=np.zeros(shape=(2,4,2,1))
P[0,:,:,:]=M[..., 2:]
P[1,:,:,:]=M[..., 2:]+1e13
R = np.linalg.solve(S, P).round().astype(np.int64)
print('f2',np.sum(np.dot(((S@R==P)*R).squeeze(),[3,1]),axis=1))

[ Voor 3% gewijzigd door KabouterSuper op 13-12-2024 18:05 ]

[.oisyn]

Soultaker schreef op vrijdag 13 december 2024 @ 17:53:
[...]

Aha, maar dit is in het algemeen niet correct. Als je y hernoemt naar z, moet je ook alle keys x die al gemapt zijn naar y updaten, anders heb je niet door dat x en z dezelfde groep zijn.

Dat hoeft helemaal niet als je in y opslaat dat hij hernoemd is naar z (kan ook zoiets zijn als een extra pointer indirectie), en dan kunnen oude cells gewoon naar y blijven wijzen.

In mijn geval (want Rust) is het een enum RegionRef { Value(Region), Ref(usize) }, waarbij de ref naar een andere index in de regions lijst wijst. De resolve naar de juiste offset is dan wel een loopje in mijn code, maar als je het goed doet zul je nooit een verwijzing tegenkomen wat zelf ook weer een verwijzing is. In C zou je het op kunnen lossen met een Region**.

Zie ook .oisyn in "Advent of Code 2024"

[ Voor 30% gewijzigd door .oisyn op 13-12-2024 19:22 ]

[FCA]

Vandaag heel lang lopen prutsen met de input parsen. Je kent het gezegde: je hebt een probleem, je ziet dat een Regex het kan oplossen, nu heb je 2 problemen .
Anyway, deel 1 uiteindelijk in de trein op weten te lossen (waarna ik daarna eerst een typefout op m'n telefoon maakte waardoor het antwoord niet werd goedgerekend, waarna ik nog 5 minuten zinloos heb zitten debuggen). Daarna deel 2 eerste op papier opgelost op het werk, met een hele extra behandeling voor het geval

spoiler:

de resulterende matrix determinant 0 zou hebben, wat dus uiteindelijk helemaal niet voor kwam

en daarna in de lunchpauze de oplossing heb kunnen insturen

spoiler:

met eerst een korte check voor de edge case, toen die niet voorkwam heb ik de implementatie daarvoor maar laten zitten

En wat zijn regexes onder Rust toch onhandig. Moet je nou een capture_iter, een find_iter, of gewoon een captures gebruiken? En dan een extract, waarom is dat nou weer nodig? En dan 1-based indexing voor de captures, wie heeft dat allemaal verzonnen....

Geef me gewoon een vector met de captures in 1 regel, of heb ik gewoon scheel lopen kijken.

[Robbinb1993]

.oisyn schreef op vrijdag 13 december 2024 @ 19:16:
[...]
maar als je het goed doet zul je nooit een verwijzing tegenkomen wat zelf ook weer een verwijzing is.

Dit lijkt zo, maar het pad in 'getActual' kan wel langer worden:

Stel je merged ID 12 met ID 5, dan heb je nu 12->5. Nu merge je 5 met 4. Dan is het 12->5->4. 4 merge je met 2. 12->5->4->2. In de worst case kan het pad O(N) worden op deze manier, alhoewel dat niet snel voor zal komen, en waarschijnlijk voor de gegeven invoer worden de paden ook niet al te lang. Als je de paden zo kort mogelijk wil houden in het algemeen kan je naar mijn C++ implementatie van DSU kijken:

https://github.com/Robbinb1993/AoC24/blob/main/dsa/dsu.h

[ Voor 13% gewijzigd door Robbinb1993 op 13-12-2024 20:45 ]

[Soultaker]

.oisyn schreef op vrijdag 13 december 2024 @ 19:16:
De resolve naar de juiste offset is dan wel een loopje in mijn code

En dat loopje is precies wat @Janoz nog niet heeft, en wat wel essentieel is voor correctheid.

maar als je het goed doet zul je nooit een verwijzing tegenkomen wat zelf ook weer een verwijzing is.

Dat is niet waar, zoals @Robbinb1993 ook uitlegde.

En hoewel ik geen fan ben van appeal to authority kun je op Wikipedia lezen dat de disjoint set al 50 jaar oud is, en dat er sindsdien nooit een strict O(1) oplossing gevonden is. Dat betekent niet dat er geen O(1) oplossing bestaat, maar je kunt wel aannemen dat het niet zo simpel is als 1 extra pointer indirection toevoegen, want dat hadden ze in 1964 ook wel kunnen verzinnen

[FCA]

Friits schreef op vrijdag 13 december 2024 @ 12:19:
Heeft er hier iemand veel ervaring van NumPy en meerdimensionale matrices in het bijzonder?

Ik heb nu een werkende oplossing die een 3-dimensionale matrix neemt van alle parameters van alle machines, en het hele stelsel van vergelijkingen in één keer oplost. Vermenigvuldig met de kosten-vector, en we zijn klaar.

Dit is natuurlijk best cool (al zeg ik het zelf), maar het zit me een beetje dwars dat ik alsnog twee berekeningen uitvoer: eentje voor de posities van deel 1, en eentje voor deel 2. De hele boel kan volgens mij ook in één keer als ik een extra dimensie toevoeg aan de positie-matrix. Zoiets:

Python:

P = np.stack([P, P+10**13])

Alleen heeft mijn hoofd een beetje moeite met 4-dimensionale data; normaal werk ik alleen maar met 1- en 2-dimensionale data voor wat statistiek, dus al deze algebra in hogere dimensies is best een uitdaging. Heeft iemand suggesties?

Mijn werkende 3-dimensionale implementatie staat hier.

spoiler:

[code=Python]
import numpy as np

M = np.fromregex('../input/2024/day13.txt', r'\d+', [('', int)]
*6).view(int).reshape(-1,3,2).swapaxes(1,2)

S = M[..., :2]
P = np.stack([M[..., 2:], M[..., 2:]+1e13])
R = np.linalg.solve(S, P).round().astype(int)
print(*np.einsum('ij,ijk->i',R.squeeze() @ [3,1], (S @ R == P).all(2)))
[/code]
doet wat je wilt. Je moet altijd goed naar de axes kijken (.shape is je vriend), n-d matrices kun je alleen vermenigvuldigen als de laatste axis van de eerste matrix overeenkomt met de eerste axis van de 2e matrix, en de np.einsum is een truc om alleen de diagonaal te berekenen (je krijgt namelijk anders een 2x2 matrix als output.

Ik werk trouwens regelmatig met 5+ dimensies voor mijn werk, en dan ben ik steeds chagrijnig dat named dimensions nog steeds geen echt goed werkende implementatie heeft. Je gaat op een gegeven moment met willekeurige groottes van elke dimensie strooien in je unit tests om te kijken of je echt wel de goede dingen met elkaar vermenigvuldigd.

[ Voor 8% gewijzigd door FCA op 13-12-2024 20:22 ]

[Robbinb1993]

[b]Soultaker schreef op vrijdag 13 december 2024 @ 20:07:En dat loopje is precies wat @Janoz nog niet heeft, en wat wel essentieel is voor correctheid.

Op dit moment vraagt Janoz het recursief op, dus het is wel correct. Alleen de paden kunnen lang worden na verloop van tijd.

[Soultaker]

Robbinb1993 schreef op vrijdag 13 december 2024 @ 21:04:
Op dit moment vraagt Janoz het recursief op, dus het is wel correct.

Ah ja, ik had de recursieve aanroep over het hoofd gezien. Dat is inderdaad correct, maar dan is het dus niet O(1). Wel goed genoeg voor AoC waarschijnlijk.

[.oisyn]

Ah ja jullie hebben idd gelijk, het komt in de praktijk niet veel voor maar je kunt wel een worst case situatie verzinnen ja.

[Janoz]

Soultaker schreef op vrijdag 13 december 2024 @ 20:07:
[...]

En dat loopje is precies wat @Janoz nog niet heeft, en wat wel essentieel is voor correctheid.

wel hoor

https://github.com/Janoz-...tions/MergingMap.java#L19

Maar door telkens het minimum terug te geven is de diepte minimaal en daarom zo goed als O(1)

[Soultaker]

Fuuuuuu....! Ik had vandaag veel sneller kunnen zijn, ware het niet dat ik voor deel 2

spoiler:

slechts een van de twee constanten 100 uit deel 1 door een parameter t vervangen had, waardoor de y-coordinaten doodleuk altijd voor frame 100 berekend werden

Daarna ging het redelijk rap. Oplossing:

spoiler:

Zoek naar de frame waar de robots zo min mogelijk overlap hebben.

Dit had ik als eerste geprobeerd, maar toen dat niets op leverde vanwege bovengenoemde bug, had ik ook allerlei andere dingen geprobeerd, zoals meten hoeveel robots er dicht bij elkaar in de buurt staan enzo.

Python code

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

[mbe81]

Soultaker schreef op zaterdag 14 december 2024 @ 06:29:
Daarna ging het redelijk rap. Oplossing:

spoiler:

Zoek naar de frame waar de robots zo min mogelijk overlap hebben.

Dit is toch geen enkele garantie voor een kerstboom-vorm? Een beetje wazige opgave wat mij betreft.

[Soultaker]

mbe81 schreef op zaterdag 14 december 2024 @ 06:36:
Dit is toch geen enkele garantie voor een kerstboom-vorm? Een beetje wazige opgave wat mij betreft.

Het is het soort opgave dat wel vaker bij Advent of Code zit; meer een puzzel dan een programmeer-uitdaging.

spoiler: dag 14 deel 2

Je kunt beredeneren dat er 10403 verschillende plaatjes mogelijk zijn. De meeste daarvan zien er vrij random uit, maar een daarvan is blijkbaar bijzonder. Het zijn teveel frames om ze allemaal handmatig te bekijken, dus moet je wat code schrijven om een uitzonderlijke situatie te herkennen.

En ja, dan moet je een beetje creatief nadenken over welke criteria je redelijkerwijs zou kunnen gebruiken. Er waren ook andere opties, bijvoorbeeld:

spoiler:

een frame waarin 10 robots in een rechte lijn staan, of waarin een 3x3 vlak gevuld is met 9 robots, maar dat is met hindsight. Je weet natuurlijk van te voren niet precies hoe de kerstboom eruit ziet, dus dan moet je een beetje experimenteren met de data die je krijgt.

[Soultaker]

Janoz schreef op vrijdag 13 december 2024 @ 22:26:
[...]

wel hoor

https://github.com/Janoz-...tions/MergingMap.java#L19

Maar door telkens het minimum terug te geven is de diepte minimaal en daarom zo goed als O(1)

Mijn excuses, dat had ik gemist. Dan is het inderdaad correct, wat het allerbelangrijkste is, en zoals je zegt is het in de praktijk vast ook best snel, hoewel ik in de verleiding kom om specifiek een testcase te maken om je performance om zeep te helpen.

[mbe81]

Dankjewel dan maar; het werkt blijkbaar wel... Zou iedereen vandaag dan dezelfde input gehad hebben?

[Soultaker]

mbe81 schreef op zaterdag 14 december 2024 @ 07:08:
Dankjewel dan maar; het werkt blijkbaar wel... Zou iedereen vandaag dan dezelfde input gehad hebben?

Ik denk het niet. Wat ik denk is dat

spoiler:

iedereen hetzelfde plaatje van de kerstboom heeft, maar dat details variëren: de random pixels eromheen, de snelheden van de robots, en het frame-nummer (het antwoord bij deel 2).

Hier is mijn resultaat als je wil vergelijken.

[Quadro!]

Soultaker schreef op zaterdag 14 december 2024 @ 06:48:
[...]

spoiler: dag 14 deel 2

Het zijn teveel frames om ze allemaal handmatig te bekijken

Haha, nee hoor, dat is exact wat ik gedaan heb.

spoiler:

Gewoon ieder frame naar de terminal barfen en terug scrollen Nu even kijken of we een mooie algoritmische oplossing kunnen bedenken...

[Janoz]

Ik heb gewoon weer mijn veel besproken connected sets algoritme gebruikt om te zien of ik ergens een set tegen kwam die boven een bepaalde treshold kwam. png-tje gemaakt voor controle.

Alleen veel te lang bezig geweest omdat ik 1 klein bugje had gemaakt waardoor ik veel te veel moves per stap deed (een i ipv een 1 )

[mbe81]

Soultaker schreef op zaterdag 14 december 2024 @ 07:21:
[...]

Ik denk het niet. Wat ik denk is dat

spoiler:

iedereen hetzelfde plaatje van de kerstboom heeft, maar dat details variëren: de random pixels eromheen, de snelheden van de robots, en het frame-nummer (het antwoord bij deel 2).

Hier is mijn resultaat als je wil vergelijken.

Ze zijn inderdaad anders. Je kan inderdaad natuurlijk makkelijk van de eindsituatie (= de kerstboom) terugrekenen naar een beginsituatie met een aantal random inputs.

[FCA]

Deel 2 was een goede headscratcher inderdaad

spoiler:

ik had gelukkig een visualisatie voor deel 1 gebouwd om te debuggen (stomme of-by-one fout, ik deed 101 stappen i.p.v. 100 ). Visualisatie naar een file pipen, Ctrl-F op een voldoende lange reeks robots. Obvious zodra je het ziet, maar vantevoren geen idee waar ik precies naar moest zoeken.

Duurde ook nog erg lang met m'n suffe hoofd om te realiseren dat met een gridgrootte van 101x103 de periode natuurlijk precies 10403 moest zijn (ze zijn beide priem)

[ Voor 19% gewijzigd door FCA op 14-12-2024 09:08 ]

[Quadro!]

Mijn oplossing voor dag 14 deel 2:

spoiler:

Neem de eerste state waarbij er tenminste x aantal posities zijn waarbij op iedere adjacent positie ook een robot vliegt. x is in dit geval 50. Een beetje arbitrair, maar het lijkt in de praktijk vrij robuust.

Code

[Janoz]

Soultaker schreef op vrijdag 13 december 2024 @ 17:09:
Ik vind het heel mooie plaatjes maar ik snap geen bal van hoe je algoritme werkt. Kun je dat uitleggen?

Nog even hierop terugkomend, ik had het algoritme niet helemaal goed geimplementeerd. Mijn eerdere implementatie had niet echt voordelen boven een standaard floodfill. Echter door de manier van matchen hoef je een punt nooit vaker dan 1x te bezoeken. Eigenlijk is het een lineair algoritme waarbij je gewoon alle punten in volgorde af kunt lopen en alleen naar het punt rechts en het punt onder hoeft te kijken.

Ik heb hem nu wel goed geimplementeerd:
https://github.com/Janoz-...oz/aoc/geo/Grid.java#L106

[Marcj]

Leuke puzzel vandaag! Voor deel 2 ging ik toch iets anders doen dan een aantal hier.

spoiler:

Ik ging het aantal punten tellen dat direct tegen elkaar aan zat. Bij de random blokken is dat aantal vrij laag. Er is maar eentje waarbij deze het hoogst is.

[ Voor 4% gewijzigd door Marcj op 14-12-2024 10:41 ]

[Soultaker]

Janoz schreef op zaterdag 14 december 2024 @ 09:45:
Eigenlijk is het een lineair algoritme waarbij je gewoon alle punten in volgorde af kunt lopen en alleen naar het punt rechts en het punt onder hoeft te kijken.

Dat is inderdaad logischer als je voor de aanpak kiest met de MergingMap. Als je het als graafalgoritme ziet zijn het niet zozeer de punten die je afloopt, maar de lijnstukken, en als twee punten verbonden zijn dan merge je de sets waartoe ze behoren.

Neemt niet weg dat de worst case nog steeds slechter is dan O(n) voor dag 12. Probeer deze invoer maar eens: aoc-2024-day-12-quadratic-cases.zip

Mijn Python code doet daar krap 6 seconde over (wat nog traag is vergeleken met native oplossingen die wel in O(n) draaien), terwijl jouw Java oplossing na 6 12 minuten nog niet klaar was. edit: na 12 minuten krijg ik een OutOfMemoryError.

Ongerelateerd: ik moest een beetje gniffelen bij het zien van deze code:

Java:

Iterator<Integer> nextRegionSupplier = IntStream.iterate(1, l->l+1).iterator();
...
nextRegionSupplier.next()

Laat me raden, jij verdient je geld met Enterprise Java code? Wat is er mis met:

Java:

int nextRegion = 1;
...
nextRegion++;

(Overigens heeft Java ook een dedicated IntSupplier class.)

[Janoz]

Soultaker schreef op zaterdag 14 december 2024 @ 11:18:
[...]

Dat is inderdaad logischer als je voor de aanpak kiest met de MergingMap. Als je het als graafalgoritme ziet zijn het niet zozeer de punten die je afloopt, maar de lijnstukken, en als twee punten verbonden zijn dan merge je de sets waartoe ze behoren.

Neemt niet weg dat de worst case nog steeds slechter is dan O(n) voor dag 12. Probeer deze invoer maar eens: aoc-2024-day-12-quadratic-cases.zip

Mijn Python code doet daar krap 6 seconde over (wat nog traag is vergeleken met native oplossingen die wel in O(n) draaien), terwijl jouw Java oplossing na 6 12 minuten nog niet klaar was.

Ongerelateerd: ik moest een beetje gniffelen bij het zien van deze code:

Java:

Iterator<Integer> nextRegionSupplier = IntStream.iterate(1, l->l+1).iterator();
...
nextRegionSupplier.next()

Laat me raden, jij verdient je geld met Enterprise Java code? Wat is er mis met:

Java:

int nextRegion = 1;
...
nextRegion++;

(Overigens heeft Java ook een dedicated IntSupplier class.)

Code wordt in een lambda uitgevoerd en dan moet alles wat daarbinnen gebruikt wordt impliciet final zijn. De iterator is dat wel, maar een int niet.

En de IntSupplier is enkel een functionele interface, die zou ik dan nog moeten implementeren, maar die implementatie is mogelijk langer dan de IntStream. De IntStream interface is voornamelijk om van een Stream via .mapToInt naar een IntStream te gaan. Het is nogal een lelijke pukkel omdat de stream api in java ook voor enkele primitieve types geimplementeerd is.

[ Voor 11% gewijzigd door Janoz op 14-12-2024 11:28 ]

[Robbinb1993]

Soultaker schreef op zaterdag 14 december 2024 @ 11:18:
Neemt niet weg dat de worst case nog steeds slechter is dan O(n) voor dag 12. Probeer deze invoer maar eens: aoc-2024-day-12-quadratic-cases.zip

Ik denk dat zoiets al veel zou schelen:

Java:

public int getActual(int i) {
    if (backingMap.containsKey(i)) {
        // Recursively find the leader
        int leader = getActual(backingMap.get(i));
        
        // Path compression: Update the current element to point directly to the leader
        backingMap.put(i, leader);
        
        return leader;
    }
    return i;
}

want hiermee compress je de paden elke keer als de leader ID opgevraagd wordt. Ben wel benieuwd hoe snel de case dan runt?

[ Voor 3% gewijzigd door Robbinb1993 op 14-12-2024 11:27 ]

[Janoz]

Robbinb1993 schreef op zaterdag 14 december 2024 @ 11:25:
[...]


Ik denk dat zoiets al veel zou schelen:

Java:

public int getActual(int i) {
    if (backingMap.containsKey(i)) {
        // Recursively find the leader
        int leader = getActual(backingMap.get(i));
        
        // Path compression: Update the current element to point directly to the leader
        backingMap.put(i, leader);
        
        return leader;
    }
    return i;
}

want hiermee compress je de paden elke keer als de leader ID opgevraagd wordt. Ben wel benieuwd hoe snel de case dan runt?

Wel een leuke exercitie om dat eens toe te voegen

---

Ik denk dat het makkelijker is om de compressie te doen bij het toevoegen. Dan krijg je denk ik iets als (ongetest)

Java:

    public int addMapping(final int i1, final int i2) {
        int ai1 = getActual(i1);
        int ai2 = getActual(i2);
        if (ai1 == ai2) return ai1;
        int result = Math.min(ai1, ai2);
        backingMap.put(Math.max(ai1,ai2), result);
        if (result != i1) backingMap.put(i1, result);
        if (result != i2) backingMap.put(i2, result);
        return result;
    }

Laat maar, bovenstaande levert erg weinig op.

[ Voor 28% gewijzigd door Janoz op 14-12-2024 12:11 ]

[Soultaker]

Janoz schreef op zaterdag 14 december 2024 @ 11:23:
Code wordt in een lambda uitgevoerd en dan moet alles wat daarbinnen gebruikt wordt impliciet final zijn. De iterator is dat wel, maar een int niet.

Oh ja, dat was inderdaad een gebrek van Java. Workaround:

Java:

int[] i = {1};

i[0]++;

Maar ik geef toe dat het minder elegant is.

En de IntSupplier is enkel een functionele interface, die zou ik dan nog moeten implementeren, maar die implementatie is mogelijk langer dan de IntStream.

Dat valt ook wel mee:

Java:

var nextRegion = new IntSupplier() {
    int i = 1;
    public int getAsInt() {
        return i++;
    }
};

Maar ik ben het met je eens dat dat net zo goed verbose is dus zeker geen significante verbetering.

Robbinb1993 schreef op zaterdag 14 december 2024 @ 11:25:
Ik denk dat zoiets al veel zou schelen: [..]

Dat denk ik ook; dat het nuttig is om dat te doen is precies waarvan ik Janoz probeerde te overtuigen.

Maar zelfs met die wijziging is het nog heel traag... misschien zit er nog ergens anders een bottleneck.

Overigens zou ik de volgende code voorstellen:

Java:

    public int getActual(int i) {
        Integer value = backingMap.get(i);
        if (value == null) {
            return i;
        }
        int parent = value;
        int root = getActual(parent);
        if (root != parent) {
            backingMap.put(i, root);
        }
        return root;
    }

Hiermee doe je niet meer map-operaties dan strict noodzakelijk (1 get en maximaal 1 put, maar meestal minder).

[Janoz]

Medium:
....1996
....512
In 654ms

Large duurt een stuk langer inderdaad, heb ik nog geen antwoord op


----
Was ie al:
....19996
....5012
In 486.065ms

Iets meer dan 8 minuten

[ Voor 27% gewijzigd door Janoz op 14-12-2024 12:01 ]

[Soultaker]

Janoz schreef op zaterdag 14 december 2024 @ 11:50:
Large duurt een stuk langer inderdaad, heb ik nog geen antwoord op

Ik merk dat je programma al m'n CPU cores probeert te gebruiken, wat bijzonder is, want je algoritme lijkt me single-threaded? Mogelijk is er veel GC overhead? (Misschien vanwege die lambdas?)

[Robbinb1993]

[b]Soultaker schreef op zaterdag 14 december 2024 @ 11:46:
Maar zelfs met die wijziging is het nog heel traag... misschien zit er nog ergens anders een bottleneck.

Misschien nog 'union by size' toepassen? Dus de kleinste set in de grootste set (de leader) mergen, waardoor we het aantal nodes in diepere lagen van de boom zo laag mogelijk houden. Dan is het volgensmij een optimale UFDS implementatie. Ik weet niet of Map zelf nog wat overhead geeft tenopzichte van een array, aangezien het een hash map is. Dus daarvoor zou indexing ook ongeveer O(1) moeten zijn, alhoewel het niet gegarandeerd is.

[ Voor 19% gewijzigd door Robbinb1993 op 14-12-2024 13:05 ]

[Satom]

Quadro! schreef op zaterdag 14 december 2024 @ 09:39:
Mijn oplossing voor dag 14 deel 2:

spoiler:

Neem de eerste state waarbij er tenminste x aantal posities zijn waarbij op iedere adjacent positie ook een robot vliegt. x is in dit geval 50. Een beetje arbitrair, maar het lijkt in de praktijk vrij robuust.

Code

Goed om, stiekem, te lezen! Dit was ook mijn idee! Vanmiddag eens toepassen, alternatief was alle grids naar de debug log te gooien (aangezien ik voor deel 1 ook een simpele “Draw” heb geschreven)

[Janoz]

Soultaker schreef op zaterdag 14 december 2024 @ 11:46:

Overigens zou ik de volgende code voorstellen:

Java:

    public int getActual(int i) {
        Integer value = backingMap.get(i);
        if (value == null) {
            return i;
        }
        int parent = value;
        int root = getActual(parent);
        if (root != parent) {
            backingMap.put(i, root);
        }
        return root;
    }

Hiermee doe je niet meer map-operaties dan strict noodzakelijk (1 get en maximaal 1 put, maar meestal minder).

Met deze code ging ik van een maximale diepte van 249 naar 2 voor medium.txt. Tijd ging van 600ms naar 500ms oid..

Large gaat naar In 301444ms

Java:

    private int getActual(int i, int depth) {
        if (backingMap.containsKey(i)) {
            return getActual(backingMap.get(i), depth + 1);
        }
        maxDepth = Math.max(maxDepth, depth);
        return i;
    }

    public int getActual(int i) {
        int result = getActual(i,0);
        if (i!=result) {
            backingMap.put(i,result);
        }
        return result;
    }

[KabouterSuper]

Quadro! schreef op zaterdag 14 december 2024 @ 09:39:
Mijn oplossing voor dag 14 deel 2:

spoiler:

Neem de eerste state waarbij er tenminste x aantal posities zijn waarbij op iedere adjacent positie ook een robot vliegt. x is in dit geval 50. Een beetje arbitrair, maar het lijkt in de praktijk vrij robuust.

Code

spoiler:

Heb ik ook gedaan met 500 buren en de eerste 300 robots. buren worden overigens wel dubbel geteld.

Bij mijn eerste poging probeerde ik om te zoeken naar symmetrie, dus meer dan 20% heeft een robot die ook voorkomt op positie (y,xsize-x-1). Helaas zat de kerstboom niet in het midden.

Draaitijd van deel 2 in pypy was 20 seconden (maar dat is zonder de tijd om de 5 1/4 diskette in de b-drive te doen).

[ Voor 6% gewijzigd door KabouterSuper op 14-12-2024 12:18 ]

[Soultaker]

@Janoz : bij mij helpt het enorm als ik de Point.hashCode() implementatie verander van Objects.hash(x, y) naar x + 31337*y.

Het probleem met de default-implementatie is dat 'ie effectief 31 * x + y doet, maar dan heb je een heleboel hash collisions en zijn HashSets en HashMaps enzo dus relatief traag.

edit:
En met deze meer “klassieke” implementatie van connectedSets() kan ik de large set oplossen binnen 50 seconden:

Java:

default Map<Integer, Set<Point>> connectedSets() {
    var regionsById = new HashMap<Integer, Set<Point>>();
    var todo = new ArrayList<Point>();
    var seen = new HashSet<Point>();
    for (int y = 0; y < getHeight(); ++y) {
        for (int x = 0; x < getWidth(); ++x) {
            Point p = new Point(x, y);
            if (seen.add(p)) {
                todo.add(p);
                T currentValue = get(p);
                for (int i = 0; i < todo.size(); ++i) {
                    for (Point n : todo.get(i).neighbours()) {
                        if (inGrid(n) && get(n).equals(currentValue) && seen.add(n)) {
                            todo.add(n);
                        }
                    }
                }
                regionsById.put(regionsById.size() + 1, new HashSet<Point>(todo));
                todo.clear();
            }
        }
    }
    return regionsById;
}

(Het kan nog 50% sneller door de seen HashMap te vervangen door een 2D boolean array.)

[ Voor 64% gewijzigd door Soultaker op 14-12-2024 13:08 ]

[torx]

Pfff ik had mijn antwoord voor deel 2 al eerder dan ik dacht...

spoiler:

Ik zag op een gegeven moment de bovenkant van de kerstboom onderin mijn visualisatie (console), met daarboven willekeurige robots. Ik dacht dus dat ik nog meer stappen moest zetten totdat de kerstboom bovenint zat en de willekeurige punten de rest van de boom vormden. Maar blijkbaar moest ik scrollen om de rest te zien

En het resultaat:

spoiler:

[.oisyn]

Deel 2 vond ik stom en heb ik niet opgelost in code.

spoiler:

had een uitdraai gemaakt van de eerste 100 stappen en het viel me op dat op stap 38 heel veel robots een gelijke x- coördinaat hadden, en op stap 88 een gelijke y-coördinaat. Die herhalen zich natuurlijk resp. 101 en 103 stappen, dus gewoon even opgelost voor:

s = 38 (mod 101)
s = 88 (mod 103)

(Chinese reststelling)

Nog even het plaatje gegenereerd voor stap s en dat was het goede antwoord.

Misschien dat ik dit nog eens in code zal gieten, maar nu geen zin in.

[Friits]

@KabouterSuper en @FCA: bedankt voor jullie implementaties! Ik zie dat ik al een heel eind in de buurt zat; bedankt voor jullie ideeën over die vierde dimensie. Leerzaam, en indrukwekkend

Vandaag heb ik ook weer iets in elkaar ge-NumPy'd; en ook dit keer zie ik weer vier dimensies:

1. robot (0 ... 500)
2. tijd (t = 0 ...)
3. positie of versnelling
4. as (x of y)

Dimensies 1 t/m 3 gebruik ik nu om in één stap de juiste x of y te vinden, en daarmee reken ik dan de juiste t uit. Vanavond nog maar even puzzelen om alles in een vier-dimensionale matrix te vouwen

---

Voor iedereen die just graag simpele code ziet, heb ik hier mijn gewone oplossing in Python. Met 15 regels is het met stip mijn langste implementatie van dit jaar, maar het is wel zeer leesbaar geworden

[ Voor 18% gewijzigd door Friits op 14-12-2024 15:57 ]

[Quadro!]

KabouterSuper schreef op zaterdag 14 december 2024 @ 12:16:
[...]

spoiler:

Heb ik ook gedaan met 500 buren en de eerste 300 robots. buren worden overigens wel dubbel geteld.

Bij mijn eerste poging probeerde ik om te zoeken naar symmetrie, dus meer dan 20% heeft een robot die ook voorkomt op positie (y,xsize-x-1). Helaas zat de kerstboom niet in het midden.

Draaitijd van deel 2 in pypy was 20 seconden (maar dat is zonder de tijd om de 5 1/4 diskette in de b-drive te doen).

Diskette? B-drive? Speciale challenge dit jaar om AoC op ancient hardware te doen?

[Camulos]

Ik vond dit een leuke puzzel!! vooral deel 2

spoiler:

Wat een zoektocht:

• Eerst 500 console outputs te hebben gekeken
• Daarna denkende aan deel 1, dat je symetrische quadranten zou moeten hebben, maar na 20K iteraties alleen maar rubbish in de output
• Daarna zoals velen hier toch maar eens gechecked of er iets geclusterd is, arbitrair threshold op 25 gezet met precies 1 uitkomst
• Ben blij dat ik niet dit op de console heb zitten bekijken

[MatHack]

Ik vond deel 2 van vandaag ook maar stom. Uiteindelijk aan de hand van de spoilers (iedereen wordt vandaag hartelijk bedankt!) hier maar de volgende oplossing gebouwd:

spoiler: dag 14, deel 2

Tel per seconde het aantal robots die meer dan 1 buur hebben. Als dat meer dan 20% van het totaal aantal robots is (> 100 dus), dan zal het wel de seconde met het plaatje zijn. En dan het plaatje voor de zekerheid nog even naar de console geprint.

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

[Ghehe]

spoiler:

Heb voor deel 2 van dag 14 mijn recursieve crawler van dag 12 gebruikt om de grootte van een region te bepalen. Hier gebruikt om grote aaneengesloten clusters te ontdekken. Kwam uiteindelijk toch een kerstboom uitrollen toen ik van 1000 stapjes naar 10000 ging

[Janoz]

Zou het kunnen dat deel 2 zo gemaakt is juist om ervoor te zorgen dat AI oplossingen er moeite mee hebben?

[Friits]

Had gekund, maar nee.

Overigens vind ik het grappig dat mensen zo verdeeld zijn over de puzzel: de een vindt het het een rare ondergespecificeerde opgave, de ander ziet het juist een echte puzzel (i.p.v. een programmeeropdrachtje). Ik vond 'm in ieder geval erg leuk, en het is interessant om te zien met wat voor een creatieve oplossingen mensen komen.

spoiler:

Iemand postte op Reddit dat 'ie voor iedere tijdstap de posities opslaat als .png-bestand. Het plaatje waar de kerstboom in zit heeft het minste "ruis", is dus het beste te comprimeren, en levert dus het kleinste bestand op!

Anderen zochten naar het tijdstip dat iedere robot een unieke positie inneemt, zochten naar de grootste componenten in de graaf, deden een simpele string search op '*******', of berekenden de uitkomst m.b.v. de Chinese reststelling. Zelf had ik een zinnetje uit deel 1 opgevat als hint, dus ik heb gezocht naar het tijdstip met de minimale "safety factor".

Licht off-topic, maar omdat we hier toch allemaal puzzelliefhebbers met een bètaknobbel zijn: de AIVD kerstpuzzel staat weer online! Voor wie denkt dat dat te moeilijk is: er is ook een junior-versie en een aantal opgaven daarvan zijn echt goed te doen. Voor opgave 8 mag je je eigen (vereenvoudigde) Enigma-machine implementeren!

[ Voor 9% gewijzigd door Friits op 14-12-2024 21:21 ]

[Soultaker]

Dag 15: Ik hou van Sokoban

M'n code is wel een ontzettend rommeltje geworden. Moet ik nog even opruimen.

Friits schreef op zaterdag 14 december 2024 @ 21:12:
Overigens vind ik het grappig dat mensen zo verdeeld zijn over de puzzel: de een vindt het het een rare ondergespecificeerde opgave, de ander ziet het juist een echte puzzel (i.p.v. een programmeeropdrachtje).

Het hangt denk ik vooral van je verwachtingen af. Ik ben ook meer fan van de klassieke programmeeropgaven, waarbij de bedoeling duidelijk is, en vorige jaren heb ik me ook wel zitten ergeren aan opgave zoals die van gisteren (of andere opgaven waarbij je de invoer in detail moet analyseren, omdat er allemaal constraints op zitten die niet in de probleemstelling staan).

Het is irritant als je je 15 minuten lang op het probleem hebt zitten blindstaren, of een veel te ingewikkelde oplossing hebt geïmplementeerd, en dat dan blijkt dat het allemaal heel anders had gemoeten of dat het veel simpeler had gekund, als je had “valsgespeeld” door dubieuze aannamen te doen.

Maar als je je realiseert dat Advent of Code nu eenmaal zo werkt, dan leg je je erbij neer, en dan is het dus de sport om zo snel mogelijk het antwoord te vinden, waarbij je gebruik maakt van alle tools die je ter beschikking hebt. Niet alleen programmeren dus, maar ook de invoer analyseren of visualiseren.

[Soultaker]

Code voor dag 15 wat opgeschoond, voor wie het interesseert: 15.py

Overigens grappig om te zien bij dit soort opgaven die wat lastiger zijn, dat de tijden op het Tweakers leaderboard nog steeds vrij dicht bij elkaar liggen: 42:15, 42:40 (!!), 49:00, 01:03:21, 01:05:31.

[bakkerjangert]

Op zich wel een leuk puzzeltje, die ik volledig in numpy heb gesimuleerd. Voor deel 2 dacht ik wel even 'whattt?'. Die code is dan ook een beetje een rommeltje, maar werkt wel.

[MatHack]

Hehe, net als @Soultaker was het eerste waar ik ook aan dacht Sokoban.

Ik was blij met mijn vrij elegante oplossing voor deel 1, maar bij deel 2 werd het toch een beetje een zooitje. Uiteindelijk toch nog redelijk elegant/netjes opgelost.

spoiler: dag 15, deel 2

Uiteindelijk maar een queue geïntroduceerd voor de dozen die dozen kunnen verschuiven, want je kunt natuurlijk hebben dat de ene hoek wel iets raakt en de andere hoek niet tot complete driehoeken van dozen die je aan het schuiven bent. En dan kom je ergens ver in een hoek van die driehoek een muur tegen...

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

[ Voor 5% gewijzigd door MatHack op 15-12-2024 08:48 ]

[KabouterSuper]

Friits schreef op zaterdag 14 december 2024 @ 15:53:
@KabouterSuper en @FCA: bedankt voor jullie implementaties! Ik zie dat ik al een heel eind in de buurt zat; bedankt voor jullie ideeën over die vierde dimensie. Leerzaam, en indrukwekkend

Vandaag heb ik ook weer iets in elkaar ge-NumPy'd; en ook dit keer zie ik weer vier dimensies:

1. robot (0 ... 500)
2. tijd (t = 0 ...)
3. positie of versnelling
4. as (x of y)

Dimensies 1 t/m 3 gebruik ik nu om in één stap de juiste x of y te vinden, en daarmee reken ik dan de juiste t uit. Vanavond nog maar even puzzelen om alles in een vier-dimensionale matrix te vouwen

---

Voor iedereen die just graag simpele code ziet, heb ik hier mijn gewone oplossing in Python. Met 15 regels is het met stip mijn langste implementatie van dit jaar, maar het is wel zeer leesbaar geworden

Thanks. Je gewone oplossing is inderdaad goed leesbaar. Het is niet nodig, maar je zou iets soortgelijks als

code:

def danger(t):
    s=[0,0,0,0]
    for x, y, dx, dy in bots:
        x,y = ((x + dx * t) % w) - w//2,((y + dy * t) % h)-h//2
        s=list(map(operator.add, s,[x>0 and y>0, x<0 and y>0, x<0 and y<0, x>0 and y<0]))

kunnen overwegen om van de a tm d af te komen (gewoon omdat het kan).

Je bent trouwens één van de weinige mensen die doorzag dat deel 1 een hint was voor deel 2, namelijk dat je de doelfunctie uit deel 1 kon gebruiken om in deel 2 over te minimaliseren. Ik zag het ook pas nadat ik jouw oplossing zag.

[Friits]

Vandaag was weer leuk, vooral deel 2. Ik heb het in zo'n 20 regels weten te passen, hopelijk zonder al te veel leesbaarheid in te leveren.

[ Voor 60% gewijzigd door Friits op 15-12-2024 15:55 ]

[Janoz]

Verslapen, dus laat begonnen. Uiteindelijk vond ik deel 2 makkelijker dan ik eerst had verwacht. Zal mogelijk best efficienter kunnen, maar 10ms per deel vind ik snel zat.

https://github.com/Janoz-...oc/y2024/day15/Day15.java

[Soultaker]

Mijn visualisatie van Dag 15

Werkt zelfs voor de grote invoerdata (en zou het juiste antwoord moeten geven!)

[FCA]

Deel 2 vond ik wel pittig, heb misschien niet helemaal de makkelijkste aanpak gekozen, maar inmiddels wel weten uit te breiden naar een implementatie die voor willekeurige vormen van boxen zou moeten werken.

Ik vond bij deel 2 de uitleg van de GPS score berekening niet heel erg duidelijk, ik had eerst letterlijk genomen wat er stond, maar dat geeft niet het goede antwoord. Na checken van de visualisaties gewoon de GPS uit deel 1 voor de linkerdelen gepakt, en dat was dan wel correct
Ik las als edge iedere edge, maar het ging dus alleen om de boven en de linker edge.

spoiler:

Oplossing
Voor deel 1 koos ik een aanpak die helaas niet werkte voor deel 2: ik probeer de doos die aan de robot grenst te "verplaatsen" naar het einde van de rij dozen, en kijk dan of dat kan. Werkt best efficient.

Voor deel 2 ben ik voor elke verplaatsingspoging de dozen die allemaal gepushed worden in een blob te vormen, en dan te kijken of ik de blob kan verplaatsen. Ik had in eerste instantie linker en rechter delen van dozen apart genomen, en dan allebei te updaten en te checken. Het werkte, maar er waren een hoop bugs om te fixen omdat de linker en rechter boxes niet altijd in sync bleven (meestal door typefoutjes/copy paste foutjes).

De versie voor algemene box-shapes werkt veergelijkbaar als deze, maar houd ook nog een id bij per doos, en een extra map van id naar box coordinaten. Als de blob wordt bewogen, worden dus 1 alle locaties bijgewerkt met de goede id, en tegelijkertijd alle id's met de juiste coordinaten. Wel wat boekhoudwerk, maar draait in minder dan 2ms, dus tevreden weer

[FCA]

Voor dag 14 heb ik trouwen eens een nieuwe implementatie, met een redelijk generieke check:

spoiler:

Gebaseerd op het minimaliseren van de entropy. Ik splits het plaatje op een platte vector, met 6 pixels per entry, en dan tel ik per bit er bij op 1 als er een robot op die plek zit (dus 2^2 als er een robot op plek 3 zit van de 6 pixels, etc.).

Daarna bereken ik de Shannon entropy van de resulterende vector.
Het kerstboomplaatje is behoorlijk regulier, dus lage entropy.

Tot nu toe mijn langzaamste oplossing, draait in net iets minder dan 100ms

[Soultaker]

Extra testdata voor dag 15: aoc-2024-day-15-challenge-1-to-4.zip

Referentie-tijden en antwoorden:

$ time pypy3 15.py < aoc-2024-day-15-challenge-1.txt
...1906
...1366

real    0m5.781s
user    0m5.700s
sys     0m0.060s

$ time pypy3 15.py < aoc-2024-day-15-challenge-2.txt
...1043
...0507

real    0m10.990s
user    0m10.734s
sys     0m0.210s

$ time pypy3 15.py < aoc-2024-day-15-challenge-3.txt 
...8202
...5552

real    0m0.140s
user    0m0.113s
sys     0m0.025s

$ time pypy3 15.py < aoc-2024-day-15-challenge-4.txt 
...8821
...9252

real    0m16.941s
user    0m16.659s
sys     0m0.200s

[Robbinb1993]

Soultaker schreef op zondag 15 december 2024 @ 17:30:
Extra testdata voor dag 15: aoc-2024-day-15-challenge-1-to-4.zip

Referentie-tijden en antwoorden:

$ time pypy3 15.py < aoc-2024-day-15-challenge-1.txt
...1906
...1366

real    0m5.781s
user    0m5.700s
sys     0m0.060s

$ time pypy3 15.py < aoc-2024-day-15-challenge-2.txt
...1043
...0507

real    0m10.990s
user    0m10.734s
sys     0m0.210s

$ time pypy3 15.py < aoc-2024-day-15-challenge-3.txt 
...8202
...5552

real    0m0.140s
user    0m0.113s
sys     0m0.025s

$ time pypy3 15.py < aoc-2024-day-15-challenge-4.txt 
...8821
...9252

real    0m16.941s
user    0m16.659s
sys     0m0.200s

aoc-2024-day-15-challenge-1: 215ms.
aoc-2024-day-15-challenge-2: 407ms.
aoc-2024-day-15-challenge-3: 0ms.
aoc-2024-day-15-challenge-4: 460ms.

Antwoorden zijn hetzelfde.

https://github.com/Robbin.../blob/main/day15/day15.cc

[breew]

Druk weekend.. maar dag 14 was leuk

duurde even voordat ik deel 2 "zag"

spoiler:

uiteindelijk was het genoeg om de coordinaten uit te rekenen voor de eerste 20000 stapen, en daarna de oplossing met kleinste standaarddeviatie te nemen..

[FCA]

Soultaker schreef op zondag 15 december 2024 @ 17:30:
Extra testdata voor dag 15: aoc-2024-day-15-challenge-1-to-4.zip

Referentie-tijden en antwoorden:

$ time pypy3 15.py < aoc-2024-day-15-challenge-1.txt
...1906
...1366

real    0m5.781s
user    0m5.700s
sys     0m0.060s

$ time pypy3 15.py < aoc-2024-day-15-challenge-2.txt
...1043
...0507

real    0m10.990s
user    0m10.734s
sys     0m0.210s

$ time pypy3 15.py < aoc-2024-day-15-challenge-3.txt 
...8202
...5552

real    0m0.140s
user    0m0.113s
sys     0m0.025s

$ time pypy3 15.py < aoc-2024-day-15-challenge-4.txt 
...8821
...9252

real    0m16.941s
user    0m16.659s
sys     0m0.200s

Mijn oplossing is niet heel veel sneller:

Challenge 1:
deel 1: 52.49ms
deel 2: 2.54s

Challenge 2:
deel 1: 532.69ms
deel 2: 6.05s

Challenge 3:
deel 1: 364 µs
deel 2: 6.14ms

Challenge 4:
deel 1: 33.38ms
deel 2: 7.54s

Antwoorden kloppen met de laatste cijfers die je hier geeft.

De oplossing voor algemene shapes is ongeveer 2x zo traag. Ik vind het voor nu allemaal even snel genoeg, geen puf meer om het sneller te maken (sowieso lig ik mooi op schema voor mijn extra doel, alle opgaves achter elkaar binnen 1 seconde oplossen, tot nu toe is alleen dag 14 boven de gemiddeld beschikbare tijd gekomen, alle andere dagen er ruim onder, dus ik heb wat speelruimte voor de laatste 10 dagen.).

[Satom]

Dag 15 ook afgerond! Deel 1 was goed te doen (met een grid'je), maar heb mij te lang vastgebeten op deel 2. Ik dacht deel 1 even te kunnen aanpassen, maar dat liep uit op steeds weer nieuwe bugs (concentratie was ook ver te zoeken vandaag). Uiteindelijk de boel omgeschreven

spoiler:

naar een lijst van objecten met 'begin' en 'eind' coördinaat. Dit werkte op beide examples perfect, alleen niet op mijn input. Na veel prutsen, debuggen en hier en daar wat herschrijven, kwam ik erachter dat een list 'Clear()' boven de '}' stond in een loop, in plaats van erbuiten. Blijkbaar kwam deze situatie niet voor in het voorbeeld

.

Nu de code nog een beetje opruimen!

[.oisyn]

Soultaker schreef op zondag 15 december 2024 @ 17:30:
Extra testdata voor dag 15: aoc-2024-day-15-challenge-1-to-4.zip

Referentie-tijden en antwoorden:

$ time pypy3 15.py < aoc-2024-day-15-challenge-1.txt
...1906
...1366

real    0m5.781s
user    0m5.700s
sys     0m0.060s

$ time pypy3 15.py < aoc-2024-day-15-challenge-2.txt
...1043
...0507

real    0m10.990s
user    0m10.734s
sys     0m0.210s

$ time pypy3 15.py < aoc-2024-day-15-challenge-3.txt 
...8202
...5552

real    0m0.140s
user    0m0.113s
sys     0m0.025s

$ time pypy3 15.py < aoc-2024-day-15-challenge-4.txt 
...8821
...9252

real    0m16.941s
user    0m16.659s
sys     0m0.200s

     Running `target\release\day15.exe -i .\extra\aoc-2024-day-15-challenge-1.txt`
Time spent: 78252.4µs
3186261906 - 3200411366

     Running `target\release\day15.exe -i .\extra\aoc-2024-day-15-challenge-2.txt`
Time spent: 218274.7µs
170571891043 - 171376050507

     Running `target\release\day15.exe -i .\extra\aoc-2024-day-15-challenge-3.txt`
Time spent: 294.3µs
1508202 - 1455552

     Running `target\release\day15.exe -i .\extra\aoc-2024-day-15-challenge-4.txt`
Time spent: 190772.8µs
1567178821 - 1565649252

@Robbinb1993 Wat mijn implementatie denk ik vooral sneller maakt is het feit dat jij 2x de processmove doorloopt. Ik gooi alle dozen in een queue, zodat ik later die queue nog een keer kan aflopen om de posities te updaten.

[ Voor 7% gewijzigd door .oisyn op 16-12-2024 01:22 ]

[mbe81]

Eindelijk dag 15, deel 2 opgelost! Ik had steeds last van het verplaatsen van halve boxen en kwam er maar niet achter waar ik de fout in ging... Heeft me wel een paar uur gekost haha.
Vanavond maar starten met dag 16, nu even geen zin meer in.

[Soultaker]

spoiler: Dag 16

De dag die je wist dat zou komen: een korste-pad probleem waarbij Dijkstra's algoritme natuurlijk de standaardoplossing is, al kun je denk ik ook een ad-hoc oplossing schrijven omdat het in de gegeven invoer altijd optimaal lijkt te zijn om het aantal draaingen te minimaliseren.

In mijn code ga ik er vanuit dat een vertex in de graaf een paar van (positie, richting) is, zodat elke vertex max. 3 buren heeft (vooruit, draai naar links, draai naar rechts). Je kunt ook alleen de positie in de graaf gebruiken, als je een draai combineert met een stap vooruit, maar dat vond ik minder voor de hand liggend, al heeft het wel voordelen zoals dat de eindvertex uniek bepaalt is bijvoorbeeld.

Voor deel 2:

spoiler:

kun je terugrekenen van het eindpunt. Als v op een optimaal pad ligt, dan geldt voor alle edges (u, v) dat u ook op een optimaal pad ligt als dist(u) + cost(u, v) = dist(v).

Je kunt dus ofwel terugrekenen waarbij je voor elke vertex de voorgangers berekent (wat niet zo ingewikkeld is), maar ik had m'n implementatie van Dijkstra's algoritme uitgebreid om voor elke bereikpare vertex bij te houden wat de optimale voorgangers zijn.

Python code

mbe81 schreef op maandag 16 december 2024 @ 06:35:
Eindelijk dag 15, deel 2 opgelost! Vanavond maar starten met dag 16, nu even geen zin meer in.

Gefeliciteerd Al zou ik persoonlijk nooit zo vroeg opstaan om niet met het probleem van vandaag te beginnen. (Je hoeft de problemen niet per se in volgorde te doen.)

[Janoz]

spoiler:

Hier ook soort van Dijkstra. Initieel wel gekozen om de stap en de draai samen te nemen waardoor je een score van 1 of 1001 had, maar dat heeft me bij deel 2 genekt waardoor ik het toch omgeschreven heb naar een losse draai en stap. Verder hou ik bij het zoeken gewoon de route bij en zodra ik ze allemaal gevonden heb flikker ik ze in een set en kijk ik hoe groot ie is.

[Soultaker]

Hier nog wat extra testcases voor dag 16: aoc-2024-day-16-testcases.zip (antwoorden zitten erbij).

De cases zijn te klein om te benchmarken; het zijn meer edge cases om de correctheid van je oplossing te valideren.

edit: Ik zie nu dat twopaths.txt een newline op het einde mist. Ik ben te lui om het te fixen maar als je programma dat niet accepteert, moet je zelf even een newline toevoegen.

[ Voor 23% gewijzigd door Soultaker op 16-12-2024 17:56 ]