Advent of Code 2022

[Creepy]

Creepy schreef op donderdag 8 december 2022 @ 14:23:
Valt me toch niet tegen. De sparse in 85 en 55ms en de rect in 20 en 10ms.

Even van Graalvm 17 CE naar OpenJDK 19 gewisseld: 70 en 50ms. voor de sparse en rect naar 15 en 9ms. Toch wel grappig om te zien dat dat stiekem best wat uit kan maken.

[Gropah]

eheijnen schreef op donderdag 8 december 2022 @ 17:19:
Krijgen we ook een dag vrij of moeten we tot en met 2e kerstdag bijven kloppen?

Werken voor je gouden sterren zul je!

KabouterSuper schreef op donderdag 8 december 2022 @ 17:29:
[...]

Overigens, ik ben nu 2019 en 2022 simultaan aan het doen (anders haal ik mijn doel niet om aan het einde van het jaar alle AoCs gedaan te hebben). Ik ben behoorlijk klaar met de intcode opdrachten.

Ik heb enigzins een interesse in dit soort problemen en een voorliefde voor automata, dus ik vond het wel een interessante reeks aan problemen. Het grootste probleem wat ik er mee heb, is dat je oplossing voor een dag wel afhankelijk word van een vorige dag. En als die lelijk in elkaar steekt, inefficient is, of het je gewoon niet gelukt is, dan heb je een (enorm) probleem. Dat vond ik er niet zo chill aan.

[.oisyn]

Gropah schreef op donderdag 8 december 2022 @ 17:48:
Ik heb enigzins een interesse in dit soort problemen en een voorliefde voor automata

Manufactoria 2022 al gespeeld?

[Gropah]

.oisyn schreef op donderdag 8 december 2022 @ 17:49:
[...]

Manufactoria 2022 al gespeeld?

*zucht*



* Gropah doet op steamwenslijstje doen

[TrailBlazer]

Python day 8
best wel blij met deze code. Misschien is het algoritme niet super wat ik gebruikt heb maar ik vind de code an sich wel netjes. Opbouwende kritiek is welkom

[eheijnen]

Toch niet het slechste resultaat in C# voor een I7 3770 met de MrHaas 2000*2000 matrix single core:

SW1 Totale tijd
SW2 File laden en matrix maken
SW3 Part 1
SW4 Part 2

code:

SW1 Elapsed Ticks......: 7274538
SW1 Elapsed MSec.......: 727
SW2 Elapsed Ticks......: 1282216
SW2 Elapsed MSec.......: 128
SW3 Elapsed Ticks......: 2855408
SW3 Elapsed MSec.......: 285
SW4 Elapsed Ticks......: 3130582
SW4 Elapsed MSec.......: 313

[tarlitz]

TrailBlazer schreef op donderdag 8 december 2022 @ 18:02:
Python day 8
best wel blij met deze code. Misschien is het algoritme niet super wat ik gebruikt heb maar ik vind de code an sich wel netjes. Opbouwende kritiek is welkom

Ik had ongeveer hetzelfde. Je zou eens naar `np.ndenumerate` kunnen kijken, die is erg handig om over array indexen te loopen.

code:

for (i, j), tree_height in np.ndenumerate(trees):
    ...

[Brilsmurfffje]

TrailBlazer schreef op donderdag 8 december 2022 @ 18:02:
Python day 8
best wel blij met deze code. Misschien is het algoritme niet super wat ik gebruikt heb maar ik vind de code an sich wel netjes. Opbouwende kritiek is welkom

Met wat @tarlitz zegt, verder vind ik persoonlijk een boolean niet zo netjes staan, beter passen als je een while loop gebruikt. Ik heb het probleem zelf opgelost met een matrix.

spoiler:

Iedere boom gepakt en dan de zichtlijnen naar de randen vanaf de boom gepakt, de hoogste boom uit die zichtlijnen gepakt, die moet lager zijn dan de boom waar je staat. Dat in array gestopt, minimale hoogte gepakt, gekeken of dat lager is dan de boom waar je bent en vervolgens een np.zeros() matrix deze boom locatie een 1 gegeven. Aan het einde kan ik die matrix sommeren om uit te komen op het aantal bomen dat zichtbaar is.

code:

spoiler:

import numpy as np

f = open("08/data.txt").readlines()

a = [list(i.strip()) for i in f]

forrest = np.array(a).astype(np.int8)

visible = np.zeros((forrest.shape[0]-2, forrest.shape[1]-2)).astype(np.int8)
# pad with ones
visible = np.pad(visible, pad_width=1, constant_values=1)

for (x,y), tree in np.ndenumerate(forrest):
# look left, right, up and down
tree_lines = np.array([
np.max(forrest[x,:y], initial=0),
np.max(forrest[x,y+1:], initial=0),
np.max(forrest[:x,y], initial=0),
np.max(forrest[x+1:,y], initial=0)
])
# minimal line of sight lower than tree to be visible
if min(tree_lines) < tree:
visible[x,y] = 1
else:
continue

print(np.sum(visible))

[Soultaker]

Brilsmurfffje schreef op donderdag 8 december 2022 @ 18:23:
code:

FYI, code tags werken niet in spoiler tags, dus je kunt je code beter elders posten (gist.github.com, pastebin.com, etc.) en hier een linkje plaatsen. Het heeft ook het voordeel dat je post verticaal minder ruimte inneemt.

[TrailBlazer]

Brilsmurfffje schreef op donderdag 8 december 2022 @ 18:23:
[...]


Met wat @tarlitz zegt, verder vind ik persoonlijk een boolean niet zo netjes staan, beter passen als je een while loop gebruikt. Ik heb het probleem zelf opgelost met een matrix.

spoiler:

Iedere boom gepakt en dan de zichtlijnen naar de randen vanaf de boom gepakt, de hoogste boom uit die zichtlijnen gepakt, die moet lager zijn dan de boom waar je staat. Dat in array gestopt, minimale hoogte gepakt, gekeken of dat lager is dan de boom waar je bent en vervolgens een np.zeros() matrix deze boom locatie een 1 gegeven. Aan het einde kan ik die matrix sommeren om uit te komen op het aantal bomen dat zichtbaar is.

code:

spoiler:

import numpy as np

f = open("08/data.txt").readlines()

a = [list(i.strip()) for i in f]

forrest = np.array(a).astype(np.int8)

visible = np.zeros((forrest.shape[0]-2, forrest.shape[1]-2)).astype(np.int8)
# pad with ones
visible = np.pad(visible, pad_width=1, constant_values=1)

for (x,y), tree in np.ndenumerate(forrest):
# look left, right, up and down
tree_lines = np.array([
np.max(forrest[x,:y], initial=0),
np.max(forrest[x,y+1:], initial=0),
np.max(forrest[:x,y], initial=0),
np.max(forrest[x+1:,y], initial=0)
])
# minimal line of sight lower than tree to be visible
if min(tree_lines) < tree:
visible[x,y] = 1
else:
continue

print(np.sum(visible))

In plaats van die bool kan ik beter de coordinaten van die boom in een set plaatsen en aan het eind de lengte van die set bepalen. Dat is iets netter inderdaad. Overigens heb jij deel 2 ook al in je code zitten? dat zit er bij wel meteen in.

spoiler:

Deel 1 is bijvangst bij het uitvoeren van deel 2. Als de zichtlijn de rand raakt is die ook zichtbaar namelijk.

[Varienaja]

Dag 8 in Java.

In het begin had ik alle code *4: voor iedere zoekrichting een eigen pad. Als je dan bij deel 2 zit te knoeien (zoals ik) kost dat onnodig veel tijd om je wijzigingen steeds 4x te moeten doen...

Nu 's avonds even gerefactored, en het ziet er stukken beter uit zo. En mijn Point class is wat gegroeid. :-)

Met de 2000x2000 input van @MrHaas 900 400 respectievelijk 700 400ms.
De 1M sparse file van @Soultaker 250175 respectievelijk 275 125ms.

^{Code streamier gemaakt, daardoor met een gemakzuchtige .parallel() de uitvoertijd versneld.}

[ Voor 18% gewijzigd door Varienaja op 08-12-2022 21:33 ]

[Remcoder]

Remcoder schreef op donderdag 8 december 2022 @ 12:29:
[...]

Vreemd, ik mis 7006 items in mijn HashMap voor de sparse dataset en krijg dus een NPE omdat een bepaalde coordinaat volgens de grid geen boom bevat...

D'oh, het bleek een copy paste fout te zijn, een paar regels waren leeg geworden

[Soultaker]

