Advent of Code 2022

[Camulos]

Dag 6 was idd vrij simpel

spoiler:

Voor Part 1 kon ik het niet laten om toch snel de 6 vergelijkingen neer te pennen (by far het snelst).. echter lukt dat niet voor 14 stuks (13! is meer dan 6 miljard vergelijkingen )..

Een Set (hashset) is daarentegen eenvoudig genoeg om unieke karakters te bepalen

C# https://github.com/flutte...tOfCode/Year2022/Day06.cs

[YoToP]

Dag 6

Ik had ook iets moeilijkers verwacht voor

spoiler:

deel 2, nouja bewaren we dat wel voor morgen.


Ik hoefde nu alleen een 4 te veranderen in 14, en de deque regelt de rest.

Nu even kijken hoe ik een .zst uitpak op Windhoos
Gewoon binnen Python houden dus, met zstandard.

dcm360 schreef op dinsdag 6 december 2022 @ 09:15:
Dus, iemand nog zin in een iets grotere invoer?
Ideale puzzel om decompressie-bommen mee te bouwen, dus let er even op dat het laatste bestand na uitpakken iets meer dan 800MB is.

grote input spoiler:

spoiler:

Link naar Python code
part 1: 4015
part 2: 21412
### input: 2022/06/inputs/aoc22d6l.txt.zst run time is 107 miliseconds
part 1: 5362711
part 2: 28601124
### input: 2022/06/inputs/aoc22d6xl.txt.zst run time is 6010 miliseconds
part 1: 85803316
part 2: 457617684
### input: 2022/06/inputs/aoc22d6xxl.txt.zst run time is 92717 miliseconds
### total run time is 98835 miliseconds

[ Voor 72% gewijzigd door YoToP op 06-12-2022 11:15 . Reden: update grote input ]

[Remcoder]

Mensen, willen jullie wel denken aan het gebruik van spoilers?

Er worden nu wel erg veel hints weggegeven voor wat er in deel 2 te verwachten is.

[Wraldpyk]

dcm360 schreef op dinsdag 6 december 2022 @ 09:15:
Dus, iemand nog zin in een iets grotere invoer?
Ideale puzzel om decompressie-bommen mee te bouwen, dus let er even op dat het laatste bestand na uitpakken iets meer dan 800MB is.

Mis ik iets, of zijn dit super kleine bestanden?

[P_Tingen]

Pff, voor deel 1 veel te lang zitten klooien. Ik dacht dat het simpel was, maar liep keer op keer vast. Uiteindelijk voor de oplossing gekozen die @Remcoder en @Camulos* ook deden.

spoiler:

Voor deel 1 werkte dat, maar voor deel 2 toch maar even heroverwogen en een functie gebruikt

In Progress 4GL: https://github.com/patric...ster/2022/Day-06/day-06.p

* @Camulos denk aan je spoilers!

[CMG]

Vandaag was volgens mij de makkelijkste, zeker qua parsen (non-existent😅)

Reddit post | Live Stream VOD

[Janoz]

dcm360 schreef op dinsdag 6 december 2022 @ 09:15:
Dus, iemand nog zin in een iets grotere invoer?
Ideale puzzel om decompressie-bommen mee te bouwen, dus let er even op dat het laatste bestand na uitpakken iets meer dan 800MB is.

Op die grote krijg ik een fout. Na 7 seconden is hij bij het einde zonder dat hij een startpunt gevonden heeft. Zal vast komen omdat de door mij gebruikte zstd library niet goed is.

Bij een buffer van 4 krijg ik iig na 815ms 85803316 als antwoord terug

[ Voor 5% gewijzigd door Janoz op 06-12-2022 10:48 ]

[dcm360]

Janoz schreef op dinsdag 6 december 2022 @ 09:36:
[...]

Als je echt je algoritme wilt flexen, zul je ook een grotere buffer moeten nemen. Met een size van 14 ga je denk ik niet echt verschil zien tussen een naïve O(N²) en een efficiënte O(1) matcher.

Het valt inderdaad waarschijnlijk wel mee met de verschillen, al zal een iets te naïeve oplossing misschien wat te veel werkgeheugen nodig hebben voor het grootste bestand. Mijn eigen oplossing heeft er bijna 4 minuten voor nodig, en dat is zeker nog niet optimaal.

Wraldpyk schreef op dinsdag 6 december 2022 @ 10:38:
[...]


Mis ik iets, of zijn dit super kleine bestanden?

Het zijn tekstbestanden ingepakt met zstandard. De tekst is een repeterend patroontje, dus dat comprimeert vrij goed.

Janoz schreef op dinsdag 6 december 2022 @ 10:47:
[...]


Op die grote krijg ik een fout. Na 7 seconden is hij bij het einde zonder dat hij een startpunt gevonden heeft. Zal vast komen omdat de door mij gebruikte zstd library niet goed is.

Bij een buffer van 4 krijg ik iig na 815ms 85803316 als antwoord terug

Interessant, in principe zouden alle bestanden hetzelfde patroon moeten volgen, namelijk:

code:

(ati)*c(unproblematic)*(undiscoverably)*

Het zou ook nog kunnen dat ik iets verkeerd heb gedaan met mijn outputstream, in dat geval zou dit bestand misschien beter werken. En anders is dit een goede hint dat zstandard niet altijd even portable is.

[Janoz]

dcm360 schreef op dinsdag 6 december 2022 @ 11:09:
Interessant, in principe zouden alle bestanden hetzelfde patroon moeten volgen, namelijk:

code:

(ati)*c(unproblematic)*(undiscoverably)*

Het zou ook nog kunnen dat ik iets verkeerd heb gedaan met mijn outputstream, in dat geval zou dit bestand misschien beter werken. En anders is dit een goede hint dat zstandard niet altijd even portable is.

Heb de bestanden maar even uitgepakt en blijkbaar heb ik er toch een bugje in zitten waardoor het niet werkt. Zelfs bij "atiaticunproblematicunproblematicundiscoverablyundiscoverably" vindt hij nog niks. Even kijken wat er aan de hand is


----

Ah, bugje gevonden. Nu vindt hij hem wel in exact 4 seconden (wat ook wel mijn verwachting was aangezien hij na 7 seconden bij het einde was)

Ben benieuwd hoe snel het gaat wanneer ik het bestand op een ramdrive zet.

[ Voor 13% gewijzigd door Janoz op 06-12-2022 11:34 ]

[.oisyn]

Grappig, nog niemand (die ook code heeft gepost) heeft de oplossing waar ik als eerste aan dacht . Die van @Marcj vind ik wel leuk bedacht trouwens!

[ Voor 9% gewijzigd door .oisyn op 06-12-2022 11:34 ]

[Marcj]

Over dag 6 implementatie:

spoiler:

Grappig dat de meesten voor een Set gaan. Heel logisch eigenlijk, maar ik dacht slimmer te zijn door met bits te gaan spelen op een int. Aangezien er maar 26 mogelijke items zijn, kan het gewoon door bits te zetten en dan een bitcount uit te voeren. Maar de testset is echt veel te klein om het verschil in performance te zien...

[Janoz]

.oisyn schreef op dinsdag 6 december 2022 @ 11:34:
Grappig, nog niemand (die ook code heeft gepost) heeft de oplossing waar ik als eerste aan dacht . Die van @Marcj vind ik wel leuk bedacht trouwens!

Waar dacht jij dan aan?

Zoiets?

[.oisyn]

@Janoz Nee, maar die is ook wel aardig . Ik dacht aan een oplossing waarbij je maar 1x langs elk teken hoeft. Geen idee of dat in de praktijk ook efficienter is hoor. Of misschien denk ik te simpel, ik heb het immers nog niet ingetypt

[ Voor 36% gewijzigd door .oisyn op 06-12-2022 11:43 ]

[MueR]

