Advent of Code 2024

[Soultaker]

Woy schreef op woensdag 4 december 2024 @ 09:54:
Part2 kan nog wat efficienter door als je een don't tegen komt naar een andere state te springen die alleen do() probeert te parsen. Dat werkt natuurlijk niet als je in 1 run zowel Part1 als 2 wil doen.

Daar heb je gelijk in, maar ik vond het niet helemaal in de geest van het oplossen zonder geheugen, aangezien je dan twee keer over dezelfde invoer moet gaan, wat impliceert dat je 'm ergens opgeslagen hebt.

(Als je ze splitst kun je overigens deel 1 ook versimpelen, want dan hoef je alleen de mul() instructies te detecteren, en kun je do()/don't() negeren.)

TrailBlazer schreef op woensdag 4 december 2024 @ 10:19:
ik heb net even gekeken. In mijn oplossing heb ik voor part 1 47006 waardes gechecked en hiervan genereerden er 516 een exception. Dus iets meer dan 1 % resulteerde in een exception. Ik weet niet wat meer performance kost het checken of ze allemaal in boundary zijn of deze exceptie afhandelen in deze use case.

Op zich heb je daar een goed punt: de totale overhead is kleiner naarmate het invoergrid groter is, dus uiteindelijk is die misschien verwaarloosbaar, en het kan zelfs zo zijn dat op een bepaald moment het range checken meer kost dan het bespaart.

Maar dat tweede is specifiek voor Python; het komt doordat de code in Python zelf trager is dan de native code, die de bounds check uiteindelijk implementeert. De snelheidswinst komt dus eigenlijk alleen door het offloaden van de check naar native code.

Friits schreef op woensdag 4 december 2024 @ 10:42:
Als je van een afstandje kijkt, zijn deel 1 en 2 ongeveer hetzelfde.

Dit soort code kun je eigenlijk wel zonder spoiler tags posten

[Corniel]

Soultaker schreef op woensdag 4 december 2024 @ 11:28:
Dit soort code kun je eigenlijk wel zonder spoiler tags posten

Idd. Daar is geen chocolade van te maken. Zelfs niet in december.

[bakkerjangert]

Soultaker schreef op zaterdag 30 november 2024 @ 15:12:
Okee nog één probleem voor de echte AoC van start gaat. Hopelijk iets makkelijker dan het probleem dat ik eerder postte, en redelijk in de trant van het soort problemen dat je bij de AoC ook voorgeschoteld krijgt.

Nog even terugkomend op de pre-puzzel van @Soultaker. Mooie kerstrijm komt eruit. Het duurde wat langer omdat ik voor deel 1 niet op het juiste antwoord kom, maar voor deel 2 het antwoord wel lijkt te kloppen. Nog steeds heb ik geen idee waarom deel 1 niet juist is, klopt jou antwoord voor deel 1 wel? Of zie ik toch iets over het hoofd. Inmiddels uitgeklaard door @Soultaker , dank voor de actie om ook de originele opgave post aan te passen.

Code in python.

spoiler:

Deel 1: jsuit_m__bsh_po"coeiditwohwel_r!_Pnhthulaa_wfdtrdd

Final decoded message:

Twas_the_night_before_Christmas,_when_all_through_
the_house/Not_a_creature_was_stirring,_not_even_a_
mouse;The_stockings_were_hung_by_the_chimney_with_
care,In_hopes_that_St._Nicholas_soon_would_be_ther
e;The_children_were_nestled_all_snug_in_their_beds
;While_visions_of_sugar-plums_danced_in_their_head
s;And_mamma_in_her_'kerchief,_and_I_in_my_cap,Had_
just_settled_our_brains_for_a_long_winter's_nap,Wh
en_out_on_the_lawn_there_arose_such_a_clatter,I_sp
rang_from_my_bed_to_see_what_was_the_matter.Away_t
o_the_window_I_flew_like_a_flash,Tore_open_the_shu
tters_and_threw_up_the_sash.When_what_to_my_wonder
ing_eyes_did_appear,But_a_miniature_sleigh_and_eig
ht_tiny_rein-deer,With_a_little_old_driver_so_live
ly_and_quick,I_knew_in_a_moment_he_must_be_St._Nic
k.More_rapid_than_eagles_his_coursers_they_came,An
d_he_whistled,_and_shouted,_and_called_them_by_nam
e:"Now,_Dasher!_now,_Dancer!_now_Prancer_and_Vixen
!On,_Comet!_on,_Cupid!_on,_Donder_and_Blitzen!To_t
he_top_of_the_porch!_to_the_top_of_the_wall!Now_da
sh_away!_dash_away!_dash_away_all!"As_leaves_that_
before_the_wild_hurricane_fly,When_they_meet_with_
an_obstacle,_mount_to_the_sky;So_up_to_the_houseto
p_the_coursers_they_flew/With_the_sleigh_full_of_t
oys,_and_St._Nicholas_too---And_then,_in_a_twinkli
ng,_I_heard_on_the_roof/The_prancing_and_pawing_of
_each_little_hoof.As_I_drew_in_my_head,_and_was_tu
rning_around,Down_the_chimney_St._Nicholas_came_wi
th_a_bound.He_was_dressed_all_in_fur,_from_his_hea
d_to_his_foot,And_his_clothes_were_all_tarnished_w
ith_ashes_and_soot;His_eyes---how_they_twinkled!_h
is_dimples,_how_merry!His_cheeks_were_like_roses,_
his_nose_like_a_cherry!His_droll_little_mouth_was_
drawn_up_like_a_bow,And_the_beard_on_his_chin_was_
as_white_as_the_snow;The_stump_of_a_pipe_he_held_t
ight_in_his_teeth,And_the_smoke,_it_encircled_his_
head_like_a_wreath;He_had_a_broad_face_and_a_littl
e_round_belly/That_shook_when_he_laughed,_like_a_b
owl_full_of_jelly.He_was_chubby_and_plump,_a_right
_jolly_old_elf,And_I_laughed_when_I_saw_him,_in_sp
ite_of_myself;A_wink_of_his_eye_and_a_twist_of_his
_head/Soon_gave_me_to_know_I_had_nothing_to_dread;
He_spoke_not_a_word,_but_went_straight_to_his_work
,And_filled_all_the_stockings;_then_turned_with_a_
jerk,And_laying_his_finger_aside_of_his_nose,And_g
iving_a_nod,_up_the_chimney_he_rose;He_sprang_to_h
is_sleigh,_to_his_team_gave_a_whistle,And_away_the
y_all_flew_like_the_down_of_a_thistle.But_I_heard_
him_exclaim,_ere_he_drove_out_of_sight---“Happy_Ch
ristmas_to_all,_and_to_all_a_good_night!”---------

[Soultaker]

bakkerjangert schreef op woensdag 4 december 2024 @ 12:09:
Nog even terugkomend op de pre-puzzel van @Soultaker. Mooie kerstrijm komt eruit. Het duurde wat langer omdat ik voor deel 1 niet op het juiste antwoord kom, maar voor deel 2 het antwoord wel lijkt te kloppen. Nog steeds heb ik geen idee waarom deel 1 niet juist is, klopt jou antwoord voor deel 1 wel? Of zie ik toch iets over het hoofd .

Oef, ik schaam me dood, maar mijn antwoord voor deel 1 was gebaseerd op 100 stappen, terwijl ik in de probleembeschrijving 1000 stappen schreef. Mijn excuses! Ik kan me voorstellen dat je daar veel tijd aan verloren bent, terwijl het idee van deel 1 juist was om mensen de mogelijkheid te geven hun oplossing te valideren voor 'm te optimaliseren. Je antwoord is natuurlijk correct.

[Soultaker]

@Janoz kun jij het antwoord van bakkerjangert voor deel 1 hier in mijn probleemstelling hier editen? (Dus “ntu...rnl” wordt “jsu...rdd”).

edit: @.oisyn heeft 'm ondanks de wachtende sinterklaassurprises geëdit.

Ik zou het zelf doen maar blijkbaar mag ik mijn bericht niet meer editen. Ik neem aan dat moderators die beperking niet hebben. En ik weet niet of iemand überhaupt nog bezig is met de pre-puzzels, maar het zou jammer zijn als nog meer mensen hun tijd verdoen omdat m'n referentie-antwoord niet klopt.

[ Voor 7% gewijzigd door Soultaker op 04-12-2024 12:48 ]

[TrailBlazer]

Vandaag weer een for … else statement in Python gebruikt. Was er niet heel bekend mee maar het is wel handig

[heuveltje]

TrailBlazer schreef op woensdag 4 december 2024 @ 13:25:
Vandaag weer een for … else statement in Python gebruikt. Was er niet heel bekend mee maar het is wel handig

Lol dat klinkt als mij code.
Vanochtend wel de puzzel gelezen, maar ben nu nog aan het werk. dus kan er alleen over nadenken.
Ben benieuwd hoe jij het aanvliegt.
als je de input inleest als een array van regels zie ik 2 opties.
mijn eerste gedachte was. ga door alle rijen heen wandelen, en als je een x tegenkomt. kijk dan of je er xmas van kan maken door vanaf daar te vertrekken in alle windrichtingen

Maar dat klinkt als relatief veel programeerwerk. (en inefficient, maar daar kijk ik nog maar niet naar )

optie 2
doe een count find string op xmas en samx voor elke horizontale regel.
Dat kan volgens mij niet op verticale rijen, dus dan zou je een nieuw array moeten maken waarbij de x en y waarde omgedraaid

wat denk ik veel minder programmeer werk is.
(en nu ik snel google. is er denk ik zelfs een ingebouwd commando in python om een array te draaien )

Lol stack exchange blijft briljant
https://scifi.stackexchan...fy-supermans-other-senses

Je moet je maar ergens in kunnen verdiepen

[ Voor 8% gewijzigd door heuveltje op 04-12-2024 15:17 ]

[TrailBlazer]

@heuveltje

spoiler:

Input inlezen en een hash maken met als key de x,y positie en de waarde de letter. Vervolgens alle acht de vectors rond de X en volgen om te kijken of er MAS staat.

code staat paar posts terug van me

[P_Tingen]

Soultaker schreef op dinsdag 3 december 2024 @ 18:36:
Maar eerst, een pop quiz: wat is het beste statement in een programmeertaal? Fout! Het is goto. Hier is een oplossing met maar liefst 81 goto statements!

Het resulterende programma gebruikt een constante hoeveelheid geheugen (ongeveer 1,5 MiB op mijn systeem) ongeacht hoe groot de invoer is. Maar is het ook snel? Ja, best wel!

$ time ./solve2 < aoc-2024-day-03-challenge-2.txt
...33600
...57973

real    0m4.797s
user    0m4.592s
sys     0m0.198s

Cool!
In Progress 4GL geen GOTO statement, maar ik kan wel doorspringen van subroutine naar subroutine...

https://github.com/patric...r/2024/Day-03/day-03b-2.p

[Soultaker]

P_Tingen schreef op woensdag 4 december 2024 @ 16:06:
Cool!
In Progress 4GL geen GOTO statement, maar ik kan wel doorspringen van subroutine naar subroutine...

https://github.com/patric...r/2024/Day-03/day-03b-2.p

Netjes geport. Is RUN een soort recursieve functie-aanroep? In dat geval loop je misschien kans op stack overflows bij grote invoer. En zoniet, als recursie niet ondersteund wordt, dan is RUN toch feitelijk een soort GOTO??

[P_Tingen]

Progress kent procedures en functies, het enige verschil is dat een functie een waarde terug geeft en een procedure dat alleen doet via parameters. In Basic zou het een GOSUB zijn, je komt bij het beëindigen van de run weer terug waar je was.

Bij (hele) grote invoer kun je inderdaad wel tegen stack overflows aanlopen, maar gezien de aard van de invoer verwacht ik dat hier niet bij. Had jij nou nog een mega invoer voor deze? Dan wil ik het wel even testen.

Deze versie was overigens wel behoorlijk trager dan mijn eigen oplossing, iets van 79ms tegen 23ms van mezelf.

[Soultaker]

[b]P_Tingen schreef op woensdag 4 december 2024 @ 19:27:Bij (hele) grote invoer kun je inderdaad wel tegen stack overflows aanlopen, maar gezien de aard van de invoer verwacht ik dat hier niet bij. Had jij nou nog een mega invoer voor deze? Dan wil ik het wel even testen.

Yep, de grote inputs staan hier.

(Dat brengt me op een idee. Ik zou eigenlijk nog even een grote invoer voor vandaag moeten maken.)

Overigens had ik ook voor dag 3 ook een eerdere oplossing die een state machine zonder goto's maar met een while-loop implementeert: day03/solve.c. Dat idee zou je waarschijnlijk ook kunnen gebruiken om de procedure calls te elimineren. (Niet dat je het per se moet doen natuurlijk.)

[Creepy]

Dag 4 viel ook weer mee. En eens met een aantal anderen; deel 2 was makkelijker
https://github.com/CodeEn...er/aoc/aoc2024/Day04.java

[Soultaker]

Voor wie wil benchmarken: aoc-2024-day-04-challenge-1.zip

Referentie:

$ time pypy3 ../04.py < aoc-2024-day-04-challenge-1.txt 
...723
...322

real    0m3.557s
user    0m3.516s
sys     0m0.031s

(Dit is ook een goede use case voor PyPy, want de normale Python interpreter doet er 10x zo lang over!)

[ProAce]

Vorig jaar al een grid implementatie gemaakt, dat maakte dit een stuk makkelijker om te implementeren.
Met de bovenstaande grote input:

code:

Day 4:
        Part 1:
                solution: ...723
                runtime: 72.724083ms
        Part 2:
                solution: ...322
                runtime: 21.820792ms

https://github.com/ysmild...lutions/2024/day4/day4.go

[Robbinb1993]

Elapsed time: 57ms
Ans part 1: 195723
Ans part 2: 138322

https://github.com/Robbinb1993/AoC24/blob/main/day4/day4.cc

[ Voor 14% gewijzigd door Robbinb1993 op 04-12-2024 22:14 ]

[Satom]

Dag 4, vanaf parsing tot het einde (in C#):

code:

Hello, World!
✔ Choose year: 2024
✔ Choose day: 4
✔ Choose which to run: A
✔ Choose input to run: Regular
-- Day4 --
Day4 is 24... in 16 msec

✔ Choose year: 2024
✔ Choose day: 4
✔ Choose which to run: B
✔ Choose input to run: Regular
-- Day4 --
Day4 is 18... in 15 msec

In eerste instantie zat ik wat te prutsen met de

spoiler:

diagonale woorden

. Na deel 1 te hebben opgelost, de boel een beetje herschreven zodat er zo weinig als mogelijk duplicate code aanwezig is!

[Friits]

Corniel schreef op woensdag 4 december 2024 @ 11:50:
[...]


Idd. Daar is geen chocolade van te maken. Zelfs niet in december.

Ouch! Ik dacht dat het met de uitleg erbij wel te begrijpen was, maar ik zal nog een poging wagen. Ik heb 'm even iets minder abstract gemaakt.

spoiler:

We lezen de input in als één lange string g, dus we maken er geen array van of zo. Voor iedere positie i in die string kijken we naar acht verschillende subsequences: die met stapgrootte 1 (gelijk aan gewoon van links naar rechts lezen), stapgrootte -1 (van rechts naar links lezen), stapgrootte 141 (van boven naar beneden lezen), etc. Zijn de eerste vier karakters van zo'n subsequence gelijk aan 'XMAS', dan hebben we er dus eentje gevonden en kunnen we ons antwoord met één ophogen.

Als je de for-loops en handmatige optelling vervangt door een sum() over een lijst-comprehensie, komt er dit uit:

print(sum(g[i::step][:4] =='XMAS' for step in (1,-1,140,-140,141,-141,142,-142) for i in range(len(g))))

Voor deel 2 doe je bijna hetzelfde, maar hoef je alleen naar de diagonalen te kijken (stapgrootte 140 en 142) máár willen we wel voor beide diagonalen een match. Dat ziet er zo uit:

print(sum(all(g[i-step::step][:3] in ('MAS','SAM') for step in (140,142)) for i in range(len(g))))

Je ziet dat er veel overlap tussen beide deeloplossingen zit, behalve de drie punten die ik in mijn vorige post ook al noemde: de noodzaak voor "any" richting vs. beide richtingen, de lengte van de string die we zoeken (4 vs. 3), en de richtingen (allemaal vs. alleen de diagonalen). Als je die drie punten in variabelen zet, kom je dus op mijn oorspronkelijke oplossing:

g = open('in.txt').read()
for f, l, s in (sum, 4, (1,140,141,142)), (all, 3, (140,142)):
print(sum(f(g[i-x::x][:l] in ('SAMX'[:l], 'SAMX'[:l][::-1]) for x in s) for i in range(len(g))))

Ik hoop dat het hiermee wat duidelijker geworden is voor iedereen. Het is een mooie aanpak (imho), maar bij nader inzien wel erg abstract. Maar goed, ieder z'n hobby: sommigen optimaliseren op milliseconden, ik vind het leuk dat m'n Python-code in een sms'je past

[Reptile209]

Friits schreef op woensdag 4 december 2024 @ 21:20:
[...]

Maar goed, ieder z'n hobby: sommigen optimaliseren op milliseconden, ik vind het leuk dat m'n Python-code in een sms'je past

Of zoals ze dat vroeger zeiden: dat mijn hele COBOL-programma op één bak ponskaarten past.

[Soultaker]

Friits schreef op woensdag 4 december 2024 @ 21:20:
[...]

Ouch! Ik dacht dat het met de uitleg erbij wel te begrijpen was, maar ik zal nog een poging wagen. Ik heb 'm even iets minder abstract gemaakt.

Ik kon 'm op zich nog net decoderen, maar dat kostte wel enige minuten, dus de kans op spoilers was nihil.

Overigens is 'ie mogelijk nog verder te minimaliseren, afhankelijk van welke maatstaf je precies gebruikt, bv:

Python:

g = open('in.txt').read()
for f, l in ((sum, 4), (all, 3)):
  print(sum(f(g[i-x::x][:l] in ('SAMX'[:l], 'XMAS'[-l:]) for x in (1,140,142,141)[-l:l]) for i in range(len(g))))

[CMG]

Soultaker schreef op woensdag 4 december 2024 @ 19:57:
Voor wie wil benchmarken: aoc-2024-day-04-challenge-1.zip

Referentie:

$ time pypy3 ../04.py < aoc-2024-day-04-challenge-1.txt 
...723
...322

real    0m3.557s
user    0m3.516s
sys     0m0.031s

(Dit is ook een goede use case voor PyPy, want de normale Python interpreter doet er 10x zo lang over!)

Voor de lol ingelezen; mijn code doet het in een halve seconde 😅

[Soultaker]

Voor dag 5:

spoiler:

Ik had oorspronkelijk een soort adhoc bubble sort geïmplementeerd. Dat gaf wel het goede antwoord maar ik vond het netter om gewoord de standaard sort() aan te roepen. Daarbij is functools.cmp_to_key() erg behulpzaam!

Python code

edit:
Overigens is een O(n) implementatie ook mogelijk! C++ code (wel 90% parsing helaas)

[ Voor 18% gewijzigd door Soultaker op 05-12-2024 07:01 ]

[FCA]

Vandaag had ik eerst vooral moeite met de parsing: je kunt niet op 2 opties splitsen in Rust zover ik kom zien, en de encoding van mijn test en echte input was anders: \r\n vs \n.

Dan wordt splitsen op een lege regel erg lastig...

Uiteindelijk opgelost door de encoding van de test aan te passen

[ Voor 12% gewijzigd door FCA op 05-12-2024 06:56 ]

[Friits]

Soultaker schreef op donderdag 5 december 2024 @ 06:32:
Voor dag 5:

Leuk, we hebben een keer ongeveer hetzelfde gedaan!

[Soultaker]

FCA schreef op donderdag 5 december 2024 @ 06:55:
Vandaag had ik eerst vooral moeite met de parsing: je kunt niet op 2 opties splitsen in Rust zover ik kom zien, en de encoding van mijn test en echte input was anders: \r\n vs \n.

Is dit onder Windows?

Voor zover ik weet wordt een tekstbestand verstuurd met content-type: text/plain en \r\n newlines, wat onder Windows ook het native formaat is voor tekstbestanden, dus dat het zo opgeslagen wordt is correct, en daar moet je altijd op voorbereid zijn.

Onder Linux converteert de browser line endings naar \n dus heb je dat probleem niet.

Friits schreef op donderdag 5 december 2024 @ 07:07:
Leuk, we hebben een keer ongeveer hetzelfde gedaan!

Nice. Lekker kort weer. Maar die comparison function is niet gegarandeerd geldig, toch? Ik zou denken dat je iets als:

spoiler:

(f'{y}|{x}' in rules)) - (f'{x}|{y}' in rules))