.oisyn schreef op donderdag 8 december 2022 @ 17:18:

===[ input.txt ]==========
Time: 416us (load:40us, part1:26us, part2:348us)
1681
201684

===[ aoc_2022_day08_rect.txt ]==========
Time: 1709us (load:36us, part1:87us, part2:1585us)
3319
672888

===[ aoc_2022_day08_sparse.txt ]==========
Time: 7386us (load:38us, part1:1576us, part2:5770us)
27476
32065007130

===[ input-mrhaas.txt ]==========
Time: 26872us (load:64us, part1:5405us, part2:21401us)
32015
1720358640

Ik doe de 2000x2000 input nu in ~150 ms single core, ~24 ms quad core met HT (inclusief “parsen”) dus of ik sneller ben of niet hangt er vanaf of jouw code nog singlethreaded is of niet. Sowieso vermoed ik dat jij een flink snellere CPU hebt dan ik. We zouden eigenlijk een AoC hardware standaard moeten introduceren om te vergelijken

[MueR]

Soms heb je van die dagen dat het gewoon niet wil.. en dan is dat duidelijk te zien aan je oplossing.



Sad..

[MaNDaRK]

Soultaker schreef op donderdag 8 december 2022 @ 12:07:
Hier nog twee challenges (niet puur op grootte):

• aoc_2022_day08_sparse.txt (1 MB); antwoorden eindigen met "76" en "30".

Thanks, altijd leuk om even te proberen!

Mijn code in python - Day 8

-[ stats ]------------------------------
Parse time:      214.91742134094238 ms
Part 1:          7142.685174942017 ms
Part 2:          10830.500602722168 ms

[.oisyn]

Soultaker schreef op donderdag 8 december 2022 @ 18:56:
[...]

Ik doe de 2000x2000 input nu in ~150 ms single core, ~24 ms quad core met HT (inclusief “parsen”) dus of ik sneller ben of niet hangt er vanaf of jouw code nog singlethreaded is of niet. Sowieso vermoed ik dat jij een flink snellere CPU hebt dan ik. We zouden eigenlijk een AoC hardware standaard moeten introduceren om te vergelijken

Wel multithreaded. 5800X 16 threads @ 3.7GHz. Ik heb nog niet geprofiled though
.edit: singlethreaded doet ie trouwens 135ms totaal, 130ms part2. Ik heb de code voor part2 wel wat generiek opgezet, die kan voor alle richtingen worden aangeroepen. Ik gok dat dat niet heel erg efficient is. Wil eigenlijk ook de data transposen voor op/neer, dat is waarschijnlijk wat vriendelijker voor de cache.
https://github.com/oisyn/...ter/Problem8/Problem8.cpp

[ Voor 24% gewijzigd door .oisyn op 08-12-2022 19:53 ]

[Daos]

Vandaag was goed te doen: https://github.com/gjscho...lob/main/Day08/Program.cs

spoiler:

Ik heb vorig jaar hier geleerd om met delta's te werken. In plaats van for-loops voor alle richtingen heb je 1 while-loop waarbij je elke keer een delta bij je positie optelt. In (x, y) is dat voor noord (0, -1), zuid (0, 1), oost (1, 0) en west (-1, 0). Je kan dezelfde functie dan meerdere keren aanroepen met een andere delta. Code is daardoor simpel en goed te begrijpen.

[CMG]

KabouterSuper schreef op donderdag 8 december 2022 @ 17:29:
[...]

Tot en met de 25e. De laatste ster krijg je als je 49 sterren verzameld hebt, dus op eerste kerstdag is er geen deel 2 (maar je moet wel op een knop duwen).

Overigens, ik ben nu 2019 en 2022 simultaan aan het doen (anders haal ik mijn doel niet om aan het einde van het jaar alle AoCs gedaan te hebben). Ik ben behoorlijk klaar met de intcode opdrachten.

Oh, ik vond de intcode opdrachten anders erg leuk 😊

[P_Tingen]

Overigens, ik ben nu 2019 en 2022 simultaan aan het doen (anders haal ik mijn doel niet om aan het einde van het jaar alle AoCs gedaan te hebben). Ik ben behoorlijk klaar met de intcode opdrachten.

I feel your pain. Ik kreeg toen de intcode machine niet goed aan de praat dus eindigde meerdere dagen met zowel eindeloos knutselen om het goed te krijgen en uiteindelijk geen oplossing te hebben, domweg omdat je de opdracht van een paar dagen geleden niet kon voltooien.

[Litpho]

.oisyn schreef op donderdag 8 december 2022 @ 15:56:
[...]

En doe het nu eens zonder include_str!()?

Dag 8 zonder include_str!: parsing: 113.60 μs, part one: 295.10 μs, part two: 206.60 μs

Dus ja, parsen wordt er een stuk langzamer van, maar aangezien het na het parsen een owned datamodel is ongeacht de oorsprong (include_str! of filesystem) is dat wel logisch (op dag 6 na waar parsen en nom gewoon geen zin had).

include_str! maakt het makkelijker om alle tests te draaien vanuit de root van de workspace, dus ik zie daar geen groot probleem in voor AoC. Voor een algemeen project wel, maar dan zou ik vermoedelijk ook iets als clap ervoor zetten om de input parameteriseerbaar te maken.

[Litpho]

Soultaker schreef op donderdag 8 december 2022 @ 16:58:
Overigens, bij mij geeft 'ie:

code:

Time spent parsing: 23.99 μs
Result part one: 1807
Time spent: 518.16 μs
Result part two: 480000
Time spent: 369.25 μs

Dus ik denk dat jou CPU sowieso 50% sneller is dan de mijne (niet zo gek, is een Kaby Lake i7-7560U laptop CPU).

Nog steeds geen slechte tijden verder . CPU snelheid maakt wel een verschil natuurlijk, maar als orde van grootte vind ik het niet verkeerd.

[Cranzai]

Vanavond pas tijd gevonden met de opdracht aan de slag te gaan, uiteindelijk maar voor de recht doorzee aanpak gegaan die ik eigenlijk niet wilde maken. Verbazingwekkend genoeg had deze implementatie niet zoveel moeite met de standaard input, dit zal voor de challenges hier anders zijn....

spoiler:

Ik bouw voor elke positie opnieuw de bijbehorende kolom, vooraf een transpose maken zou wel kunnen maar is alleen praktisch zolang de grid square is als ik me niet vergis.
Uiteindelijk ben ik wel fan van de oplossing van @Soultaker

[.oisyn]

Litpho schreef op donderdag 8 december 2022 @ 20:52:
[...]

Dag 8 zonder include_str!: parsing: 113.60 μs, part one: 295.10 μs, part two: 206.60 μs

Dus ja, parsen wordt er een stuk langzamer van, maar aangezien het na het parsen een owned datamodel is ongeacht de oorsprong (include_str! of filesystem) is dat wel logisch (op dag 6 na waar parsen en nom gewoon geen zin had).

include_str! maakt het makkelijker om alle tests te draaien vanuit de root van de workspace, dus ik zie daar geen groot probleem in voor AoC.

include_str! maakt dat alle data @compiletime beschikbaar is, en de compiler dus bepaalde optimalisaties kan doen die hij niet kan doen bij onbekende data. Dat is mijn voornaamste bezwaar

[.oisyn]

.oisyn schreef op donderdag 8 december 2022 @ 19:47:
Wil eigenlijk ook de data transposen voor op/neer, dat is waarschijnlijk wat vriendelijker voor de cache.

Een snelle test leert dat een transpose doen (op een naieve manier) zo'n 4ms kost, maar de processing van part2 gaat daarmee wel van 130ms naar 115ms singlethreaded. Dat is dus een winst. In multithreading blijft er echter geheel niets van de winst over. En dan heb ik mijn boom score nog niet goed omdat die data dan natuurlijk ook nog getransposed moet worden.

Wellicht dat dit interessant wordt als je meerdere rijen tegelijk wil doen met SIMD. Jammer dat AVX2 nog geen scatter instructies heeft, alleen maar gather. Misschien mijn CPU eens upgraden naar een Zen4 met AVX512 (jammer alleen dat ik dan ook weer mijn mobo+mem moet vervangen)

[ Voor 17% gewijzigd door .oisyn op 08-12-2022 21:09 ]

[eheijnen]

Is het al 6 uur...?

[Visitor.q]

Sjongejonge, ik zit helemaal vast op dag 7. Ik heb een mooie class gemaakt met lists van dir en file objecten, en ik krijg de test input goed geparsed en het juiste antwoord eruit, maar ik kom niet door de echte input set. Ik word nu helemaal tureluurs van de recursieve lijstjes met file en dirnames, sizes.