Vandaag was wel erg makkelijk hoor. 5 minuten en klaar..

[DataGhost]

Marcj schreef op dinsdag 6 december 2022 @ 11:35:
Over dag 6 implementatie:

spoiler:

Grappig dat de meesten voor een Set gaan. Heel logisch eigenlijk, maar ik dacht slimmer te zijn door met bits te gaan spelen op een int. Aangezien er maar 26 mogelijke items zijn, kan het gewoon door bits te zetten en dan een bitcount uit te voeren. Maar de testset is echt veel te klein om het verschil in performance te zien...

Dat soort micro-optimalisaties doen eigenlijk helemaal niks met de grote-O-looptijd dus die vind ik persoonlijk minder interessant om te doen, terwijl het qua code een stuk minder leesbaar wordt wat je precies probeert te bereiken (als je het over een paar maanden nog eens bekijkt ofzo).

spoiler:

Zeker met een klein alfabet heb je eigenlijk bij elke set-operatie (in Python) de average case te pakken waardoor elke operatie O(1) is met een totaal van O(n), en ik gok dat dit voor de meeste talen/libraries ook geldt.

Maar goed, de eerste paar dagen zijn de opdrachten simpel genoeg om hier tijd voor over te hebben en hier geschikt voor te zijn, en in absolute tijd zijn er dan wel procentueel significante winsten te halen ja. Vanaf eind deze week verwacht ik niet meer dat dat het geval is.

[Janoz]

Hmm, dat zie ik zo nog niet voor me @.oisyn. Je zult toch bij moeten houden wanneer tekens weer uit de buffer gaan lopen lijkt me. Ben heel benieuwd hoe je dat dan gaat doen.

Maar zoals ik eerder al zei. de optimalisaties zijn marginaal aangezien zelfs voor grote sets het alfabet en dus de zoekbuffer gemaximaliseerd is. Uiteindelijk meet je gewoon hoe snel je de hele string in kunt lezen.

[Swedish Clown]

Dag 6 in Erlang leuke simplele dag :-) Vanavond eens kijken hoe de boel draait met de grotere inputs

[timvisee]

dcm360 schreef op dinsdag 6 december 2022 @ 09:15:
Dus, iemand nog zin in een iets grotere invoer?
Ideale puzzel om decompressie-bommen mee te bouwen, dus let er even op dat het laatste bestand na uitpakken iets meer dan 800MB is.

Thanks! Aardig snel in Rust op één core met grote jumps in de search space.

Part 2: 720 ns (0.00072 ms)
Set 1 (40KB): 982 ns 1.10 μs (0.001 ms)
Set 2 (54MB): 865 μs 1.01 ms
Set 3 (858MB): 13.81 ms 15.81 ms

Source: https://github.com/timvis...master/day06b/src/main.rs

[ Voor 7% gewijzigd door timvisee op 06-12-2022 15:20 ]

[gedonie]

Snel in de lunch pauze even dag 6 opgelost in Java.

Vond wel dat deel 2 dit keer wel erg makkelijk was.

[.oisyn]

dcm360 schreef op dinsdag 6 december 2022 @ 09:15:
Dus, iemand nog zin in een iets grotere invoer?
Ideale puzzel om decompressie-bommen mee te bouwen, dus let er even op dat het laatste bestand na uitpakken iets meer dan 800MB is.

Heb je ook iets dat 7zip wél ondersteunt? Geen zin om weer een andere archiver te installeren

.edit: nvm, heb een versie van 7zip gevonden die het wel ondersteunt

[ Voor 6% gewijzigd door .oisyn op 06-12-2022 12:46 ]

[Jens VD]

Janoz schreef op dinsdag 6 december 2022 @ 11:51:
Hmm, dat zie ik zo nog niet voor me @.oisyn. Je zult toch bij moeten houden wanneer tekens weer uit de buffer gaan lopen lijkt me. Ben heel benieuwd hoe je dat dan gaat doen.

Maar zoals ik eerder al zei. de optimalisaties zijn marginaal aangezien zelfs voor grote sets het alfabet en dus de zoekbuffer gemaximaliseerd is. Uiteindelijk meet je gewoon hoe snel je de hele string in kunt lezen.

Je zou een bit string kunnen bijhouden die voor elke letter een bit op 1 heeft als die in de laatste n keer gezien is, en een aparte datastructuur die bijhoudt binnen hoeveel iteraties een bit weer naar 0 moet gaan. Dat vergt wel wat meer bookkeeping en ik heb geen idee of het daadwerkelijk beter zou zijn, maar zo loop je wel slechts 1 maal over de input.

[DataGhost]

Iedereen die deel 2 (te) makkelijk vond: er zijn zat mensen die nog weinig ervaring hebben met algoritmiek, tijdscomplexiteit en dit soort wedstrijden in het algemeen. Deel 2 is meestal bedoeld om je te laten zien dat je eerste naïeve gedachte die voor deel 1 prima werkte niet zomaar vertaalt naar deel 2. Als je direct al het "goede" algoritme gebruikte zal het makkelijk lijken inderdaad. Aan de andere kant word je op sommige dagen wel een beetje in de val gelokt met uiteindelijk een over-engineered oplossing voor deel 1 met de verwachting van een deel 2 die uiteindelijk heel anders bleek

[.oisyn]

Janoz schreef op dinsdag 6 december 2022 @ 11:51:
Hmm, dat zie ik zo nog niet voor me @.oisyn. Je zult toch bij moeten houden wanneer tekens weer uit de buffer gaan lopen lijkt me. Ben heel benieuwd hoe je dat dan gaat doen.

Maar zoals ik eerder al zei. de optimalisaties zijn marginaal aangezien zelfs voor grote sets het alfabet en dus de zoekbuffer gemaximaliseerd is. Uiteindelijk meet je gewoon hoe snel je de hele string in kunt lezen.

spoiler:

Je hoeft alleen maar bij te houden voor elke letter wanneer je hem het laatst gezien hebt, en wanneer de eerstvolgende potentiele startpositie is. Voor elke letter die je leest update je z'n last-seen, en update je de potentiele startpositie als oude last-seen + window-size groter is. Zodra je de startpositie begint uit te lezen dan ben je klaar

[DataGhost]

Jens VD schreef op dinsdag 6 december 2022 @ 12:32:
[...]


Je zou een bit string kunnen bijhouden die voor elke letter een bit op 1 heeft als die in de laatste n keer gezien is, en een aparte datastructuur die bijhoudt binnen hoeveel iteraties een bit weer naar 0 moet gaan. Dat vergt wel wat meer bookkeeping en ik heb geen idee of het daadwerkelijk beter zou zijn, maar zo loop je wel slechts 1 maal over de input.

Het is uiteindelijk net zo duur om die tweede keer over de input te loopen als in die datastructuur te kijken.

[eheijnen]

Ongelooflijk wat een drukte de laatste dagen....

[breew]

eheijnen schreef op dinsdag 6 december 2022 @ 12:35:
Ongelooflijk wat een drukte de laatste dagen....

dat krijg je als de puzzel te simpel is

[Jens VD]

DataGhost schreef op dinsdag 6 december 2022 @ 12:34:
[...]

Het is uiteindelijk net zo duur om die tweede keer over de input te loopen als in die datastructuur te kijken.

Niet noodzakelijk, op die manier kan ik uitsluitend acteren op de buffer waarmee het inlezen van de file gebeurt. Als 2 maal over de input loopt zal je toch data moeten kopieren of met meerdere buffers werken.

[eheijnen]

Is goed om te zien dat er toch nog leven in zit...

[.oisyn]

425ms 77ms op de 800MB file met windowsize 14.

spoiler:

457617684

[ Voor 23% gewijzigd door .oisyn op 06-12-2022 13:00 ]

[Janoz]

Jens VD schreef op dinsdag 6 december 2022 @ 12:32:
[...]


