Advent of Code 2023

[Litpho]

.oisyn schreef op maandag 4 december 2023 @ 10:40:
[...]


Sowieso, het enige dat je met de loten blijkbaar kunt winnen is nog meer loten

En de oud papier prijs is ook niet meer wat hij geweest is...

[TrailBlazer]

Litpho schreef op maandag 4 december 2023 @ 10:43:
[...]

En de oud papier prijs is ook niet meer wat hij geweest is...

mijn totaal aantal loten is ruim 8 miljoen. Als je 40 loten op een A4tje propt zijn dit 400 pakken A4 papier. :

[Ghehe]

TrailBlazer schreef op maandag 4 december 2023 @ 10:39:

spoiler:

ben benieuwd hoe eerlijk deze loten zijn want de laaste paar hebben nooit meer matches dan er totaal aan loten zijn.
card 189 has 2 matches
card 190 has 1 matches
card 191 has 0 matches

Dat is gewoon de implementatie van wat er in de opgave staat? "Cards will never make you copy a card past the end of the table."

[Dido]

TrailBlazer schreef op maandag 4 december 2023 @ 10:39:

spoiler:

ben benieuwd hoe eerlijk deze loten zijn want de laaste paar hebben nooit meer matches dan er totaal aan loten zijn.
card 189 has 2 matches
card 190 has 1 matches
card 191 has 0 matches

spoiler:

Dat werd inderdaad gewoon in de opgave vermeld.
Ergens wel een beetje jammer, was wel grappig geweest als je had moeten loopen naar ticket 1, en dan maar hopen dat er iets in de opgave verscholen zit om uit de oneindige loop te komen.
Of dat het geaccepteerde antwoord daadwerkelijk #NaN is, of zo

[Diderikdm]

Dido schreef op maandag 4 december 2023 @ 12:10:
[...]

spoiler:

Dat werd inderdaad gewoon in de opgave vermeld.
Ergens wel een beetje jammer, was wel grappig geweest als je had moeten loopen naar ticket 1, en dan maar hopen dat er iets in de opgave verscholen zit om uit de oneindige loop te komen.
Of dat het geaccepteerde antwoord daadwerkelijk #NaN is, of zo

spoiler:

Of hoeveel tickets missen er van de stapel? tickets * missing oid

[Varienaja]

Ik heb opgeschoond, mijn resultaat is toonbaar. Dag 4 in Java.

[Visitor.q]

Wat een onwijs leuke puzzel vandaag! Niet teveel hannessen met parsing enzo, maar gewoon gaan

Python

spoiler:

Ik heb (uiteraard?) recursie gebruikt, en kon fijn spelen met functools.cache om de boel te versnellen want nu bezoekt/processed hij de kaarten talloze keren.

De runtime ging van 59.56 seconden naar 0.0022 seconden

spoiler:

Het moet vast ook mogelijk zijn om alle kaarten slechts 1 keer te doorlopen en op basis van de uitkomst daarvan een sommetje te maken, maar ik ben er nog niet helemaal uit hoe dan

Ninja edit: ik was begonnen met het idee dat de winnende nummers verwezen naar de kaart nummer kopieën die je krijgt, maar toen dat niet het geval bleek

spoiler:

kon ik die hele card ID ook aan de kant gooien.

[ Voor 15% gewijzigd door Visitor.q op 04-12-2023 12:56 ]

[DataGhost]

Visitor.q schreef op maandag 4 december 2023 @ 12:54:
Wat een onwijs leuke puzzel vandaag! Niet teveel hannessen met parsing enzo, maar gewoon gaan

Python

spoiler:

Ik heb (uiteraard?) recursie gebruikt, en kon fijn spelen met functools.cache om de boel te versnellen want nu bezoekt/processed hij de kaarten talloze keren.

De runtime ging van 59.56 seconden naar 0.0022 seconden

spoiler:

Het moet vast ook mogelijk zijn om alle kaarten slechts 1 keer te doorlopen en op basis van de uitkomst daarvan een sommetje te maken, maar ik ben er nog niet helemaal uit hoe dan

spoiler:

Het aantal winnende getallen op een kaart verandert nooit

en

spoiler:

verder hoef je alleen maar te weten hoe vaak je een kaart krijgt, dat is puur afhankelijk van de kaarten erboven, geen andere kaarten.

[ProAce]

Veel te lang vastgezeten op part 2 door slecht lezen. Halverwege een gare recursieve implementatie er achter komen dat je het verkeerd begrepen hebt en het simpeler is dan het leek

https://github.com/ysmild...tree/master/pkg/2023/day4

[.oisyn]

Visitor.q schreef op maandag 4 december 2023 @ 12:54:

spoiler:

Het moet vast ook mogelijk zijn om alle kaarten slechts 1 keer te doorlopen en op basis van de uitkomst daarvan een sommetje te maken, maar ik ben er nog niet helemaal uit hoe dan

spoiler:

Twee manieren

1. Hou een tabelletje bij hoeveel kopieën je van een kaart moet hebben. Als je een winnende kaart hebt, dan tel je het aantal kopieën van die kaart (incl origineel) bij de kopieën van de N opeenvolgende kaarten.
2. Of, en dat is de manier die ik gebruik, hou een lijstje bij met hoeveel wins je nog hebt lopen, inclusief het aantal kopieën die voor die wins gezorgd hebben, en tel die af. Het aantal kopieën wat je van een kaart hebt is dan het origineel plus de som van alle aantallen kopieën in dat lijstje. Als een entry aftelt naar 0 dan haal je 'm weg

[fruitschaal2]

spoiler:

Zonder recursie in python.

Een class gemaakt met ID, winnende set en set van getallen. Daarna eenvoudig de intersection van elke set gepakt. Voor part 2 de lijst met card objecten omgezet naar een dictionary zodat je eenvoudig de aantallen kan optellen bij elke volgende kaart. (aantal is daarom toegevoegd als attribute met standaard waarde 1).

[code]
Function read_cards(<class 'list'>,): time elapsed: 2.718 [ms]
Function puzzle1(<class 'list'>,): time elapsed: 0.198 [ms]
Puzzle 1: 21568
Function puzzle2(<class 'list'>,): time elapsed: 0.295 [ms]
Puzzle 2: 11827296
Function main(): time elapsed: 5.420 [ms]
[/code]

[ Voor 65% gewijzigd door fruitschaal2 op 04-12-2023 13:25 ]

[BernardV]

spoiler:

Ook zonder recursie in PHP: https://github.com/BernardV/aoc2023/blob/main/day4/both.php

Ook geen multiplier gebruikt maar een bit shift, 1 << count-1 voor de punten.

[MatHack]

Mugwump schreef op maandag 4 december 2023 @ 09:57:
Nou mijn beroepseer is gered.

spoiler:

Het origineel
Total value: 5920640
Execution time 6.612145250s

De verbeterde versie
Total value: 5920640
Execution time 28.917291ms

Nog steeds niet helemaal blij met het gebruik van mutable datastructures, volgens mij kan het ook gewoon met recursief terugkijken oid.