Ik sla deze even over en pak hem later wel weer op. Die van dag 08 ziet er al beter uit, ik werk liever met cijfertjes. Ik heb nog steeds het doel om deze aoc2022 uit te spelen trouwens

[Soultaker]

.oisyn schreef op donderdag 8 december 2022 @ 19:47:
Wel multithreaded. 5800X 16 threads @ 3.7GHz. Ik heb nog niet geprofiled though
.edit: singlethreaded doet ie trouwens 135ms totaal, 130ms part2. Ik heb de code voor part2 wel wat generiek opgezet, die kan voor alle richtingen worden aangeroepen. Ik gok dat dat niet heel erg efficient is. Wil eigenlijk ook de data transposen voor op/neer, dat is waarschijnlijk wat vriendelijker voor de cache.
https://github.com/oisyn/...ter/Problem8/Problem8.cpp

Bedankt voor de code! Dit is de huidige versie van mij met multithreading support: https://gist.github.com/m...32f314f9c22254#file-08-cc

Ik heb je code naar Linux geport zodat ik 'm kan vergelijken. Ik heb je findchar() implementatie vervangen door een simpele std::find() omdat mijn CPU geen AVX-512 instructies ondersteunt, maar ik denk niet dat dat veel verschil maakt (sowieso doe ik in mijn eigen oplossing hetzelfde).

Dan krijg ik de volgende timings op m'n quad core i5-8259U:

===[ ../testdata/08.in ]==========
Time: 525us (load:13us, part1:40us, part2:471us)
1785
345168

===[ ../extradata/aoc_2022_day08_rect.txt ]==========
Time: 2507us (load:10us, part1:105us, part2:2391us)
3319
672888

===[ ../extradata/aoc_2022_day08_sparse.txt ]==========
Time: 16658us (load:12us, part1:1994us, part2:14651us)
27476
32065007130

===[ ../extradata/day8-2000x2000.txt ]==========
Time: 79767us (load:21us, part1:7636us, part2:72108us)
32015
1720358640

Jij doet de 2000x2000 set in 79 ms vs ik in 23 ms, dus ik ben 3x sneller.

En in single thread modus doe jij er 247 ms over en ik 152 ms, dus ik ben ~39% sneller.

Ik denk dus dat mijn algoritme efficiënter is.

