Advent of Code 2022

[FrankMennink]

Dag 7 in Python

spoiler:

Hele tijd vast gezeten op deel 1, te laag. Ik had in mijn implementatie eerst alle foldernamen ansich als keys in de dictionary staan zonder hun parent folder erbij. Vele minuten later erachter gekomen dat een paar folders hetzelfde heten

Beide delen inc parsing in 0.9ms, ik ben tevreden Met de grote input nog wat dingen (onsuccesvol) geprobeerd, nu op 0.6ms

[ Voor 9% gewijzigd door FrankMennink op 07-12-2022 14:00 ]

[breew]

FrankMennink schreef op woensdag 7 december 2022 @ 10:08:
Dag 7 in Python

spoiler:

Hele tijd vast gezeten op deel 1, te laag. Ik had in mijn implementatie eerst alle foldernamen ansich als keys in de dictionary staan zonder hun parent folder erbij. Vele minuten later erachter gekomen dat een paar folders hetzelfde heten

Beide delen inc parsing in 0.9ms, ik ben tevreden

da's vast geen toeval... ik kwam ook al snel paths als

spoiler:

/dtcfhsm/tzhbztd/qtwnndbg/tnvlnmw/qtwnndbg/

tegen

[bakkerjangert]

FrankMennink schreef op woensdag 7 december 2022 @ 10:08:
Dag 7 in Python

spoiler:

Hele tijd vast gezeten op deel 1, te laag. Ik had in mijn implementatie eerst alle foldernamen ansich als keys in de dictionary staan zonder hun parent folder erbij. Vele minuten later erachter gekomen dat een paar folders hetzelfde heten

Beide delen inc parsing in 0.9ms, ik ben tevreden

Ik had exact dezelfde fout gemaakt; gelukkig leverde dit bij mij een foutmelding in code op en wist dus al dat er iets mis ging.

Mijn code in python.

[Diderikdm]

Dag 7 - Python

Hetzelfde issue als @FrankMennink en @bakkerjangert

spoiler:

Dacht dat ik met levels in de key names wel voldoende zou hebben afgevangen, maar bleek dat er toch dezelfde keys op dezelfde diepte lagen..

[ Voor 4% gewijzigd door Diderikdm op 08-12-2022 14:20 ]

[FrankMennink]

Blij om te zien dat ik niet de enige ben

[Remcoder]

spoiler:

MIjn enige fout was dat ik de folderSize op -1 initialiseerde, tenzij het een file was, om daarna de size te bepalen door de size van alle directories en files in de collectie bij de huidige size op te tellen.

Dan krijg je fijne off-by-ones die door cascaden. Mijn slaperige hoofd ging eerst de input nalopen of ik niet per ongeluk iets verkeerd gekopieerd had. Gelukkig begin ik altijd met de voorbeeld input, en niet met de echte input.

[P_Tingen]

Hier ging het eigenlijk in 1x goed, afgezien van wat tikfouten. Mijn grootste fout was dat ik een 0 te weinig had bij de controle op total size <= 100.000 en dus met 10.000 werkte

[CMG]

P_Tingen schreef op woensdag 7 december 2022 @ 11:03:
Hier ging het eigenlijk in 1x goed, afgezien van wat tikfouten. Mijn grootste fout was dat ik een 0 te weinig had bij de controle op total size <= 100.000 en dus met 10.000 werkte

ja, hier ook. Geen shortcuts genomen; enkel vergeten om .. te implementeren toen ik het de eerste keer runde en om de subdirs toe te voegen; toen ik dat gedaan had, was het eigenlijk allemaal goed.

spoiler:

Omdat ik ook al een dictionary met absolute paden bijhield, was deel 2 echt super makkelijk.

[breew]

CMG schreef op woensdag 7 december 2022 @ 11:33:
[...]

spoiler:

Omdat ik ook al een dictionary met absolute paden bijhield, was deel 2 echt super makkelijk.

die 'mazzel' had ik ook na part 1 had ik de volgende data.table. Part 2 is dan niet meer dan een simpel sommetje.

spoiler:

path filetotal
1: / 43956976
2: /dtcfhsm/ 19406820
3: /dtcfhsm/drjhjtm/ 3669401
4: /dtcfhsm/drjhjtm/cvrf/ 1544596
5: /dtcfhsm/drjhjtm/cvrf/tpwvvbh/ 870980
---
187: /hblzj/vmwddb/wpw/ 187278
188: /jbssdwf/ 31839
189: /ljv/ 270886
190: /nhp/ 76321
191: /nhp/sgffh/ 76321

[ Voor 56% gewijzigd door breew op 07-12-2022 11:50 ]

[CMG]

breew schreef op woensdag 7 december 2022 @ 11:34:
[...]

die 'mazzel' had ik ook..

Heb ook toen ik deel 2 moest doen

spoiler:

, die zelfde dict gebruikt om een pad/recursive size lijst op te bouwen; en daarna deel 1 aangepast dat hij die lookup weer gebruikt

zodat ik voor 1 en 2 het maar 1x hoef te doen.

[Soultaker]

Een extra uitdaging voor dag 7: aoc_2022_day07_deep.zip (5 MB). Hint: de correcte antwoorden zijn palindromen.

[MueR]

Dag 7 ook weer gedaan.. https://github.com/MueR/a...fCode2022/Day07/Day07.php

Kan vast nog wat optimaliseren, maar vind het eigenlijk wel prima.

[BernardV]

Soultaker schreef op woensdag 7 december 2022 @ 12:17:
Een extra uitdaging voor dag 7: aoc_2022_day07_deep.zip (5 MB). Hint: de correcte antwoorden zijn palindromen.

Dank je!

spoiler:

➜ day07 time php 1.php
Total size is: 7676767
php 1.php 0.48s user 0.09s system 97% cpu 0.587 total

➜ day07 time php 2.php
Folder size is: 28966982
php 2.php 0.48s user 0.09s system 97% cpu 0.589 total

Voor een PHP oplossing nog vlot genoeg.

spoiler:

Ik heb de tijd nog kunnen halveren, nu voor dit bestand voor zowel deel 1 als deel 2 ongeveer 250ms in PHP.
Ik sloeg de bestanden op en later gebruikte ik die weer om de size uit te rekenen, maar bij het parsen van de data kun je natuurlijk ook gelijk de size van de bestanden in de folder op folderniveau opslaan, immers heb je de bestanden zelf niet nodig.

[ Voor 23% gewijzigd door BernardV op 07-12-2022 13:12 ]

[FrankMennink]

Ik sla waarschijnlijk te veel op voor de grote set, memory use gaat >32GB en dan loopt alles vast

[CMG]

FrankMennink schreef op woensdag 7 december 2022 @ 13:22:
Ik sla waarschijnlijk te veel op voor de grote set, memory use gaat >32GB en dan loopt alles vast

Ik had 'm voor de lol ook gevoerd; maar kreeg stackoverflow op het uitrekenen van de sizes 😅

spoiler:

In principe hoef je de individuele files niet op te slaan maar gewoon de totale size bijhouden. Daarna, als alles geparsed is, van diepste naar boven vastleggen hoe groot je bent en dan maar 1 niveau diep kijken zodat je niet alles 1 miljoen keer opnieuw doet 😅

[Jern_97]

Soultaker schreef op woensdag 7 december 2022 @ 12:17:
Een extra uitdaging voor dag 7: aoc_2022_day07_deep.zip (5 MB). Hint: de correcte antwoorden zijn palindromen.

Ik heb hiervoor een extra parser moeten schrijven die niet recursief is, want kreeg stackoverflows (was waarschijnlijk de bedoeling van de input):

Time: 5204μs

spoiler:

Part 1: 7676767
Part 2: 28966982

Voor de originele input is de recursieve implementatie wel consistent sneller (22 vs 30μs).
Dat vind ik vreemd, ik zou verwachten dat de niet-recursieve manier altijd minstens even snel zou zijn (minder overhead + compiler heeft meer optimalisatie mogelijkheden?).

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

[ Voor 23% gewijzigd door Jern_97 op 07-12-2022 17:22 ]

[Camulos]

Hier ook quick & dirty voor dag 7 in C# https://github.com/flutte...tOfCode/Year2022/Day07.cs

spoiler:

Parsen zoals altijd duurde het langst.. en verder een recursieve tree-structure gebruikt, goed genoeg voor AoC.. maar zal toch wel wat improvements moeten maken om de extra lange input die @Soultaker aandraagt te kunnen verwerken

[MaNDaRK]

Hier ook eindelijk opgelost. De input van het voorbeeld werkte uitstekend, alleen de puzzle input niet...

spoiler:

Ik was vergeten om de parents ook de filesize mee te geven

Dag 7 - Python

[timvisee]

Dag 7: Snel en simpel. Minimale data, omdat losse bestanden of node namen niet nodig zijn.

Deel 1: 0.008ms (8.11 μs)
Deel 2: 0.011ms (11.40 μs)

Day 1 tot en met dag 7 totaal: 0.240 ms (0.122 ms parallel)

[CMG]

Soultaker schreef op woensdag 7 december 2022 @ 12:17:
Een extra uitdaging voor dag 7: aoc_2022_day07_deep.zip (5 MB). Hint: de correcte antwoorden zijn palindromen.

Code moeten omschrijven om niet recursief te werken, daarna werkt het; maar duurt 3m22s om te verwerken 😅

spoiler:

We matched 154 directories with a max size of 100000; total combined size: 7676767

Filesystem: 70.000.000
Required freespace: 30.000.000
Used: 68.966.772
Free: 1.033.228
Required: 28.966.772

Size of dir we need to delete: 28.966.982 (28966982)
Code runtime: 00:03:22.4451658

// Update; zag dat ik een stuk onnodig deed; code is nu een stuk sneller, maar duurt nog steeds 46s

We matched 154 directories with a max size of 100000; total combined size: 7676767

Filesystem: 70.000.000
Required freespace: 30.000.000
Used: 68.966.772
Free: 1.033.228
Required: 28.966.772

Size of dir we need to delete: 28.966.982 (28966982)
Code runtime: 00:00:46.9358198

[ Voor 34% gewijzigd door CMG op 07-12-2022 14:41 ]

[BernardV]

Dit is mijn code in PHP, ongeveer 250ms voor de 'deep' versie.
https://gist.github.com/B...258f17d9903b596991860881a

//EDIT: De GIST even bijgewerkt zodat Part 1 en 2 aanwezig zijn ipv alleen part 2.

[ Voor 25% gewijzigd door BernardV op 07-12-2022 15:04 ]

[gedonie]

Heb maar even tussendoor dag 7 gedaan in Java. Niet de meest snelle oplossing (18ms voor deel 1 en 27ms voor deel 2), maar werkt goed genoeg.

[MueR]

BernardV schreef op woensdag 7 december 2022 @ 14:43:
Dit is mijn code in PHP, ongeveer 250ms voor de 'deep' versie.
https://gist.github.com/B...258f17d9903b596991860881a

//EDIT: De GIST even bijgewerkt zodat Part 1 en 2 aanwezig zijn ipv alleen part 2.

Oh die is nasty.. wel verdraaid efficient. Netjes.

[.oisyn]

timvisee schreef op woensdag 7 december 2022 @ 14:18:
Dag 7: Snel en simpel. Minimale data, omdat losse bestanden of node namen niet nodig zijn.

Deel 1: 0.014ms (13.94 μs)

Deel 2: 0.017ms (17.49 μs)

Day 1 tot en met dag 7 totaal: 0.252 ms (0.122 ms parallel)

Volgens mij klopt je Day6b nog steeds niet. Heb een comment achtergelaten op github

[BernardV]

MueR schreef op woensdag 7 december 2022 @ 15:17:
[...]

Oh die is nasty.. wel verdraaid efficient. Netjes.

Dank je! Ik ga ook niet altijd voor 'schoonheid', soms is 'nasty' ook gewoon prima.

[Tubby]

gedonie schreef op woensdag 7 december 2022 @ 14:50:
Heb maar even tussendoor dag 7 gedaan in Java. Niet de meest snelle oplossing (18ms voor deel 1 en 27ms voor deel 2), maar werkt goed genoeg.

Ook in Java 6ms voor deel 1 en 4ms voor deel2, wel typisch dat de tweede sneller is dan de eerste.

[Camulos]

Soultaker schreef op woensdag 7 december 2022 @ 12:17:
Een extra uitdaging voor dag 7: aoc_2022_day07_deep.zip (5 MB). Hint: de correcte antwoorden zijn palindromen.

Na heel wat improvements binnen 250ms

spoiler:

Recursieve functies eruit gehaald, unieke namen toegevoegd voor nodes (directories), maar 1x over alle nodes heenlopen om de grootte te bepalen; tevens helper class even gesnoeid

Day07, part 1: 7676767
Day07, part 2: 28966982

Execution time was about 230ms

https://github.com/flutte...tOfCode/Year2022/Day07.cs

[dcm360]

Tubby schreef op woensdag 7 december 2022 @ 16:22:
[...]

Ook in Java 6ms voor deel 1 en 4ms voor deel2, wel typisch dat de tweede sneller is dan de eerste.

Welkom op de JVM zou ik maar zeggen. Mijn oplossing in Scala doet deel 1 in 17ms en deel 2 in 8ms, maar als ik daarna beiden nog een keer laat uitrekenen gaan ze beiden in 2,5ms. De JVM is sneller met uitvoeren van code als het al een keer eerder uitgevoerd is

[gedonie]

Tubby schreef op woensdag 7 december 2022 @ 16:22:
[...]

Ook in Java 6ms voor deel 1 en 4ms voor deel2, wel typisch dat de tweede sneller is dan de eerste.

Ik heb zojuist ook even gekeken of ik hem sneller kon krijgen. Heb nu ook nog een iets geoptimaliseerde versie geschreven die het binnen 7ms doet.