Dat moet nog veel beter kunnen, mijn eerste versie van deel 2 runt in 2,5598ms en dat is in een VM waarvan ik van vorige jaren weet dat die een stukje trager is dan direct op het systeem draaien (en debug build).

[MueR]

Dag 4

spoiler:

Ook geen recursie. Kan vast efficiënter, maar daar kijk ik vanavond wel eens naar.. runtimes nog altijd onder de milliseconde, dus meh. Ik parse wel de input 2 keer (voor elke part los), dus er zou nog wat tijd af kunnen.
Part 1 output: (298.503µs)
Part 2 output: (301.656µs)

[ Voor 12% gewijzigd door MueR op 04-12-2023 14:26 ]

[P_Tingen]

KabouterSuper schreef op maandag 4 december 2023 @ 08:56:
Ziezo, vandaag ook weer klaar.

spoiler:

Net iets te lang bezig geweest met het bepalen wat de identifiers van de Cards waren om in deel 2 de volgende kaarten te identificeren. In het voorbeeld heet de eerste kaart "Card<spatie>1", maar in de echte set "Card<spatie><spatie><spatie>1". Ik had beter het regelnummer kunnen pakken als identifier in plaats van

int(line.split(':')[0].replace(' ','')[4:])

Godsamekrake, hier dus dezelfde fout. Ik sloeg zo ongeveer mijn monitor van het bureau omdat ik /wist/ dat het goed moest zijn, om er dan na veel te lang achter te komen dat ik dezelfde fout had gemaakt.

spoiler:

in mijn geval was de makkelijkste oplossing om als eerste stap alle >1 spaties te vervangen door 1 spatie te vervangen

[.oisyn]

spoiler:

Ik zoek gewoon 1 keer naar de ':', dan naar de '|', en dan naar de newline, en dan weet ik precies waar de getallen staan op elke regel.

218µs voor het hele ding trouwens.

[breew]

na ene kort nachtje dag 4 in 1x allebei goed.

https://github.com/wimpel...e2023/blob/main/r/day04.R

hier mijn R-benadering:

spoiler:

input splitsen in "kaart + nummers" en "kaart + winnende nummers"
daarna joinen op nummer en kaart.. je ziet dan direct welke nummers per kaart een winnend nummer zijn.
deel 1 en 2 antwoorden volgend dan vrij eenvoudig

[.oisyn]

Ik zit trouwens naar de personal leader board te kijken op https://adventofcode.com/2023/leaderboard/self, maar hoe moet ik die tijden interpreteren?

Het zijn geen absolute tijden, en ook niet de tijd sinds het publiceren van de puzzel.

.edit: ooh wacht, het is UTC+2 en een 12h clock. Waarom?!

[ Voor 11% gewijzigd door .oisyn op 04-12-2023 16:24 ]

[DataGhost]

Que? Het is de tijd na het beschikbaar komen van de opdracht van die dag.

[Gropah]

Nou dit was volgens mij wel een erg makkelijke opdracht in vergelijking met de vorige dagen. Was alsnog erg laat omdat ik niet voor het werk aan de slag kon. Als ik dit had geweten, had ik een kwartiertje eerder opgestaan... Was een stuk beter geweest voor mn rankings

.oisyn schreef op maandag 4 december 2023 @ 16:22:
Ik zit trouwens naar de personal leader board te kijken op https://adventofcode.com/2023/leaderboard/self, maar hoe moet ik die tijden interpreteren?

Het zijn geen absolute tijden, en ook niet de tijd sinds het publiceren van de puzzel.

.edit: ooh wacht, het is UTC+2 en een 12h clock. Waarom?!

Het is zoals DataGhost aangeeft de verstreken tijd sinds het vrijkomen van de puzzel.

[DataGhost]

Gropah schreef op maandag 4 december 2023 @ 16:32:
Nou dit was volgens mij wel een erg makkelijke opdracht in vergelijking met de vorige dagen. Was alsnog erg laat omdat ik niet voor het werk aan de slag kon. Als ik dit had geweten, had ik een kwartiertje eerder opgestaan... Was een stuk beter geweest voor mn rankings


[...]


Het is zoals DataGhost aangeeft de verstreken tijd sinds het vrijkomen van de puzzel.

De vrijdag- en weekend-opdrachten zijn meestal iets moeilijker dan het niveau de rest van de week, want dan hebben mensen doorgaans meer tijd. Nu begon het toevallig op vrijdag waardoor het al wat moeilijker leek te beginnen. Dus dat deze wat makkelijker zou zijn lag opzich wel voor de hand, alleen het leeswerk was nog wel belangrijk

[.oisyn]

DataGhost schreef op maandag 4 december 2023 @ 16:25:
Que? Het is de tijd na het beschikbaar komen van de opdracht van die dag.

Daar klopt in mijn geval niets van. Als ik kijk naar mijn git commits, die ik vrij vlak na het indienen van de tweede deel heb gemaakt, dan komt dat niet overeen met de looptijd van de puzzel. Die worden toch om 6:00 lokale tijd gepubliceerd?

EDIT: Oh allejezus. De dagen tellen *af* in het lijstje

[ Voor 56% gewijzigd door .oisyn op 04-12-2023 16:44 ]

[DataGhost]

Je weet toch dat je goed moet lezen bij AoC

[Diderikdm]

spoiler:

je kan ook de line splitten en zoeken naar een str.count(x) == 2 (gedeeld door twee ivm paartjes), als het goed is zijn er geen dubbele waarden in zowel winning als je eigen, en de kaarten zelf hebben een ":" eraan vast.

Obscure oneliner omdat het kan:

print((a,sum(b))if not(a:=0)and(b:=[1]*len(c:=open("day04.txt","r").read(
).splitlines()))and[x for e,x in enumerate(c)if(a:=a+(1<<(s:=sum(x.split(
).count(y)== 2 for y in{*x.split()}if y))>>1))and[b.insert(d,b.pop(d)+1*b[e]
)for d in range(e+1,e+s+1)]]else 0)

[ Voor 47% gewijzigd door Diderikdm op 04-12-2023 17:52 ]

[Mugwump]

MatHack schreef op maandag 4 december 2023 @ 13:39:
[...]


Dat moet nog veel beter kunnen, mijn eerste versie van deel 2 runt in 2,5598ms en dat is in een VM waarvan ik van vorige jaren weet dat die een stukje trager is dan direct op het systeem draaien (en debug build).

Ik draai het gewoon vanuit mijn IDE, maar je kunt talen ook niet zo maar vergelijken. Qua parsen van de file doe ik ongeveer hetzelfde als jij en dat kost al zo'n 16ms.

[Kazu]

Wat een absolute puinzooi vandaag Na twee dagen geen tijd vandaag wel genoeg om in ieder geval deel 1 en 2 te doen.

https://github.com/Unreal...n/day4-second/src/main.rs

spoiler:

Ik ben echt dom bezig geweest. Om een of andere reden bleef ik hangen bij hashmaps, terwijl ik het bepalen van de intersect ook gewoon letterlijk met sets had kunnen doen (geen idee waarom dat nieteens in me op is gekomen). Vervolgens bij part 2 het gebruik van de hashmap doorgetrokken in m'n recursive oplossing, omdat ik niet stilstond dat ik die traceability helemaal niet nodig heb .