Het is ook interessant om te zien hoe we multithreading anders aanpakken: jij splitst de invoer op in T blokken waarbij T het aantal threads is. Ik creëer veel meer blokken en laat threads steeds het volgende stukje pakken (in dit probleem is een blok simpelweg (1 rij van de invoer). Volgens mij heeft jouw aanpak het nadeel dat verschillende taken niet op hetzelfde moment klaar zijn, waardoor je altijd op de traagste thread moet wachten, terwijl met mijn aanpak de utilization veel dichter bij 100% blijft (met als nadeel dat je moet synchroniseren op de atomic variable).

edit:
Ook interessant om te zien dat memory mappen onder Windows blijkbaar aanzienlijk langzamer is dan onder Linux, al is het nog steeds maar een beperkt percentage van de totale tijd.

[ Voor 3% gewijzigd door Soultaker op 08-12-2022 21:29 ]

[YoToP]

Visitor.q schreef op donderdag 8 december 2022 @ 21:24:
Sjongejonge, ik zit helemaal vast op dag 7. Ik heb een mooie class gemaakt met lists van dir en file objecten, en ik krijg de test input goed geparsed en het juiste antwoord eruit, maar ik kom niet door de echte input set. Ik word nu helemaal tureluurs van de recursieve lijstjes met file en dirnames, sizes.

Ik sla deze even over en pak hem later wel weer op. Die van dag 08 ziet er al beter uit, ik werk liever met cijfertjes. Ik heb nog steeds het doel om deze aoc2022 uit te spelen trouwens

misschien heb je wat aan mijn code. Ik heb ook een class gemaakt met lijstjes van dirs en files. Ik ben niet helemaal tevreden over de methodes, want ik ben een weg in gegaan en kwam er ook niet uit maar heb het met minimale wijzigingen kunnen rechttrekken.

[farlane]

Visitor.q schreef op donderdag 8 december 2022 @ 21:24:
Sjongejonge, ik zit helemaal vast op dag 7. Ik heb een mooie class gemaakt met lists van dir en file objecten, en ik krijg de test input goed geparsed en het juiste antwoord eruit, maar ik kom niet door de echte input set. Ik word nu helemaal tureluurs van de recursieve lijstjes met file en dirnames, sizes.

Ik sla deze even over en pak hem later wel weer op. Die van dag 08 ziet er al beter uit, ik werk liever met cijfertjes. Ik heb nog steeds het doel om deze aoc2022 uit te spelen trouwens

Zou je willen aanraden om ook een parent member op te nemen zodat je makkelijk een cd .. kunt doen.

[Varienaja]

Visitor.q schreef op donderdag 8 december 2022 @ 21:24:
Sjongejonge, ik zit helemaal vast op dag 7.

De meest gemaakte fout is dat men bij dag 7 de grootte van de file /a/b/c/lalala.txt per ongeluk optelt bij directory /c

[.oisyn]

Soultaker schreef op donderdag 8 december 2022 @ 21:28:
Ik heb je code naar Linux geport zodat ik 'm kan vergelijken. Ik heb je findchar() implementatie vervangen door een simpele std::find() omdat mijn CPU geen AVX-512 instructies ondersteunt, maar ik denk niet dat dat veel verschil maakt (sowieso doe ik in mijn eigen oplossing hetzelfde).

Het is AVX-2. De instrinsic komt idd uit de AVX-512 lijst en GCC is daar heel anal over (in MVSC++ mag je gewoon alles gebruiken ookal is dat niet je target arch, hij zal ze alleen niet uit zichzelf genereren), maar het compilet gewoon naar een opcode die compatible is met AVX-2. Het is feitelijk hetzelfde als _mm256_loadu_si256(), alleen verwacht die een pointer naar __m256i wat gewoon irritant is.

Dan krijg ik de volgende timings op m'n quad core i5-8259U:

===[ ../testdata/08.in ]==========
Time: 525us (load:13us, part1:40us, part2:471us)
1785
345168

===[ ../extradata/aoc_2022_day08_rect.txt ]==========
Time: 2507us (load:10us, part1:105us, part2:2391us)
3319
672888

===[ ../extradata/aoc_2022_day08_sparse.txt ]==========
Time: 16658us (load:12us, part1:1994us, part2:14651us)
27476
32065007130

===[ ../extradata/day8-2000x2000.txt ]==========
Time: 79767us (load:21us, part1:7636us, part2:72108us)
32015
1720358640

Ik pak wel in mijn DoParallel code wel aantal hardware threads - 2. Dat werkt bij mij beter dan allemaal. Maar als je er dan maar 4 hebt dan hou je er maar 2 over.

Het is ook interessant om te zien hoe we multithreading anders aanpakken: jij splitst de invoer op in T blokken waarbij T het aantal threads is. Ik creëer veel meer blokken en laat threads steeds het volgende stukje pakken (in dit probleem is een blok simpelweg (1 rij van de invoer). Volgens mij heeft jouw aanpak het nadeel dat verschillende taken niet op hetzelfde moment klaar zijn, waardoor je altijd op de traagste thread moet wachten, terwijl met mijn aanpak de utilization veel dichter bij 100% blijft (met als nadeel dat je moet synchroniseren op de atomic variable).

[Visitor.q]

YoToP schreef op donderdag 8 december 2022 @ 21:29:
[...]


misschien heb je wat aan mijn code. Ik heb ook een class gemaakt met lijstjes van dirs en files. Ik ben niet helemaal tevreden over de methodes, want ik ben een weg in gegaan en kwam er ook niet uit maar heb het met minimale wijzigingen kunnen rechttrekken.

Nice, nu kan ik iig verifiëren hoe ik uit moet komen. De website gaf al aan dat ik te laag zat...

farlane schreef op donderdag 8 december 2022 @ 21:38:
[...]

Zou je willen aanraden om ook een parent member op te nemen zodat je makkelijk een cd .. kunt doen.

Yes, die heb ik Bij het aanmaken van een nieuwe dir stel ik meteen de parent in.Tnx!

Varienaja schreef op donderdag 8 december 2022 @ 21:38:
[...]

De meest gemaakte fout is dat men bij dag 7 de grootte van de file /a/b/c/lalala.txt per ongeluk optelt bij directory /c

Maar die file hoort toch in c? Of bedoel je letterlijk /c (dus een dir in root)?
Wel een goed idee trouwens, ik kan een directory in de root aanmaken met gelijke naam aan een of andere subdir, en kijken of dat goed gaat.

[Cranzai]

.oisyn schreef op donderdag 8 december 2022 @ 21:39:
[...]

Het is AVX-2. De instrinsic komt idd uit de AVX-512 lijst en GCC is daar heel anal over (in MVSC++ mag je gewoon alles gebruiken ookal is dat niet je target arch, hij zal ze alleen niet uit zichzelf genereren), maar het compilet gewoon naar een opcode die compatible is met AVX-2. Het is feitelijk hetzelfde als _mm256_loadu_si256(), alleen verwacht die een pointer naar __m256i wat gewoon irritant is.


[...]

Ik pak wel in mijn DoParallel code wel aantal hardware threads - 2. Dat werkt bij mij beter dan allemaal. Maar als je er dan maar 4 hebt dan hou je er maar 2 over.


[...]

[Afbeelding]

Multi-threaden bij AoC
Doe dan ook maar een snelle openacc gpu implementatie
Grote kans dat je meer I/O hebt dan daadwerkelijk zinvol werk

[ Voor 3% gewijzigd door Cranzai op 08-12-2022 21:49 ]

[Varienaja]

Cranzai schreef op donderdag 8 december 2022 @ 21:48:
Multi-threaden bij AoC

Ik heb van 't voorjaar alle jaren AoC ingehaald die ik nog niet had. IntCode (2019) en multithreading gaan heel goed samen!

[Soultaker]

.oisyn schreef op donderdag 8 december 2022 @ 21:39:
Het is AVX-2. De instrinsic komt idd uit de AVX-512 lijst en GCC is daar heel anal over (in MVSC++ mag je gewoon alles gebruiken ookal is dat niet je target arch, hij zal ze alleen niet uit zichzelf genereren), maar het compilet gewoon naar een opcode die compatible is met AVX-2. Het is feitelijk hetzelfde als _mm256_loadu_si256(), alleen verwacht die een pointer naar __m256i wat gewoon irritant is.

Enig idee hoe ik dat gecompileerd krijg? Of zal ik het maar zo laten? (Het lijkt me niet echt een fundamenteel deel van je algoritme.)

Ik pak wel in mijn DoParallel code wel aantal hardware threads - 2. Dat werkt bij mij beter dan allemaal. Maar als je er dan maar 4 hebt dan hou je er maar 2 over.

Goed punt, ik heb even geprobeerd zonder de - 2, en dan ga je van 79 ms naar 75 ms voor de 2000x2000 set.

Overigens geeft std::thread::hardware_concurrency() het aantal hyperthreads, dus 8 voor deze CPU met 4 cores met HT enabled.

.oisyn schreef op donderdag 8 december 2022 @ 21:39:
[Afbeelding]

Ik weet niet wat deze kleurtjes betekenen. Ik neem aan dat je zegt dat alle threads ~100% bezig zijn? Kan zijn; ik heb in het verleden wel aanzienlijke snelheidswinst behaald met m'n aanpak, maar misschien gaat dat voor dit problem/jouw algoritme niet op.

edit:
Maar als ik naar de data kijk: met multithreading ga jij van 242 ms naar 74 ms, een speedup van slechts 3.27x, wat weinig is voor 4 cores en 8 hyperthreads, en ik van 135 naar 23 ms, een speedup van 5.87x (meer dan de 4 cores, minder dan de 8 hyperthreads). Dat suggereert dat mijn aanpak een aanzienlijk hogere speedup mogelijk maakt, in ieder geval voor mijn algoritme.

[ Voor 9% gewijzigd door Soultaker op 08-12-2022 22:09 ]

[farlane]

Visitor.q schreef op donderdag 8 december 2022 @ 21:44:
[...]
Maar die file hoort toch in c? Of bedoel je letterlijk /c (dus een dir in root)?
Wel een goed idee trouwens, ik kan een directory in de root aanmaken met gelijke naam aan een of andere subdir, en kijken of dat goed gaat.

Kweetniet wat je daar mee bedoelt, maar als je die tree hebt opgebouwd is de grootte van een dir de grootte van zijn subdirs + de grootte van z'n files:

code:

public int Size() { return Dirs.Sum(d => d.Size()) + Files.Sum(f => f.Size); }

[Cranzai]

Ik heb zo'n donkerbruin vermoeden dat @Visitor.q tegen twee folders in verschillende locaties met dezelfde naam aanloopt?

[.oisyn]

Soultaker schreef op donderdag 8 december 2022 @ 21:51:
[...]

Enig idee hoe ik dat gecompileerd krijg? Of zal ik het maar zo laten? (Het lijkt me niet echt een fundamenteel deel van je algoritme.)

Het zal het verschil idd niet maken, maar ipv die loadu_epi8 gewoon een loadu_si256 doen, en de input ptr even casten naar __m256i*

Ik weet niet wat deze kleurtjes betekenen. Ik neem aan dat je zegt dat alle threads ~100% bezig zijn? Kan zijn; ik heb in het verleden wel aanzienlijke snelheidswinst behaald met m'n aanpak, maar misschien gaat dat voor dit problem/jouw algoritme niet op.

Oh sorry, helemaal vergeten erbij te zeggen . Bij rood zijn ze in wait state en doen ze niets. Dus er is hier nog een hoop winst te halen

[farlane]

Cranzai schreef op donderdag 8 december 2022 @ 22:38:
Ik heb zo'n donkerbruin vermoeden dat @Visitor.q tegen twee folders in verschillende locaties met dezelfde naam aanloopt?

Owhja ok, ik had het ding als een tree opgebouwd dan heb je daar geen last van.

[Visitor.q]

Tegen beter weten in toch de hele avond met Day07 bezig geweest...

Ik heb het probleem met @YoToP zijn code weten terug te brengen naar 1 file die wordt toegevoegd aan een subfolder ergens deep down. Yotop zijn script pakt die mee, en geeft daardoor een grotere uitkomst dan mijn script. In mijn script lijkt de file list van die directory leeg, terwijl de parser wel een file heeft gezien. Wellicht gaat er met het toevoegen iets niet goed.

Morgen verder.

[.oisyn]

@Soultaker Het is echt verbazend hoeveel sneller een per boom score berekenen algoritme is. Ik kom op 62ms singlethreaded bij een eerste poging, terwijl die andere 130ms kostte

.edit:

===[ input.txt ]==========
Time: 222us (load:38us, part1:29us, part2:154us)
1681
201684

===[ aoc_2022_day08_rect.txt ]==========
Time: 448us (load:40us, part1:103us, part2:304us)
3319
672888

===[ aoc_2022_day08_sparse.txt ]==========
Time: 4764us (load:41us, part1:2019us, part2:2704us)
27476
32065007130

===[ input-mrhaas.txt ]==========
Time: 18524us (load:43us, part1:7180us, part2:11300us)
32015
1720358640

En een stuk betere thread utilization:


.edit2: oh wacht mijn antwoorden kloppen niet
.edit3: typo . Nu klopt het wel. Timings iets langzamer daardoor wel.

[ Voor 79% gewijzigd door .oisyn op 09-12-2022 00:14 ]

[Wraldpyk]

Tot en met dag 8 gelukt met JavaScript! Ik ben benieuwd hoe ver ik kom deze keer.

Had wel even een probleem met part 2 vandaag, maar dat kwam door een stomme `.reverse` die om een of andere reden dingen niet helemaal maakte wat ik dacht dat het zou worden. (objects ftw)

https://github.com/Topene...blob/2022/day8/program.js

[Soultaker]

.oisyn schreef op donderdag 8 december 2022 @ 23:32:
@Soultaker Het is echt verbazend hoeveel sneller een per boom score berekenen algoritme is. Ik kom op 62ms singlethreaded bij een eerste poging, terwijl die andere 130ms kostte

Ja he? Het ging ook compleet tegen mijn intuïtie in, het lijkt alsof je zoveel dubbel werk doet. Ik besefte me pas dat dat niet zo is toen Creepy mijn sparse dataset (die dat soort oplossingen zou moeten afstraffen) in enkele milliseconden wist op te lossen. Weet niet of je 'm gelezen hebt, maar ik heb hier proberen uit te leggen waarom de per-boom aanpak net zo snel is als de meer-obvious-lineaire oplossing die wij allebei in eerste instantie geïmplementeerd hadden.

De twee delen vervolgens combineren was mijn eigen innovatie (maar ook weer geïnspireerd doordat me opviel dat Creepy's oplossing in deel 1 en deel 2 precies dezelfde while-loops had geïmplementeerd); weet niet of het precies een factor 2 winst oplevert maar ik denk dat het wel in de buurt kan komen.

[.oisyn]

Soultaker schreef op vrijdag 9 december 2022 @ 00:01:
De twee delen vervolgens combineren was mijn eigen innovatie (maar ook weer geïnspireerd doordat me opviel dat Creepy's oplossing in deel 1 en deel 2 precies dezelfde while-loops had geïmplementeerd)

Lol, ik dacht echt exact hetzelfde toen ik dit aan het intypen was . Als je toch per boom kijkt, kun je net zo goed meteen tellen of je voor die boom de rand hebt gehaald. Dat deel heb ik nog niet geimplementeerd.

.edit: nu wel

===[ input.txt ]==========
Time: 302us (load:37us)
1681
201684

===[ aoc_2022_day08_rect.txt ]==========
Time: 361us (load:39us)
3319
672888

===[ aoc_2022_day08_sparse.txt ]==========
Time: 2818us (load:40us)
27476
32065007130

===[ input-mrhaas.txt ]==========
Time: 10584us (load:43us)
32015
1720358640

Code geupdatet. Die is ook een heel stuk simpeler geworden.

.edit: meerdere runs is ook wel interessant

===[ input.txt ]==========
Time: 306us (load:44us)
1681
201684
Time: 138us (load:34us)
1681
201684
Time: 111us (load:34us)
1681
201684
Time: 112us (load:34us)
1681
201684
Time: 111us (load:29us)
1681
201684
Time: 118us (load:35us)
1681
201684
Time: 116us (load:28us)
1681
201684
Time: 114us (load:35us)
1681
201684
Time: 106us (load:33us)
1681
201684
Time: 108us (load:27us)
1681
201684

===[ aoc_2022_day08_rect.txt ]==========
Time: 264us (load:42us)
3319
672888
Time: 239us (load:35us)
3319
672888
Time: 337us (load:34us)
3319
672888
Time: 204us (load:35us)
3319
672888
Time: 213us (load:35us)
3319
672888
Time: 366us (load:48us)
3319
672888
Time: 232us (load:35us)
3319
672888
Time: 212us (load:35us)
3319
672888
Time: 234us (load:34us)
3319
672888
Time: 244us (load:32us)
3319
672888

===[ aoc_2022_day08_sparse.txt ]==========
Time: 2605us (load:42us)
27476
32065007130
Time: 2521us (load:35us)
27476
32065007130
Time: 2765us (load:36us)
27476
32065007130
Time: 2396us (load:36us)
27476
32065007130
Time: 2329us (load:36us)
27476
32065007130
Time: 2187us (load:35us)
27476
32065007130
Time: 2167us (load:36us)
27476
32065007130
Time: 2186us (load:35us)
27476
32065007130
Time: 2504us (load:37us)
27476
32065007130
Time: 2479us (load:37us)
27476
32065007130

===[ input-mrhaas.txt ]==========
Time: 9849us (load:43us)
32015
1720358640
Time: 10090us (load:36us)
32015
1720358640
Time: 10310us (load:42us)
32015
1720358640
Time: 9957us (load:40us)
32015
1720358640
Time: 9767us (load:37us)
32015
1720358640
Time: 10063us (load:35us)
32015
1720358640
Time: 10712us (load:37us)
32015
1720358640
Time: 10293us (load:35us)
32015
1720358640
Time: 10455us (load:36us)
32015
1720358640
Time: 10575us (load:38us)
32015
1720358640

[ Voor 81% gewijzigd door .oisyn op 09-12-2022 00:41 ]

[Varienaja]

Ik had een goeie dag vandaag. 2801e voor part 1, en een stuk hoger: 1511e voor part 2. Dag 9 in Java.

[jmerle]

Dag 9 in Python

spoiler:

Ik representeerde locaties eerst als (x, y) tuples, maar halverwege deel 1 heb ik dat toch maar omgegooid naar een Point class om het overzichtelijk te houden. Deel 2 was vandaag gelukkig wel goed te doen met mijn opzet voor deel 1, ik zie relatief ongeveer hetzelfde verschil als @Varienaja in ranglijst posities (599e/332e).

[Janoz]

jmerle schreef op vrijdag 9 december 2022 @ 07:13:
Dag 9 in Python

spoiler:

Ik representeerde locaties eerst als (x, y) tuples, maar halverwege deel 1 heb ik dat toch maar omgegooid naar een Point class om het overzichtelijk te houden. Deel 2 was vandaag gelukkig wel goed te doen met mijn opzet voor deel 1, ik zie relatief ongeveer hetzelfde verschil als @Varienaja in ranglijst posities (599e/332e).

spoiler:

Ik had nog een pointclass liggen van vorig jaar dag 13 bomvol herbruikbare functionaliteit. Hoewel mijn verplaats oplossing bij deel 1 gelijk werkte voor deel 2 ben ik nog al wat tijd kwijt geweest omdat ik niet overal netjes de variabelen aan het vervangen was

[MatHack]

Dag 9 in C#

In één keer redelijk nette code m.i., opdracht was goed te doen.

spoiler:

Omzetten van deel 1 naar deel 2 was voornamelijk array maken van de segmenten ipv twee losse variabelen, dat ging redelijk snel.

[Thorwing]

voor part 2 maakte ik initieel een foutje waar ik veelste lang mee bezig was

spoiler:

Had pas veelste laat door dat een touw van langere lengte dus ervoor zorgt dat punten 2 kunnen verschillen op beide assen, hierdoor ging de verschuiving helemaal verkeerd

Hier mijn oplossing in 'functionele' kotlin: Dag9 Thorwing

[Diderikdm]

Goed te doen vandaag min een foutje op begrijpend lezen deel 2

spoiler:

10 knots is niet 1 head + 10 tails

Dag 9 - Python

[Remcoder]

MatHack schreef op vrijdag 9 december 2022 @ 07:54:
Dag 9 in C#

In één keer redelijk nette code m.i., opdracht was goed te doen.

spoiler:

Omzetten van deel 1 naar deel 2 was voornamelijk array maken van de segmenten ipv twee losse variabelen, dat ging redelijk snel.

spoiler:

Dat had ik dus ook

Alhoewel ik eerst was begonnen met een Map heb ik die na het lezen van jou reactie inderdaad even omgekrast naar een array.

Daarnaast kon ik mijn Coordinate class uit mijn library mooi gebruiken, na wat uitbreidingen om de verschillende hoeken te bepalen.

[BernardV]

Nog even voor Dag 8 in PHP:

Eerste poging, werkt prima, maar met de 2000x2000 en de sparse was deze erg traag.
https://gist.github.com/B...785f1ed108fdea97b3c3db2ac

Daarna de map omgezet naar 1 lange array, factor 20 sneller op de sparse ongeveer en 40x op de 2000x2000:
https://gist.github.com/B...4cafcace93ebd30814e48bd20

Dag 9 wordt later vandaag, nog geen tijd voor helaas.

[YoToP]

Hah, ja ik had dus dit:

Thorwing schreef op vrijdag 9 december 2022 @ 07:55:
...

spoiler:

Had pas veelste laat door dat een touw van langere lengte dus ervoor zorgt dat punten 2 kunnen verschillen op beide assen, hierdoor ging de verschuiving helemaal verkeerd

en dit:

Diderikdm schreef op vrijdag 9 december 2022 @ 08:44:

spoiler:

10 knots is niet 1 head + 10 tails

Maar wel weer gelukt Linkje

[ Voor 7% gewijzigd door YoToP op 09-12-2022 09:22 ]

[Xqlusive]

Ik loop een beetje vast op deel 1 van dag 9...

De testcase doorloopt hij perfect, ik heb zelfs de hele sequence aan verwachte coördinaten van de tail uitgeschreven en vergeleken met de sequence die ik simuleer. Dit komt voor de testdata keurig overeen, maar het getal dat uit de echte data komt klopt dan blijkbaar weer niet.

Ongetwijfeld zal ik iets verkeerd doen, maar het is wel lastig debuggen als de oplossing wel perfect werkt op de testdata, maar het op de echte data niet blijkt te kloppen...

[P_Tingen]

Xqlusive schreef op vrijdag 9 december 2022 @ 09:28:
Ik loop een beetje vast op deel 1 van dag 9...

De testcase doorloopt hij perfect, ik heb zelfs de hele sequence aan verwachte coördinaten van de tail uitgeschreven en vergeleken met de sequence die ik simuleer. Dit komt voor de testdata keurig overeen, maar het getal dat uit de echte data komt klopt dan blijkbaar weer niet.

Ongetwijfeld zal ik iets verkeerd doen, maar het is wel lastig debuggen als de oplossing wel perfect werkt op de testdata, maar het op de echte data niet blijkt te kloppen...

Hier idem. Ik zit me nu af te vragen hoeveel tijd ik hier tegenaan moet gooien. Hou je rekening met negatieve coordinaten?

[Ghehe]

Xqlusive schreef op vrijdag 9 december 2022 @ 09:28:
Ongetwijfeld zal ik iets verkeerd doen, maar het is wel lastig debuggen als de oplossing wel perfect werkt op de testdata, maar het op de echte data niet blijkt te kloppen...

Beschouw de testdata als 1 van je tests om je code te valideren en maak zelf andere inputs voor (edge) cases terwijl je programmeert. Of doe het op de TDD manier. In de opdracht van vandaag zijn er namelijk cases die niet voorvallen in de testdata maar wel in de input.

[Xqlusive]

P_Tingen schreef op vrijdag 9 december 2022 @ 09:33:
[...]

Hier idem. Ik zit me nu af te vragen hoeveel tijd ik hier tegenaan moet gooien. Hou je rekening met negatieve coordinaten?

Naar mijn idee zou het ook moeten werken met negatieve coördinaten, maar ik zie nu dat dat niet in de testdata voorkomt. Misschien daar maar eens een testcase voor schrijven van.

Ghehe schreef op vrijdag 9 december 2022 @ 09:34:
[...]


Beschouw de testdata als 1 van je tests om je code te valideren en maak zelf andere inputs voor (edge) cases terwijl je programmeert. Of doe het op de TDD manier. In de opdracht van vandaag zijn er namelijk cases die niet voorvallen in de testdata maar wel in de input.

Check, laat ik beginnen met een testcase met negatieve coordinaten, waarschijnlijk gaat daar dan toch iets niet helemaal lekker.

[Janoz]

YoToP schreef op vrijdag 9 december 2022 @ 09:22:
Hah, ja ik had dus dit:

En dat terwijl de opdracht dit nog extra had toegelicht

Ik heb trouwens al mijn code weer ff gepushed. Mijn online repo liep nog een paar dagen achter.

dag 9

[Xqlusive]

Ok, fixed it! Er stond blijkbaar een haakje verkeerd bij een abs()... Nu deel 2

edit: toch mooi als deel 2 binnen 5 minuten is te implementeren omdat je iets meer moeite hebt genomen om classes generieker op te zetten

[ Voor 46% gewijzigd door Xqlusive op 09-12-2022 10:13 ]

[Litpho]

Wat tijd besteed aan het generiek krijgen van de functionaliteit tot ik er achter kwam dat arrays van verschillende sizes generiek meegeven nog niet gestabiliseerd is. Toen het eenmaal een Vec was geworden was het verder simpel.

dag 9

[FrankMennink]

Dag 9 in Python

Goed te doen, wel veel leeswerk (veel geblaat, weinig wol)

spoiler:

Deel 2 was toevoegen van een array van 10 posities om bij te houden ipv 2. De rest bleef redelijk hetzelfde. Vervolgens deel 1 ook in de code van deel 2 gestopt, Deel 1 is de positie van knoop 1. Kan waarschijnlijk een heel stuk sneller dan de brute force die ik nu heb, maar met 25ms vind ik t prima

[Janoz]

FrankMennink schreef op vrijdag 9 december 2022 @ 10:23:
Dag 9 in Python

Goed te doen, wel veel leeswerk (veel geblaat, weinig wol)

spoiler:

Deel 2 was toevoegen van een array van 10 posities om bij te houden ipv 2. De rest bleef redelijk hetzelfde. Vervolgens deel 1 ook in de code van deel 2 gestopt, Deel 1 is de positie van knoop 1. Kan waarschijnlijk een heel stuk sneller dan de brute force die ik nu heb, maar met 25ms vind ik t prima

spoiler:

Of deel 2 hetzelfde was is puur afhankelijk van de implementatie van deel 1. Zoals ook in de opdracht staat zijn er meer mogelijkheden. Als je daar niet (per ongeluk) rekening mee gehouden had was deel 2 een stuk lastiger geweest

Wel een leuke manier om deel 1 en 2 te combineren . Heb het gelijk maar ff voor mijn oplossing gejat

[ Voor 6% gewijzigd door Janoz op 09-12-2022 10:35 ]

[dcm360]

In deel 1 had ik dus een shortcut zitten waardoor met wat hergebruik de uitkomst van deel 2 subtiel anders werd (het voorbeeld zat de tail bij mij 1 keer 1 vakje anders).

spoiler:

En dit maar op de hack-manier opgelost, door de 2.000 instructies om te bouwen naar ruim 11.000 instructies met altijd afstand 1

[ Voor 3% gewijzigd door dcm360 op 09-12-2022 11:06 ]

[BernardV]

dcm360 schreef op vrijdag 9 december 2022 @ 11:05:
... (het voorbeeld zat de tail bij mij 1 keer 1 vakje anders)...

spoiler:

Had ik ook doordat ik een combinatie in een "if" deed van afstand x en afstand y, toen ik deze los van elkaar pakte ging het goed. Ergens halverwege ging tail "2" niet diagonaal maar naar rechts. In part 1 had ik daar geen last van.

[P_Tingen]

Wat de bloederige fuck ben ik voor een klootzak. Mijn programma was goed maar door een dyslectische aanval of een gebrek aan koffie draai ik twee cijfers om bij het ingeven van de oplossing. Het moest voor mij 3256 zijn en ik tik in 3265.

Geen wonder dat ik het niet kon vinden; het programma wás al goed

[MatHack]

P_Tingen schreef op vrijdag 9 december 2022 @ 11:16:
Wat de bloederige fuck ben ik voor een klootzak. Mijn programma was goed maar door een dyslectische aanval of een gebrek aan koffie draai ik twee cijfers om bij het ingeven van de oplossing. Het moest voor mij 3256 zijn en ik tik in 3265.

Geen wonder dat ik het niet kon vinden; het programma wás al goed

Gewoon copy/paste van de output van je oplossing naar de input op de website, toch...

[P_Tingen]

MatHack schreef op vrijdag 9 december 2022 @ 11:43:
[...]
Gewoon copy/paste van de output van je oplossing naar de input op de website, toch...

In hindsight: yes. Maar ja....

[CMG]

Oh jezus wat een dag 🤣

Had voor deel een iets heel slims uitgevonden, wat me daarna finaal in de knoop hielp.

spoiler:

Als tail out of bounds gaat, wordt positie head + negatief van de move die hij gedaan heeft

code | video deel 1 | video deel 2

[StefanLemmens]

Dag 9 Part 1 in LabVIEW

spoiler:

[TrailBlazer]

spoiler:

geen idee hoe maar blijkbaar kan er opeens tussen twee knopen 2 in de breedte en 2 in de hoogte verschil zitten. Toen ik dat gefix had werkte het allemaal
code nog even opschonen shitload aan debug er in

[KabouterSuper]

Ik voel inspiratie om een alternatieve Snake te maken. Ik heb Snake 2 op mijn Nokia (3310?) helemaal uitgespeeld, dus ik ben wel toe aan een versie waarbij de bewegingen anders gaan. Ben benieuwd of dit het spel moeilijker of makkelijker maakt (ik denk dat het wel prettig is om pas te kijken of je jezelf raakt nadat je klaar bent met een volledige move). Ik gok dat het moeilijker wordt, omdat je staart niet altijd een stap vooruit gaat, waardoor je niet achterlangs jezelf kunt lopen.
Voorbeeld als je 8 blokjes lang bent:
5678
4321
Als je bij Snake omhoog gaat:
6781
5432
Als je de AoC slang pakt:
567* (*=botsing van 1 met
432

Het is grappig dat je jezelf in 1 keer een rij op kunt laten schuiven
. . . 123456789
Doe nu een stap naar beneden:
. . . 23456789
. . 1
en dan een stap naar links:
. . . . . . . . . . .
. . 123456789

[armageddon_2k1]

Ik kon het toch niet laten, ben toch maar weer begonnen. De laatste dagen even ingehaald.

Vandaag Dag 9 in Kotlin. Easy peasy weer! En lekker compact.

spoiler:

Je kan hier mooi gebruik maken van de sign functie en het verschil van 2 vectors.

[armageddon_2k1]

CMG schreef op vrijdag 9 december 2022 @ 12:24:
Oh jezus wat een dag 🤣

Had voor deel een iets heel slims uitgevonden, wat me daarna finaal in de knoop hielp.

spoiler:

Als tail out of bounds gaat, wordt positie head + negatief van de move die hij gedaan heeft

code | video deel 1 | video deel 2

spoiler:

Welke bounds heb je nodig dan? Er zijn geen bounds?

[Gropah]

TrailBlazer schreef op vrijdag 9 december 2022 @ 13:24:

spoiler:

geen idee hoe maar blijkbaar kan er opeens tussen twee knopen 2 in de breedte en 2 in de hoogte verschil zitten. Toen ik dat gefix had werkte het allemaal
code nog even opschonen shitload aan debug er in

spoiler:

Door de keten kan de 2 breedte- en 2 hoogteverschil voorkomen.

Volgens mij is dit een minimale probleemstelling. Stel er liggen 3 delen diagonaal rechts naar boven. waarbij rechtsboven de kop is. Als die 1 naar rechts beweegt, beweegt het middenstuk 1 omhoog en 1 naar rechts.

[TrailBlazer]

Python Day 9
eigenlijk geen leuke opdracht vooral veel gedoe met indexen

[CMG]

armageddon_2k1 schreef op vrijdag 9 december 2022 @ 13:52:
[...]

spoiler:

Welke bounds heb je nodig dan? Er zijn geen bounds?

bounds, as-in niet meer horizontaal, verticaal of diagonaal verbonden

[Dricus]

armageddon_2k1 schreef op vrijdag 9 december 2022 @ 13:51:
Ik kon het toch niet laten, ben toch maar weer begonnen. De laatste dagen even ingehaald.

Vandaag Dag 9 in Kotlin. Easy peasy weer! En lekker compact.

spoiler:

Je kan hier mooi gebruik maken van de sign functie en het verschil van 2 vectors.

Oh nice, die kende ik nog niet! Dat scheelt weer 2 whens. Meteen toegepast in mijn oplossing:

Dag 9 - Kotlin

[Soultaker]

Nog wat extra grote inputs voor dag 9:

• aoc_2022_day09_large-1.zip (4.4 MB, 1M instructies); antwoorden eindigen op 673 en 518
• aoc_2022_day09_large-2.zip (44 MB, 10M instructies); antwoorden eindigen op 628 en 182

Mijn Python oplossing doet de eerste set in ongeveer 27 seconden. Mijn C++ oplossing (met absl::flat_hash_set) de eerste in ongeveer 5, en de tweede in 68 seconden. Dat kan vast beter

[ Voor 5% gewijzigd door Soultaker op 09-12-2022 14:47 ]

[DataGhost]

MatHack schreef op vrijdag 9 december 2022 @ 11:43:
[...]


Gewoon copy/paste van de output van je oplossing naar de input op de website, toch...

Dat is bij mij al vaak zat misgegaan omdat copy-on-select niet altijd werkte dus ik denk dat ik het dit jaar toch eindelijk maar eens in m'n framework bak. Hij haalt de testdata al volautomatisch op, dan mag het submitten ook wel toch?

[TrailBlazer]

FrankMennink schreef op vrijdag 9 december 2022 @ 10:23:
Dag 9 in Python

Goed te doen, wel veel leeswerk (veel geblaat, weinig wol)

spoiler:

Deel 2 was toevoegen van een array van 10 posities om bij te houden ipv 2. De rest bleef redelijk hetzelfde. Vervolgens deel 1 ook in de code van deel 2 gestopt, Deel 1 is de positie van knoop 1. Kan waarschijnlijk een heel stuk sneller dan de brute force die ik nu heb, maar met 25ms vind ik t prima

Ik heb exact dezelfde methode gekozen gewoon secuur war variabelen namen wijzigen was voldoende plus een case die bij deel 1 niet kon even meenemen.

[TrailBlazer]

Soultaker schreef op vrijdag 9 december 2022 @ 14:46:
Nog wat extra grote inputs voor dag 9:

• aoc_2022_day09_large-1.zip (4.4 MB, 1M instructies); antwoorden eindigen op 673 en 518
• aoc_2022_day09_large-2.zip (44 MB, 10M instructies); antwoorden eindigen op 628 en 182

Mijn Python oplossing doet de eerste set in ongeveer 27 seconden. Mijn C++ oplossing (met absl::flat_hash_set) de eerste in ongeveer 5, en de tweede in 68 seconden. Dat kan vast beter

spoiler:

waarom doe je nog Solve(2) die is ook al onderdeel van Solve(10) volgens mij

[CMG]

Soultaker schreef op vrijdag 9 december 2022 @ 14:46:
Nog wat extra grote inputs voor dag 9:

• aoc_2022_day09_large-1.zip (4.4 MB, 1M instructies); antwoorden eindigen op 673 en 518
• aoc_2022_day09_large-2.zip (44 MB, 10M instructies); antwoorden eindigen op 628 en 182

Mijn Python oplossing doet de eerste set in ongeveer 27 seconden. Mijn C++ oplossing (met absl::flat_hash_set) de eerste in ongeveer 5, en de tweede in 68 seconden. Dat kan vast beter

spoiler:

Tail visited 167327628 positions.
Tail visited 139740182 positions.
Code runtime: 00:03:15.0803628

[Soultaker]

TrailBlazer schreef op vrijdag 9 december 2022 @ 15:06:

spoiler:

waarom doe je nog Solve(2) die is ook al onderdeel van Solve(10) volgens mij

spoiler:

Klopt, je kan ze combineren, maar het leek niet veel snelheidswinst op te leveren. Voordeel is wel dat je dan de invoer niet hoeft te cachen. Ik heb het maar zo gelaten.

[gedonie]

Dag 9 in Java toch maar gedaan. Liep eerst tegen wat problemen aan bij deel 2 over het volgen van de verschillende knopen in het touw.

[ThaSandman]

Ik doe dit jaar ook mee met Ruby. Volgens het lijstje de enige dus zal binnenkort mijn code even naar een repo verplaatsen. Sneak preview van day 1, opdracht was natuurlijk niet erg moeilijk maar wel blij Ruby syntax.

spoiler: code

data = File.read('day1.txt')

result = data.split("\n\n").map do |elf|
elf.split("\n").map(&:to_i).sum
end

puts "result 1 #{result.max}"
puts "result 2 #{result.max(3).sum}"

[Jern_97]

Soultaker schreef op vrijdag 9 december 2022 @ 14:46:
Nog wat extra grote inputs voor dag 9:

• aoc_2022_day09_large-1.zip (4.4 MB, 1M instructies); antwoorden eindigen op 673 en 518
• aoc_2022_day09_large-2.zip (44 MB, 10M instructies); antwoorden eindigen op 628 en 182

Mijn Python oplossing doet de eerste set in ongeveer 27 seconden. Mijn C++ oplossing (met absl::flat_hash_set) de eerste in ongeveer 5, en de tweede in 68 seconden. Dat kan vast beter

Mijn antwoord voor deel 1 van input 1 eindigt op wel 672.
De rest komt overeen.

2.5s voor 1ste input
33s voor 2de input

https://github.com/Jeroen...022/blob/main/src/day9.rs

EDIT: bug fixed, finale posities werden niet meer gevoegd in hashset...

[ Voor 3% gewijzigd door Jern_97 op 09-12-2022 16:09 ]

[Janoz]

Nou, ik krijg in 13 seconden toch echt 673 uit deel 1. Een out of memory bij deel 2 trouwens

[MatHack]

Grote set:

spoiler:

Part1: 167327628
Part2: 139740182

Part1 in 46s 635,0306ms
Part2 in 82s 646,6539ms

Kan vast nog wel sneller in C#, maar ik ben tevreden over mijn huidige oplossing

[Soultaker]

Jern_97 schreef op vrijdag 9 december 2022 @ 15:39:
Mijn antwoord voor deel 1 van input 1 eindigt op wel 672.

Ik zie een bug in je code

(Overigens heb ik mijn C++ oplossing inmiddels geoptimaliseerd tot 2 resp. 24 seconde.)

[Litpho]

Large-1 in ongeveer 6 seconden, large 2 in 116 seconden. Ik ga er eens aan puzzelen of ik daar nog iets aan kan optimaliseren.

[Varienaja]

Soultaker schreef op vrijdag 9 december 2022 @ 14:46:
Nog wat extra grote inputs voor dag 9:

Met 4M input 9,6s voor part 1, 12s voor part 2.

spoiler:

Solution 09a: 16877673
Solution 09b: 14108518

Janoz schreef op vrijdag 9 december 2022 @ 15:43:
Nou, ik krijg in 13 seconden toch echt 673 uit deel 1. Een out of memory bij deel 2 trouwens

Met 44M input krijg ik ook een OOM...

Eens kijken wat ik er aan kan doen. :-)

Gatverpielekens ik kom tot 9M regels, dan komt de taskkiller van Linux mijn progje om zeep helpen.

[ Voor 49% gewijzigd door Varienaja op 09-12-2022 17:24 ]

[CMG]

Soultaker schreef op vrijdag 9 december 2022 @ 15:51:
[...]

Ik zie een bug in je code

(Overigens heb ik mijn C++ oplossing inmiddels geoptimaliseerd tot 2 resp. 24 seconde.)

Dat is wel serieus snel 😅 even gekeken; lezen van disk is 110ms, parsen rond de 1.3s (split op newline 😅) deel 1 in 79s, deel 2 109s

[joppybt]

Ik had vandaag een unieke ervaring.

Mijn code voor deel 1 aangepast voor deel 2 en deel 2 was de eerste run direct 100% correct voor beide testcases en mijn echte input. Dat is me nog nooit eerder gelukt.

[Jern_97]

Soultaker schreef op vrijdag 9 december 2022 @ 15:51:
[...]

Ik zie een bug in je code

(Overigens heb ik mijn C++ oplossing inmiddels geoptimaliseerd tot 2 resp. 24 seconde.)

Merci, heb bug gevonden en heb nog 1/3 van mijn rekentijd eraf kunnen snijden door deze hash implementatie te gebruiken ipv de default: https://crates.io/crates/fxhash

Kom nu op 22.5s ongeveer voor input 2 (Apple M1)

[dcm360]

De grote input wil op zich wel door mijn programma heen, maar dan wel met een rekentijd van 4 minuten en voor 18GB RAM. Grootste deel van de tijd lijkt de GC bezig te zijn, aangezien mijn eigen code single-threaded is en ik het grootste deel van de tijd meer cores belast zie worden.

[.oisyn]

@Soultaker Lol, nog even terugkomend op die transpose van de data van gisteren. Als ik met het per-tree-check-algo een buffer toevoeg waarin de data transposed is speciaal voor de up/down searches, dan ga ik van 95ms singlethreaded naar 100ms singlethreaded op het 2000x2000 grid. Ik had gehoopt dat het voor de up/down search wel wat sneller zou zijn ivm betere cache locality, maar in de regel heb je daar toch al niet zo'n last van (immers, als je vanaf (x, y) up/down gaat, dan raak je over het algemeen dezelfde cache lines als up/down vanaf (x+1, y) en (x-1, y)).

Maar goed, dit was niet het eindstation. Wat ik naartoe wilde waren searches met AVX2, want dan kan ik 32 bytes per keer checken. En om die up/down te doen heb ik getransposede data nodig.

En dat is uiteindelijk een flinke winst . Van 95ms singlethreaded in het origineel naar 45ms singlethreaded. De winst in multithreaded is in absolute zin natuurlijk kleiner, van 11ms naar 6ms. De transpose zelf kost me dan wel weer 1,2ms (multithreaded en AVX2 gather+swizzle)

(Het AVX2 gedeelte van de transpose was een leuke oefening. Ik lees van elke 8 opeenvolgende regels 4 bytes tegelijk middels een gather instructie, dan wat shuffles/permutes om de data te herrangschikken, en dan vervolgens 4 regels van 8 bytes wegschrijven. AVX2 kent helaas geen scatter, maar door een 4x8 rect om te zetten naar een 8x4 hou ik 4 losse writes van 64 bit ints over)

Dus ik kom uiteindelijk hierop:

===[ input.txt ]==========
Time: 281us (load:44us, transpose:132us, algo:104us)
1681
201684

===[ aoc_2022_day08_rect.txt ]==========
Time: 290us (load:41us, transpose:77us, algo:171us)
3319
672888

===[ aoc_2022_day08_sparse.txt ]==========
Time: 2004us (load:39us, transpose:483us, algo:1481us)
27476
32065007130

===[ input-mrhaas.txt ]==========
Time: 7530us (load:41us, transpose:1393us, algo:6095us)
32015
1720358640

[Soultaker]

Jern_97 schreef op vrijdag 9 december 2022 @ 16:55:
Merci, heb bug gevonden en heb nog 1/3 van mijn rekentijd eraf kunnen snijden door deze hash implementatie te gebruiken ipv de default: https://crates.io/crates/fxhash

Kom nu op 22.5s ongeveer voor input 2 (Apple M1)

Niet slecht! Single-threaded heb ik nog niet weten te verbeteren (ik zit nog rond de 24 s, maar eerder heb ik vastgesteld dat mijn CPU trager is dan die van jou, dus ik tel dit als een kleine winst ) maar ik heb een multithreaded implementatie die de grootste set in 9.6 seconde doet. Het is wel een interessant probleem om te proberen te parallelliseren.

dcm360 schreef op vrijdag 9 december 2022 @ 17:22:
De grote input wil op zich wel door mijn programma heen, maar dan wel met een rekentijd van 4 minuten en voor 18GB RAM. Grootste deel van de tijd lijkt de GC bezig te zijn, aangezien mijn eigen code single-threaded is en ik het grootste deel van de tijd meer cores belast zie worden.

Dat is ook een manier om meerdere cores te benutten. Ik had hetzelfde probleem met m'n Python oplossing op de large-2 set, behalve dat ik slechts 16 GB RAM heb dus hij crashte voordat 'ie klaar was.

.oisyn schreef op vrijdag 9 december 2022 @ 17:31:
En dat is uiteindelijk een flinke winst . Van 95ms singlethreaded in het origineel naar 45ms singlethreaded. De winst in multithreaded is in absolute zin natuurlijk kleiner, van 11ms naar 6ms. De transpose zelf kost me dan wel weer 1,2ms (multithreaded en AVX2 gather+swizzle)

Nice! Dat ga ik niet meer inhalen (ook omdat ik geen AVX kan).

[Visitor.q]

Yesss! Eindelijk tijd gehad tussen werk, sporten en kerstboom opbouwen om Day07 af te maken. Ik ben gestopt met de strategie om de subdir size te bepalen door recursief alle child dirs te evalueren en dan de sizes op te tellen. Dat ging ergens mis en ik weet niet waar. Wat ik nu heb gedaan is:

spoiler:

bij het toevoegen van een file de grootte óók recursief aan de parent folder(s) toekennen, en doodgewoon een platte lijstje gemaakt van alle Dir objecten. Die kun je dan heel makkelijk queryen.

Jammer dat ik daar nu pas aan denk maar ik denk dat mijn oorspronkelijke aanpak netter was geweest. Maar goed, omwille van de tijd doe ik dat later wel.

Ook geprobeerd om de pep8 wat beter aan te houden, ten minste het laag hangend fruit qua naamgeving en comments

Leuk, ik kijk uit naar 08, 09 en vandaag

Members only: Day 07 in Python

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[MatHack]

Soultaker schreef op vrijdag 9 december 2022 @ 18:15:
[...]

Dat is ook een manier om meerdere cores te benutten. Ik had hetzelfde probleem met m'n Python oplossing op de large-2 set, behalve dat ik slechts 16 GB RAM heb dus hij crashte voordat 'ie klaar was.

Heb je het hier over dag 9? Want zo geheugen intensief is dag 9 toch niet? Ik heb maar 8GB in de VM waar ik in zit te werken en had geen enkele geheugenprobleem met jouw grote set (10M lines) in C#.

[Jern_97]

Soultaker schreef op vrijdag 9 december 2022 @ 18:15:
[...]

Niet slecht! Single-threaded heb ik nog niet weten te verbeteren (ik zit nog rond de 24 s, maar eerder heb ik vastgesteld dat mijn CPU trager is dan die van jou, dus ik tel dit als een kleine winst ) maar ik heb een multithreaded implementatie die de grootste set in 9.6 seconde doet. Het is wel een interessant probleem om te proberen te parallelliseren.

Ja inderdaad, hardware maakt veel uit. Vreemd genoeg doet mijn 7950X er deze keer langer over dan M1 (30s vs 23s).
Toevallig zin om uit te leggen hoe je te werk gaat om dit probleem enigzins te parallelliseren?
Ik heb echt totaal geen idee...