[TrailBlazer]

Dag 7 in Python

spoiler:

waarschijnlijk nodeloos complex want ik heb een class gemaakt voor elke folder met daarin de files en de referentie naar de subfolders. Ik ben geen held in alles met minimale var names direct in een list van hashes met daarin tuples etc te modeleren.
Wel blij dat ik mijn recursive function in een keer goed had twee jaar geleden liep ik vast op die tassen met tassen er in dit is feitelijk hetzelfde.

[Tubby]

dcm360 schreef op woensdag 7 december 2022 @ 17:12:
[...]

Welkom op de JVM zou ik maar zeggen. Mijn oplossing in Scala doet deel 1 in 17ms en deel 2 in 8ms, maar als ik daarna beiden nog een keer laat uitrekenen gaan ze beiden in 2,5ms. De JVM is sneller met uitvoeren van code als het al een keer eerder uitgevoerd is

Ja, dus eigenlijk moeten we het met spring-boot 3.0 AOT compilen naar een native executable zeg je?

[dcm360]

Vorig jaar heb ik mijn code zowel op de JVM uitgevoerd als ook door Graal Native Image en Scala Native laten compilen. Het was vooral veel wachten op de compiler voor een performancewinst die zich het beste laat beschrijven als gerommel in de marge. Op de wat complexere puzzels krijgt de JVM het toch ook wel vrij vlot richting optimaal.

[timvisee]

Soultaker schreef op woensdag 7 december 2022 @ 12:17:
Een extra uitdaging voor dag 7: aoc_2022_day07_deep.zip (5 MB). Hint: de correcte antwoorden zijn palindromen.

Leuk! Met een grotere stack size voor part 2:

Deel 1: 4.21 ms
Deel 2: 11.40 ms

Ditmaal wel met de goede resultaten

spoiler:

7676767
28966982

Heb je nog een grotere?

[ Voor 6% gewijzigd door timvisee op 07-12-2022 18:43 ]

[Cranzai]

Over-engineered, misschien?
Maar wel weer een goeie kans om mijn toolkit

spoiler:

OOP trees en recursion

weer een beetje bij te spijkeren, vorig jaar voor het eerst mee gespeeld in AoC en daarna nog niet veel weer gebruikt...
Uiteindelijk een mooie oplossing neergeklad al zeg ik het zelf:
https://github.com/Cranza...b/main/2022/day07/day7.py

[Cranzai]

Soultaker schreef op woensdag 7 december 2022 @ 12:17:
Een extra uitdaging voor dag 7: aoc_2022_day07_deep.zip (5 MB). Hint: de correcte antwoorden zijn palindromen.

"Maximum recursion depth exceeded"
F*ck

code:

import sys
sys.setrecursionlimit(1000000)

Succes

A:
real 0m1.267s
user 0m1.161s
sys 0m0.100s

B:
real 0m1.285s
user 0m1.177s
sys 0m0.102s

A en B tegelijk:
real 0m1.326s
user 0m1.228s
sys 0m0.091s

Meeste tijd zal dus zitten in het bouwen van mijn tree en het bepalen van de grootte van alle folders, daarna lekker vlot

[Soultaker]

timvisee schreef op woensdag 7 december 2022 @ 18:33:
Heb je nog een grotere?

Nou vooruit!

Een extra diepe: aoc_2022_day07_deep-2.txt.zst (62 MB ingepakt, 189 MB uitgepakt), of aoc_2022_day07_deep-2.zip, (74 MB ingepakt). Geen mooie antwoorden, maar de som van de antwoorden van deel 1 en 2 is 411477448.

En een andere, waarbij de nadruk meer op parsing ligt: (43 MB ingepakt, 142 MB uitgepakt):
aoc_2022_day07_large.txt.zst, of aoc_2022_day07_large.zip (49 MB ingepakt). Som van de antwoorden is 1031118791.

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

[Creepy]

Luie devver (die teveel heeft getypt voor dag 7) meld zich weer

spoiler:

Boom opbouwen met een minimale stack based parser, vervolgens recursief de boom door om alle grootte's te bereken, en daarna voor dag 1 filteren en tellen, en voor dag 2 de minimale grootte bijhouden terwijl we recursief door de boom gaan.

Ooit, als ik minder lui ben en tijd wil vrijmaken nog eens kijken of we zonder recursie de boel kunnen oplossen.

Ik kwam wel goed weg met het feit dat er niet een "cd /" midden in de input ergens staan. Die lijkt alleen maar aan het begin te staan.

https://github.com/CodeEn...er/aoc/aoc2022/Day07.java

En waar moet ik zijn om zst's uit te pakken? Speciaal nog 7zip bijgewerkt maar die heeft er dan nog steeds geen zin in?

[ Voor 29% gewijzigd door Creepy op 07-12-2022 21:14 ]

[Soultaker]

Creepy schreef op woensdag 7 december 2022 @ 20:54:
En waar moet ik zijn om zst's uit te pakken? Speciaal nog 7zip bijgewerkt maar die heeft er dan nog steeds geen zin in?

De officiële zstd releases staan hier: https://github.com/facebook/zstd/releases/tag/v1.5.2

Er is ook een 7-zip clone met zstd support en anders PeaZip.

edit:
Ik wil m'n testdata ook wel met zip inpakken als mensen dat liever hebben. Maar ik zag anderen zstd data aanleveren zonder dat daar commentaar op kwam, en aangezien ik zelf ook fan ben van zstd omdat het een superieur compressie-algoritme is, dacht ik dat ik er wel mee weg kon komen om bestanden in .zst-formaat te uploaden.

[ Voor 25% gewijzigd door Soultaker op 07-12-2022 21:03 ]

[Creepy]

Ik heb de afgelopen dagen de moeite niet genomen om naast 7zip nog een andere util te installeren en daardoor ook niks gedaan met extra uitdagende inputs. Morgen heb ik wel wat extra tijd dus dan denk ik dat ik wel een poging waag om wat algoritmes te gaan optimaliseren. Ik kende zst nog helemaal niet en ben gewend dat 7zip zo'n beetje alles uitpakt wat je er tegenaan gooit, maar dit dus niet. Maar van mij hoef je het niet anders aan te leveren hoor.

[Soultaker]

Creepy schreef op woensdag 7 december 2022 @ 21:11:
Ik kende zst nog helemaal niet en ben gewend dat 7zip zo'n beetje alles uitpakt wat je er tegenaan gooit, maar dit dus niet. Maar van mij hoef je het niet anders aan te leveren hoor.

Zoveel moeite is het ook weer niet. Maar los eerst deze data set maar eens op.

edit:
Ik heb de zipfiles hier toegevoegd.

[ Voor 12% gewijzigd door Soultaker op 07-12-2022 21:30 ]

[TrailBlazer]

spoiler:

Ik moet wel zeggen dat de input heel erg clean is. Geen directories die twee keer bezocht worden. Niet terug naar start door een een cd /. Geen missende subdirectories oid