Vandaag was een groot gevalletje tunnelvisie, gemixt met nog wat meer stoeien met Rust, waardoor mijn code echt om te huilen is

spoiler:

Running time is 464ms, wat waarschijnlijk voor een groot deel komt door mijn inefficiënte manier van het splitsen van de slice, wat wederom niet nodig was. Het valt me wel op, gezien de andere oplossingen, dat ik een van de weinige ben geweest die het opsplitsen van de regels via regex heb gedaan.

[Woy]

Zo ik heb dag 3 en 4 ook opgelost

https://github.com/rverst.../blob/main/Y2023/Day03.cs
https://github.com/rverst.../blob/main/Y2023/Day04.cs

Dag 4 was weer erg makkelijk, dag 3 moest ik even over nadenken hoe het op te lossen. Op zich is het probleem niet zo lastig, maar de code werd als snel wat minder leesbaar

[.oisyn]

Kazu schreef op maandag 4 december 2023 @ 17:54:
Wat een absolute puinzooi vandaag Na twee dagen geen tijd vandaag wel genoeg om in ieder geval deel 1 en 2 te doen.

https://github.com/Unreal...n/day4-second/src/main.rs

spoiler:

Ik ben echt dom bezig geweest. Om een of andere reden bleef ik hangen bij hashmaps, terwijl ik het bepalen van de intersect ook gewoon letterlijk met sets had kunnen doen (geen idee waarom dat nieteens in me op is gekomen). Vervolgens bij part 2 het gebruik van de hashmap doorgetrokken in m'n recursive oplossing, omdat ik niet stilstond dat ik die traceability helemaal niet nodig heb .

spoiler:

Ik gebruik gewoon een u128 als bitset

[Kazu]

.oisyn schreef op maandag 4 december 2023 @ 18:23:
[...]

spoiler:

Ik gebruik gewoon een u128 als bitset

spoiler:

Ik zag het, ja. Veel makkelijker en sneller

[Soultaker]

Woy schreef op maandag 4 december 2023 @ 17:59:
https://github.com/rverst.../blob/main/Y2023/Day04.cs

Wel bijzonder dat je eerst de kaartnummers in de invoer weggooit onder de (correcte) aanname dat ze simpelweg van 1 to N lopen, dan vervolgens in SolvePart2() een dictionary maakt. Dat kan dan net zo goed een simpele array van integers zijn.

[Woy]

Soultaker schreef op maandag 4 december 2023 @ 18:33:
[...]

Wel bijzonder dat je eerst de kaartnummers in de invoer weggooit onder de (correcte) aanname dat ze simpelweg van 1 to N lopen, dan vervolgens in SolvePart2() een dictionary maakt. Dat kan dan net zo goed een simpele array van integers zijn.

Ja dat besefte ik mij ook, maar had geen zin meer om het aan te passen.

[gedonie]

Na een hele daq moeten vergaderen maar even snel tussendoor gedaan. Maar dag 4 in Java is dan toch eindelijk af.

Deel 2 was op zich een makkie als je voor deel 1 al gelijk een goede data structuur kiest.

[rengeltje]

KabouterSuper schreef op maandag 4 december 2023 @ 08:56:
Ziezo, vandaag ook weer klaar.

spoiler:

Net iets te lang bezig geweest met het bepalen wat de identifiers van de Cards waren om in deel 2 de volgende kaarten te identificeren. In het voorbeeld heet de eerste kaart "Card<spatie>1", maar in de echte set "Card<spatie><spatie><spatie>1". Ik had beter het regelnummer kunnen pakken als identifier in plaats van

int(line.split(':')[0].replace(' ','')[4:])

Ja, stoeien met replace en indices is nooit leuk. Gewoon doorgaan met split() en strip(), simpel en robuust:

int(line.split(':')[0].split()[-1].strip())

Overigens is strip() niet eens nodig bij int(), die slurpt whitespace zelf wel weg zolang er maar iets wat op een integer lijkt komt (ooit).

[Varienaja]

gedonie schreef op maandag 4 december 2023 @ 18:56:
Na een hele daq moeten vergaderen maar even snel tussendoor gedaan. Maar dag 4 in Java is dan toch eindelijk af.

Deel 2 was op zich een makkie als je voor deel 1 al gelijk een goede data structuur kiest.

Nice. Maar ik begrijp de keuze voor Math.Min() niet. Daar zou een assert of een throws moeten staan. Dan vind je de eventuele problemen ipv dat je ze moeizaam debuggen moet. Je kunt zelfs helemaal niks defensief programmeren, dan gooit Java zelf wel een OutOfBounds.
Gelukkig is AoC lief en geeft altijd heel consistente input, zodat dit allemaal niet uitmaakt in dit geval.

[ Voor 6% gewijzigd door Varienaja op 04-12-2023 19:30 ]

[Creepy]

En dag 4 ook klaar.

spoiler:

Recursie? Ik loop twee keer door het geheel heen. 1 keer door de input en hou vervolgens het aantal winnende getallen bij per kaart. En de tweede loop door alle kaarten en dan bij de opvolgende kaarten optellen met 1 x het aantal wins van de huidige kaart. Klaar.

En strings.Fields() ontdekt in Go, fixt gelijk alle ellende met whitespaces

https://github.com/CodeEn...23/blob/main/days/Day4.go

[ Voor 20% gewijzigd door Creepy op 04-12-2023 22:59 ]

[gedonie]

Varienaja schreef op maandag 4 december 2023 @ 19:27:
[...]

Nice. Maar ik begrijp de keuze voor Math.Min() niet. Daar zou een assert of een throws moeten staan. Dan vind je de eventuele problemen ipv dat je ze moeizaam debuggen moet. Je kunt zelfs helemaal niks defensief programmeren, dan gooit Java zelf wel een OutOfBounds.
Gelukkig is AoC lief en geeft altijd heel consistente input, zodat dit allemaal niet uitmaakt in dit geval.

De Math.min of eigenlijk de out of bounds kan optreden als een van de latere kaarten bijvoorbeeld meer goede nummers heeft dan dat er nog kaarten over zijn in de lijst, of dat zo is bij de input heb ik niet gecontroleerd. Maar dat is gezien het verhaal van vandaag niet uitgesloten.

[Creepy]

gedonie schreef op maandag 4 december 2023 @ 20:17:
[...]


De Math.min of eigenlijk de out of bounds kan optreden als een van de latere kaarten bijvoorbeeld meer goede nummers heeft dan dat er nog kaarten over zijn in de lijst, of dat zo is bij de input heb ik niet gecontroleerd. Maar dat is gezien het verhaal van vandaag niet uitgesloten.

Dat is gezien het verhaal van vandaag wel uitgesloten

Cards will never make you copy a card past the end of the table.

[MatHack]

gedonie schreef op maandag 4 december 2023 @ 20:17:
[...]