Je zou een bit string kunnen bijhouden die voor elke letter een bit op 1 heeft als die in de laatste n keer gezien is, en een aparte datastructuur die bijhoudt binnen hoeveel iteraties een bit weer naar 0 moet gaan. Dat vergt wel wat meer bookkeeping en ik heb geen idee of het daadwerkelijk beter zou zijn, maar zo loop je wel slechts 1 maal over de input.

Bitjes gaan niet helpen. Een letter kan vaker voorkomen binnen de buffer. Check mijn oplossing eens. Die is volgens mij nog efficiënter dan de datastructuur waar jij nu over aan het nadenken bent. Mijn linkje linkt naar de oplossing waar ik de hele string in geheugen heb, maar met een circulaire buffer blijft het een O[1] operatie.

[Janoz]

.oisyn schreef op dinsdag 6 december 2022 @ 12:33:
[...]

spoiler:

Je hoeft alleen maar bij te houden voor elke letter wanneer je hem het laatst gezien hebt, en wanneer de eerstvolgende potentiele startpositie is. Voor elke letter die je leest update je z'n last-seen, en update je de potentiele startpositie als oude last-seen + window-size groter is. Zodra je de startpositie begint uit te lezen dan ben je klaar

Ik moest even nadenken, maar nu snap ik hem.

spoiler:

ipv mijn frequentie tabel heb je een positie tabel

[Remcoder]

DataGhost schreef op dinsdag 6 december 2022 @ 12:33:
Iedereen die deel 2 (te) makkelijk vond: er zijn zat mensen die nog weinig ervaring hebben met algoritmiek, tijdscomplexiteit en dit soort wedstrijden in het algemeen. Deel 2 is meestal bedoeld om je te laten zien dat je eerste naïeve gedachte die voor deel 1 prima werkte niet zomaar vertaalt naar deel 2. Als je direct al het "goede" algoritme gebruikte zal het makkelijk lijken inderdaad. Aan de andere kant word je op sommige dagen wel een beetje in de val gelokt met uiteindelijk een over-engineered oplossing voor deel 1 met de verwachting van een deel 2 die uiteindelijk heel anders bleek

Yup, die valkuil ben ik al meerdere keren in gevallen...

Tegenwoordig doe ik dus geen aannames meer over deel 2, die ene keer dat ik gelijk heb weegt niet op tegen alle keren dat ik ongelijk heb gehad.

[Remcoder]

dcm360 schreef op dinsdag 6 december 2022 @ 09:15:
Dus, iemand nog zin in een iets grotere invoer?
Ideale puzzel om decompressie-bommen mee te bouwen, dus let er even op dat het laatste bestand na uitpakken iets meer dan 800MB is.

Zoals al een aantal keer aangegeven is test deze dataset eigenlijk alleen wie het snelste een string kan lezen.

Interessanter wordt als je een dataset bouwt die bv een window van 10000 groot ofzo moet bekijken. Je moet dan wel zowat alle mogelijke characters gaan gebruiken, anders heb je geheid herhaling.

[Jern_97]

.oisyn schreef op dinsdag 6 december 2022 @ 12:47:
425ms 77ms op de 800MB file met windowsize 14.

spoiler:

457617684

Ben zeer benieuwd hoe je dit voor elkaar gekregen hebt
Is je code ergens beschikbaar?

[.oisyn]

Jern_97 schreef op dinsdag 6 december 2022 @ 13:07:
[...]


Ben zeer benieuwd hoe je dit voor elkaar gekregen hebt
Is je code ergens beschikbaar?

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

Zit nog een hoop boilerplate in wat gedupliceerd wordt tussen alle oplossingen, moet de boel even opschonen. Dus als je denkt "wat veel code", het meeste is copypaste werk . GetStart() is where the magic happens.

[Janoz]

Ik vermoed data in RAM en dan de methode toepassen die hij hier beschreven heeft.

[Jern_97]

.oisyn schreef op dinsdag 6 december 2022 @ 13:12:
[...]


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

Zit nog een hoop boilerplate in wat gedupliceerd wordt tussen alle oplossingen, moet de boel even opschonen. Dus als je denkt "wat veel code", het meeste is copypaste werk . GetStart() is where the magic happens.

Interessant! Waarschijnlijk is een multithreaded variant hiervan nog een stuk sneller, waarbij de totale string verdeelt wordt in gelijke delen.

[.oisyn]

@Jern_97 Dat is het al

[KabouterSuper]

Ik ben ook maar eens begonnen. Ik had dit jaar mezelf als doel gesteld om alle AdventofCodes te voltooien. Ik heb de jaren in willekeurige volgorde gemaakt: 2021 vorig jaar (in quarantaine), 2015, 2016, 2018 en 2020 afgelopen maanden en 2017 afgelopen week. Gisteren en vandaag even 2022 ingehaald. Tot nu toe gaat het me goed af. Ik vrees wel de dag dat er een register-challenge komt waarbij je met set, mul, add,sub en jmp-achtige constructies aan de slag moet. Ik heb hier zo'n hekel aan (lees: ik ben er zo slecht in). Ik heb maar vast wat functies geschreven waarmee ik instructies kan taggen met commentaar, kan indenten en herschrijven. Hopelijk lukt het me dan wat sneller om er doorheen te komen.

[Creepy]

En hier weer een luie ontwikkelaar die

spoiler:

met een set checkt of de boel uniek is. Een Deque gebruikt voor het bijhouden van de laatste X karakters)

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

[timvisee]

Jern_97 schreef op dinsdag 6 december 2022 @ 13:07:
[...]


Ben zeer benieuwd hoe je dit voor elkaar gekregen hebt
Is je code ergens beschikbaar?

Ik solve de 858MB input van dag 6 inmiddels in 13.8 ms 15.81 ms.

Post: timvisee in "Advent of Code 2022"

Source: https://github.com/timvis...master/day06b/src/main.rs

Correctie: dat is enkel part 2; dus een window size van 14.

[ Voor 29% gewijzigd door timvisee op 06-12-2022 15:14 ]

[.oisyn]

timvisee schreef op dinsdag 6 december 2022 @ 13:24:
[...]


Ik solve de 858MB input van dag 6 inmiddels in 15.81 ms.

Post: timvisee in "Advent of Code 2022"

Source: https://github.com/timvis...master/day06b/src/main.rs

Correctie: dat is enkel part 2; dus een window size van 14.

include_bytes! is ook niet erg fair he . Dan staat de data in je executable en kan de compiler in feite al het antwoord uitrekenen.

[timvisee]

.oisyn schreef op dinsdag 6 december 2022 @ 13:38:
[...]


include_bytes! is ook niet erg fair he . Dan staat de data in je executable en kan de compiler in feite al het antwoord uitrekenen.

Binary inspection laat zien dat dat niet het geval is!

[.oisyn]

timvisee schreef op dinsdag 6 december 2022 @ 13:39:
[...]


Binary inspection laat zien dat dat niet het geval is!

Ik geloof er niets van dat je in 15ms met dat loopje over 850MB heen loopt. Hoe time je je code, en wat voor CPU heb je?

.edit: als ik op mijn 5800X single-threaded over die data heen loop die al in memory sta en alle tekens bij elkaar optel, dan kost dat 210ms.

[ Voor 19% gewijzigd door .oisyn op 06-12-2022 14:04 ]

[Gilotto]