[Soultaker]

TrailBlazer schreef op woensdag 7 december 2022 @ 21:28:

spoiler:

Ik moet wel zeggen dat de input heel erg clean is. Geen directories die twee keer bezocht worden. Niet terug naar start door een een cd /. Geen missende subdirectories oid

Ja, dat viel mij ook op. Dat is wel vaker zo bij AoC: de probleembeschrijving laat vaak allerlei corner cases toe die in de praktijk niet voorkomen (mijn deep invoer is daar ook een voorbeeld van).

In een van mijn extra test sets heb ik expres wel een

spoiler:

"cd /" toegevoegd

. Dat er geen subdirectories missen snap ik wel, want dan zou het ongedefinieerd zijn wat de grootte van een directory is (al zou je subdirectories weg kunnen laten voor directories die toch al te groot zijn om irrelevant te zijn voor deel 1 of deel 2).

En inderdaad, je zou ook directories opnieuw kunnen bezoeken (cd /, cd foo, cd bar, ls, cd /, cd foo, cd baz, ls) of zelfs dubbele directory listings toevoegen. Ik heb daar wel aan gedacht en er op z'n minst een assert voor toegevoegd; veel andere oplossingen gaan denk ik de mist in.

[MueR]

BernardV schreef op woensdag 7 december 2022 @ 16:17:
[...]

Dank je! Ik ga ook niet altijd voor 'schoonheid', soms is 'nasty' ook gewoon prima.

Ja dat is. Mijn oplossing was te "mooi" zeg maar.

[.oisyn]

timvisee schreef op woensdag 7 december 2022 @ 18:33:
[...]


Leuk! Met een grotere stack size voor part 2:

Deel 1: 4.21 ms
Deel 2: 11.40 ms

Ditmaal wel met de goede resultaten

spoiler:

7676767
28966982

Heb je nog een grotere?

Ik vertrouw jouw timings niet (nvm, een lokale timing met mijn input komt wel redelijk overeen. Ben wel verbaasd over de optimale code die Rust genereert ). Je code op github geeft een stack overflow met Soultaker's input. Kun je een nieuwe pushen?

[ Voor 9% gewijzigd door .oisyn op 08-12-2022 00:29 ]

[.oisyn]

Ik heb geen aparte timings voor deel 1 en 2.

==[ input.txt ]==========
Time: 23us (Parse: 22us)
1334506
7421137

==[ aoc_2022_day07_deep.txt ]==========
Time: 4192us (Parse: 4121us)
7676767
28966982

==[ aoc_2022_day07_deep-2.txt ]==========
Time: 155781us (Parse: 153570us)
386487535
24989913

==[ aoc_2022_day07_large.txt ]==========
Time: 120086us (Parse: 118667us)
979898913
51219878

https://github.com/oisyn/...ter/Problem7/Problem7.cpp

spoiler:

Ik support hier alleen de extra cd / omdat dat nodig was voor aoc_2022_day07_large.txt . Gelukkig gaat ie daarna een dir in die nog niet eerder was gevisit, want dat ondersteun ik niet

.

.edit: een behoorlijke optimize deelt de tijd bijna door 2

[ Voor 33% gewijzigd door .oisyn op 08-12-2022 00:42 ]

[Swedish Clown]

Dag 7 in Erlang

Kan vast sneller maar vind het wel prima zo. Code is in ieder geval gemakkelijk te volgen

[BernardV]

Soultaker schreef op woensdag 7 december 2022 @ 20:33:
[...]


Nou vooruit!

Een extra diepe: aoc_2022_day07_deep-2.txt.zst (62 MB ingepakt, 189 MB uitgepakt), of aoc_2022_day07_deep-2.zip, (74 MB ingepakt). Geen mooie antwoorden, maar de som van de antwoorden van deel 1 en 2 is 411477448.

En een andere, waarbij de nadruk meer op parsing ligt: (43 MB ingepakt, 142 MB uitgepakt):
aoc_2022_day07_large.txt.zst, of aoc_2022_day07_large.zip (49 MB ingepakt). Som van de antwoorden is 1031118791.

deep-2:

code:

Part 1: 386487535
Part 2: 24989913
Total execution time in milliseconds: 33687.45303154

Met de PHP code dus ongeveer 34 seconden

Large:

code:

Notice: Undefined index: ##size## in /Volumes/Data/aoc/2022/day07/combined.php on line 31

Notice: Undefined index: ##size## in /Volumes/Data/aoc/2022/day07/combined.php on line 31
Part 1: 979898913
Part 2: 51219878
Total execution time in milliseconds: 32006.18314743

Het resultaat klopt in 32 sec, maar ik mis blijkbaar iets waardoor die Notice ontstaat. Ga er nu geen tijd aan besteden, maar dat is wel iets wat ik ga bekijken.

//EDIT: Deze timing is op een 7 jaar oude MBP i5 dus kan zeker sneller ;-)

[Jern_97]

Soultaker schreef op woensdag 7 december 2022 @ 20:33:
[...]


Nou vooruit!

Een extra diepe: aoc_2022_day07_deep-2.txt.zst (62 MB ingepakt, 189 MB uitgepakt), of aoc_2022_day07_deep-2.zip, (74 MB ingepakt). Geen mooie antwoorden, maar de som van de antwoorden van deel 1 en 2 is 411477448.

En een andere, waarbij de nadruk meer op parsing ligt: (43 MB ingepakt, 142 MB uitgepakt):
aoc_2022_day07_large.txt.zst, of aoc_2022_day07_large.zip (49 MB ingepakt). Som van de antwoorden is 1031118791.

~250ms voor elk van de nieuwe instanties

[jmerle]

Dag 8 in Python

spoiler:

Deel 1 was redelijk te doen vandaag, maar op deel 2 ben ik een hoop tijd verloren met onnodig complexe code en omgedraaide minder dan/groter dan tekens.

[Janoz]

@jmerle

spoiler:

Ik moest mijn eerste implementatie naar /dev/null sturen omdat ik even helemaal geen rekening gehouden had met dat dezelfde boom van meerdere kanten te zien is. Vervolgens maar de naïve benadering gekozen die me vervolgens bij stap twee flink geholpen heeft

[bakkerjangert]

Leuke opdracht vandaag. Mijn code in python.

spoiler:

Wel een tijdje bezig geweest met deel 2; te snel gelezen en iets geprogrammeerd waarvan ik dacht dat dat gevraagd werd (terwijl de omschrijving zeer helder is ). Door de subtiele verschillen tussen deel 1 en deel 2 kon ik niet veel hergebruiken.

[Gropah]

spoiler:

Ik wou te fancy doen en tussen resultaten voor visibility cachen. Dit omdat ik verwachtte dat part 2 daar weer gebruik van zou maken. Na daar te lang mee te kloten, er maar voor gekozen om het dom te implementeren en toen was het best prima te doen.

note to self: niet altijd te fancy willen doen en ook niet proberen vooruit te denken