De Math.min of eigenlijk de out of bounds kan optreden als een van de latere kaarten bijvoorbeeld meer goede nummers heeft dan dat er nog kaarten over zijn in de lijst, of dat zo is bij de input heb ik niet gecontroleerd. Maar dat is gezien het verhaal van vandaag niet uitgesloten.

Dat er geen kaarten buiten de set zullen vallen staat letterlijk in de tekst van vandaag:

(Cards will never make you copy a card past the end of the table.)

[Varienaja]

gedonie schreef op maandag 4 december 2023 @ 20:17:
[...]


De Math.min of eigenlijk de out of bounds kan optreden als een van de latere kaarten bijvoorbeeld meer goede nummers heeft dan dat er nog kaarten over zijn in de lijst, of dat zo is bij de input heb ik niet gecontroleerd. Maar dat is gezien het verhaal van vandaag niet uitgesloten.

Dat begrijp ik wel. Maar ik begrijp niet dat je zelf en vrijwillig een bug inprogrammeert, waardoor je een fout antwoord gaat genereren bij rare invoer. Ik zou liever het feit dat de invoer inconsistent is luid en duidelijk de wereld in slingeren.

[vDorst]

That means card 1 is worth 8 points (1 for the first match, then doubled three times for each of the three matches after the first).

Ben ik de enige die niet snap wat ik hier moet doen?
Parsen en zoeken op dubbelen was een eitje maar ik snapte niet hoe de scoring nu werkte.
Door de spieken bij anderen kon ik pas door.

Deel 2 was goed te doen.

[Varienaja]

Het staat er precies. Met 4 overeenkomsten dus:
1 punt voor de eerste overeenkomst
*2 voor de tweede
*2 voor de derde
*2 voor de vierde

1*2*2*2 = 8

Wiskundig is dit simpelweg 2 ^ (aantal_overeenkomsten - 1)

[ Voor 16% gewijzigd door Varienaja op 04-12-2023 21:08 ]

[TrailBlazer]

Varienaja schreef op maandag 4 december 2023 @ 20:53:
Het staat er precies. Met 4 overeenkomsten dus:
1 punt voor de eerste overeenkomst
*2 voor de tweede
*2 voor de derde
*2 voor de vierde

1*2*2*2 = 8

Wiskundig is dit simpelweg 2 ^ (aantal_overeenkomsten - 1)

niet helemaal want bij nul overeenkomsten zou je met deze formule op 1/2 uitkomen daar moet je dus wat voor regelen.

[Varienaja]

TrailBlazer schreef op maandag 4 december 2023 @ 21:39:
[...]

niet helemaal want bij nul overeenkomsten zou je met deze formule op 1/2 uitkomen daar moet je dus wat voor regelen.

Dat is waar.

[ Voor 7% gewijzigd door Varienaja op 04-12-2023 21:54 ]

[.oisyn]

Varienaja schreef op maandag 4 december 2023 @ 21:53:
[...]

Nee hoor. 2 tot de macht 0 is namelijk 1.

Ja, maar 2 tot de macht -1 is 0,5, en dat krijg je bij 0 winnende getallen als je daar niet expliciet op controleert

[ Voor 3% gewijzigd door .oisyn op 04-12-2023 22:02 ]

[breew]

.oisyn schreef op maandag 4 december 2023 @ 21:54:
[...]

Ja, maar 2 tot de macht -1 is 0,5, en dat krijg je bij 0 winnende getallen als je daar niet expliciet op controleert

lelijke oplossing: omlaag afronden op integer

[.oisyn]

Wat niet gaat werken als je bitshift

[breew]

.oisyn schreef op maandag 4 december 2023 @ 22:17:
Wat niet gaat werken als je bitshift

ik weet niet wat dat is ;-), maar ik ga het opzoeken.
daarom werk ik waarschijnlijk in R in plaats van 'echt' programmeren .

[Camulos]

Even inhaalslag gemaakt en meteen dag 2 tm 4 gedaan

Niet zo kort en krachtig als @Woy, maar zeker wel leesbaar/verbose en run snel (300ms)

https://github.com/flutte...tOfCode/Year2023/Day04.cs

[Varienaja]

Wauw. Dag 5, onderdeel 2 ga ik niet afkrijgen voordat ik weg moet.

Edit 1: Maar..... ik heb wél een idee gekregen. Dat is voor in de trein zometeen.

Edti 2: Tóch nog kunnen implementeren voordat ik weg moet. Woei!

[ Voor 58% gewijzigd door Varienaja op 05-12-2023 06:55 ]

[TrailBlazer]

Nog niet echt begonnen maar waarom is de volgorde destination source range. Ipv source destination range. Klopt gewoon niet in mijn hoofd.

Helemaal omdat de tekst wel source dest is.

[ Voor 14% gewijzigd door TrailBlazer op 05-12-2023 08:18 ]

[Mugwump]

TrailBlazer schreef op dinsdag 5 december 2023 @ 08:15:
Nog niet echt begonnen maar waarom is de volgorde destination source range. Ipv source destination range. Klopt gewoon niet in mijn hoofd.

Om je leesvaardigheid op de vroege ochtend te testen.
Maar inderdaad, daar las ik ook bijna overeen.

spoiler:

Beiden opgelost met een vrij domme iteratie over alle seeds. Wel correcte antwoord, deel 2 alleen enorm traag natuurlijk. Nu even kijken of ik een meer algoritmische aanpak kan vinden voor zover het werk het toelaat.

[Litpho]

Even knutselen om het onderliggende model goed te krijgen, maar daarna waren zowel deel 1 als deel 2 redelijk simpel met een brute force. Deel 1 in de microseconden, deel 2 aanzienlijk langzamer. Daar mag nog wel een slim laagje overheen.

[MatHack]

Deel 1 was voornamelijk parsen, de oplossing was daarna vrij simpel te vinden. Deel 2 koste iets meer moeite (maar is geen brute-force, kost 3 ms).

spoiler:

In eerste instantie ook brute-force geprobeerd (deel1, maar dan met een grote lijst seeds), maar kreeg een out-of-memory exception (zit op een VM met 8GB RAM te werken). Dus toen toch maar range overlaps gebouwd. Kost me altijd redelijk wat denkwerk, maar het werkt wel binnen een maar milliseconden.

https://github.com/realma...de.Y2023/Solvers/Day05.cs

[ Voor 6% gewijzigd door MatHack op 05-12-2023 09:46 . Reden: taalvauten ]

[mbe81]

MatHack schreef op dinsdag 5 december 2023 @ 08:41:
Deel 1 was voornamelijk parsen, de oplossing was daarna vrij simpel te vinden. Deel 2 koste iets meer moeite (maar is geen brute-force).

spoiler:

In eerste instantie ook brute-force geprobeerd (deel1, maar dan met een grote lijst seeds), maar kreeg een out-of-memory exception (zit op een VM met 8GB RAM te werken). Dus toen toch maar range overlaps gebouwd. Kost me altijd redelijk wat denkwerk, maar het werkte wel binnen een maar milliseconden.

https://github.com/realma...de.Y2023/Solvers/Day05.cs

Jouw oplossing ga ik dan zeker bekijken! Ik heb nu ook gewoon een nested loop maar snel is het niet. Wel goed ;-)