Zo, even bijgewerkt! (Alles in F#)

Dag 3

Dag 4

Dag 5

Dag 6

Opdrachten zijn nog goed te doen

[Visitor.q]

Code van vandaag was vrij gemakkelijk, maar een goeie gelegenheid om te oefenen met

spoiler:

sets. Ik wilde niet meteen een brute force methode toepassen maar zag met een window van 4 ook zo gauw niet hoe het nu efficienter kon, dus ik ga zo wel even in dit topic rondneuzen wat ik eigenlijk had kunnen doen
Bij een window size van 14 werd het iets voordeliger om de stapgrootte dynamisch te maken nav het aantal unieke karakters in het window, en daarmee niet meer elke subset na te hoeven lopen, maar op de XL dataset van hierboven gaat de runtime van 11 naar 12 second tov pure bruteforce. De meeste vertraging zit echter in het maken van de set (python built-in) en bepalen van de lengte ervan...
Bij de XXL dataset gaat hij trouwens van 8m50 naar 5m30 (457617684).

Members only: Python dag 6

Alleen zichtbaar voor ingelogde gebruikers. Inloggen

BeefHazard schreef op maandag 5 december 2022 @ 23:54:
[...]


Oké, paar dingen die ik zie dan.

- Let op pep8 (vscode kan hier enorm bij helpen), dingen zoals consequent spaties na komma's en witregels op de juiste plaatsen helpen jezelf enorm. Python is ontworpen vanuit de gedachte je ook tijdens het programmeren meer je eigen code aan het lezen bent dan aan het schrijven.
- Pep8 geldt ook voor hoofdletters en snake_case, al vind ik het voor een chemicus wel passend om variabelen als Nc, Fr, To te maken Maar als ik 't snel doorlees denk ik dat dat classes zijn, zo kleurt GitHub ze ook in.
- Super cool dat je regex gebruikt, heb ik zelf niet gedaan
- je kunt

code:

for line,n in zip(lines,range(len(lines))):

Iets meer Pythonic en leesbaarder schrijven als::

code:

for (n, line) in enumerate(lines):

- de hele moveList-routine tussen lines 10 en 16 kun je uit de grote loop halen als functie en alleen aanroepen als hasInit. Dat soort 'separation of concerns' maakt alles gelijk leesbaarder en maakt het tijdens het ontwikkelen makkelijker om te ontdekken welke dingen wel goed gaan en welke niet. Des te meer je gaat zoeken naar manieren om subroutines die je kan hergebruiken in een aparte function te zetten, des te minder je voor elke dag weer een nieuwe grote loop zit te schrijven. Op een gegeven moment merk je dat je regelmatig (enigszins aangepaste) onderdelen van vorige dagen kan hergebruiken zonder dat ze afhankelijk zijn van alles dat je in de loop van die dag had lopen

Hartstikke bedankt voor je gedetailleerde feedback! Ik had gisteravond al een duimpje gedaan maar ging ook slapen dus niet reageren
Die pep8 in vscode, da's een goeie ga ik mee aan de slag. Dat zit in de linter zie ik (en die stond dus uit). Knap dat je het überhaupt kon lezen Die enumerate heb ik opgeslagen incl use case, veel mooier idd.

[armageddon_2k1]

Hydra schreef op maandag 5 december 2022 @ 14:53:
[...]


Voel me aangevallen

Ik heb op dit moment geen tijd Misschien op een later moment kijken hoe ver ik kom voordat ik het te lang vind duren.

Haha, nee hoor. Maar jij bent een van de weinige Kotlin'ers. Zodoende.

[timvisee]

.oisyn schreef op dinsdag 6 december 2022 @ 13:51:
[...]


Ik geloof er niets van dat je in 15ms met dat loopje over 850MB heen loopt. Hoe time je je code, en wat voor CPU heb je?

.edit: als ik op mijn 5800X single-threaded over die data heen loop die al in memory sta en alle tekens bij elkaar optel, dan kost dat 210ms.

Timing is best of 100 runs. Dat is exclusief het laden van de binary door de kernel of het lezen van de input file, dus de binary en input al in memory (zoals veel dat doen).

At runtime de input file lezen (dus zonder include_bytes!) geeft dezelfde timing.

Specs: Linux 6.0 (liquorix kernel), AMD Ryzen 9 5900X (24) @ 3.7GHz, 16GB DDR4

Source staat hier, feel free to give it a try!

Source voor het meten van alle oplossingen vind je hier.

[ Voor 12% gewijzigd door timvisee op 06-12-2022 14:29 ]

[.oisyn]

Ik kom op 43ms voor puur je main()

.edit: ik zie nu wat je doet, wel slim. Je gaat van achter naar voor, dus je skipt over best wel wat tekens.

[ Voor 60% gewijzigd door .oisyn op 06-12-2022 14:36 ]

[Tubby]

Creepy schreef op dinsdag 6 december 2022 @ 13:23:
En hier weer een luie ontwikkelaar die

spoiler:

met een set checkt of de boel uniek is. Een Deque gebruikt voor het bijhouden van de laatste X karakters)

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

Zoiets had ik eerst ook, nu heb ik t platter

spoiler:

ik hou de huidige partial telkens bij en die substring ik "vooruit" en daarna count ik op een distinct char stream hoeveel chars er zijn

https://github.com/tubbyn.../StartPacketDetector.java

[DataGhost]

Jens VD schreef op dinsdag 6 december 2022 @ 12:40:
[...]


Niet noodzakelijk, op die manier kan ik uitsluitend acteren op de buffer waarmee het inlezen van de file gebeurt. Als 2 maal over de input loopt zal je toch data moeten kopieren of met meerdere buffers werken.

Nogmaals het teken bekijken wat op het punt staat uit je buffer te vallen is O(1), net als gewoon opvragen welk teken er op positie X in de input stond (ook O(1)). Conceptueel gezien loop je dus tweemaal over de input ongeacht op welke manier je het doet.

[.oisyn]

Heeft iemand een hash van de 850mb dataset? Want ik krijg dus consistent een ander antwoor dan anderen hier, ook met andere implementaties.

[SPee]

Remcoder schreef op dinsdag 6 december 2022 @ 13:02:
[...]

Yup, die valkuil ben ik al meerdere keren in gevallen...

Tegenwoordig doe ik dus geen aannames meer over deel 2, die ene keer dat ik gelijk heb weegt niet op tegen alle keren dat ik ongelijk heb gehad.

En toch is je oplossing overengineered

spoiler:

Die hele CountingCollector kun je vervangen voor een simpele Set.
En die controle op alle waardes door een set.size()==4.

Zelf ben ik gegaan voor simpele for loopjes.

[Remcoder]

SPee schreef op dinsdag 6 december 2022 @ 15:00:
[...]


En toch is je oplossing overengineered

spoiler:

Die hele CountingCollector kun je vervangen voor een simpele Set.
En die controle op alle waardes door een set.size()==4.

Zelf ben ik gegaan voor simpele for loopjes.

spoiler:

Die over engineering is ook pas gekomen toen ik deel 2 zag en ik het zat was om voor de zoveelste keer unieke elementen in een stream te moeten tellen.

[Soultaker]

Een iets andere uitdaging voor dag 6: aoc_2022_day06_extra_input.zip

Dit bestand van 10 miljoen bytes bevat niet alleen de letters a-z, maar alle 94 printable ASCII karakters (en 1 newline op het eind).

Vraag 1: op welke positie komt voor het eerst 94 verschillende karakters voor?

Vraag 2: (pas openen als je deel 1 hebt opgelost)

spoiler:

noem de positie waar voor het eerst x verschillende karakters voorkomen p(x), zodat b.v. p(1) = 1 en p(94) is het antwoord van deel 1. Wat is dan de som van p(1) + p(2) + ... + p(94)?

[BeefHazard]

Soultaker schreef op dinsdag 6 december 2022 @ 15:29:
Een iets andere uitdaging voor dag 6: aoc_2022_day06_extra_input.zip

Dit bestand van 10 miljoen bytes bevat niet alleen de letters a-z, maar alle 94 printable ASCII karakters (en 1 newline op het eind).

Vraag 1: op welke positie komt voor het eerst 94 verschillende karakters voor?

spoiler:

9876543

edit: wups, copy ik nog het verkeerde getal ook

Vraag 2: (pas openen als je deel 1 hebt opgelost)