moet doen.

(Die cmp_to_key() call buiten de lus halen is trouwens wel een goed idee; beetje zinloos om 'm voor elke regel opnieuw aan te roepen, zoals ik deed.)

[Mugwump]

Deze was vrij simpel inderdaad.
Mijn oplossing in Kotlin

[FCA]

Soultaker schreef op donderdag 5 december 2024 @ 07:19:
[...]

Is dit onder Windows?

Voor zover ik weet wordt een tekstbestand verstuurd met content-type: text/plain en \r\n newlines, wat onder Windows ook het native formaat is voor tekstbestanden, dus dat het zo opgeslagen wordt is correct, en daar moet je altijd op voorbereid zijn.


Onder Linux converteert de browser line endings naar \n dus heb je dat probleem niet.

Onder windows inderdaad, maar ik gebruik een helper crate (cargo-aoc), die blijkbaar het anders doet dan Windows native

Overigens is mijn oplossing hetzelfde idee als de anderen hier hadden bedacht

spoiler:

custom cmp functie (moest dat ook even uitzoeken, risico van een nieuwe taal uitproberen), en er vanuit gaan dat de ordering een beetje netjes is (als niet kleiner dan, dan dus groter dan)

[Friits]

Soultaker schreef op donderdag 5 december 2024 @ 07:19:
Nice. Lekker kort weer. Maar die comparison function is niet gegarandeerd geldig, toch?

Klopt. Bij AoC ga ik voor de "als het werkt, dan werkt het"-aanpak, zeker als de code korter of leesbaarder maakt. En dan lever ik inderdaad soms wat in op theoretische correctheid

[Corniel]

@Friits Wat Soultaker ook al zei: het is geen spoiler. Mensen die dat kunnen ontcijferen hebben de puzzel ook wel gemaakt. (en vanwege de tijd van het jaar wilde ik er een chocolade grap van maken. )

@Soultaker Volgens mij is het safe voor de echte input, maar niet voor de voorbeeld input. Ik had iets soort gelijks en dat ging goed voor de echte input, maar niet voor het voorbeeld (bij de refactoring achteraf).

Mijn oplossing

[Woy]

Vandaag niet echt veel tijd, wel een oplossing, maar heb het idee dat het een stuk eenvoudiger kan, en ook netter qua code:

https://github.com/rverst.../blob/main/Y2024/Day05.cs

[ Voor 6% gewijzigd door Woy op 05-12-2024 10:46 ]

[nescafe]

@Corniel @Woy erg mooie oplossingen! Ik heb het zelf een stuk onhandiger gedaan

https://github.com/nescaf...b/05%20Print%20Queue.linq

[ Voor 11% gewijzigd door nescafe op 05-12-2024 12:02 ]

[fruitschaal2]

spoiler:

Ik was niet bekend met de cmp_to_key functie. Uiteindelijk alles in een dict gedaan en een while loop om de incorrecte pages correct te maken.

https://topaz.github.io/p...7ZhBVQjbe6Z3BMLNMcP8r3iUA

[gedonie]

Dag 5 was vooral even kijken voor deel 2 met sorteren de rest kon ik zonder problemen van deel 1 overnemen.

https://github.com/gjong/...nt/years/y2024/Day05.java

[breew]

dag 5 in R afgerond.
https://github.com/wimpel...e2024/blob/main/r/day05.R

[Soultaker]

Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Hier zijn twee voorbeeld invoeren voor dag 5: aoc-2024-day-05-challenge-1-and-2.zip

Als je de antwoorden van deel 1 en deel 2 vermenigvuldigt moet er 9812096 (voor challenge-1.txt) en 6145186 (voor challenge-2.txt) uitkomen. Ben heel benieuwd hoeveel programma's de correcte uitvoer genereren!

[breew]

Soultaker schreef op donderdag 5 december 2024 @ 13:44:
Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Hier zijn twee voorbeeld invoeren voor dag 5: aoc-2024-day-05-challenge-1-and-2.zip

Als je de antwoorden van deel 1 en deel 2 vermenigvuldigt moet er 9812096 (voor challenge-1.txt) en 6145186 (voor challenge-2.txt) uitkomen. Ben heel benieuwd hoeveel programma's de correcte uitvoer genereren!

ik kom uit op 9812096 en 6145186.. meester coder dat ik ben (of ik had geluk.. geen idee)

[gedonie]

Soultaker schreef op donderdag 5 december 2024 @ 13:44:
Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Hier zijn twee voorbeeld invoeren voor dag 5: aoc-2024-day-05-challenge-1-and-2.zip

Als je de antwoorden van deel 1 en deel 2 vermenigvuldigt moet er 9812096 (voor challenge-1.txt) en 6145186 (voor challenge-2.txt) uitkomen. Ben heel benieuwd hoeveel programma's de correcte uitvoer genereren!

Ik heb het vermoeden inderdaad dat de sort die ik gebruik in de knoei komt in de case dat na verschuiven van een getal door die verschuiving de rij alsnog weer invalide wordt. Maar het is niet onbewust dat dit soort cases niet vaak voorkomen in AoC, aangezien hij het opzet voor beginnende ontwikkelaars en wat verder gevorderde.

[fruitschaal2]

Soultaker schreef op donderdag 5 december 2024 @ 13:44:
Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Hier zijn twee voorbeeld invoeren voor dag 5: aoc-2024-day-05-challenge-1-and-2.zip

Als je de antwoorden van deel 1 en deel 2 vermenigvuldigt moet er 9812096 (voor challenge-1.txt) en 6145186 (voor challenge-2.txt) uitkomen. Ben heel benieuwd hoeveel programma's de correcte uitvoer genereren!

Gelukkig kom ik ook op de goede antwoorden uit:

code:

Challenge 1: result = (p1 * p2)=9812096
Challenge 2: result = (p1 * p2)=6145186

[Janoz]

Soultaker schreef op donderdag 5 december 2024 @ 13:44:
Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Hier zijn twee voorbeeld invoeren voor dag 5: aoc-2024-day-05-challenge-1-and-2.zip

Als je de antwoorden van deel 1 en deel 2 vermenigvuldigt moet er 9812096 (voor challenge-1.txt) en 6145186 (voor challenge-2.txt) uitkomen. Ben heel benieuwd hoeveel programma's de correcte uitvoer genereren!

Ik ben nu niet in de mogelijkheid om iets met je voorbeeld te doen, maar ik had inderdaad wel het gevoel dat er edge cases zouden kunnen zijn waarbij het gewoon sorteren mogelijk niet zou werken. Maar ik heb de bende ge-yolo-ed en ik kreeg het goede antwoord dus ben er eigenlijk verder niet dieper op in gegaan.

[dcm360]

Grappig. Mijn oplossing (met insertion sort) doet het niet goed, maar convergeert wel richting het juiste antwoord. Dus net zo lang het rijtje van volgorde veranderen totdat er een correcte oplossing uitkomt werkt.

[ Voor 5% gewijzigd door dcm360 op 05-12-2024 14:22 ]

[TrailBlazer]

Ik heb het mezelf nodeloos complex gemaakt en nog steeds niet werkend. Misschien zitnik helemaal fout maar ik had het volgende bedacht
Kijk welke paginas er achter een pagina moeten zitten en kijk vervolgens recursive wel daar ook achter moeten uit het voorbeeld

53 moet achter 47 en 29 moet achter 53 dus moet 29 ook achter 47. Op deze manier heb ik opgebouwd welke paginas er achter een pagina kunnen zitten. Het voorbeeld geeft het goede antwoord maar de echte input niet. Maak ik een denkfout ergens?

[Janoz]

TrailBlazer schreef op donderdag 5 december 2024 @ 14:22:
Ik heb het mezelf nodeloos complex gemaakt en nog steeds niet werkend. Misschien zitnik helemaal fout maar ik had het volgende bedacht
Kijk welke paginas er achter een pagina moeten zitten en kijk vervolgens recursive wel daar ook achter moeten uit het voorbeeld

53 moet achter 47 en 29 moet achter 53 dus moet 29 ook achter 47. Op deze manier heb ik opgebouwd welke paginas er achter een pagina kunnen zitten. Het voorbeeld geeft het goede antwoord maar de echte input niet. Maak ik een denkfout ergens?

Ik denk dat je denkfout is dat 29 alleen achter 47 hoort als in de reeks een 53 staat

[Soultaker]

dcm360 schreef op donderdag 5 december 2024 @ 14:22:
Grappig. Mijn oplossing (met insertion sort) doet het niet goed, maar convergeert wel richting het juiste antwoord. Dus net zo lang het rijtje van volgorde veranderen totdat er een correcte oplossing uitkomt werkt.

Ik weet niet zeker of dat gegarandeerd is. Staat je code ergens online? Ben benieuwd of ik een tegenvoorbeeld kan vinden

TrailBlazer schreef op donderdag 5 december 2024 @ 14:22:
Kijk welke paginas er achter een pagina moeten zitten en kijk vervolgens recursive wel daar ook achter moeten uit het voorbeeld

Ik denk dat zoiets in theorie moet kunnen, maar het hangt er natuurlijk ook een beetje vanaf hoe je het geïmplementeerd hebt. Als je je code deelt kunnen we er misschien meer zinnigs over zeggen.

[TrailBlazer]

Ik heb er nu wel het goede antwoord uit voor deel 1 ik heb alleen een fix moeten doen waarvan ik niet snap waarom ik ga eerste even opschonen en dan nog even goed denken

Maar los daarvan deze complexe oplossing is nutteloos voor deel 2

[ Voor 16% gewijzigd door TrailBlazer op 05-12-2024 15:11 ]

[dcm360]

Soultaker schreef op donderdag 5 december 2024 @ 15:04:
[...]

Ik weet niet zeker of dat gegarandeerd is. Staat je code ergens online? Ben benieuwd of ik een tegenvoorbeeld kan vinden

Oh, echt zeker weten doe ik het ook niet, maar op de gegeven input werkt het (en zo lukt het op zich wel vaker om oplossingen in elkaar te zetten die formeel niet correct zijn voor de opgave, maar wel voldoen voor de input). Als je zin hebt om er naar te kijken, staat mijn code met aanpassing (want op het origineel werkt het sowieso niet) hier .

[SideSplitter]

spoiler:

Pff, het duurde even voordat ik door had dat het voor kon komen dat één pagina meerdere regels kon hebben. Uiteraard gaat dat natuurlijk wel goed voor de test input

[Janoz]

Soultaker schreef op donderdag 5 december 2024 @ 15:04:

Ik denk dat zoiets in theorie moet kunnen, maar het hangt er natuurlijk ook een beetje vanaf hoe je het geïmplementeerd hebt. Als je je code deelt kunnen we er misschien meer zinnigs over zeggen.

1|2
2|4
3|1
4|3

1,2,4
4,3,1

[TrailBlazer]

Janoz schreef op donderdag 5 december 2024 @ 15:31:
[...]


1|2
2|4
3|1
4|3

1,2,4
4,3,1

Maar dan zou een sort toch ook over de vlos gaan?

[Robbinb1993]

Soultaker schreef op donderdag 5 december 2024 @ 13:44:
Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Hier zijn twee voorbeeld invoeren voor dag 5: aoc-2024-day-05-challenge-1-and-2.zip

Als je de antwoorden van deel 1 en deel 2 vermenigvuldigt moet er 9812096 (voor challenge-1.txt) en 6145186 (voor challenge-2.txt) uitkomen. Ben heel benieuwd hoeveel programma's de correcte uitvoer genereren!

We kunnen in plaats van een custom comparator een topologische sortering gebruiken om het probleem correct op te lossen (Wikipedia: Topological sorting). Dit is ook relatief efficiënt (O(|E| + |V|)). Ik heb mijn code nog niet volledig geoptimaliseerd, maar dit geeft de correcte output voor deze test cases:

https://github.com/Robbinb1993/AoC24/blob/main/day5/day5.cc

[ Voor 3% gewijzigd door Robbinb1993 op 05-12-2024 17:34 ]

[Soultaker]

dcm360 schreef op donderdag 5 december 2024 @ 15:16:
Als je zin hebt om er naar te kijken, staat mijn code met aanpassing (want op het origineel werkt het sowieso niet) hier .

Thanks! Als ik het goed interpreteer (Scala is niet echt mijn sterkste punt) is deze oplossing correct. Je doet iets meer dan alleen insertion sort, waardoor je gegarandeerd alle inversions vindt en oplost (uiteindelijk).

Of het heel efficiënt is durf ik niet te zeggen, maar dat zijn mijn “correcte” oplossingen tot nu toe ook niet.

Janoz schreef op donderdag 5 december 2024 @ 15:31:
1|2
2|4
3|1
4|3

1,2,4
4,3,1

Dit is ook een interessante case. Ik krijg er 5/0 uit wat volgens mij correct is aangezien beide regels al gesorteerd zijn. Gaat wel mis als je probeert de pagina's globaal te ordenen i.p.v. lokaal, maar wat @Robbinb1993 hierboven doet zou goed moeten gaan.

[Mugwump]

Soultaker schreef op donderdag 5 december 2024 @ 13:44:
Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Hier zijn twee voorbeeld invoeren voor dag 5: aoc-2024-day-05-challenge-1-and-2.zip

Als je de antwoorden van deel 1 en deel 2 vermenigvuldigt moet er 9812096 (voor challenge-1.txt) en 6145186 (voor challenge-2.txt) uitkomen. Ben heel benieuwd hoeveel programma's de correcte uitvoer genereren!

Misbruik maken van de inputdata hoort ook gewoon bij AoC.

[Corniel]

Mugwump schreef op donderdag 5 december 2024 @ 16:11:

Misbruik maken van de inputdata hoort ook gewoon bij AoC.

Gebruik.

[Janoz]

Soultaker schreef op donderdag 5 december 2024 @ 15:55:
Dit is ook een interessante case. Ik krijg er 5/0 uit wat volgens mij correct is aangezien beide regels al gesorteerd zijn. Gaat wel mis als je probeert de pagina's globaal te ordenen i.p.v. lokaal, maar wat @Robbinb1993 hierboven doet zou goed moeten gaan.

Het voorbeeld is ook vooral bedoeld om aan te geven dat de sortering niet transitief hoeft te zijn.

[Janoz]

TrailBlazer schreef op donderdag 5 december 2024 @ 15:35:
[...]

Maar dan zou een sort toch ook over de vlos gaan?

Dat hangt af van de implementatie en de input. Er zijn inderdaad setjes samen te stellen die niet sorteerbaar zijn (denk aan 1,2,3,4), maar zolang je de setjes juist samenstelt dan zou het gewoon moeten werken. Een comparator die alleen maar de vergelijkingen in de tabel gebruikt werkt gewoon.

[Soultaker]

Janoz schreef op donderdag 5 december 2024 @ 16:24:
Het voorbeeld is ook vooral bedoeld om aan te geven dat de sortering niet transitief hoeft te zijn.

Ah ja, ik zie nu wat je bedoelt. Dat is wel een goede test case, die nog niet in mijn testinvoeren verwerkt zat.

spoiler:

Als je de transitieve afsluiting per “update” berekent, en niet globaal, dan zijn cases zoals dit geen probleem. Maar als je inderdaad probeert dat globaal te doen, dan kom je in de problemen.

[Friits]

Voor alle snelheidsduivels hier:

spoiler:

Volgens mij hoeven we eigenlijk helemaal niets te sorteren. Na wat preprocessing van de volgorde-regels kunnen we een lijst van paginanummers eenmaal doorlopen tot we een ongeldig paartje tegenkomen (kan in O(n). Daarmee bepalen we of de lijst meedoet voor deel 1 of voor deel 2. Bij de lijsten voor deel 1 pakken we het middelste element (constante tijd), voor deel 2 de mediaan (O(n) met Hoare's quickselect). Optellen en klaar!

[Robbinb1993]

Soultaker schreef op donderdag 5 december 2024 @ 16:37:
[...]

Ah ja, ik zie nu wat je bedoelt. Dat is wel een goede test case, die nog niet in mijn testinvoeren verwerkt zat.

spoiler:

Als je de transitieve afsluiting per “update” berekent, en niet globaal, dan zijn cases zoals dit geen probleem. Maar als je inderdaad probeert dat globaal te doen, dan kom je in de problemen.

In de globale invoer komen er inderdaad cycli voor in de afhankelijkheidsgraaf van printvolgordes. Per update is de graaf wel een directed acyclic graph (DAG), waardoor een topologische sortering mogelijk is.

[ Voor 4% gewijzigd door Robbinb1993 op 05-12-2024 17:00 ]

[Soultaker]

Friits schreef op donderdag 5 december 2024 @ 16:41:
[..] Na wat preprocessing van de volgorde-regels [..]

Wat had je hierbij precies in gedachten?

De rest van de comment klinkt exact als wat ik vanochtend al geïmplementeerd had (std::nth_element() doet iets als Quickselect intern), en dat is inderdaad loeiend snel, maar helaas niet correct (het werkt toevallig wel op de AoC invoer, dus als dat je standaard is, kun je het inderdaad daarbij laten).

Robbinb1993 schreef op donderdag 5 december 2024 @ 16:54:
In de globale invoer komen er inderdaad cycli voor in de afhankelijkheidsgraaf van printvolgordes. Per update is de graaf wel een directed acyclic graph (DAG), waardoor een topologische sortering in dat geval mogelijk is. Anders zou er ook geen geldige sortering mogelijk zijn voor die update.

Hier zijn we het hier over eens. Het punt was dat mijn testcases dat nog niet uitgebreid checkten (de pagina's in mijn beide testcases zijn globaal te ordenen, in het eerste geval is het een total order, in het tweede geval een partial order waarbij ik garandeer dat het middelste element van elke “update” uniek bepaald is).

Dit is een voorbeeld van een oplossing die correct werkt voor de officiële invoer, en ook voor mijn test cases, maar niet op het voorbeeld dat Janoz gaf.

[Marcj]

Mijn oplossing werkt wel met de input van de site, maar die van Soultaker niet . De Rust implementatie van sort_by gooit zelfs deze error: "user-provided comparison function does not correctly implement a total order" op de tweede input. Ik heb geen zin om nu even dit op te lossen, maar wel een interessant probleem.

[Marcj]

FCA schreef op donderdag 5 december 2024 @ 06:55:
Vandaag had ik eerst vooral moeite met de parsing: je kunt niet op 2 opties splitsen in Rust zover ik kom zien, en de encoding van mijn test en echte input was anders: \r\n vs \n.

Dan wordt splitsen op een lege regel erg lastig...

Uiteindelijk opgelost door de encoding van de test aan te passen

Ik heb altijd een iterator over de regels, dus met Strings. Ken je dan ook de by_ref() methode? Dan kun je een iterator gebruiken tot een bepaald punt met take_while(..). Zie hier het voorbeeld hoe ik het doe.

[Marcj]

Friits schreef op donderdag 5 december 2024 @ 16:41:
Voor alle snelheidsduivels hier:

spoiler:

Volgens mij hoeven we eigenlijk helemaal niets te sorteren. Na wat preprocessing van de volgorde-regels kunnen we een lijst van paginanummers eenmaal doorlopen tot we een ongeldig paartje tegenkomen (kan in O(n). Daarmee bepalen we of de lijst meedoel voor deel 1 of voor deel 2. Bij de lijsten voor deel 1 pakken we het middelste element (constante tijd), voor deel 2 de mediaan (O(n) met Hoare's quickselect). Optellen en klaar!

Alle paartjes doorlopen tot een foute is volgens mij O(n^2) toch? Dit probeerde ik eerst en is trager dan een slim sorteeralgoritme.

[Satom]

Soultaker schreef op donderdag 5 december 2024 @ 13:44:
Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Hier zijn twee voorbeeld invoeren voor dag 5: aoc-2024-day-05-challenge-1-and-2.zip

Als je de antwoorden van deel 1 en deel 2 vermenigvuldigt moet er 9812096 (voor challenge-1.txt) en 6145186 (voor challenge-2.txt) uitkomen. Ben heel benieuwd hoeveel programma's de correcte uitvoer genereren!

Ik ben geslaagd(!)

---

Heb mij wel lang vastgebeten op deel 2, van alles geprobeerd en iedere oplossing resulteerde in een snelle example run, maar een zeer langzame reguliere run. Uiteindelijk mijzelf voor de kop geslagen toen ik doorhad dat je eenvoudig

spoiler:

de getallen van de "gehitte" rule kunt verwisselen en dit blijven doen totdat het een geldig result is

. Deel 2 kost ongeveer 350 msec, wat mij betreft voor nu helemaal goed. Ben allang blij dat ik in ieder geval tot (en met) dag 5 bij ben!

[nescafe]

Satom schreef op donderdag 5 december 2024 @ 18:31:
[...]
Ik ben geslaagd(!)

spoiler:

Met nog een beetje slimmigheid kun je het proces versnellen: Je hoeft bijv. niet telkens vanaf 0 te beginnen, hooguit vanaf de laagste positie die je daarvoor gewisseld hebt.

[Friits]

Soultaker schreef op donderdag 5 december 2024 @ 17:07:Wat had je hierbij precies in gedachten?

Nog niets, had alleen (met een hoop handwaving) beredeneerd dat het wel zou moeten kunnen. Zelf heb ik niet echt de behoefde (of de tijd) om er mee aan de slag te gaan, maar ik dacht: ik gooi het in de groep, misschien vindt iemand het interessant om te gebruiken voor hele snelle code

(...) dat is inderdaad loeiend snel, maar helaas niet correct (het werkt toevallig wel op de AoC invoer, dus als dat je standaard is, kun je het inderdaad daarbij laten).

Oh dat is inderdaad mijn standaard: ik los de puzzel op en niet het algemene probleem. Wel heel leuk dat sommigen hier het breder trekken!

[Creepy]

Meh. Deel 1 was zo gebeurd, deel 2 had ik wat meer moeite mee en ben er dan ook niet tevreden over. Het werkt, maar het is traag. Ja het is effectief een bubble sort, die ook nog eens meerdere keren herhaalt wordt.
https://github.com/CodeEn...er/aoc/aoc2024/Day05.java

[Bolukan]

Vandaag dag 4 en 5 gedaan. Dag 5 grootste probleem dat ik het antwoord uit de testdata bleef intikken.
Dag 4: 0,05 seconde

spoiler:

Gewerkt met een array van directions, en bij deel 2 had ik een bug dat ik spiegelde ipv draaide

Dag 5: 0,2 seconde

spoiler:

Nadat ik circel-volgordes vond (1-2, 2-3, 3-1), ben ik gestopt met pre-processing. Alle combinaties andersom als string in de volgordelijst gezocht, en voor deel 2 geswapt.

[FCA]

Soultaker schreef op donderdag 5 december 2024 @ 13:44:
Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Hier zijn twee voorbeeld invoeren voor dag 5: aoc-2024-day-05-challenge-1-and-2.zip

Als je de antwoorden van deel 1 en deel 2 vermenigvuldigt moet er 9812096 (voor challenge-1.txt) en 6145186 (voor challenge-2.txt) uitkomen. Ben heel benieuwd hoeveel programma's de correcte uitvoer genereren!

Als je heel strict leest is deel 2 volgens deze interpretatie niet oplosbaar:
Bij deel 1 kun je inderdaad alle paren checken of ze toegestaan zijn (dus niet b, a als er een regel a|b is), maar bij deel 2 zou je gewoon een aantal "onvergelijkbare" elementen kunnen toevoegen (die dus niet een ordering relatie met andere getallen in de lijst hebben), kun je meerdere "correcte" goede orderings hebben, en dus geen eenduidig antwoord. Impliciet wordt er dus voor deel 2 vanuit gegaan dat de ordering compleet per rij is, terwijl dat niet gespecificeerd wordt in de tekst.

Concreter, stel je hebt
75|53
75|47
97|75
75|61
97|61
97|47
97|53
47|53
61|53

75,97,47,61,53

Nu zijn 47 en 61 onvergelijkbaar, en zijn
97,75,47,61,53
en
97,75,61,47,53
correct gesorteerde oplossingen, maar met 2 verschillende middenwaardes.

[ Voor 8% gewijzigd door FCA op 05-12-2024 22:04 ]

[FCA]

Marcj schreef op donderdag 5 december 2024 @ 17:21:
[...]

Ik heb altijd een iterator over de regels, dus met Strings. Ken je dan ook de by_ref() methode? Dan kun je een iterator gebruiken tot een bepaald punt met take_while(..). Zie hier het voorbeeld hoe ik het doe.

Dank! Die kende ik nog niet. Heb gelijk nu toegepast, gaat vast van nut zijn bij de volgende dagen.

[Bolukan]

Soultaker schreef op donderdag 5 december 2024 @ 13:44:
Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Hier zijn twee voorbeeld invoeren voor dag 5: aoc-2024-day-05-challenge-1-and-2.zip

Als je de antwoorden van deel 1 en deel 2 vermenigvuldigt moet er 9812096 (voor challenge-1.txt) en 6145186 (voor challenge-2.txt) uitkomen. Ben heel benieuwd hoeveel programma's de correcte uitvoer genereren!

Niet nodig gehad voor AoC, maar mijn code verbeterd zodat deze opgaven ook juist opgelost worden.

[Creepy]

Zo, ff de standaard sort optie gebruikt met een eigen comperator en dan werkt het wel snel. Te gaar om te zien dat het "gewoon" een sort is.

[TrailBlazer]

Mijn oplossing om één hele grote lijst van de juiste volgorde werkte dus niet omdat er rare loops in zitten. Uiteindelijk met cmp_to_key een sort gemaakt. Uiteindelijk ook veel makkelijker voor deel2

[ElkeBxl]

Soultaker schreef op donderdag 5 december 2024 @ 13:44:
Ik ben er zojuist achter gekomen dat het merendeel van de oplossingen die hier gepost zijn eigenlijk niet klopt, inclusief de oplossing die ik zelf gepost had. (Maar de oplossing die ik oorspronkelijk in elkaar gehackt had was wél correct! Dus bij het “mooier maken” heb ik een bug geïntroduceerd.) Jullie hebben allemaal mazzel dat Eric Wastl zo lief is dat er geen moeilijke cases in de invoer zitten.

Geniaal, mijn code werkte voor AoC maar niet voor je challenges Met een vuile oplossing lukt het me wel tot de oplossing te komen. Heb even gezocht maar geen idee hoe het proper op te lossen.

Dag 5 in TypeScript

[Trasos]

Merk hier in de comments al dat er toch wel een verschil zit in de 'enterprise' programmeurs zoals ik, die gechargeerd alleen CRUD-applicaties maken en de 'echte' programmeurs die wiskundig het probleem weten te doorgronden.

Na een paar dagen AoC beginnen de imposter syndroom symptomen alweer aardig op te spelen bij mij.
Deze beginnerspuzzels kosten me al aardig wat tijd, vooral als zoals vandaag de opdracht me niet meteen helemaal duidelijk was.

Maar we gaan we gewoon lekker door, en leer ondertussen nog wat bij van jullie oplossingen.

[CrossProd]

Voor het eerst deze AoC dat ik om 6:00 ben begonnen en blij met mijn 965e plek in de ranglijst

spoiler:

Erg naïeve oplossing door op alle plekken (1 voor 1) langs het pad een obstructie te plaatsen en te kijken of het een loop maakt. Dit kan vast een stuk beter maar dat komt later vandaag wel.

Oplossing in Swift: github

[ Voor 3% gewijzigd door CrossProd op 06-12-2024 06:52 ]

[Soultaker]

Ik dacht vandaag wat tijd te besparen door een array met richtingen uit een ander scriptje te kopiëren:

Python:

DIRS = [(-1, 0), (0, 1), (1, 0), (-1, 0)]

Spot de fout. Kon ik dat weer zitten debuggen. Heeft me uiteindelijk meer tijd gekost dan opgeleverd, maar ja, dat is de risico van het vak.

Verder is mijn oplossing redelijk traag (ruim 3 2,5 seconde mét PyPy, maar liefst 16 8 zonder) dus eigenlijk wil ik dat ook nog even fixen.

---

En nog even over dag 5:

FCA schreef op donderdag 5 december 2024 @ 21:44:
Als je heel strict leest is deel 2 volgens deze interpretatie niet oplosbaar:
Bij deel 1 kun je inderdaad alle paren checken of ze toegestaan zijn (dus niet b, a als er een regel a|b is), maar bij deel 2 zou je gewoon een aantal "onvergelijkbare" elementen kunnen toevoegen (die dus niet een ordering relatie met andere getallen in de lijst hebben), kun je meerdere "correcte" goede orderings hebben, en dus geen eenduidig antwoord. Impliciet wordt er dus voor deel 2 vanuit gegaan dat de ordering compleet per rij is, terwijl dat niet gespecificeerd wordt in de tekst.

Zoals ik het las, garandeerde de probleemstelling alleen dat het middelste element eenduidig te bepalen is. Hoewel ik nu zie dat er ook wel iets in de tekst staat wat jouw interpretatie ondersteunt:

use the page ordering rules to put the page numbers in the right order

Je kunt “the right order” redelijkerwijs interpreteren als: er is dus 1 specifieke correcte ordening, en niet meer dan dat.

Maar zelfs bij partiële ordening kan het middelste element eenduidig bepaald zijn. Hier is een voorbeeld:

1|3
2|3
3|4
3|5

1,2,3,4,5
5,4,3,2,1

Je zou hier meerdere sorteringen kunnen hanteren (2,1,3,4,5 of 1,2,3,5,4 b.v.) maar het middelste element moet duidelijk 3 zijn.

Ik snap dat dat een discutabele interpretatie van het probleem is, vandaar dat ik deze cases in de tweede testset gestopt had, en niet de eerste, die alleen ondiscutabele cases met totale ordening bevat, zoals:

1|2
2|3
3|4
4|5

1,3,5,2,4
3,4,5,1,2

(Hier is alleen "1,2,3,4,5" een correcte oplossing.) Grappig genoeg lijken de meeste oplossingen ófwel beide sets goed te doen, ófwel beide sets fout. Het onderscheid dat je hier maakt tussen totale en partiële ordeningen lijkt dus praktisch weinig uit te maken.

[ Voor 0% gewijzigd door Soultaker op 06-12-2024 08:27 . Reden: Iets sneller gemaakt ]

[mbe81]

Helaas, op de voorbeeldinput krijg ik de juiste antwoorden, op de werkelijke input krijg ik voor stap 2 een verkeerd resultaat. Later vandaag nog maar eens verder kijken.

[Corniel]

Soultaker schreef op vrijdag 6 december 2024 @ 07:02:

Verder is mijn oplossing redelijk traag (ruim 3 seconde mét PyPy, maar liefst 16 zonder) dus eigenlijk wil ik dat ook nog even fixen.

Mijn oplossing voor deel 2 is 1.2s, en deel 1 is 610 us (C#). Ik ben tevreden over hoe netjes ik het heb opgeschreven en ondanks dat ik vermoed dat bij deel twee er vast een (flink) aantal early exits genomen kunnen worden, denk ik dat ik het er bij laat.

@Trasos Niet zo hard op je zelf. En heb je een link naar de je oplossingen? Ben wel benieuwd wat jij in de AoC context als corperate bestempelt.

[FCA]

Deel 1 waa redelijk standaard AoC kost, snel gepiept. Voor deel 2 was mijn idee goed

spoiler:

gewoon een for loop om deel 1 heen zetten met als mogelijke blokkeerposities de stappen die de guard in deel had gezet, en de richting in de hashset van "ben ik al geweest" ook de richting te zetten, maar de uitvoering was wat te gehaast, dus eerst vergeten de initial guard positie te resetten, de initiele guard positie uit te sluiten, en als uitsmijter had ik een aanname over de data die voor de testset en voor deel 1 waar was, maar nu niet meer. Karma laten we maar zeggen

En ik benieuwd of er een snellere oplossing voor deel 2 is, mijn oplossing is nu meer dan 1000x trager dan deel 1

[ Voor 9% gewijzigd door FCA op 06-12-2024 07:42 ]

[Friits]

Soultaker schreef op vrijdag 6 december 2024 @ 07:02:
Spot de fout. Kon ik dat weer zitten debuggen. Heeft me uiteindelijk meer tijd gekost dan opgeleverd, maar ja, dat is de risico van het vak.

Mag ik het evangelie van complexe getallen verkondigen?

De positie is een getal in de vorm van x + y j, de richting is één van 1, -1, 1 j, of -1j. Een stapje zetten kan dan eenvoudigweg door positie en richting op te tellen:

code:

>>> pos = 6+3j
>>> dir = 1j
>>> pos + dir
(6+4j)

Van richting veranderen is ook heel elegant: eenvoudigweg vermenigvuldigen met 1 j of -1j:

code:

>>> dir = 1j
>>> dir * 1j
(-1+0j)

---

Soultaker: Verder is mijn oplossing redelijk traag (ruim 3 seconde mét PyPy, maar liefst 16 zonder) dus eigenlijk wil ik dat ook nog even fixen.

Mijn implementatie werd juist trager met PyPy (6 i.p.v. 5 seconden).

[Corniel]

Friits schreef op vrijdag 6 december 2024 @ 07:53:
[...]

Mag ik het evangelie van complexe getallen verkondigen? (..)

---

Elegant is het zeker. Zelf heb ik de notie van een Point, Vector en Cursor (combo van de twee). Ik kan dus dingen doen als

code:

point = point + new Vector(3, 2);

var cusor = new Cursor(point, new Vector(1, 0));
cursor = cursor.Move();
cursor = cursor.RotateRight();
cursor = cursor.Move(-3);
cursor = cursor.UTurn();

En ja, points en vectors zijn wiskundig uitwisselbaar, maar door ze te scheiden voorkom je bugs waarbij punten bij elkaar worden opgeteld e.d.

Ik merk dat dit soort code mij helpt om minder bugs te creeeren, en mijn code voor simpele zielen als ik zelf leesbaar en begrijpelijk te houden.

[ Voor 0% gewijzigd door Corniel op 06-12-2024 09:27 . Reden: opmaak ]

[mbe81]

mbe81 schreef op vrijdag 6 december 2024 @ 07:18:
Helaas, op de voorbeeldinput krijg ik de juiste antwoorden, op de werkelijke input krijg ik voor stap 2 een verkeerd resultaat. Later vandaag nog maar eens verder kijken.

spoiler:

Sukkel dat ik ben! Ik ging er vanuit dat je na een draai altijd op een geldige positie terecht zou komen. Maar soms staat daar ook al een blokkade en moet je dus nog een keer draaien.

[Remcoder]

mbe81 schreef op vrijdag 6 december 2024 @ 08:17:
[...]

spoiler:

Sukkel dat ik ben! Ik ging er vanuit dat je na een draai altijd op een geldige positie terecht zou komen. Maar soms staat daar ook al een blokkade en moet je dus nog een keer draaien.

D'oh, die had ik ook gemist

[Soultaker]

Friits schreef op vrijdag 6 december 2024 @ 07:53:
Mag ik het evangelie van complexe getallen verkondigen?

Erg slim gevonden, en geeft een mooie compacte oplossing De implementatie is wel een beetje te obscuur voor m'n smaak, en het staat me tegen dat die complexe getallen intern als floating point getallen geïmplementeerd worden.

Mijn implementatie werd juist trager met PyPy (6 i.p.v. 5 seconden).

Interessant, het is zelden dat PyPy de code trager maakt. Mogelijk kan PyPy de operaties op complexe getallen niet optimaliseren, of de interactie met de dictionary.

(Overigens doet jouw oplossing er bij mij 15 s over met Python3, en ~16,5 s me PyPy. Merk op dat dit een dag is waar de uitvoertijd sterk kan verschillen per invoerbestand.)

[ElkeBxl]

Tijdens het sporten vanochtend had ik plots een idee hoe ik dag 5 toch nog kon oplossen met @Soultaker zijn 2 challenges. Resultaat voor challenge 2 vindt hij nu ergens na 600ms, good enough for now.

Vanavond of morgen dag 6 doen

Trasos schreef op vrijdag 6 december 2024 @ 01:06:
Merk hier in de comments al dat er toch wel een verschil zit in de 'enterprise' programmeurs zoals ik, die gechargeerd alleen CRUD-applicaties maken en de 'echte' programmeurs die wiskundig het probleem weten te doorgronden.

Na een paar dagen AoC beginnen de imposter syndroom symptomen alweer aardig op te spelen bij mij.
Deze beginnerspuzzels kosten me al aardig wat tijd, vooral als zoals vandaag de opdracht me niet meteen helemaal duidelijk was.

Maar we gaan we gewoon lekker door, en leer ondertussen nog wat bij van jullie oplossingen.

Herkenbaar. Het is zelden dat ik nog iets zoals sortering moet doen en in mijn job kom ik er vaak mee weg om gewoon .sort() te doen en zijn zaken zoals een queue of een stack eerder een uitzondering. Dat is 1 van de redenen om mee te doen met de AoC, dan schrijf ik nog eens wat algoritmes zoals een insertion sort en onthou ik nog wat het verschil is tussen een queue en een stack

[ Voor 69% gewijzigd door ElkeBxl op 06-12-2024 08:39 ]

[Friits]

Soultaker schreef op vrijdag 6 december 2024 @ 08:32:
Erg slim gevonden, en geeft een mooie compacte oplossing De implementatie is wel een beetje te obscuur voor m'n smaak, en het staat me tegen dat die complexe getallen intern als floating point getallen geïmplementeerd worden.

Ik moest ook even wennen, maar inmiddels behoort het tot m'n standaard-uitrusting voor grid-based problemen in AoC (ook doolhoven, etc.) net als de defaultdict().

[ Voor 242% gewijzigd door Friits op 06-12-2024 09:00 . Reden: Hier stond een slecht idee :X ]

[nescafe]

FCA schreef op vrijdag 6 december 2024 @ 07:41:
En ik benieuwd of er een snellere oplossing voor deel 2 is, mijn oplossing is nu meer dan 1000x trager dan deel 1

spoiler:

De mogelijke blokkeerposities kun je beperken tot de afgelegde route in deel 1

[FCA]

nescafe schreef op vrijdag 6 december 2024 @ 08:56:
[...]

spoiler:

De mogelijke blokkeerposities kun je beperken tot een rand om de afgelegde route in deel 1

Dat doe ik al

spoiler:

sterker nog, je hoeft alleen posities te proberen die in deel 1 daadwerkelijk bezocht worden

maar dat levert nog steeds de 1000x factor op.

spoiler:

ik bedacht me net dat ik alleen hoef te checken per obstakel wat bezocht wordt, niet elke positie die bezocht wordt, dat kan een hap schelen

[Woy]

Vandaag redelijk brute-force de oplossing voor deel 2 gedaan. IMHO ook veel te veel code, maar ik merk dat ik op het moment gewoon niet de rust en tijd heb om het veel eleganter te doen.

https://github.com/rverst.../blob/main/Y2024/Day06.cs

[MatHack]

FCA schreef op vrijdag 6 december 2024 @ 09:01:

spoiler:

ik bedacht me net dat ik alleen hoef te checken per obstakel wat bezocht wordt, niet elke positie die bezocht wordt, dat kan een hap schelen

spoiler:

Mis je dan niet de loops die ontstaan door een obstakel in het pad te zetten, waarna het pad afwijkt van het pad van deel 1?

[Mugwump]

FCA schreef op vrijdag 6 december 2024 @ 07:41:
Deel 1 waa redelijk standaard AoC kost, snel gepiept. Voor deel 2 was mijn idee goed

spoiler:

gewoon een for loop om deel 1 heen zetten met als mogelijke blokkeerposities de stappen die de guard in deel had gezet, en de richting in de hashset van "ben ik al geweest" ook de richting te zetten, maar de uitvoering was wat te gehaast, dus eerst vergeten de initial guard positie te resetten, de initiele guard positie uit te sluiten, en als uitsmijter had ik een aanname over de data die voor de testset en voor deel 1 waar was, maar nu niet meer. Karma laten we maar zeggen

En ik benieuwd of er een snellere oplossing voor deel 2 is, mijn oplossing is nu meer dan 1000x trager dan deel 1

spoiler:

Dit was ook mijn aanpak, maar bij mij is ongeveer 10000x trager. Deel 1 gaat in 16ms, deel 2 in 165s waarbij ik dan ook nog gebruik maak van parallel streams omdat je de verschillende opties onafhankelijk van elkaar kunt evalueren.

[Woy]

Mugwump schreef op vrijdag 6 december 2024 @ 09:06:
[...]

spoiler:

Dit was ook mijn aanpak, maar bij mij is ongeveer 10000x trager. Deel 1 gaat in 16ms, deel 2 in 165s waarbij ik dan ook nog gebruik maak van parallel streams omdat je de verschillende opties onafhankelijk van elkaar kunt evalueren.

spoiler:

Bij mij is het maar ongeveer ~600 maal trager, maar het zal ook aan de input liggen hoe lang het duurt voordat een cycle onstaat en dus hoe lang de check duurt

[Hagdos]

Voor dag 6 laat ik de guard nu steeds 1 stap "vooruit" zetten, om dan te controleren of daar een obstakel staat. Ik denk dat dat sneller zou moeten kunnen door meteen in de hele rij/kolom te zien wat het volgende obstakel is. Is daar een handige manier voor?

Itereren over alle obstakels is niet echt minder dan itereren over de stappen tot je bij het volgende obstakel bent.

[Woy]

Hagdos schreef op vrijdag 6 december 2024 @ 09:11:
Voor dag 6 laat ik de guard nu steeds 1 stap "vooruit" zetten, om dan te controleren of daar een obstakel staat. Ik denk dat dat sneller zou moeten kunnen door meteen in de hele rij/kolom te zien wat het volgende obstakel is. Is daar een handige manier voor?

Itereren over alle obstakels is niet echt minder dan itereren over de stappen tot je bij het volgende obstakel bent.

Je kunt natuurlijk een simpele datastructuur maken waar je alleen de obstakels inzet en groepeert per rij/column, dan kun je met een pos/richting eenvoudig het eerste obstakel vinden.

[Robbinb1993]

Hagdos schreef op vrijdag 6 december 2024 @ 09:11:
Voor dag 6 laat ik de guard nu steeds 1 stap "vooruit" zetten, om dan te controleren of daar een obstakel staat. Ik denk dat dat sneller zou moeten kunnen door meteen in de hele rij/kolom te zien wat het volgende obstakel is. Is daar een handige manier voor?

Itereren over alle obstakels is niet echt minder dan itereren over de stappen tot je bij het volgende obstakel bent.

Ik had dezelfde optimalisatie in gedachten. Wat het alleen wat ingewikkelder maakt, is dat als je voor part 2 obstakels gaat toevoegen, de datastructuur op meerdere plekken aangepast dient te worden (links, rechts, boven, onder). Voor de volgende stap moet dit weer gerevert worden. Ik ga hier later vandaag naar kijken.

We kunnen in eerste instantie eenvoudig rij voor rij (van links naar rechts, rechts naar links), kolom voor kolom (van boven naar onder, onder naar boven) de grid preprocessen, waarbij we bijhouden waar het vorige obstakel ligt en deze lokatie in opvolgende cells opslaan in een matrix. Dan weten we hoe ver we kunnen bewegen als we in een van die cellen aankomen, waarbij we lege cells skippen door op te vragen waar het volgende obstakel zich bevindt (hierbij is de direction ook een variabele). Dit is een vorm van 1D dynamisch programmeren.

[ Voor 42% gewijzigd door Robbinb1993 op 06-12-2024 09:41 ]

[Corniel]

Zonder weg te geven wat ik heb geoptimaliseerd (al kon het worden samengevat met: niet onnodig bijhouden) zit ik nu op
deel 1: 284 us
deel 2: 157 ms
factor 633

Hoewel niet fantastisch vind ik 157ms een prima tijd, en ik ga proberen niet nog verder te zoeken naar meer verbeteringen (kijken of dat ook lukt).

[Friits]

Het idee van @FCA (als ik het goed begrijp) levert op mijn input een factor 2 winst op:

spoiler:

Voor deel 1 moeten we alle bezochte plekken bijhouden om het antwoord uit te rekenen. Voor deel 2 hoeft dat niet, dus het is voldoende om alle "keerpunten" bij te houden: maken we een bepaalde draai opnieuw, dan zitten we in een loop. In mijn code was dat een eenvoudige verandering; de regel

seen |= {(pos,dir)}

verplaatsen van buiten naar binnen de conditie voor het detecteren van een obstakel.

[ Voor 6% gewijzigd door Friits op 06-12-2024 09:26 ]

[Marcj]

Ik had eerst maar een hele domme implementatie gemaakt voor deel 2.

spoiler:

Het grid vaak kopieren en gewoon op elke lege plek proberen een blokkade te zetten en dan kijken of er een loop onstaat bij het wandelen of niet.

Maar met een release build weet Rust het zo te optimaliseren dat het nog steeds vrij snel is. Dus ja, moeten we dan moeite stoppen in het verder optimaliseren?

code:

$ day6 < input/day6.txt
Executing
 ├── Input parsed in 196µs
 ├── Part 1 calculated in 52µs: 4711
 ├── Part 2 calculated in 34,838µs: 1562
 └── Total time: 35,115µs

Als ik vanmiddag ergens tijd heb wil ik wel even verder kijken...

[ Voor 8% gewijzigd door Marcj op 06-12-2024 09:41 ]

[Mugwump]

Friits schreef op vrijdag 6 december 2024 @ 09:25:
Het idee van @FCA (als ik het goed begrijp) levert op mijn input een factor 2 winst op:

spoiler:

Voor deel 1 moeten we alle bezochte plekken bijhouden om het antwoord uit te rekenen. Voor deel 2 hoeft dat niet, dus het is voldoende om alle "keerpunten" bij te houden: maken we een bepaalde draai opnieuw, dan zitten we in een loop. In mijn code was dat een eenvoudige verandering; de regel

seen |= {(pos,dir)}

verplaatsen van buiten naar binnen de conditie voor het detecteren van een obstakel.

Kennelijk maakt je input hier echt heel, heel veel uit.

spoiler:

Ik had bij deel 1 een route met 5199 punten. Voor deel 2 heb ik 1915 geldige blokkadeposities.

Als ik deel 2 doe door elke bezochte positie bij te houden om een loop te detecteren duurt het dus zo ongeveer 165 seconden.
Houd ik enkel de draaipunten bij, dan is dit slechts 850ms, oftewel ongeveer 200x zo snel.

[MueR]

Woy schreef op vrijdag 6 december 2024 @ 09:03:
Vandaag redelijk brute-force de oplossing voor deel 2 gedaan. IMHO ook veel te veel code, maar ik merk dat ik op het moment gewoon niet de rust en tijd heb om het veel eleganter te doen.

CPU go brrrrr is toch prima?

Mijn dag 6 doet ook redelijk brr.

[bakkerjangert]

Mijn implementatie met numpy. Voor deel2 hergebruik ik de uitkomst van deel 1.