Edit: deel 2 kost mij nu 3,5 minuut...

[eheijnen]

@TrailBlazer
Misschien doen ze dat om de opdracht een beetje lastiger te maken en je noopt om de tekst goed door te nemen, Maar wat maakt het uit als je de juiste volgorde weet...?

[ Voor 4% gewijzigd door eheijnen op 05-12-2023 08:53 ]

[FCA]

So, deel 2 is een pittige

spoiler:

Heb uiteindelijk maar gewoon een range checker/splitter gebouwd, ik zag met die hoeveelheid seeds het niet zitten om het brute-force te doen. Hij draait wel lekker snel: 5ms, in Python nog wel Eerst nog even overwogen om een backwards binary search te doen, maar dat zag ik toch niet zitten, hoewel dat dan wel de volgorde van de input zou volgen

[P_Tingen]

FCA schreef op dinsdag 5 december 2023 @ 09:17:
So, deel 2 is een pittige

spoiler:

Heb uiteindelijk maar gewoon een range checker/splitter gebouwd, ik zag met die hoeveelheid seeds het niet zitten om het brute-force te doen. Hij draait wel lekker snel: 5ms, in Python nog wel Eerst nog even overwogen om een backwards binary search te doen, maar dat zag ik toch niet zitten, hoewel dat dan wel de volgorde van de input zou volgen

spoiler:

Ehm, hoe/wat werkt een "range checker/splitter"? Heb je dan meerdere threads of hoe werkt dat? Ik zit nu tegen een brute-force poging aan te kijken die al een kwartier draait en nog niet klaar is met de eerste conversie van seed-to-soil .... (lang leve een 4GL)

Edit: de ranges overlappen elkaar natuurlijk. Als je dat er uit filtert, scheelt dat aanzienlijk werk. Ben alleen bang dat mijn 4GL dat nog steeds niet trekt. Ik heb hem nu afgebroken, na 20 min nog niet halverwege de eerste conversie van de eerste range. Die gaat niet finishen zo voor kerst

[ Voor 16% gewijzigd door P_Tingen op 05-12-2023 09:27 ]

[Soultaker]

Het was helemaal niet in me opgekomen om dag 5 deel 2 te bruteforcen... achteraf gezien had het waarschijnlijk wel gekund, maar dan had ik van Python moeten overstappen naar een snellere taal als C++.

De testdata was ook niet zo gemeen als 'ie had kunnen zijn. Voor wie z'n code wil benchmarken hier iets moeilijkere invoer:

1. medium.in (31 bits integers nodig)
2. large.in (63 bits integers nodig)

[ Voor 2% gewijzigd door Soultaker op 05-12-2023 10:08 . Reden: Data sets geüpdated ]

[MatHack]

Soultaker schreef op dinsdag 5 december 2023 @ 09:27:
Het was helemaal niet in me opgekomen om dag 5 deel 2 te bruteforcen... achteraf gezien had het waarschijnlijk wel gekund, maar dan had ik van Python moeten overstappen naar een snellere taal als C++.

De testdata was ook niet zo gemeen als 'ie had kunnen zijn. Voor wie z'n code wil benchmarken hier iets moeilijkere invoer:

1. medium.in (31 bits integers nodig)
2. large.in (63 bits integers nodig)

10012ms (~10sec) voor de medium set
De large set vindt mijn oplossing niet leuk (parse error naar datatype), ook al heb ik al overal Int64 (.NET) gebruikt.

[Soultaker]

MatHack schreef op dinsdag 5 december 2023 @ 09:51:
10012ms (~10sec) voor de medium set

Niet slecht! Maar het kan sneller.

De large set vindt mijn oplossing niet leuk (parse error naar datatype), ook al heb ik al overal Int64 (.NET) gebruikt.

Ah, my bad. Ik had inderdaad te grote getallen in beide invoerbestanden staan. Ik heb het gefixt (en de links aangepast).

[.oisyn]

Zo, dag5 ook klaar.

code:

Time spent: 210.1µs

Wat bedoelen jullie met "brute-forcen"?

[.oisyn]

Soultaker schreef op dinsdag 5 december 2023 @ 09:27:

1. medium.in (31 bits integers nodig)
2. large.in (63 bits integers nodig)

Die sets mappen allemaal seeds op dezelfde destination. Klopt dat wel?

[MatHack]

Soultaker schreef op dinsdag 5 december 2023 @ 10:10:
[...]

Niet slecht! Maar het kan sneller.