spoiler:

noem de positie waar voor het eerst x verschillende getallen voorkomen p(x), zodat b.v. p(1) = 1 en p(94) is het antwoord van deel 1. Wat is dan de som van p(1) + p(2) + ... + p(94)?

WIP

[ Voor 3% gewijzigd door BeefHazard op 06-12-2022 15:36 ]

[timvisee]

Soultaker schreef op dinsdag 6 december 2022 @ 15:29:
Een iets andere uitdaging voor dag 6: aoc_2022_day06_extra_input.zip

Dit bestand van 10 miljoen bytes bevat niet alleen de letters a-z, maar alle 94 printable ASCII karakters (en 1 newline op het eind).

Vraag 1: op welke positie komt voor het eerst 94 verschillende karakters voor?

Vraag 2: (pas openen als je deel 1 hebt opgelost)

spoiler:

noem de positie waar voor het eerst x verschillende getallen voorkomen p(x), zodat b.v. p(1) = 1 en p(94) is het antwoord van deel 1. Wat is dan de som van p(1) + p(2) + ... + p(94)?

Part 1 in 7.44 ms (source).
Part 2 in 35.02 ms (multithreaded 24-core) (source).

spoiler:

9876543
506020000

Kloppen die, of heb ik een fout gemaakt? Ik zie iemand met andere resultaten.

.edit: off-by-one error, oops, fixed.

[ Voor 11% gewijzigd door timvisee op 06-12-2022 16:58 ]

[Soultaker]

timvisee schreef op dinsdag 6 december 2022 @ 15:44:
Kloppen die, of heb ik een fout gemaakt?

Helaas, de correcte antwoorden zijn enigszins mooie getallen.

[dcm360]

.oisyn schreef op dinsdag 6 december 2022 @ 14:57:
Heeft iemand een hash van de 850mb dataset? Want ik krijg dus consistent een ander antwoor dan anderen hier, ook met andere implementaties.

code:

> md5sum ./aoc22d6xxl.txt
546933b126de57d0ace8e901cb0b6481  ./aoc22d6xxl.txt

[Jern_97]

Soultaker schreef op dinsdag 6 december 2022 @ 15:29:
Een iets andere uitdaging voor dag 6: aoc_2022_day06_extra_input.zip

Dit bestand van 10 miljoen bytes bevat niet alleen de letters a-z, maar alle 94 printable ASCII karakters (en 1 newline op het eind).

Vraag 1: op welke positie komt voor het eerst 94 verschillende karakters voor?

Vraag 2: (pas openen als je deel 1 hebt opgelost)

spoiler:

noem de positie waar voor het eerst x verschillende karakters voorkomen p(x), zodat b.v. p(1) = 1 en p(94) is het antwoord van deel 1. Wat is dan de som van p(1) + p(2) + ... + p(94)?

Zijn dit de correcte antwoorden?

spoiler:

Part 1: 9876543
Part 2: 506020001

[Soultaker]

Jern_97 schreef op dinsdag 6 december 2022 @ 15:53:
Zijn dit de correcte antwoorden?

spoiler:

Part 1: 9876543
Part 2: 506020001

Bijna, het antwoord voor deel 2 is off-by-1, ik gok dat je

spoiler:

p(0) meetelt

.

[P_Tingen]

Ik heb het (in Progress 4GL) opgelost met een functie:
https://github.com/patric...ster/2022/Day-06/day-06.p

Maar:

spoiler:

Ik denk dat het beter kan.

Ik doe nu een loop over de string en na 3 (of 13) tekens ga ik checken of teken nummer X ook in de voorliggende characters zit. Hier doe ik natuurlijk veel te veel checks.

Je zou - denk ik - een extra variabele kunnen gebruiken die je laat wijzen naar het teken waarvan je vermoedt dat dat het begin van je header kan zijn. Als het character van je hoofdloop gevonden kan worden ná het vermoedelijke begin van de header, dan stel je die variabele bij.

Klopt dit en heeft iemand dit gedaan?

[.oisyn]

dcm360 schreef op dinsdag 6 december 2022 @ 15:50:
[...]

code:

> md5sum ./aoc22d6xxl.txt
546933b126de57d0ace8e901cb0b6481  ./aoc22d6xxl.txt

Thanks. Dat komt dus wel overeen met wat ik heb.

@timvisee Je antwoord klopt niet . Bij jou geeft ie 85803325. Maar de laatste 14 tekens voorgaand aan offset 85803325 zijn: "iaticunproblem"

Ik zie daar 2x een i.

Dan snap ik wel waarom je zo snel bent ja . En ik gok dat ik de fout al zie...

.edit2: en jawel, met het jiuste antwoord:

Elapsed: 3.32s
457617684

Wat een beetje overeenkomt met mijn C++ implementatie van jouw algoritme (die deed er 2.5s over). Dus uiteindelijk toch niet zo snel

[ Voor 42% gewijzigd door .oisyn op 06-12-2022 16:17 ]

[timvisee]

.oisyn schreef op dinsdag 6 december 2022 @ 16:12:
[...]


Thanks. Dat komt dus wel overeen met wat ik heb.

@timvisee Je antwoord klopt niet . Bij jou geeft ie 85803325. Maar de laatste 14 tekens voorgaand aan offset 85803325 zijn: "iaticunproblem"

Ik zie daar 2x een i.

Dan snap ik wel waarom je zo snel bent ja . En ik gok dat ik de fout al zie...

.edit2: en jawel, met het jiuste antwoord:

Elapsed: 3.32s
457617684

Wat een beetje overeenkomt met mijn C++ implementatie van jouw algoritme (die deed er 2.5s over). Dus uiteindelijk toch niet zo snel

Good catch! Thanks! Dat valt tegen. Blijkbaar kwam dit door een off-by-one, die waarschijnlijk tijdens het golfen ertussen gekomen.

Gefixte implementatie met het juiste antwoord doet er 2.1 seconde over. Dat is inderdaad een significant verschil.

[.oisyn]

Zit ik helemaal een PR te maken, push je je change net voor mij

[Jern_97]

Soultaker schreef op dinsdag 6 december 2022 @ 15:56:
[...]

Bijna, het antwoord voor deel 2 is off-by-1, ik gok dat je

spoiler:

p(0) meetelt

.

Er was een bug waardoor hij voor p(1) altijd 2 gaf...
Nu werkt het volledig naar behoren.
Deel 1 is 3ms, Deel 2 is 170ms.
Kan waarschijnlijk nog heel veel sneller als je alle p(x)'n op een of andere manier in dezelfde loop zou kunnen berekenen...

[fruitschaal2]

Die van vandaag was goed te doen, zolang de input niet te groot wordt.

Normaal werk ik en python, zo ook voor deze code. Alleen had ik het idee om de Console met javascript eens te testen:

spoiler:

[code]
N=4; txt = document.documentElement.textContent; for(i=N; i<txt.length; i++){ if([...new Set(txt.slice(i-N, i).split(''))].length == N){console.log(i); break;}};

N=14; txt = document.documentElement.textContent; for(i=N; i<txt.length; i++){ if([...new Set(txt.slice(i-N, i).split(''))].length == N){console.log(i); break;}};
[/code]

[Soultaker]

Jern_97 schreef op dinsdag 6 december 2022 @ 16:32:
Er was een bug waardoor hij voor p(1) altijd 2 gaf...

Aha, waarschijnlijk dezelfde bug die @timvisee nog heeft.

Kan waarschijnlijk nog heel veel sneller als je alle p(x)'n op een of andere manier in dezelfde loop zou kunnen berekenen...

Yep, deel 2 kan ongeveer net zo snel als deel 1, zonder fratsen met multithreading ofzo. Het is zelfs vrij simpel!

[Jern_97]

Soultaker schreef op dinsdag 6 december 2022 @ 16:46:
Yep, deel 2 kan ongeveer net zo snel als deel 1, zonder fratsen met multithreading ofzo. Het is zelfs vrij simpel!