[ Voor 14% gewijzigd door Gropah op 08-12-2022 08:25 ]

[MatHack]

Dag 8 in C#

Deel1: 24ms
Deel2: 10ms

Later maar eens kijken of ik de code nog beter/netter kan maken.

spoiler:

Ik had het geluk dat ik bijna alle code van deel 1 kon hergebruiken voor deel 2, moest alleen de berekening voor een zichtslijn bouwen. Vooral veel tijd versplit aan: heb ik nou de goede afmeting (hoogte/breedte), achteraf gezien is het grid dezelfde hoogte als breedte
Vraag me achteraf ook af of het nou slim was om een 1-dimensie array te gebruiken ipv een 2-dimensies array...

[ Voor 22% gewijzigd door MatHack op 08-12-2022 09:13 ]

[Diderikdm]

Quick and dirty, maar wel een leuke puzzel!

Dag 8 - Python

[ Voor 10% gewijzigd door Diderikdm op 08-12-2022 14:19 ]

[Camulos]

spoiler:

Moest behoorlijk wat code kloppen om alle kanten op te lopen.
Net als @Janoz had ik in het begin wat bomen dubbel geteld

Ik vraag me of hoe dit efficienter gecode kan worden, behalve letterlijk door alle bomen (X*Y), en dan alle kanten op te lopen met early stop -> ~ 0,5 * ( X+Y) stappen, dus ongeveer op 100 (rij) * 100 (kolom) * (0-200 stappen) = ~ 1M stappen

Niet de mooiste code, maar wel lekker snel

C# Day 08

[P_Tingen]

Ook hier weer voordeel van in-memory database tabellen (a.k.a Temp-Tables) in Progress 4GL.

De grid ingelezen in een tabel met indexen op de X en Y coordinaat. Die code had ik vorig jaar al in mijn toolbox gegooid omdat we vaker grids inlezen, dus dat was simpel. Vanaf daar is het een kwestie van een paar FIND FIRST of FIND LAST statements en de resultaten optellen.

spoiler:

Deel 1 kon volledig worden herbruikt voor deel 2 door deze opzet, ik had alleen verwacht dat in het tweede deel ook de diagonale zichtlijnen erbij zouden komen. Gelukkig heb ik door schade en schande al afgeleerd om in deel 1 rekening te houden met wat er misschien in deel 2 aan zit te komen

https://github.com/patric...e/tree/master/2022/Day-08

[.oisyn]

Camulos schreef op donderdag 8 december 2022 @ 09:29:

spoiler:

Moest behoorlijk wat code kloppen om alle kanten op te lopen.
Net als @Janoz had ik in het begin wat bomen dubbel geteld

Ik vraag me of hoe dit efficienter gecode kan worden, behalve letterlijk door alle bomen (X*Y), en dan alle kanten op te lopen met early stop -> ~ 0,5 * ( X+Y) stappen, dus ongeveer op 100 (rij) * 100 (kolom) * (0-200 stappen) = ~ 1M stappen

Niet de mooiste code, maar wel lekker snel

C# Day 08

spoiler:

Een 100x100 grid kan volgens mij in maximaal 2x100x100 stappen? In ieder geval in maximaal 4x100x100

.edit: ja ben vrij zeker dat het in 2x100x100 kan. Al denk ik wel dat de loop daardoor gecompliceerder wordt waardoor 4x100x100 alsnog sneller is.

[ Voor 10% gewijzigd door .oisyn op 08-12-2022 10:20 ]

[CMG]

Poeh, vandaag meer dan een uur bezig geweest doordat lezen toch moeilijker is dan gedacht 🤣C# code (niet refactored, geen schoonheidsprijs)

[Remcoder]

Ik heb het nog best leesbaar opgelost, mede doordat ik in mijn library een grid en coordinaat implementatie heb gemaakt die hier heel nuttig toegepast kan worden.

[tarlitz]

Oef, ik had echt een hele dikke faaldag. Dit was de eerste keer dat ik hem niet in 1x goed had.

spoiler:

Deel 1 zat ik onnodig de randen te checken en dit leidde tot een grote rabbit hole om meer over pattern matching te leren en debuggen, terwijl dit gewoon met de general case meekon.

Deel 2 totaal verkeerd gelezen.

spoiler:

Ik dacht dat je na een grote boom geen kleinere boom meer kon zien, maar je kon sowieso alle kleinere bomen zien tot de eerste grotere boom.🤦 Eerst was ik vergeten dat je vanuit de boom kijkt waardoor ik mijn lijst moest reversen. Ik had wel steeds het voorbeeld goed, dus beetje frustrerend.

Achteraf was de opdracht best goed te doen 😅

[ Voor 12% gewijzigd door tarlitz op 08-12-2022 10:36 ]

[BernardV]

Leuke opdracht!

spoiler:

Ik heb de grid ingelezen daarna een kopie gemaakt en die 90 graden gedraaid, in PHP makkelijk te doen door:

array_unshift($input, null);
$input = call_user_func_array('array_map', $input);

Als je die beiden hebt is het makkelijk een slice te pakken alle kanten op.

[Jern_97]

~650μs voor parsing + part 1 + part 2

[.oisyn]

Dit is wel een leuke waarbij we veel uiteenlopende tijden gaan zien bij grotere grids. Zowel in algoritmische complexiteit als parallelliseerbaarheid. Gaan we ook een gpgpu-oplossing zien?

[TrailBlazer]

spoiler:

Ik ben nu gegaan voor een oplossing om gewoon boom voor boom af te gaan en met behulp van numpy de rijen/kolommen te checken. Benieuwd of er een slimmer algoritme is

[MrHaas]

Hier een 2000x2000 grid. M'n originele doet er heel lang over, m'n verbeterde oplossing doet 'm in 11s, daar kan ws nog heel wat van af.

[Soultaker]

Dag 8: ik heb gelijk maar het optimale O(H×W) algoritme geïmplementeerd (Python code).

Doet de officiële invoer in ongeveer 100 ms.

MrHaas schreef op donderdag 8 december 2022 @ 11:19:
Hier een 2000x2000 grid.

spoiler:

32015
1720358640

Klopt dat?

5.6s met Pypy, 25s met CPython. Het blijft wel Python hè. Ik zal m'n algo eens naar C porten, dan gaat het fast een stuk rapper.

[MrHaas]

Soultaker schreef op donderdag 8 december 2022 @ 11:30:
Dag 8: ik heb gelijk maar het optimale O(H×W) algoritme geïmplementeerd (Python code).

Doet de officiële invoer in ongeveer 100 ms.


[...]

spoiler:

32015
1720358640

Klopt dat?

5.6s met Pypy, 25s met CPython. Het blijft wel Python hè. Ik zal m'n algo eens naar C porten, dan gaat het fast een stuk rapper.

spoiler:

Yes, althans, ik heb hetzelfde er uit .