Haha, natuurlijk kan dat sneller, ik zit op een niet optimale dev-omgeving (VM) in een niet-optimale taal/platform (C#/.NET) dit te bouwen. Voor de snelheid zal je sowieso iets als C++/Rust/Kotlin moeten hebben. Helaas moet ik aan de slag voor de studie, dus het blijft hier van mijn kant even bij.

[P_Tingen]

Damn, ik heb een goede oplossing voor deel 2 in mijn trage 4GL: 2 msec. Eat that, bitches!

spoiler:

De crux is om andersom te werken. Je begint met de location en werkt dan terug naar de seed. Begin bij location 1, reken terug naar de seed en check of die in de mapping voorkomt.

Dit duurt natuurlijk nog retelang, dus bouw je daar een lus omheen waarin je met grote stappen er doorheen gaat. Ik begin met stapgrootte 10.000.000. Als ik dan een match vind, trek ik de stapgrootte van de location af waar ik mee begonnen ben (omdat ik anders te hoog zit), deel de stapgrootte door 10 en doe het nog een keer. Uiteindelijk vind je zo in een paar stappen het goede antwoord.

Oplossing in Progress 4GL. Zal voor de meesten even wennen zijn, maar het is goed leesbaar. De magic begint ongeveer halverwege. Daarvoor is het inlezen en parsen van de data.

https://github.com/patric...ter/2023/Day-05/day-05b.p

[Mugwump]

MatHack schreef op dinsdag 5 december 2023 @ 10:26:
[...]


Haha, natuurlijk kan dat sneller, ik zit op een niet optimale dev-omgeving (VM) in een niet-optimale taal/platform (C#/.NET) dit te bouwen. Voor de snelheid zal je sowieso iets als C++/Rust/Kotlin moeten hebben. Helaas moet ik aan de slag voor de studie, dus het blijft hier van mijn kant even bij.

Kotlin is gewoon een JVM taal die verder niet significant sneller draait dan Java, absoluut niet te vergelijken met talen als C++ of Rust, eerder met C#.

[Soultaker]

.oisyn schreef op dinsdag 5 december 2023 @ 10:19:
Die sets mappen allemaal seeds op dezelfde destination. Klopt dat wel?

Dat was het idee inderdaad; de probleemomschrijving garandeert niet dat doelbereiken niet kunnen overlappen.

P_Tingen schreef op dinsdag 5 december 2023 @ 10:28:

spoiler:

De crux is om andersom te werken. Je begint met de location en werkt dan terug naar de seed. Begin bij location 1, reken terug naar de seed en check of die in de mapping voorkomt.

Dit duurt natuurlijk nog retelang, dus bouw je daar een lus omheen waarin je met grote stappen er doorheen gaat. Ik begin met stapgrootte 10.000.000. Als ik dan een match vind, trek ik de stapgrootte van de location af waar ik mee begonnen ben (omdat ik anders te hoog zit), deel de stapgrootte door 10 en doe het nog een keer. Uiteindelijk vind je zo in een paar stappen het goede antwoord.

spoiler:

Dit is vergelijkbaar met de binary search die @FCA ook noemde, maar dat werkt toch niet in z'n algemeenheid? De mogelijke outputs zijn niet een continue bereik; er kunnen allerlei gaten in zitten. Dus met individuele steekproeven kun je geen begin vinden. Bijvoorbeeld, als je precies 1 seed hebt die op locatie 42 terecht komt. Hoe vind je die dan?

[.oisyn]

Soultaker schreef op dinsdag 5 december 2023 @ 10:57:
[...]

Dat was het idee inderdaad; de probleemomschrijving garandeert niet dat doelbereiken niet kunnen overlappen.

Vooruit dan maar.

code: large.in

1234567890987654321 1234567890987654321
Time spent: 272.4µs

[ Voor 37% gewijzigd door .oisyn op 05-12-2023 12:03 . Reden: copy-paste error in het antwoord ;) ]

[FCA]

Soultaker schreef op dinsdag 5 december 2023 @ 10:57:
[...]

Dat was het idee inderdaad; de probleemomschrijving garandeert niet dat doelbereiken niet kunnen overlappen.


[...]

spoiler:

Dit is vergelijkbaar met de binary search die @FCA ook noemde, maar dat werkt toch niet in z'n algemeenheid? De mogelijke outputs zijn niet een continue bereik; er kunnen allerlei gaten in zitten. Dus met individuele steekproeven kun je geen begin vinden. Bijvoorbeeld, als je precies 1 seed hebt die op locatie 42 terecht komt. Hoe vind je die dan?

spoiler:

Nee, binary search gaat inderdaad niet werken (vroeg/duf hoofd, etc.), en zo'n search met steeds kleinere stappen heeft inderdaad ook geen garantie (alhoewel, je kunt natuurlijk iets zeggen over het aantal intervallen wat je maximaal hebt, over een bepaalde mogelijke range, dus wie weet..), maar vaak is de input, zeker in de eerste paar dagen, niet al te pathologisch gekozen, dus kom je er nog wel mee weg hier.

P_Tingen schreef op dinsdag 5 december 2023 @ 09:21:
[...]

spoiler:

Ehm, hoe/wat werkt een "range checker/splitter"? Heb je dan meerdere threads of hoe werkt dat? Ik zit nu tegen een brute-force poging aan te kijken die al een kwartier draait en nog niet klaar is met de eerste conversie van seed-to-soil .... (lang leve een 4GL)

Edit: de ranges overlappen elkaar natuurlijk. Als je dat er uit filtert, scheelt dat aanzienlijk werk. Ben alleen bang dat mijn 4GL dat nog steeds niet trekt. Ik heb hem nu afgebroken, na 20 min nog niet halverwege de eerste conversie van de eerste range. Die gaat niet finishen zo voor kerst

spoiler:

Je begint met de input-ranges. Dan kijk je waar die overlappen met de 1e source-ranges en map je die overlappen naar de destination range (dus als je input van 10-17 is, je eerste source range van 9-14 is, en de destination van 2 - 7 is, dan wordt dat dus naar 3-7 en houd je 15 - 17 over). De restanten map je naar zichzelf (wat ik heb gedaan is de source-ranges opvullen met "triviale" maps, zodat ik wat randgevallen niet hoefde te checken). Zo itereer je door de maps heen, totdat je bij het eind bent.

Tussendoor elke keer de ranges en de source-ranges sorteren, anders blijf je bezig met zoeken.
Ik heb geen merges van ranges gedaan als ze overlapten, dat zou het nog wat sneller kunnen maken.

[Diderikdm]

Python - d5

Poef, is nog wel wat te refactoren/combineren aan deze boemerang denk ik.

Beide parts runnen wel in ~8 ms

spoiler:

Zat heel lang te stoeien met wat nou min wat en wat plus wat, example bleef natuurlijk wel werken..

[ Voor 6% gewijzigd door Diderikdm op 05-12-2023 11:55 ]

[Remcoder]

Mugwump schreef op dinsdag 5 december 2023 @ 10:47:
[...]


Kotlin is gewoon een JVM taal die verder niet significant sneller draait dan Java, absoluut niet te vergelijken met talen als C++ of Rust, eerder met C#.

Waarom blijven mensen toch vasthouden aan het beeld dat de JVM perse trager is dan C++? Er zijn al meerdere onderzoeken gedaan, en er zijn tegenwoordig veel gevallen waarbij de JVM net zo goed presteert als rauwe C++/C code.

[.oisyn]

Remcoder schreef op dinsdag 5 december 2023 @ 11:53:
[...]

Waarom blijven mensen toch vasthouden aan het beeld dat de JVM perse trager is dan C++? Er zijn al meerdere onderzoeken gedaan, en er zijn tegenwoordig veel gevallen waarbij de JVM net zo goed presteert als rauwe C++/C code.

Hoe is Java met SIMD intrinsics en cache locality?

[Remcoder]

.oisyn schreef op dinsdag 5 december 2023 @ 12:02:
[...]

Hoe is Java met SIMD intrinsics en cache locality?

De specifics ervan weet ik niet, maar een snelle search leert me dat Java hier support voor heeft.

[Mugwump]

Remcoder schreef op dinsdag 5 december 2023 @ 11:53:
[...]

Waarom blijven mensen toch vasthouden aan het beeld dat de JVM perse trager is dan C++? Er zijn al meerdere onderzoeken gedaan, en er zijn tegenwoordig veel gevallen waarbij de JVM net zo goed presteert als rauwe C++/C code.

Dat zeg ik ook niet. Ik zeg dat Kotlin niet sneller is dan Java omdat het op de JVM draait. Degene waar ik op reageer werkt in C# en contrasteert C# met talen als Kotlin / C++ / Rust, terwijl qua werking JVM talen meer lijken op talen uit de .Net wereld.
Laten we ook wel wezen, in het gros van de applicaties waar mensen hier hoogstwaarschijnlijk aan werken is het al veel als 10% van de doorlooptijd van acties in je systeem bestaat uit compute in je code (ipv netwerkverkeer, database queries, enz).

Ik denk wel dat je bij complexe algoritmische problemen met talen als Rust / C++ nog net wat meer performance kunt halen, al hangt dat ook af van wat je hoe implementeert. Ik ben lang niet zo hardcore als @.oisyn wat dat betreft.

[P_Tingen]

FCA schreef op dinsdag 5 december 2023 @ 11:35:
[...]

spoiler:

Je begint met de input-ranges. Dan kijk je waar die overlappen met de 1e source-ranges en map je die overlappen naar de destination range (dus als je input van 10-17 is, je eerste source range van 9-14 is, en de destination van 2 - 7 is, dan wordt dat dus naar 3-7 en houd je 15 - 17 over). De restanten map je naar zichzelf (wat ik heb gedaan is de source-ranges opvullen met "triviale" maps, zodat ik wat randgevallen niet hoefde te checken). Zo itereer je door de maps heen, totdat je bij het eind bent.

Tussendoor elke keer de ranges en de source-ranges sorteren, anders blijf je bezig met zoeken.
Ik heb geen merges van ranges gedaan als ze overlapten, dat zou het nog wat sneller kunnen maken.

Dank voor deze uitleg, maar ik snap er nog steeds geen kont van. Als je zin en tijd hebt hou ik me aanbevolen voor een uitgebreidere uitleg voor dummies

[.oisyn]

Remcoder schreef op dinsdag 5 december 2023 @ 12:10:
[...]

De specifics ervan weet ik niet, maar een snelle search leert me dat Java hier support voor heeft.

Ah wat ik vond was dat de Vector API nog niet af was, maar dat is het nu wel? Cache locality blijft een ding, je hebt in de JVM geen expliciete keuze voor value-type objects, of is dat er inmiddels ook? Je moet dan maar hopen dat references niet daadwerkelijk references blijven.

[.oisyn]

P_Tingen schreef op dinsdag 5 december 2023 @ 12:20:
[...]

Dank voor deze uitleg, maar ik snap er nog steeds geen kont van. Als je zin en tijd hebt hou ik me aanbevolen voor een uitgebreidere uitleg voor dummies

spoiler:

Stel je hebt een range mapping M van a..b naar x..y, en je hebt een range R van p..q. Dan wil je kijken welk deel van R overlapt met M, en specifiek die overlap wil je remappen. Dan krijg je te maken met 6 verschillende cases

#1 en #2: geen overlap: b<p || q<a
a====M====b
              p====R===q


             a====M====b
p====R===q

#3: p valt in de mapping, q niet
a====M====b
       p====R===q
       
#4: q valt in de mapping, p niet
     a====M====b
p====R===q
       
#5: zowel p als q vallen binnen de mapping
       a====M====b
         p==R==q

#6: de mapping valt volledig binnen de range, maar p en q zelf niet
       a==M==b
    p=====R====q

Bij geen overlap blijft de oorspronkelijke range natuurlijk gelijk.
In geval van #3 wordt het begin van R regemapped, maar het einde hou je over om verder te checken
#4 is als #3, maar dan wordt juist het einde geremapped en het begin hou je over
Bij #5 wordt de volledige range geremapped
Bij #6 wordt het midden van de range geremapped. Het begin en het eind hou je over.

En nu ik dit typ realiseer ik me dat ik #6 ben vergeten te implementeren . Maakt blijkbaar niet uit voor het eindresultaat.

[Diderikdm]

P_Tingen schreef op dinsdag 5 december 2023 @ 12:20:
[...]

Dank voor deze uitleg, maar ik snap er nog steeds geen kont van. Als je zin en tijd hebt hou ik me aanbevolen voor een uitgebreidere uitleg voor dummies

spoiler:

Mijn code doet dit toevallig ook, misschien kan je het daaruit herleiden?

[Remcoder]

.oisyn schreef op dinsdag 5 december 2023 @ 12:20:
[...]


Ah wat ik vond was dat de Vector API nog niet af was, maar dat is het nu wel? Cache locality blijft een ding, je hebt in de JVM geen expliciete keuze voor value-type objects, of is dat er inmiddels ook? Je moet dan maar hopen dat references niet daadwerkelijk references blijven.

Value type objects zijn er ook tegenwoordig voor Java. Daar zitten wel een aantal regels aan vast, zoals dat je niet meer afhankelijk mag zijn van reference equality, maar enkel de object equality mag gebruiken.

Java gaat snel tegenwoordig

[Mugwump]

.oisyn schreef op dinsdag 5 december 2023 @ 12:20:
[...]


Ah wat ik vond was dat de Vector API nog niet af was, maar dat is het nu wel? Cache locality blijft een ding, je hebt in de JVM geen expliciete keuze voor value-type objects, of is dat er inmiddels ook? Je moet dan maar hopen dat references niet daadwerkelijk references blijven.

Nee. Je hebt inmiddels records in Java. Dat lijken ogenschijnlijk value-type objects, maar het blijven references.

Edit: Oh remcoder heeft gelijk. Je hebt ook ValueTypes tegenwoordig natuurlijk.

[ Voor 7% gewijzigd door Mugwump op 05-12-2023 12:57 ]

[P_Tingen]

.oisyn schreef op dinsdag 5 december 2023 @ 12:34:
[...]
(blok code)

Dank voor de uitleg! Nu snap ik wat je bedoelt inderdaad.

@Diderikdm Tnx, duidelijk!

[Soultaker]

Remcoder schreef op dinsdag 5 december 2023 @ 12:54:
Value type objects zijn er ook tegenwoordig voor Java.

Bron?

En kun je dan ook een ArrayList<MyValueType> alloceren waarbij de data in contiguous memory staat (zoals in C++ al 30 jaar kan met std::vector<>) in plaats van een array van pointers naar heap-allocated objects met behoorlijke overhead, zoals tot nu toe het geval was?

[FCA]

P_Tingen schreef op dinsdag 5 december 2023 @ 13:02:
[...]

Dank voor de uitleg! Nu snap ik wat je bedoelt inderdaad.

@Diderikdm Tnx, duidelijk!

Fijn, mijn uitleg was ook erg gaar... nog steeds last van de griep, ik kan de oplossing wel coderen op intuitie, maar uitleggen, ho maar

[Camulos]

Jemig wat een opgave met dag 5!

Eerste was easy-peasy met binnen aantal ms opgelost..
de 2e stuk gewoon bruteforce, na 36 minuten kwam het juiste antwoord eruit

[Remcoder]

Soultaker schreef op dinsdag 5 december 2023 @ 13:17:
[...]

Bron?

En kun je dan ook een ArrayList<MyValueType> alloceren waarbij de data in contiguous memory staat (zoals in C++ al 30 jaar kan met std::vector<>) in plaats van een array van pointers naar heap-allocated objects met behoorlijke overhead, zoals tot nu toe het geval was?

Mmh, ik was me aan het baseren op deze 2 bronnen: Oracle docs en uitleg op baeldung.

Maar als ik dan deze JEP lees, is het nog niet ingebouwd.

Mmh, ik word hier ff nerd sniped, interessante materie om later verder uit te zoeken

[FrankMennink]

Dag 5 in Python

Zo deel 2 was toch wel een stuk pittiger, had wel al door dat bruteforcen niet heel handig zou zijn. Na een tijdje denken ook op de oplossingsmanier van .oisyn (in de quote) gekomen. Implementeren daarvan was wel een k-klus Deel 2 runt uiteindelijk netjes in ~2ms

.oisyn schreef op dinsdag 5 december 2023 @ 12:34:
[...]

spoiler:

Stel je hebt een range mapping M van a..b naar x..y, en je hebt een range R van p..q. Dan wil je kijken welk deel van R overlapt met M, en specifiek die overlap wil je remappen. Dan krijg je te maken met 5 verschillende cases

#1 en #2: geen overlap: b<p || q<a
a====M====b
              p====R===q


             a====M====b
p====R===q

#3: p valt in de mapping, q niet
a====M====b
       p====R===q
       
#4: q valt in de mapping, p niet
     a====M====b
p====R===q
       
#5: zowel p als q vallen binnen de mapping
       a====M====b
         p==R==q

#6: de mapping valt volledig binnen de range, maar p en q zelf niet
       a==M==b
    p=====R====q

Bij geen overlap blijft de oorspronkelijke range natuurlijk gelijk.
In geval van #3 wordt het begin van R regemapped, maar het einde hou je over om verder te checken
#4 is als #3, maar dan wordt juist het einde geremapped en het begin hou je over
Bij #5 wordt de volledige range geremapped
Bij #6 wordt het midden van de range geremapped. Het begin en het eind hou je over.

En nu ik dit typ realiseer ik me dat ik #6 ben vergeten te implementeren . Maakt blijkbaar niet uit voor het eindresultaat.

[gedonie]

Dag 5 In Java is ook weer gedaan.

spoiler:

Was wel even aan het puzzelen omdat ik een aantal denk fouten had gemaakt in de overlap gevallen tussen de mutaties en de seeds.

[MueR]

.oisyn schreef op dinsdag 5 december 2023 @ 12:34:
[...]

spoiler:

En nu ik dit typ realiseer ik me dat ik #6 ben vergeten te implementeren . Maakt blijkbaar niet uit voor het eindresultaat.

Hehe, als ik jouw code run met mijn input maakt het wel uit. Heb jij geluk.

[.oisyn]

MueR schreef op dinsdag 5 december 2023 @ 14:28:
[...]


Hehe, als ik jouw code run met mijn input maakt het wel uit. Heb jij geluk.

Wanneer heb je die code gepakt? Want ik heb een paar minuten geleden de fix gepusht

[MueR]

.oisyn schreef op dinsdag 5 december 2023 @ 14:29:
[...]

Wanneer heb je die code gepakt? Want ik heb een paar minuten geleden de fix gepusht

Vijftien minuten 20 minuten geleden.. typisch

[ Voor 3% gewijzigd door MueR op 05-12-2023 14:31 ]

[.oisyn]

Het was 14:09 volgens github. Ik heb de fix niet getest overigens.

[MueR]

Met die fix komt er wel de correcte uitkomst uit iig.

[W1LL3M]

tot nu toe alle opdrachten in js/typescript opgelost, maar deel 2 van dag 5 daar had firefox het te moeilijk mee
edge deed het wel

[MadEgg]

Pfoeh, dat was nog wel even stoeien.

spoiler:

De naïeve implementatie met de ranges uitklappen duurde veel te lang. Dan de ranges steeds maar expanden naar relevante ranges of dummy ranges in de volgende stap.

Uiteindelijk redelijk tevreden met het resultaat. Niet zo functioneel als ik had gewild maar het moet maar klaar zijn. En het is met 75ms gebeurd.

Dag 5 - Kotlin

[CrossProd]

Ik had eerst een brute-force oplossing en dat deed er 90 seconden over. Nu even een rewrite gedaan die met alleen de ranges werkt en dat is in ~0.15 milliseconden klaar

Dag 5 - Swift

[YoToP]

dag 5 gelukt in Python

spoiler:

Deel twee bruteforcen met Python lukte niet. dus moest toch maar anders

standard input:
part 1 - 10 ms
part 2 - 3 ms
medium input
part 2 - <does not compute>
large input
part 2 - <does not compute>

[arnold_m]

Bij deel 1 vreselijk zitten stoeien met het parsen, misschien moet ik toch eens regex-crate voor Rust opzoeken.

spoiler:

* arnold_m moet gewoon de documentatie van BufReader<> in Rust beter lezen.

Na deel 1 was het tijd voor andere dingen.
Voor het tweede deel heb ik een aanpak zoals die van @.oisyn gekozen. Dat zat er vrij snel in en gaat snel genoeg.

[SPee]

Camulos schreef op dinsdag 5 december 2023 @ 13:26:
Jemig wat een opgave met dag 5!

Eerste was easy-peasy met binnen aantal ms opgelost..
de 2e stuk gewoon bruteforce, na 36 minuten kwam het juiste antwoord eruit

Ik heb mijn oplossing moeten aanpassen. Hij was veel langer bezig dan dat en nog geen antwoord.
En dat was voor mijn oplossing die al 20GB gebruikt voordat ik hem stopte.

Uiteindelijk toch gelukt.

spoiler:

Eerst nog gedacht om bij de seed ranges een remapping waarde te berekenen.
Maar uiteindelijk gegaan om de herberekende ranges steeds door te geven.

[Gropah]

Zo, gedaan. En daarmee is het ook wel gezegd

spoiler:

Ja, je kan met ranges etc werken. Maar ben vandaag een luie donder dus heb het gewoon gebruteforced waarbij ik eerst ook nog eens alle seeds tegelijk in geheugen wou... Dat vond de JVM niet leuk. Dus nu seed voor seed. Hij was ongeveer 6 minuten aan het rekenen. Dat was goedkoper om te draaien dan mij een uur op de ranges laten proggen zullen we maar als verantwoording gebruiken

[Remcoder]

spoiler:

Hoe krijgen mensen een runtime met een resultaat in minuten?

Mijn eerste poging vrat in no time al het geheugen op. Alle seeds maken en in het geheugen proppen was blijkbaar niet zo snugger.

Mijn tweede poging zou vast nu nog aan het lopen zijn.

En mijn derde poging was klaar binnen 8 seconden, wat ik al veel vind. Daarbij begin ik met location 0, die reken ik terug naar een seed en dat net zo lang ophogen tot ik een seed in range vond.

Zonder parallelisatie, dus mijn machine stond lekker single threaded te stampen.

Dus, hoe kom je tot een runtime die realistisch in minuten kan tellen?

[Gropah]

Remcoder schreef op dinsdag 5 december 2023 @ 19:11:

spoiler:

Hoe krijgen mensen een runtime met een resultaat in minuten?

Mijn eerste poging vrat in no time al het geheugen op. Alle seeds maken en in het geheugen proppen was blijkbaar niet zo snugger.

Mijn tweede poging zou vast nu nog aan het lopen zijn.

En mijn derde poging was klaar binnen 8 seconden, wat ik al veel vind. Daarbij begin ik met location 0, die reken ik terug naar een seed en dat net zo lang ophogen tot ik een seed in range vond.

Zonder parallelisatie, dus mijn machine stond lekker single threaded te stampen.

Dus, hoe kom je tot een runtime die realistisch in minuten kan tellen?

spoiler:

Gezien hoe groot de getallen worden had ik niet eens bedacht om van de locatie terug te rekenen. Ik ben gewoon alle seeds 1 voor 1 aan het bereken, voor alle seeds die er zijn (en dat zijn er nogal wat, 2.207.992.808 om precies te zijn) , terwijl ondertussen de laagste locatie word opgeslagen.