Hmmm, kom nu aan 22ms door het volgende te doen:

spoiler:

om p(x+1) te weten hoef je maar te zoeken vanaf index: p(x) - x

Iets zegt me dat dit nog niet helemaal is wat je naar hint...

[BeefHazard]

BeefHazard schreef op dinsdag 6 december 2022 @ 15:35:
[...]

spoiler:

9876543

edit: wups, copy ik nog het verkeerde getal ook

[...]


WIP

Toch nog gelukt (pastebin), uiteindelijk de juiste output. Maar op mijn laptop met i7-6700HQ is het ook met multiprocessing nog wel een klusje van 5 minuten. Terwijl ik toch dacht dat ik juist vooral operaties met hele lage time complexity uitvoerde.

[Soultaker]

Jern_97 schreef op dinsdag 6 december 2022 @ 18:12:
Hmmm, kom nu aan 22ms door het volgende te doen:

spoiler:

om p(x+1) te weten hoef je maar te zoeken vanaf index: p(x) - x

Iets zegt me dat dit nog niet helemaal is wat je naar hint...

Jawel, dat is wat ik in gedachte had. Daarmee is de worst-case complexiteit van je algoritme

spoiler:

O(N)

dus veel efficiënter kan het niet.

Hier heb ik dat idee geïmplementeerd door het in @timvisee's oplossing van deel 1 te hacken: file-day-6-extra-part-2.rs.

Je zou er nog wel multithreading aan toe kunnen voegen. De truc is dan om

spoiler:

voor elk blok de waarden van p(1) t/m p(94) te berekenen, en die uiteindelijk samen te voegen

wat waarschijnlijk een speedup levert die bijna proportioneel is aan het aantal cores dat je gebruikt.

[eheijnen]

Deel 3 (volgens deel 2) volgens de @.oisyn methode in C#.
Wel single threaded met de 800MB file op een i7 3770.

SW2 is de tijd in de loop en SW1 het totaal.
Ca. 2.5 sec gaat op aan het laden van de file.

Die marker zit dus ongeveer in het midden.
De file bevat: 858.033.151 chars

code:

Part 3 Result.................: Marker 457617684
Part 3 FileSize...............: 837922 KB
Part 3 SW1 Elapsed Ticks......: 92389652
Part 3 SW1 Elapsed MSec.......: 9238
Part 3 SW2 Elapsed Ticks......: 66764828
Part 3 SW2 Elapsed MSec.......: 6676

[ Voor 9% gewijzigd door eheijnen op 06-12-2022 19:20 ]

[Varienaja]

Dag 6 in Java.

Soultaker schreef op dinsdag 6 december 2022 @ 15:29:
Een iets andere uitdaging voor dag 6:
...

Met een piepkleine aanpassing vindt mijn code de antwoorden voor onderdeel a en b in in 13 seconden.

[CMG]

Had nog wat inspiratie

spoiler:

en ivp substring en distinct te tellen, maar

iets geschreven dat iets efficienter werkt.

Hmm, krijg spoiler gecombineerd met code tag niet werkend hier 😅dus linkje naar de code,

[Jern_97]

Soultaker schreef op dinsdag 6 december 2022 @ 18:35:
[...]

Jawel, dat is wat ik in gedachte had. Daarmee is de worst-case complexiteit van je algoritme

spoiler:

O(N)

dus veel efficiënter kan het niet.

Hier heb ik dat idee geïmplementeerd door het in @timvisee's oplossing van deel 1 te hacken: file-day-6-extra-part-2.rs.

Je zou er nog wel multithreading aan toe kunnen voegen. De truc is dan om

spoiler:

voor elk blok de waarden van p(1) t/m p(94) te berekenen, en die uiteindelijk samen te voegen

wat waarschijnlijk een speedup levert die bijna proportioneel is aan het aantal cores dat je gebruikt.

Ik had wel praktisch gelijke rekentijd daarnet in singlethreaded modus, maar mijn multithreaded implementatie was elke p(x) individueel voor alle blokken uitrekenen (en pas daarna p(x+1) over alle blokken enz.). Daarom werden telkens nieuwe threads gespawned en was er er dus meer overhead. Door per block direct de volledige range (1-94) te berekenen valt die bottleneck weg en kom ik aan volgende tijden/scaling:

1T
Part 1: 9876543 (15ms)
Part 2: 506020000 (14ms)

8T
Part 1: 9876543 (3ms)
Part 2: 506020000 (2ms)

Bijna lineair dus
https://github.com/Jeroen...022/blob/main/src/day6.rs

[ Voor 14% gewijzigd door Jern_97 op 06-12-2022 20:42 ]

[.oisyn]

CMG schreef op dinsdag 6 december 2022 @ 19:49:
Had nog wat inspiratie

spoiler:

en ivp substring en distinct te tellen, maar

iets geschreven dat iets efficienter werkt.

Hmm, krijg spoiler gecombineerd met code tag niet werkend hier 😅dus linkje naar de code,

Kun je eens omschrijven in woorden wat je probeert te bewerkstelligen? Ik vind het vrij gecompliceerd.

[CMG]

.oisyn schreef op dinsdag 6 december 2022 @ 20:19:
[...]


Kun je eens omschrijven in woorden wat je probeert te bewerkstelligen? Ik vind het vrij gecompliceerd.

😅
Basically in plaats van steeds

spoiler:

substring, distinct, count

te checken,

spoiler:

bijhouden wanneer je een karakter voor het laatst gezien hebt; dan vooruit kijken voor het aantal posities die je nodig hebt, als je geen indexen binnen je start range vind,

heb je je string gevonden.

Deze oplossing was 2x sneller voor deel 1 en 6x sneller voor deel 2 vergeleken met wat ik eerst had gemaakt.

code:

|   Method |        Mean |    Error |   StdDev |
|--------- |------------:|---------:|---------:|
|    Part1 |   169.64 us | 1.338 us | 1.186 us |
|    Part2 | 1,026.63 us | 6.963 us | 6.172 us |
| Part1Alt |    83.62 us | 1.244 us | 1.164 us |
| Part2Alt |   157.68 us | 2.811 us | 2.761 us |

[CMG]

.oisyn schreef op dinsdag 6 december 2022 @ 20:19:
[...]


Kun je eens omschrijven in woorden wat je probeert te bewerkstelligen? Ik vind het vrij gecompliceerd.

Hmm, je hebt me aan het denken gezet; in principe zou je ook gewoon elke keer met een nieuwe hashset kunnen kijken of je de letter al hebt😂

[CMG]

Ok, na inspiratie door de vraag van .oisyn nog een andere versie gemaakt; die is een stuk sneller 😅

[update] zag dat ik de set niet clearde; blijkt dat die oplossing langzamer is 😅

code:

|    Method |        Mean |     Error |    StdDev |
|---------- |------------:|----------:|----------:|
|     Part1 |   175.75 us |  2.975 us |  2.637 us |
|     Part2 | 1,069.49 us | 19.592 us | 18.327 us |
|  Part1Alt |    86.99 us |  0.916 us |  0.857 us |
|  Part2Alt |   161.50 us |  1.657 us |  1.550 us |
| Part1Alt2 |    99.83 us |  0.862 us |  0.806 us |
| Part2Alt2 |   227.02 us |  2.684 us |  2.511 us |

Heb hierna nog een optimalisatie geschreven zodat hij probeert te unwinden en dingen niet dubbel doet; dan is het wel sneller 😊

code:

| Part1Alt3 | 27.37 us | 0.518 us | 0.532 us |
| Part2Alt3 | 53.58 us | 0.591 us | 0.553 us |

Code voor alle varianten 😅

[ Voor 39% gewijzigd door CMG op 06-12-2022 20:59 ]

[.oisyn]