Mijn oplossing doet het met PyPy in 1.5s. Deel 1 hebben we wel ongeveer hetzelfde opgelost maar deel 2 heb ik volgens mij net wat andere approach: ik loop door elke rij en houd per rij bij wanneer ik een bepaalde hoogte voor het laatste gezien heb. Score voor huidige cel is dan huidige index - (max van de laast geziene hoogtes >= huidige hoogte).

[ Voor 22% gewijzigd door MrHaas op 08-12-2022 11:40 ]

[Soultaker]

MrHaas schreef op donderdag 8 december 2022 @ 11:36:

spoiler:

Deel 1 hebben we wel ongeveer hetzelfde opgelost maar deel 2 heb ik volgens mij net wat andere approach: ik loop door elke rij en houd per rij bij wanneer ik een bepaalde hoogte voor het laatste gezien heb.

Ah ja, je haalt effectief deze buitenste for-loop naar binnen (en in plaats van "n = n + 1" totdat je een boom tegenkomt doe je inderdaad een aftrekking wat vermoedelijk iets efficiënter is). Daarmee zijn de algoritmen feitelijk wel equivalent.

De enige reden dat jouw oplossing iets trager is komt denk ik door de generators. Ik was ook zo begonnen tot ik me besefte

spoiler:

dat ik in beide delen altijd volledig over alle lijnen heenloop, dus dan kun je die coördinaten net zo goed direct in een lijst gooienr

.

[FrankMennink]

Dag 8 in Python

spoiler:

Deel 1 redelijk brute force aangepakt. Voor deel 2 wel de aanname gemaakt dat we alleen de zichtbare bomen die niet op de rand zitten kunnen pakken omdat de rest zeer waarschijnlijk toch lager is. Erg moeilijk om een hoog nummer in 2+ richtingen te krijgen als je niet zichtbaar bent. Zijn wel cases voor te bedenken, rand 0, rand daarbinnen 9, dan allemaal 0 en middelste punt 9, dus perfect is de code niet. Kan makkelijk aangepast worden door wel alle bomen te checken, maar zoals vaker bij AoC, het goede antwoord komt er uit dus is t goed genoeg

Voor de grote set mn "optimalisatie" er uit moeten gooien.

1.9s voor deel 1, 8.8s voor deel 2

[ Voor 7% gewijzigd door FrankMennink op 08-12-2022 12:06 ]

[Creepy]

.oisyn schreef op donderdag 8 december 2022 @ 10:57:
Gaan we ook een gpgpu-oplossing zien?

Nou, maak die eens dan?

Anyway, hier ook weer een straightforward oplossing.

spoiler:

Voor deel 1 een ray casten in 4 richtigen en kijken of we het einde van de map halen. En deel 2 eigenlijk hetzelfde en dan niet vergeten dat als je het einde van de map haalt je score 1 te hoog is.....

https://github.com/CodeEn...er/aoc/aoc2022/Day08.java

[Soultaker]

Hier nog twee challenges (niet puur op grootte):

• aoc_2022_day08_rect.txt (55 KB); antwoorden eindigen met "19" en "88".
• aoc_2022_day08_sparse.txt (1 MB); antwoorden eindigen met "76" en "30".

[Remcoder]

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

• aoc_2022_day08_rect.txt (55 KB); antwoorden eindigen met "19" en "88".
• aoc_2022_day08_sparse.txt (1 MB); antwoorden eindigen met "76" en "30".

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...

[Marcj]

Dag 8 ook in Kotlin opgelost. Hier was best wel wat optimalisatie mogelijk. Als je meer uitleg wilt hebben waarom het eigenlijk werkt moet ik meer gaan schrijven denk ik. De officiële invoer gaat in 9ms.

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

• aoc_2022_day08_rect.txt (55 KB); antwoorden eindigen met "19" en "88".
• aoc_2022_day08_sparse.txt (1 MB); antwoorden eindigen met "76" en "30".

De rechthoek gaat in 20ms en de sparse in 100ms. Nog best vlot volgens mij.

MrHaas schreef op donderdag 8 december 2022 @ 11:19:
Hier een 2000x2000 grid. M'n originele doet er heel lang over, m'n verbeterde oplossing doet 'm in 11s, daar kan ws nog heel wat van af.

Deze doet mijn programma nu in 350ms. Snel zat denk ik

[Brilsmurfffje]

Vandaag weer een belangrijk lesje gehad in het belang het juiste datatype gebruiken voor de data die je aan het verwerken bent, voor het initiele probleem netjes een int8 gedefineerd in numpy. Deze code gekopieerd naar het volledige probleem en er na enkele uren achter gekomen dat dat de reden is waarom mijn max bij part2 128 is

Oplost met Python en numpy voor leesbare code:

spoiler:

[code]
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)).astype(np.int32)

def view_distance(array, num):
if array.size == 0:
return 0
distance = 0
for i in array:
if i < num:
distance += 1
elif i >= num:
distance += 1
break
return distance

for (x,y), tree in np.ndenumerate(forrest):
# look left, right, up and down
tree_lines = np.array([
view_distance(np.flip(forrest[x,:y]), tree),
view_distance(forrest[x,y+1:], tree),
view_distance(np.flip(forrest[:x,y]), tree),
view_distance(forrest[x+1:,y], tree)
])
# minimal line of sight lower than tree to be visible
if np.prod(tree_lines) <= -1:
pass
visible[x,y] = np.prod(tree_lines)

print(np.max(visible))
[/]

[timvisee]

.oisyn schreef op woensdag 7 december 2022 @ 22:41:
[...]


Ik vertrouw jouw timings niet (nvm, een lokale timing met mijn input komt wel redelijk overeen. Ben wel verbaasd over de optimale code die Rust genereert ). Je code op github geeft een stack overflow met Soultaker's input. Kun je een nieuwe pushen?

Nouzeg!

Klopt. Ik heb simpelweg de stacksize vergroot (`ulimit -s unlimited`) en dan draait het zonder problemen. Quite common voor programmeerpuzzels voor zover ik weet. Gister had ik niet de energie om een recursiveless versie te schrijven.

Ja, Rust doet het aardig goed als het gaat om efficiënte binaries bakken (zie). De strictness van de typesystem en de LLVM backend helpen.

Erg strakke timings overigens, netjes gedaan. Kudos!

[MatHack]

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

• aoc_2022_day08_rect.txt (55 KB); antwoorden eindigen met "19" en "88".
• aoc_2022_day08_sparse.txt (1 MB); antwoorden eindigen met "76" en "30".

Mijn originele oplossing werkte meteen voor de rect versie, niet de beste tijd schat ik (C#):

Deel 1 in 359,0773ms
Deel 2 in 196,1369ms

spoiler: oplossingen rect

Deel 1: 3319
Deel 2: 672888

[.oisyn]

timvisee schreef op donderdag 8 december 2022 @ 13:18:
Ja, Rust doet het aardig goed als het gaat om efficiënte binaries bakken (zie). De strictness van de typesystem en de LLVM backend helpen.

Ik ben zelf sinds kort lead dev op rust-gpu, ik weet hoe gecompliceerd de codestructuur is die uit de Rust front-end komt rollen met allerlei loops met iterators, want daar hebben we een hele kluif aan om dat efficient om te zetten naar loops voor de GPU. Ik weet dat LLVM daar wel goed raad mee weet, maar de performance verbaast me alsnog

[Camulos]

MatHack schreef op donderdag 8 december 2022 @ 13:21:
Mijn originele oplossing werkte meteen voor de rect versie, niet de beste tijd schat ik (C#):
Deel 1 in 359,0773ms
Deel 2 in 196,1369ms

spoiler:

Oef daar heeft je CPU goed op zitten kraken
Hier zelfde antwoorden! behalve dan in 12ms in C#

Heb je initieel voor Dag 8 in AoC naive aanpak gebruikt?

[MatHack]

Camulos schreef op donderdag 8 december 2022 @ 13:28:
[...]

spoiler:

Oef daar heeft je CPU goed op zitten kraken
Hier zelfde antwoorden! behalve dan in 12ms in C#

Heb je initieel voor Dag 8 in AoC naive aanpak gebruikt?

Het is in een VM, dus dat zal niet helpen. Daarnaast is mijn code zeker niet geweldig... Zijn nog genoeg mogelijkheden om te optimaliseren.

spoiler:

Ik vermoed dat de grote hoeveelheid array splices niet helpen.

[Jolijter]

Ik heb het naïef aangepakt, voor de AoC input is dat vooralsnog vlot genoeg (<40ms per test).

Members only:

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

[gedonie]

Moest wel goed opletten vandaag, maar toch dag 8 in Java opgelost.

spoiler:

Eerste deel was zo gedaan, maar bij het 2de deel had ik eerst niet goed opgelet dat er tussen jou en de hoogste boom een richting op nog een boom kon staan die minder hoog als de hoogste was, maar hoger of gelijk aan hoogte aan jou.

[Jern_97]

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

• aoc_2022_day08_rect.txt (55 KB); antwoorden eindigen met "19" en "88".
• aoc_2022_day08_sparse.txt (1 MB); antwoorden eindigen met "76" en "30".

rect: 3.6ms
sparse: 55ms

MrHaas schreef op donderdag 8 december 2022 @ 11:19:
Hier een 2000x2000 grid. M'n originele doet er heel lang over, m'n verbeterde oplossing doet 'm in 11s, daar kan ws nog heel wat van af.

Deze gaat in 250ms

https://github.com/JeroenGar/advent_of_code_2022/blob/main/src/day8.rs
Moet nog eens nadenken om de code wat compacter te schrijven

Zijn er btw nog mensen die gretig gebruik maken van Github Copilot? Het versnelt bij mij het programmeerwerk zeer significant. Zeker bij een opdracht met als die van vandaag.

[ Voor 6% gewijzigd door Jern_97 op 08-12-2022 13:52 ]

[breew]

Dag 8 in R

zo dan.. dit was even pielen. de eerste echte puzzel-dag (voor mij althans).. Duurde even voordat ik de uitleg in mijn hoofd kon vertalen naar een werkende aanvliegroute. Wel leuk, en uiteindelijk een oplossing die om mijn oude bak draait in 700ms (inlezen + part 1 + part 2).

[Creepy]

Valt me toch niet tegen. De sparse in 85 en 55ms en de rect in 20 en 10ms.

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

• aoc_2022_day08_rect.txt (55 KB); antwoorden eindigen met "19" en "88".
• aoc_2022_day08_sparse.txt (1 MB); antwoorden eindigen met "76" en "30".

Ik krijg bij sparse deel 2 een antwoord dat eindigt op 00. De overige 3 zijn wel gelijk?

[ Voor 80% gewijzigd door Creepy op 08-12-2022 14:26 ]

[Soultaker]

Creepy schreef op donderdag 8 december 2022 @ 14:23:
Ik krijg bij sparse deel 2 een antwoord dat eindigt op 00. De overige 3 zijn wel gelijk?

Komt omdat ik de invoer speciaal heb bedacht om een specifieke bug te triggeren Laat me raden: je antwoord is (hint)

spoiler:

tien cijfers lang

en (grotere hint)

spoiler:

begint met 21 of misschien 20?

Zo ja, vraag je dan af hoe ik dat kan weten zonder je code uit te voeren, en wat er speciaal is aan die eigenschappen. (Zo nee, dan is er iets anders mis met je code.)

[ Voor 16% gewijzigd door Soultaker op 08-12-2022 14:47 ]

[Marcj]

Soultaker schreef op donderdag 8 december 2022 @ 14:36:
[...]

Komt omdat ik de invoer speciaal heb bedacht om een specifieke bug te triggeren Laat me raden: je antwoord is (hint)

spoiler:

tien cijfers lang

en (grotere hint)

spoiler:

begint met 21 of misschien 20?

Zo ja, vraag je dan af hoe ik dat kan weten zonder je code uit te voeren, en wat er speciaal is aan die eigenschappen. (Zo nee, dan is er iets anders mis met je code.)

Ja, daar liep ik ook eerst tegenaan, maar herkende het nummer vrij snel

[Litpho]

Swedish Clown schreef op donderdag 1 december 2022 @ 09:39:
Bonus challenge for those that accept


***members only***


@P_Tingen ^

Dat zijn de betere bestanden.

Time spent parsing: 2.08 s
Time spent part one: 3.90 ms
Time spent part two: 244.90 ms

https://github.com/litpho...lob/main/day1/src/main.rs

Ik gebruik nom om te parsen omdat ik nom beter wil leren, niet omdat de complexiteit van deze opdracht dat nu echt nodig heeft .

[ Voor 3% gewijzigd door Litpho op 08-12-2022 15:28 ]

[Soultaker]

Janoz schreef op donderdag 8 december 2022 @ 07:48:

spoiler:

Ik moest mijn eerste implementatie naar /dev/null sturen omdat ik even helemaal geen rekening gehouden had met dat dezelfde boom van meerdere kanten te zien is.

Haha, ik precies hetzelfde. Nu ik weet dat ik niet de enige ben die die fout maakte voel ik me iets minder dom.

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.

Heel netjes! Veel sneller dan mijn Python code.

Ik heb eens naar je code gekeken en ik dacht dat die aanpak traag zou zijn, maar nu ik er over nadenk klopt dat niet, en is 'ie zelfs asymptotisch optimaal.

spoiler:

Ik dacht eerst dat het suboptimaal was om per boom afzonderlijk het veld te scannen, zoals jij doet. Jouw methoden isVisible() en getScore() kosten O(N) worst-case per aanroep, waardoor het lijkt alsof je hele algoritme O(N³) nodig heeft voor een vierkant bos met zijde N.

Maar dit klopt niet. Hoewel de O(N) worst case wel klopt, is het gemiddelde over het hele bos noodzakelijkerwijs veel kleiner, O(1) zelfs.

In beide methoden doe je praktisch hetzelfde (sterker nog, de 4 while-loops zijn identiek!): je scant vanuit een boom naar links (of rechts, boven, onder) tot je een boom van gelijke of grotere hoogte tegenkomt (of de rand van het bos).

Dat betekent dat je bijvoorbeeld een reeks kunt hebben als: 00001111122223333.....9999, en als je naar links scant, dan zijn er precies 10 bomen die tot de rand moeten scannen (de eerste 0, de eerste 1, etc.), alle anderen zijn meteen klaar. Als je het bekijkt vanuit de boom waarmee vergeleken wordt, dan wordt een boom met hoogte x hooguit 4×(9-x) keer gescand wordt (1 keer per richting, per hogere boom), waardoor je algoritme feitelijk in O(36×N²) = O(N²) per deel draait.

[Creepy]

Soultaker schreef op donderdag 8 december 2022 @ 14:36:
[...]

Komt omdat ik de invoer speciaal heb bedacht om een specifieke bug te triggeren Laat me raden: je antwoord is (hint)

spoiler:

tien cijfers lang

en (grotere hint)

spoiler:

begint met 21 of misschien 20?

Zo ja, vraag je dan af hoe ik dat kan weten zonder je code uit te voeren, en wat er speciaal is aan die eigenschappen. (Zo nee, dan is er iets anders mis met je code.)

Motherf....... anyway, dat is correct. Ok, ik moest iets gaan fixen, ik weet nu nog niet wat

Edit: ik heb een vermoeden......

Edit2: Ik zou de code kunnen aanpassen zodat er voor beide delen maar 1 scan nodig is, zou weer tijd schelen. Maar ja, moeite enzo

[ Voor 11% gewijzigd door Creepy op 08-12-2022 15:19 ]

[Creepy]

En mijn vermoeden was niet juist.. daar gaat mijn middag

[Soultaker]

Creepy schreef op donderdag 8 december 2022 @ 15:27:
En mijn vermoeden was niet juist.. daar gaat mijn middag

Nog een hint:

spoiler:

komt het getal 2.147.483.647 je bekend voor? Zo niet, even Googlen.

[Litpho]

Opdrachten tot en met dag 8 in Rust - het blijft indrukwekkend om te zien hoe efficient de binaries gemaakt kunnen worden

Dag 1 - parsing: 65.10 μs, part one: 300.00 ns, part two: 7.00 μs
Dag 2 - parsing: 100.20 μs, part one: 33.30 μs, part two: 40.20 μs
Dag 3 - parsing: 20.30 μs, part one: 452.40 μs, parsing: 24.00 μs, part two: 146.20 μs
Dag 4 - parsing: 71.60 μs, part one: 7.60 μs, parsing: 78.10 μs, part two: 1.00 μs
Dag 5 - parsing: 37.60 μs, part one: 16.30 μs, parsing: 39.00 μs, part two: 50.70 μs
Dag 6 - parsing: 1.20 μs, part one: 4.80 μs, part two: 12.90 μs
Dag 7 - parsing: 480.20 μs, part one: 500.00 ns, part two: 1.50 μs
Dag 8 - parsing: 25.40 μs, part one: 370.10 μs, part two: 208.50 μs

[Creepy]

Soultaker schreef op donderdag 8 december 2022 @ 15:34:
[...]

Nog een hint:

spoiler:

komt het getal 2.147.483.647 je bekent voor? Zo niet, even Googlen.

O echt, die had ik van mijlen ver aan moeten zien komen

spoiler:

Ik doe echt standaard alles met long, juist hier om. Zul je net zien dat ik score als int heb gepakt.. * zucht *

[.oisyn]

Litpho schreef op donderdag 8 december 2022 @ 15:35:
Opdrachten tot en met dag 8 in Rust - het blijft indrukwekkend om te zien hoe efficient de binaries gemaakt kunnen worden

En doe het nu eens zonder include_str!()?

[Flamesz]

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

• aoc_2022_day08_rect.txt (55 KB); antwoorden eindigen met "19" en "88".
• aoc_2022_day08_sparse.txt (1 MB); antwoorden eindigen met "76" en "30".

Ik had in verwachting van een grote dataset vandaag alvast gemaakt met wat Parallel.For in C#.
Kwam nog wel twee plaatsen tegen waar ik width en length had verwisseld, wat voor de rectangle in out of bounds errors resulteerde, en voor sparse moest ik wat integers omzetten.
Krijg daarmee de volgende tijden, exclusief het parsen.

rect deel 1 in 33ms, deel 2 in 4ms
sparse deel 1 37ms deel 2 in 51ms.

Ik dacht eerst dat sparse er vele minuten over deed, maar ik had nog code aanstaan die na het berekenen de lijst van alle scores van bomen voor deel 2 in een string stopte om te weergeven haha.

[MatHack]

Ondertussen mijn C# code behoorlijk omgeschreven (zie spoiler voor wijzigingen).

Nu zijn de tijden van de rect van @Soultaker:
Part1 in 5,0741ms
Part2 in 5,2685ms

Veeeeeel sneller dan voorheen dus, mijn code is ondertussen ook een stuk netter...

spoiler:

- Van one-dimension array naar een jagged array gegaan (int[] naar int[][] dus). Ik weet niet wat voor brainfart ik vanochtend had, maar dit is leesbaarder en sneller
- Rechtstreeks in grid kijken voor de verschillende richtingen ipv subarrays maken van elk pad en deze dan door een algemene methode halen. Dit was de grootste winst, al die arrays aanmaken kostte meer dan ik had gedacht.

Tijden van de sparse:
Part1 in 84,8015ms
Part2 in 95,1032ms

[ Voor 4% gewijzigd door MatHack op 08-12-2022 16:59 . Reden: sparse toegevoegd ]

[Soultaker]

Litpho schreef op donderdag 8 december 2022 @ 15:35:
Dag 8 - parsing: 25.40 μs, part one: 370.10 μs, part two: 208.50 μs

Mijn C++ code (gebaseerd op @Creepy's aanpak, maar ik heb de fasen samengevoegd; volgens mij ben ik de eerste die dit bedacht heeft) is sneller: mediaan 461 us voor deel 1 + 2 samen (158 us parsing, 302 us solving, maar parsen heb ik nog niet geoptimaliseerd).

Voor day8-2000x2000.txt: 218 ms (78 ms parsen, 140 ms solven).
Voor day08_sparse.txt: 54 ms (18 ms parsen, 37 ms solven).

Litpho schreef op donderdag 8 december 2022 @ 15:35:
Dag 8 - parsing: 25.40 μs, part one: 370.10 μs, part two: 208.50 μs

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).

[ Voor 30% gewijzigd door Soultaker op 08-12-2022 17:08 ]

[.oisyn]

===[ 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

[eheijnen]

Krijgen we ook een dag vrij of moeten we tot en met 2e kerstdag bijven kloppen?

[KabouterSuper]

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?

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.

[ Voor 22% gewijzigd door KabouterSuper op 08-12-2022 17:31 ]