CMG schreef op dinsdag 6 december 2022 @ 20:33:
[...]


😅
Basically in plaats van steeds

spoiler:

substring, distinct, count

te checken,

spoiler:

bijhouden wanneer je een karakter voor het laatst gezien hebt; dan vooruit kijken voor het aantal posities die je nodig hebt, als je geen indexen binnen je start range vind,

heb je je string gevonden.

spoiler:

Ja dat vooruit kijken snap ik dus niet helemaal . Je code lijkt namelijk een beetje kwa idee op die van mij. Eigenlijk hoef je alleen maar bij te houden wanneer je een letter voor het laatst gezien hebt, en daarnaast nog 1 ander ding: het potentiele einde van de window (potential-window-end) waarbinnen alle letters uniek zijn.

Stel het 3e teken is een A, en het 10e teken is ook weer en A, en je hebt een window van 14 nodig. Dan kom je dus langs positie 3, dan registreer je dat: A heb je het laatst gezien op plek 3. Even verderop lees je op positie 10 weer een A. Dan weet je dus dat de eerstvolgende mogelijkheid dat de A uniek is binnen de window, het moment is dat positie 3 buiten de window raakt. Oftewel, als je t/m plek 17 (3+14) verder geen A meer leest, dan is A uniek. Dus behalve die last-seen per letter, hou je ook die potential-window-end=17 bij. Kom je ergens t/m de 17 weer een A tegen, bijvoorbeeld op plek 15, dan kijk je weer wanneer je A daarvoor voor het laatst gezien had (plek 10) en update je de potential-window-end naar 10+14=24, terwijl je natuurlijk ondertussen de last-seen van A ook update naar 15. Zolang je A's binnen de window tegenkomt, blijft deze waarde voouitschuiven. Totdat je een keertje geen A meer bent tegengekomen, en dan weet je dat de A's uniek zijn. Bijvoorbeeld, als er t/m 24 geen A's meer zijn, dan wordt die potential-window-end niet geupdatet en weet je dus: ok, ik heb nu plek 24 afgehandeld, die potential-window-end is ook 24, dus mijn A's zijn uniek.

Dit doe je natuurlijk niet alleen voor de A, maar voor alle letters. Maar het mooie is dat je die potential-window-end niet per letter hoeft bij te houden. Je hoeft alleen maar de grootste te weten. Immers, als er een letter is met een grotere potential-window-end maakt het niet uit dat de andere letters wel uniek zijn, je moet minstens zo ver lezen om die ene letter weer uniek te maken.

[Swedish Clown]

spoiler:

Als ik jullie zo goed begrijp, zijn er echter wel twee aannames die moeten kloppen:
1. Het splitten dan wel het aanmaken van nieuwe strings is dermate goedkoop dat het nagenoeg gratis is.
2. Een string is indexed oftewel string[i] geeft je de character terug op positie i van de string.

Beide is in mijn geval (Erlang) niet van toepassing...

(Of begrijp ik jullie nou verkeerd?)

[CMG]

Swedish Clown schreef op dinsdag 6 december 2022 @ 21:09:

spoiler:

Als ik jullie zo goed begrijp, zijn er echter wel twee aannames die moeten kloppen:
1. Het splitten dan wel het aanmaken van nieuwe strings is dermate goedkoop dat het nagenoeg gratis is.
2. Een string is indexed oftewel string[i] geeft je de character terug op positie i van de string.

Beide is in mijn geval (Erlang) niet van toepassing...

(Of begrijp ik jullie nou verkeerd?)

Ja, in C# (mijn taal) is een string onder water een char array. Niet bekend met Elang helaas, dus kan je niet zeggen wat het makkelijker zou maken😅in principe maakt de soort data niet veel uit, dus als je je string transcode naar een array van bytes, kun je de zelfde logica gewoon hanteren.

[CMG]

.oisyn schreef op dinsdag 6 december 2022 @ 21:02:
[...]

spoiler:

Ja dat vooruit kijken snap ik dus niet helemaal . Je code lijkt namelijk een beetje kwa idee op die van mij. Eigenlijk hoef je alleen maar bij te houden wanneer je een letter voor het laatst gezien hebt, en daarnaast nog 1 ander ding: het potentiele einde van de window (potential-window-end) waarbinnen alle letters uniek zijn.

Stel het 3e teken is een A, en het 10e teken is ook weer en A, en je hebt een window van 14 nodig. Dan kom je dus langs positie 3, dan registreer je dat: A heb je het laatst gezien op plek 3. Even verderop lees je op positie 10 weer een A. Dan weet je dus dat de eerstvolgende mogelijkheid dat de A uniek is binnen de window, het moment is dat positie 3 buiten de window raakt. Oftewel, als je t/m plek 17 (3+14) verder geen A meer leest, dan is A uniek. Dus behalve die last-seen per letter, hou je ook die potential-window-end=17 bij. Kom je ergens t/m de 17 weer een A tegen, bijvoorbeeld op plek 15, dan kijk je weer wanneer je A daarvoor voor het laatst gezien had (plek 10) en update je de potential-window-end naar 10+14=24, terwijl je natuurlijk ondertussen de last-seen van A ook update naar 15. Zolang je A's binnen de window tegenkomt, blijft deze waarde voouitschuiven. Totdat je een keertje geen A meer bent tegengekomen, en dan weet je dat de A's uniek zijn. Bijvoorbeeld, als er t/m 24 geen A's meer zijn, dan wordt die potential-window-end niet geupdatet en weet je dus: ok, ik heb nu plek 24 afgehandeld, die potential-window-end is ook 24, dus mijn A's zijn uniek.

Dit doe je natuurlijk niet alleen voor de A, maar voor alle letters. Maar het mooie is dat je die potential-window-end niet per letter hoeft bij te houden. Je hoeft alleen maar de grootste te weten. Immers, als er een letter is met een grotere potential-window-end maakt het niet uit dat de andere letters wel uniek zijn, je moet minstens zo ver lezen om die ene letter weer uniek te maken.

Ah, dat is ook een optie inderdaad 😅😂

[.oisyn]

Swedish Clown schreef op dinsdag 6 december 2022 @ 21:09:
Als ik jullie zo goed begrijp, zijn er echter wel twee aannames die moeten kloppen:
1. Het splitten dan wel het aanmaken van nieuwe strings is dermate goedkoop dat het nagenoeg gratis is.

Waarom zou je hier überhaupt gebruik maken van nieuwe strings? Er is er maar 1: je invoer. Voor de rest heb je eigenlijk alleen te maken met karakters.

2. Een string is indexed oftewel string[i] geeft je de character terug op positie i van de string.

Mijn algoritme itereert gewoon van voor naar achter over de string, dus de string hoeft niet indexeerbaar te zijn, als hij maar itereerbaar is. Maar vaak kun je wel cheaten door de codes op te vragen die wel direct indexeerbaar zijn, en in het geval van louter ASCII, wat hier zo is, weet je dat dat equivalent is (een ASCII string als UTF-8 of UTF-16 heeft geen surrogate pairs)

.edit:

The Erlang string type is implemented as a single-linked-list of unicode code points. That is, if we write “Hello” in the language, this is represented as

[$H, $e, $l, $l, $o]

Right, dat wil je dus sowieso niet. Heb je geen byte arrays? Ik zie dat je iets als bit strings hebt, kun je dat niet gebruiken?

[ Voor 14% gewijzigd door .oisyn op 06-12-2022 21:26 ]

[CMG]

Lol .oisyn, ik heb even jouw idee geimplementeerd; way to make me feel dumb 😅🤣

code:

|    Method |      Mean |     Error |    StdDev |
|---------- |----------:|----------:|----------:|
| Part1Alt3 | 27.822 us | 0.5204 us | 0.5344 us |
| Part2Alt3 | 55.167 us | 1.0734 us | 1.2361 us |
| Part1Alt4 |  1.672 us | 0.0238 us | 0.0222 us |
| Part2Alt4 |  3.117 us | 0.0622 us | 0.0949 us |

[ElkeBxl]

Dag 6 in Rust
Ik dacht dat ik vandaag niet veel tijd ging hebben tijdens de dag om een puzzel te fixen en dat ik het dus beter 's avonds ging doen. In het vervolg lees ik de opdracht eens rap bij het opstaan, ik had het vanochtend toch kunnen doen als ik wist hoe eenvoudig dit ging zijn

spoiler:

https://docs.rs/itertools...ls.html#method.all_unique

[TrailBlazer]

vanavond maar weer eens opgezocht hoe Dijkstra ook al weer geimplementeerd wordt. Ze gaan vast nog wel verdwalen in die jungle.

[SPee]

ElkeBxl schreef op dinsdag 6 december 2022 @ 21:31:
Dag 6 in Rust
Ik dacht dat ik vandaag niet veel tijd ging hebben tijdens de dag om een puzzel te fixen en dat ik het dus beter 's avonds ging doen. In het vervolg lees ik de opdracht eens rap bij het opstaan, ik had het vanochtend toch kunnen doen als ik wist hoe eenvoudig dit ging zijn

Ik heb deze opdracht ook in rust gedaan. Dat leek me ook nog wel te doen (de rest bewaar ik tot het weekend/vakantie).
Maar dat is wel helemaal makkelijk.
En ik maar moeilijk doen met for loopjes, match, slice en u32 vs usize.

[eheijnen]

eheijnen schreef op dinsdag 6 december 2022 @ 19:04[/message]:
Deel 3 (volgens deel 2) volgens de @.oisyn methode in C#.
Wel single threaded met de 800MB file op een i7 3770.

SW2 is de tijd in de loop en SW1 het totaal.
Ca. 2.5 sec gaat op aan het laden van de file.

Die marker zit dus ongeveer in het midden.
De file bevat: 858.033.151 chars

code:

Part 3 Result.................: Marker 457617684
Part 3 FileSize...............: 837922 KB
Part 3 SW1 Elapsed Ticks......: 92389652
Part 3 SW1 Elapsed MSec.......: 9238
Part 3 SW2 Elapsed Ticks......: 66764828
Part 3 SW2 Elapsed MSec.......: 6676

Nu ook met multi threading in C# met de 800MB file op een i7 3770.
Waarmee de tijd vanaf 8 threads ca. 6 seconden is en met 16 threads ca. 5 seconden.
Behalve de eerste marker op: 457617684, Zitten er nog een aantal van deze markers in:
536270800 | 643524957 | 750779114 | 457617684 | 482643780 | 536270865 | 589897950 | 643525035 | 697152120 | 750779205 | 804406290 | 457617684 | 482643897 | 509457446 | 536270995 | 563084544 | 589898093 | 616711642 | 643525191 | 670338740 | 697152289 | 723965838 | 750779387 | 777592936 | 804406485 | 831220034

SW1 Totale tijd
SW2 Tijd besteed aan het zoeken.

code:

16 Threads.

Part 4 FileSize...............: 837922 KB
Part 4 SW1 Elapsed Ticks......: 49326969
Part 4 SW1 Elapsed MSec.......: 4932
Part 4 SW2 Elapsed Ticks......: 21821949
Part 4 SW2 Elapsed MSec.......: 2182

[ Voor 6% gewijzigd door eheijnen op 07-12-2022 04:18 ]

[MrHaas]

Dag 7: https://github.com/arjand...oc_2022/day07/solution.py
Puzzel was niet direct moeilijk maar vergde vooral wat data-modelling. Al met al wel leuk!

[jmerle]

Dag 7 in Python

spoiler:

De pathlib module was erg handig vandaag. Ik ben het meeste tijd verloren aan het niet opmerken dat sommige directories geen bestanden maar enkel subdirectories bevatten, en dat de groottes van al die subdirectories bij elkaar soms ook <= 100,000 is. Mijn eerste oplossing miste een regel code om die directories de juiste grootte te geven, waardoor ik steeds net te laag uit kwam op deel 1 (maar enkel op de volledige input, niet op het voorbeeld). Uiteindelijk heb ik de problematische code herschreven met een andere API en toen werkte het wel correct.

[Thorwing]

ook de leaderboard maar ff gejoined, vandaag grote frustraties omdat de test input wel werkte, maar de echte niet. Bleek een recursieve fout te wezen achteraf.

Dag 7: https://github.com/mdekas.../main/kotlin/day7/Day7.kt

[Osxy]

Vandaag was vooral moeite in het parsen, wel leuke opdracht. Ik heb verre van de meest efficiente oplossing maar hij lost het nog steeds in 10ms op dus vind het prima.

Dag 7 in C#

[KabouterSuper]

Ik heb het vandaag (dag 7) maar even quick&dirty opgelost, met een klein foutje als gevolg

spoiler:

Ik maak gewoon absolute paden van de files en sommeer deze per dir met filter filename[0:len(dir)]==dir

Het foutje: initieel geen trailing slash gebruikt in de dirnaam.

[MatHack]

Dag 7 in C#

Eerste dag dat ik het antwoord voor deel 1 niet in één keer had, waarschijnlijk hadden @Thorwing en ik een soort gelijke fout, want de testdata werkte wel met mijn oplossing, maar de daadwerkelijke input niet. Uiteindelijk maar lelijker opgelost...

spoiler:

Liep vooral te stooien met de recursieve functies vandaag, gezien hoe lelijk ik uiteindelijk mijn oplossing heb gemaakt (class variabele ipv waarde in recursieve functie), vraag ik me af of een (do-)while loop oid niet een betere optie was voor de tree traversal...

[ Voor 14% gewijzigd door MatHack op 07-12-2022 21:23 . Reden: link toegevoegd ]

[P_Tingen]

Dit zit een beetje in mijn natuurlijke flow. Ons pakket leest orders van klanten in die ze via email sturen. We halen de bijlage eruit en parsen die op zoek naar orderregels, leverdatum en leveradres en dergelijke. Aangezien bijna alle klanten een eigen formaat hebben, hebben we 168 verschillende klant-specifieke inleesprogramma's, waarvan er minimaal 150 van mijn hand zijn. Dus parsen is wel iets wat me ligt. De oplossing kon ik dan ook vrij recht-to recht-aan erin rammen en Progress 4GL leent zich hier ook prima voor en lost beide op in 21ms

https://github.com/patric...ter/2022/Day-07/day-07a.p

[tarlitz]

jmerle schreef op woensdag 7 december 2022 @ 07:02:
Dag 7 in Python

spoiler:

De pathlib module was erg handig vandaag. Ik ben het meeste tijd verloren aan het niet opmerken dat sommige directories geen bestanden maar enkel subdirectories bevatten, en dat de groottes van al die subdirectories bij elkaar soms ook <= 100,000 is. Mijn eerste oplossing miste een regel code om die directories de juiste grootte te geven, waardoor ik steeds net te laag uit kwam op deel 1 (maar enkel op de volledige input, niet op het voorbeeld). Uiteindelijk heb ik de problematische code herschreven met een andere API en toen werkte het wel correct.

spoiler:

Hah, mooie oplossing, mijn eerste gedachte was ook meteen om pathlib te gebruiken, werkte prima! Het enige verschil is dat ik heb het parsen heb gedaan met pattern matching. Wellicht overkill, maar ik werk normaal met python 3.7, dus ik grijp elke mogelijkheid aan om nieuwe features toe te kunnen passen ;-)

[breew]

dag 07 in R

part 1 in 0.23 sec, part 2 in 0.02 (i5-4670 CPU @ 3.40GHz, 16GB)

[CMG]

Was een leuke vandaag 😊 code | video

[Jern_97]

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

23μs voor parsing + beide parts