>>107476777
25 minutes, where is everybody?
there's finally going to be a hard puzzle today, aren't you excited?
today's the day! for real this time!

>>107476777
>the first 6 problems scaled in difficulty like previous years
>the last 6 problems will scale 4x faster than previous years
brace yourselves

File: lucky.jpg (122 KB, 1280x720)

122 KB JPG

>>107476777
>lucky 777
25 minutes until show time

babies first maze incoming. It wont be satisfying or difficult in any way.

fuck let me google djikstra's again

File: tgf 1765165163 - merged -(...).png (718 KB, 1911x1963)

718 KB PNG

>117 non filtered users
>the thread is dead
Be honnest, how many user accounts do you fags have?

File: dance.gif (402 KB, 544x384)

402 KB GIF

aoc time
https://files.catbox.moe/tuevnx.mp4

>>107476839
cancer music

>>107476835
117, why?

If it's another nothing-burger day, I will kms.
>>107476819
Make sure to understand what separates it from BFS/DFS and A* as well.

>>107476802
>there's finally going to be a hard puzzle today, aren't you excited?
Nope.

>>107476849
A* just dijkstra's with a heuristic
no point in learning it

File: WALL_INCOMING.jpg (157 KB, 462x260)

157 KB JPG

TONIGHT'S THE NIGHT

>>107476839
AI gem

File: pump_it.jpg (153 KB, 1280x720)

153 KB JPG

I predict shoelace algo

>>107476863
HOLD THE LINE
DO NOT POOP

>>107476884
math tricks aren't inclusive, sorry

>>107476848
actually 120 right now, in total for both leaderboards

>>107476855
Ya but if your heuristic is fucked, it can fuck it up. But yes sure in general it's safer to not know it than to know it.

chinese remainder theorem

https://cp-algorithms.com/graph/dijkstra.html
read up, anon
yes (You)

>>107476913
>cp
nice try fed

https://www.youtube.com/watch?v=dixIdOlhqOU&t=500s
post programming music
bonus points if sophisticated like mine

>>107476913
I agree, it feels like it's time for a dijkstra or A*

>>107476932
this is a prank, right?

don't really feel like writing pathfinding again

>>107476932
https://www.youtube.com/watch?v=tKi9Z-f6qX4

>>107476933
per haps nigger `hip hop' is more your speed
you are not refined

5 MINUTES

File: showtime.jpg (46 KB, 640x480)

46 KB JPG

https://www.youtube.com/watch?v=hjGZLnja1o8

>>107476953
cancer music

Problem preview is up for AoC++

>>107476942
https://www.youtube.com/watch?v=SqayDnQ2wmw

tea = brewed

File: 244564.jpg (213 KB, 1920x1080)

213 KB JPG

>>107476932
Crystal Mother Fucking Castles. Tell me this isn't hacker vibe!
https://www.youtube.com/watch?v=9XViPhRnOiQ

File: 1671512323771599.png (49 KB, 662x242)

49 KB PNG

>>107476953

>>107476961
I'm reading it now, did Eric jump the shark? I don't even know where to start with programming this task, this is way too hard

>>107476961
AoC# hints were up yesterday, poorfag

>>107476961
>boring shit again
fuuuuuck why do I pay for this garbage

>>107476932
https://www.youtube.com/watch?v=w0vtAaAV9oI

>>107476911
Been listening to French 79 lately. Great if you like 'chill' electronic music.
https://www.youtube.com/watch?v=FpnXnQqVrBQ

>>107476968
>3.5
seems like centuries ago....

>>107476932
https://www.youtube.com/watch?v=iZndVv-jl-U
something about the chaos is soothing to my brain when i'm trying to think or power through burnout

>>107476971
they've already rewritten the hints in rust

>>107476932
https://youtu.be/g4mHPeMGTJM
kino

>>107476932
https://www.youtube.com/watch?v=2FG8-ksygKc
Core memory listening to this while solving AOC 2021

>>107476953
>>107476954
I click on these every thread every year. At first I hated it. Now I love it.
>ONE TWO SEVEN THREE
GOOD LUCK

the great filter

FUCK

FUCK

>3D space
LET'S GOOOOOOOO

>>107477000
>trips
>exact time

Blessed post

wtf

>3d pathfinding
yay

FUCK

>it's another slightly convoluted parsing problem

fell for it again participation ribbon

TRAVELING CHRISTMAS LIGHTS PROBLEM?? WTF

>>107476777 = 67 * 1604131
>a list of all of the junction boxes' positions in 3D space
how much did you pay for AoC#?

File: dubsfall.jpg (67 KB, 855x625)

67 KB JPG

>>107477000
holy checked

>union find

oh fug this sounds hard

oh shit nigga this really is the filter

giving this problem on a sunday night huh

If you're not implementing an octree right now you're not real programmer

File: 1746565035364762.png (467 KB, 800x800)

467 KB PNG

wtf is this uninspired junk

>3D Problem
>3D Cube OP
>PREDICTED??
eric makes 4chan threads confirmed. nice try eric.

>>107477038
>tree
no thanks, those guys are always talking about "deforestation" and praising a lack of depth. Weird, backwards people.

>pass my compiled bin as the daily input 12 times in a row
>open compiled bin in vs thinking it's my corrupted daily input
>paste correct input in the bin file
>try to run this bin 5 more times

i will kill myself, it's the only honourable way

SOLVED
that was at least interesting
still wasn't crazy difficult though

well i got the first connection right, then none of the others are right because i'm supposed to reuse the first point for the next connection

File: xarbon.png (22 KB, 884x980)

22 KB PNG

I started writing the DSU but then the brute ran lol

Day   -Part 1-   -Part 2-
  8   00:15:18   00:22:19

>problem has a separate parameter for how many connections to make
>this parameter is different between inputs
>it is specified nowhere in the input
fuck you eric I thought we were done with this kind of stuff

File: carbon.png (127 KB, 1768x648)

127 KB PNG

>import solution

Day   -Part 1-   -Part 2-
  8   00:11:52   00:19:55

>>107476981
very soothing
>'chill' electronic music
this reminded me of this one:
https://www.youtube.com/watch?v=I--4bc6S59U

File: 1752068241413022.jpg (50 KB, 462x623)

50 KB JPG

LE MERGE MEME

File: code.png (457 KB, 1572x2154)

457 KB PNG

Day   -Part 1-   -Part 2-
  8   00:25:16   00:27:32

finally some good puzzles

File: CodeSnap_2025-12-08_at_00(...).png (833 KB, 2101x3000)

833 KB PNG

>easy puzzle again
My morale is at an all time low. Its time to kill Eric

god i hate ones where i have to change some parameters in the code due to the examples being different from the real one, i always forget

>>107477167
>death threat
jeet or mudslime?

>>107477181
first day huh buddy? Enjoy your stay, its a school night today so you better get to bed.

>>107477187
>thinks it's midnight
So amerimutt, got it. Or H-1B jeet or mudslime.

>>107477195
>le edgy racist

>>107477201
I'm not racist, I'm culturist. Death threats are not very fashionable nor the usual modus operandi against someone who you don't like in western culture.

File: 1745811617650487.jpg (34 KB, 793x594)

34 KB JPG

there are only 4 puzzles left

>30 minutes post puzzle drop
>/pol/niggers are here
alright pack it up guys, /aocg/ is a rotting corpse.

advent of reading comprehension

>>107477221
back to where you came from, tourist

>>107477142
not even going to bother washing my ass after seeing this, you mogged me hard

>>107477234
using networkx doesn't count as mogging

File: 1587006326150.png (73 KB, 834x1256)

73 KB PNG

i solved it in my head but i dont want to write the code

File: 1761639361417773.jpg (218 KB, 555x555)

218 KB JPG

>straight-line distance
FUCKING ERIC

File: carbon.png (130 KB, 724x736)

130 KB PNG

Day   -Part 1-   -Part 2-
  8   00:26:07   00:29:35

>an import solution day
Phew, I almost had to write some code this year.

>>107477229
if you weren't on /prog/ you need to sit your ass down and respect your elders.

>>107477243
I wrote the code but still have not solved it in my head. that union find bullshit never sat right with me

> preoptimized with DSU for skipping already connected components during p1
> whining that they don't have cables
> they keep connecting them anyway in p2

That it's elves, back to the Shein factory you go

>>107477227
definitely

>>107477248
this tripped me up too

>>107477218
how are everyones bonus puzzles going. I feel like mine is too convoluted with 10000 edge cases in the rules. Also I forgot that my part 1 is like identical to a part 1 in a previous year. Also I haven't made the input or the test case or the problem statement or the story yet.

>>107477142
This is the solution that actually gets you a job

I'm curious if the input has anything interesting when visualized.

File: 1763419142112584.png (83 KB, 669x907)

83 KB PNG

I really need to start using libraries

>mfw it wasn't slow, it was in an infinite loop

>>107477297
I purposefully choose to never import itertools and functools and spend 10 minutes fucking up my implementation of combinations and permutations and caching every time. I should just import.

>>107477297
use math.dist at least

Really struggled today with lang issues

Day   -Part 1-   -Part 2-
  8   00:45:20   00:52:00

I implemented DSU, unlike some import solution anons here :)

>>107477132
>but then the brute ran lol
it often does, anon. sadly

>>107477321
why mess with floats when ints do? just don't do the sqrt and the order will still hold between them

>>107477321
Thanks, I'm new to python. I realised after posting that you don't actually need to do the sqrt() you can compare the squared distances and save some time.

File: 8.png (356 KB, 1518x2344)

356 KB PNG

first actually fun puzzle (still way too though)

>>107477337
>why mess with floats when ints do? just don't do the sqrt and the order will still hold between them
because implementing it yourself is a waste of time

>>107476994
The song has become synonymous with AoC for me, it's awesome.

File: carbon(2).png (529 KB, 1346x4842)

529 KB PNG

>part 2 was like three extra lines and an early exit

thank god my spaghetti pulled through. there has to be a better way than what i did lel

>>107477343
anon, aoc is a waste of time

>>107477342
it's not idiomatic if you don't use the same array for parent and size :)

>>107477340
that's the way anon. avoid floats when you can

apparently I'm making some wrong connection in the example input, and I don't know why...

162,817,812 <-> 425,690,689
162,817,812 <-> 431,825,988
906,360,560 <-> 805,96,715
862,61,35 <-> 984,92,344
52,470,668 <-> 117,168,530
819,987,18 <-> 941,993,340
906,360,560 <-> 739,650,466
346,949,466 <-> 425,690,689
906,360,560 <-> 984,92,344
592,479,940 <-> 425,690,689

Is there a better algorithm / data structure instead of generating 1 million distances then sort?

>>107477378
idk if this is your issue, but something that tripped me up is that the next shortest distance might be between two boxes that are already connected. so that connection should be ignored

>>107477378
The skipped connections still count towards the total

>>107477387
i was trying to think of something for that since it seems absurd but yeah i guess you can't really know the next shortest one unless you've already computed them. shouldn't take that long since its just pure math to get the dist

>>107477366(Me)
part 1 really tricked me because I thought we had to make first 1000 actual connections, and not just that many edges need to be processed

also, finding the largest 3 should not require full sorting. a 3 pass selection sort should do. or just insertion sort into a 3 len array

>>107477378
show your dist finding function. additionally, avoid floats to not deal with precision issues (probably that won't be the case because of integer coords)

>>107477387
see prim's algo on dense graph

>>107477378
You are missing one, and it just so happens to contain the light on the last line. Parsing issue/off by one. My invoice is in the mail

>>107477395
wait what? but the problems states
>Because these two junction boxes were already in the same circuit, nothing happens!
&
>After making the ten shortest connections
if nothing happens, then no connection was made, therefor a skip should NOT count as part of the 10

>>107477407

int distance = sqrt(pow(jboxes[jb1].x - jboxes[jb0].x, 2) + pow(jboxes[jb1].y - jboxes[jb0].y, 2) + pow(jboxes[jb1].z - jboxes[jb0].z, 2));

>>107477387
https://en.wikipedia.org/wiki/Ball_tree
This can be used for part 1

File: don't_believe_his_lies2.jpg (81 KB, 600x576)

81 KB JPG

>>107477415

>>107477415
A is connect to B is connected to C. Connecting C to A doesn't do anything because they are all already on, but it's still making a connection

I don't get it...

>>107477407
nvm, prim's won't do. since we need to process them in dist order. yeah, can't think of a way of avoiding sorting edges by dist. waiting for other anons' optimizations

>>107477415
a skip counts in A. this tripped me up too

16/16 for vibecoder bros!

File: 1755493397687555.jpg (99 KB, 1080x1084)

99 KB JPG

>>107477433
same anon

>>107477433
https://en.wikipedia.org/wiki/Disjoint-set_data_structure

>>107477429
but it specifically says nothing happens

>>107477444
nothing happens with the lights. ESL?

>arguing semantics
>arguing AOC semantics

>>107477444
yeah, but it does not say it won't count towards the 10 connections. nothing happens as in those don't need to be connected as they are alrady connected indirectly

>>107477433
problem is not worded properly (eric ik you see this, fix it man). you're supposed to pairwise connect nodes regardless if they are in the same component, though by the wording it may seem like "since these are already connected, nothing happens" that you don't add that edge

>>107477297
"I really need to start using libraries"
>things said moments before npm installing 300mb of dependencies to render a simple webpage

>>107477452
if they don't need to be connected then why woult they count towards the 10 connections? the problem context implies the 10 limit is because they only have 10 cables. if you don't make a connection, then you don't use a cable

>>107477452
it should (ideally) say the next two nodes are blah and blah, we connect them, but nothing happens; not just nothing happens

File: 1735455899309019.png (67 KB, 1170x603)

67 KB PNG

>>107477461
>100k weekly downloads

>>107477473
I kneel.
https://github.com/i-voted-for-trump/is-even/blob/master/index.js#L10-L14

Hey guys, the power is out and when I flicked the light switch the lights didn't turn out. DId i flick the switch or not?

anons just brute it with a bunch of hashmaps

>>107477462
>>107477465
>connect together the 1000 pairs of junction boxes which are closest together
yeah, I think there is no need need to avoid connecting two junction boxes even if they are in the same component. just add them (duplicate links). no issue there

>>107477484
I flicked your mum's switch last night if you know what I mean ;)

>>107477473
nature is recovering

>>107477489
my mom has a penis though

>>107477481
>return !isOdd(i);
>i-voted-for-trump
checks out

I'm boycotting todays problem on principle. be explicit in the questions wording next time eric

>>107477481
lmfao. the state of webshitters

>>107477497
Rust coder?

the puzzle here is understanding what the actual puzzle is
eric you did it again

>>107477395
>"Because these two junction boxes were already in the same circuit, nothing happens!"
>this doesn't mean you don't connect them though haha
That's so fucking stupid

>>107477502
and isOdd has a dependency too
https://github.com/i-voted-for-trump/is-odd/blob/master/index.js#L10-L24

>>107477497
Trannies don't understand jokes

File: day 8 visual.png (72 KB, 1000x1000)

72 KB PNG

>>107477285
Doesn't look like there's anything interesting.
Maybe if rotated a specific way, but I don't know what tools to use for that.

Are you retards really so bored you are just making excuses to have another file size of 0?

File: grin.gif (564 KB, 800x430)

564 KB GIF

>>107477481

File: carbon.png (135 KB, 834x736)

135 KB PNG

>>107477321
>added in Python 3.8
Well fuck.
I genuinely wasted about 15 minutes sorting out my distance function, because I thought I had one in my library (mostly written 2018/2019 for Python 3.7), but I couldn't figure out which one was which, so I ended up rewriting it, but kept fucking it up.

>>107477249
Also fixed an off-by-1 introduced while washing and added an optional '-p [pair count]' parameter to handle the example input.
Interestingly the off-by-1 (checking the 3 largest groups after adding 1001 pairs) did not affect my real input. Most problems of most years would have handling to punish this (e.g. make sure that pair 999, 1000, and 1001 each add a node to one of the top 3 groups).

>>107477285
eric is too careless to hide such easter eggs. besides, there are far too many inputs to all have something interesting hidden in them

>>107477515
there's a swastika in there somewhere

>>107477433
for part 1:
>you have a list of coordinates
>find the distances between all of these coordinates
>iterate through those distances, shortest first
>connect the boxes with the shortest distance (10 times in the example, 1000 times in th input)
>boxes will get indirectly connected in this process (a to b to c)
>now find the three longest connection you made and multiply together those sizes
>so if you have (a,b,c,d,e), (f,g,h,i), and (j,k,l) as your three biggest circuits, thats 5 * 4 * 3

you just KNOW eric has a blacked.com subscription

>>107477553
the combined answers for the last 5 years yield the sha256 for his username and password. that's why he keeps mentioning quantum algorithms, since if they come to pass anyone can crack the hash to login to his account

>>107477553
There's no way Eric does. I think porn is disrespectful to woman

>>107477571
whuddabout gay porn

>>107477515
eric barely bothered to make puzzles at all this year, do you REALLY think he put cool easter eggs in the inputs.

>bruteforced with disjoint sets
>accidentally solved p2 before p1
>humiliation ritual of waiting 3 minutes for my brute to run each time
okay what's the nonretarded solution?

guys it's over
we're going to have to lean into everybody codes with the gay ducks next year

>>107477587
DP

File: aoc_day_8.png (1.25 MB, 810x897)

1.25 MB PNG

You know what? I liked this one. This feels like the start of a more difficult week. I'm hopeful! See you tomorrow boys!

>>107477593
except i'm one of the dp anons
you shan't trick me

>optimal substructure?
no
>overlapping subproblems?
no

>>107477421
it can be used for part 2 too in combination with a dsu. but it seems too complicated for this. maybe for bigboys. current is O(n^2 log(n^2)) and O(n^2) space.
but I think it will still be the same time complexity because you will be enumerating all the edges anyway in min dist order

File: CodeSnap_2025-12-08_at_01(...).png (608 KB, 2373x1620)

608 KB PNG

>>107477167
probably a smarter way to merge the groups, but this is as washed as i'm going to get it today

Haha, what the fuck?

>>107477625
>current is O(n^2 log(n^2))
has eric gone back on his ten second promise?

>>107477644
are you surprised at this point? Eric has given up

>>107477619
non-DP

Is Eric ESL or just autistic?

>>107477534
>>107477586
Duck Eric spoiled me.

>>107477587
>disjoint sets
anon you answered it. look up dsu

>>107477644
n is 1e3 so that's more than fine

>>107477644
It's still well under 10 seconds

>>107477667
was ec any good? Might have to switch to it from advent of disappointment

>day 8
>no wall
it's really over isn't it

EE here, I know about electricity and circuits but damn, im being walled and I dont like it

File: 1741431196919864.png (57 KB, 600x593)

57 KB PNG

>managed to properly sort the distances and get the same results as the example
>still the other half of part 1 to go

>>107477683
Fellow EE, hang on, we can make it.

(print(list(reverse(sorted(len(map(x))))))))))
Finally some quality lisp.

i've been filtered. remember me.

File: d08_035158.png (169 KB, 960x1900)

169 KB PNG

Fuck, at least I know what to do for PS2 but fuck me even.

>>107477687
>>107477683
Actually now I think of it, we're practically building a ratsnest.

>>107477699
I completely forgot python had types that people actually used.

anons, I don't think a ball tree will work. any better way than sorting the edges and DSU?
at this rate the bigboy will have to be pretty small

>>107477698
I spit on my screen.

>example works
>"your answer is too low"
>try a different solution
>example works
>"your answer is too low"

>>107477671
>anon you answered it. look up dsu
i am using dsu
i must be doing something retarded

>>107477710
It doesn't really. The types are just labels. It's "pythonic" to type them but it means fucking nothing. If you type C: set = () it still casts it as a tuple.

>>107477718
so this happened to me. the actual last two he’s referring to is the last pair added when all the lights are connected. you don’t actually have to keep track of which one was added second last or anything

>>107477687
will do, thanks
>>107477702
a what? messed up wiring connection?

>>107477730
>but it means fucking nothing
you can get your editor to cry about it even if the interpreter is unbothered

So it's safe to assume that any one junction box can be circuited to just up to two other junction boxes directly?

>>107477681
day 9
trvst the plvn

File: giga_duck.png (302 KB, 604x606)

302 KB PNG

>>107477590
duck was a one-time thing, next year will be some other gay high fantasy shit

>calendar
is that a fucking pipe? oh no no no

>>107477753
no, think of 5 pts, 4 forming a square and one at the center of the square. the center one will be connected to all other 4

>>107477753
No?

>>107477726
oh okay fuck me i'm not precomputing and sorting distances
literally n^3
brootbros, am i doing it right?

>>107477765
>>107477764
Naruhodou

>>107477619
The problems involves shortest paths from each of the nodes, I think you should try a series of single-step Dijkstras.

>>107477297
at a point you should just make your own smaller libraries if you're the sort of autist that wants to know exactly what everything does

>>107477685
I just regenerate the distance list every single time lmao

>>107477570
if eric was based thats how he'd hand over control of advent of code to someone new now that hes tired of it
day 25 puzzle would be his hardest yet, and would reveal his login details to let the best puzzler take over

~ how many iterations is part2?

>>107477820
4000-5000

>>107477681
day 12 will break you, cap this post

>>107477815
>Santa is ready to retire, and has one last puzzle for his elves. Solve it, and you'll be the head of all future North Pole disasters.
>The problem is simple.
>Given a number, if it is even, divide it by 2.
>If it is odd, multiply it by 3, and add 1.
>What is the smallest initial number that never reaches the value 1, no matter how many steps?

File: rape_me.png (158 KB, 1218x2146)

158 KB PNG

this raped me

>>107477820
7224 cycles for me

File: carbon.png (351 KB, 774x2234)

351 KB PNG

>part one: 75582 (took 12.930792ms)
>part two: 59039696 (took 14.694542ms)

File: 176189717.jpg (6 KB, 225x225)

6 KB JPG

>>107477857
>using classes

File: code.png (627 KB, 1312x4012)

627 KB PNG

comfy C solution. ngl this one felt hardest so far.
poor folks who don't know about union-find, but even then it was pretty messy

>>107477850
>sympy import solution

>>107477867
its a struct mannn

>>107477857
>comments
thank you sarr for sharing chatgpt's solution

what... shall we use to conduct this beautiful current with. what particular element comes to mind?

aaaahh brute force

File: solve_impl.png (1.22 MB, 5546x7742)

1.22 MB PNG

idiomatic Rust solution

>>107477881
pretty sure an AI would solve this way better than my shitcode

>>107477892
mfw no abs diff in zig so I have to do stupid @intCast TwT

>>107477873
it's intuitive enough to figure out on your own, especially given it's been three hours

>>107477873
i have no idea what union find is but solved it ages ago

>>107477901
in my experience, beginners don't have the intuition

File: UnionFindKruskalDemo.gif (333 KB, 744x1052)

333 KB GIF

>>107477907
it's precisely the right algorithm/data structure for connecting things and checking if they are on the same sub-graph
each node tracks its parent, starting with being its own parent
instead of connecting the nodes directly, you connect their roots
you can rewrite node's parent during a lookup to only have 1 hop to traverse for the next lookups, this keeps it amortized
checking of two nodes are on the same sub-graph is then O(1)

Advent of my dogshit reading comprehension

>>107477933
>O(1)
It's not, it's of the order of the inverse Ackermann function.
And that's not an achievement, pretty much any set data structure will do that much.
The point of union-find is that merging is of the same complexity.
Anyway, this is completely pointless because you are still doing a naive loop over all pairs of connections to find the distances.

For part 1, the "correct" solution will need a better spatial data structure, although for the official inputs something simple will be enough to get a good speedup.
For part 2, you will need to look at Euclidean MST algorithms.

>just shy of 500,000 pair distances
Heck. Ok, if I have the distance as a 32bit float and store two indexes to the junction list as 16bit integers, that's 4MB of memory I need to allocate for that.
If I use the indexes for the circuits too, I can keep that under 1MB.
Ok, I might be able to do this. I will need to write a sorting function in assembly, though.
>inb4 single precision isn't good enough

File: rape_me.png (136 KB, 1228x1902)

136 KB PNG

lmao ok

>>107478045
someone posts about this shit every day, just default to 64 bit ints you faggot, you're not flashing this shit onto a microcontroller where every bit of space matters
>but actually i am
meme solutions get the rope

>>107478029
>it's of the order of the inverse Ackermann function
which doesn't exceed 4 for n < 10^600
just call it O(1)

>>107478073
I don't have the memory to default to 64bit ints you faggot.

>>107478029
>Euclidean MST algorithms
is there a data structure that gives the smallest pair distance and also supports merging components?

>this is completely pointless because you are still doing a naive loop
yes, and that O(n^2) loop will be worse if it weren't for an almost constant time merging. also, it's pretty convenient rather than maintaining an array of sets and then merging and updating which set each belong to.

File: carbon.png (209 KB, 1700x806)

209 KB PNG

>import solution day

>>107477644
Takes 1s in python so no problems here.

>>107478079
>well it's not REALLY O(1) but the input is small enough that it's BASICALLY O(1)
well everyone has the same length input so I guess my solution is O(1) for every input too lol it runs in the same amount of time for each input if they're all the same length lol I guess we both have O(1) solutions then

>You have successfully implemented Kruskal's Algorithm (Minimum Spanning Tree) without even realizing it.
is that even true >>107478057
why is the AI saying this. it said my code was very good so thats all the validation i rneed

>example input works
>real input doesn't work
:D

File: file.png (131 KB, 500x375)

131 KB PNG

put something related to this in the non-existent calendar

>>107478108
are there enough atoms in the universe with which you could store today's input exceeding n > 10^600? no? so it's O(1) as far as you're concerned

>>107478045
Single precision isn't good enough unless you get lucky with input since log(3*100000^2) is 34.8

>>107478125
>connections are counted even if no actually connections are made
FUCK YOU ERIC

>>107478029
>For part 1, the "correct" solution will need a better spatial data structure, although for the official inputs something simple will be enough to get a good speedup.
such as? all I know only give me closest neighbors from selected node, not closest pair globally.
add the iteration over closest pairs, that is removing visited edges, not nodes. I really can't think of any.

>It's not O(1), it's of the order of the inverse Ackermann function.
I wonder if this still holds if you override parent references to root on every lookup. (which I didn't, that would be a valid critique)

> Because these two junction boxes were already in the same circuit, ***nothing happens***!
> After making the ten shortest connections...

If nothing happens then why does it count as making a connection? Was that the puzzle?

>>107478157
you already made this post. stop

>>107478157
>s-stop noticing
>noo youre arguing semantics
>nooticing is not allowed

>>107478157
it makes sense with context:
>By connecting these two junction boxes together, because electricity can flow between them, they become part of the same circuit. After connecting them, there is a single circuit which contains two junction boxes, and the remaining 18 junction boxes remain in their own individual circuits.
>Now, the two junction boxes which are closest together but aren't already directly connected are 162,817,812 and 431,825,988. After connecting them, since 162,817,812 is already connected to another junction box, there is now a single circuit which contains three junction boxes and an additional 17 circuits which contain one junction box each.
>The next two junction boxes to connect are 906,360,560 and 805,96,715. After connecting them, there is a circuit containing 3 junction boxes, a circuit containing 2 junction boxes, and 15 circuits which contain one junction box each.
>The next two junction boxes are 431,825,988 and 425,690,689. Because these two junction boxes were already in the same circuit, nothing happens!
after connecting other ones, the circuits have changed as it wasnt connected to the circuit previously
after connecting this one, it was already part of the circuit so they havent changed. but you still connected it

>>107477678
I only did this year, haven't looked at 2024 or any of their mini-events.
Presentation is very well done, way better than AoC's webpages.
Puzzle quality is on par with pre-peak AoC, ~2015-16. Not at the quality of peak AoC (17-19), but it's promising.
Pacing is well-done, good slow difficulty ramp without any major spikes except for Fridays (and EC gives weekends off, so you have 72 hours to solve them before the next puzzle).
Lots of easter eggs in the inputs, it's usually worth it to try rendering them where applicable.

The biggest annoyance was that every part of every puzzle has a different input, which makes for 3 text files to wrangle every day. I did it manually but next time I do a year (including 2024 whenever I get around to it) I'm definitely writing some code to handle downloading my inputs automatically. Also doubly annoying when the different parts' inputs require you to rewrite your parser, although I guess AoC does that too sometimes (e.g. day 6 of this year).

I'm far more looking forward to next year's EC compared to this phoned-in bullshit. Just hoping whoever runs it doesn't lose motivation, considering how low the turnout was this year. It's around ~1% of AoC, and I just checked and turnout was only half for this year compared to 2024. The /g/derboard constituted around 10% of total participants after the first week, and about half of us made it the entire way through, which I think is cool.

/shilling (it was fun and I want more Anons in our thread next year)

>5,4,3
>5,4,3
>5,4,3
>throw away code entirely, start from scratch
>5,4,3
>5,4,3
>5,4,3
getting filtered hard by the example

>>107478208
i got 60 instead of 40 for the example when i wasnt managing the sets properly (e.g. i had some duplicates)
check if you have any (x,y,z) contained in more than 1 of the sets

File: file.png (49 KB, 925x284)

49 KB PNG

the filter has arrived

File: carbon(8).png (394 KB, 1498x2806)

394 KB PNG

Year 3 of using Haskell and NOT learning how to use the state monad.
First year I take the time to write a (bad) union find though.

File: 1741225561017507.webm (1.05 MB, 1000x1000)

1.05 MB WEBM

Visual for the example input(x, y axis).

>>107478232
grim
perhaps the first 6 days are equivalent to days 1-6
perhaps the last 6 days are equivalent to days 20-25

>>107478232
>sorting distances was the filter
>also easy to broot
the absolute state

>>107477933
>>107477873
Isn't union find... to find a union? The whole thing is a union. All edges are connected to all edges no?

>>107478257
exactly

>>107478251
nah this is almost certainly just the usual first 12 puzzles rather than rebalanced to account for not having all 25
theres usually a few semi-filters
1 around 7-9, one around 12-14 then a few more from 17 onwards

>>107478232
>>107478251
1-6 were all very easy, day 7 was slightly more difficult and day 8 a little bit more so. I'm hoping they start sharply increasing in difficulty now, instead of the year ending right when they get hard.

>>107478185
Oh yeah that does make sense.

>>107478257
I'd just like to interject for a moment. What you're referring to as union find, is in fact, union/find or as I've recently taken to calling it, union plus find
union plus find not only allows you to efficiently find which set an element belongs to, but also to efficiently join two sets

>>107476777
the yearly union find, tomorrow is dijkstra for sure

>>107478232
I got filtered by reading comprehension

File: wtf8.png (234 KB, 994x1372)

234 KB PNG

>>107478255
those distances look sorted to me

File: 08.cc.png (664 KB, 1454x4644)

664 KB PNG

Unwashed C++ ass. I knew it was a union-find problem instantly but I had to go back and refresh my memory on the implementation. Need more practice for better recall of that type of stuff.

I'm gonna have to use so many subroutines for this.

Was this the first time an AoC problem required using floating point numbers?

>>107478390
dumb retard, just don't do the square root

File: 1749654759568536.jpg (25 KB, 290x227)

25 KB JPG

>>107478390

>>107478390
no, but it was the first time it required multiple cores

>>107477628
>>107478100
>>107477603
>>107477699
these python codes do the exact same thing in slightly different ways. the only real difference is the white one burns my eyes. now this is why I aoc! I can definitely improve mine now.

>>107478232
Not everybody lives in New York. Us Euros got up, went to work/university and will solve the puzzle in about 6 - 8 hours from now.

>>107478427
you are irrelevant

>>107478427
just get up sooner

>>107478232
>declaring filter status 4 hours after the puzzle drops
You've have to give it 24 hours to really tell if it was a filter or not.

>>107478395
Can I manhat distance instead?
I don't think any of the distances are close enough that single precision is a problem, but it would suck to do everything and then find out it is.

>>107478459
>Can I manhat distance instead?
no

>>107478459
my n word, just don't take square root of the distances

>>107478463
I suppose you can just not sqrt it can't you? Because all that does is make them all relatively smaller, doesn't change their order at all.

>>107478472
now you got it

>>107478029
Can't you use the MST for 1 as well
Sort points by shortest adjacent edge length in the MST and then for each point take all neighbors closer than the next shortest edge in MST until 1000 edges reached

>>107478480
Ok, so I'm looking at about 10MB of RAM requirement.
I can do this. Just pray for me, because I have a lot of subroutines to write now.

>>107478494
yes

>>107478227
it's Eric's dogshit specification that has an example with
>seven circuits which each contain a single junction box.
without ever explaining how that result is even possible. The only rule he offers for why two boxes wouldn't be connected is: they're already in separate circuits, which obviously excludes monocircuits.
I noticed this gap immediately, and asked that to myself several times while reading it, and while implementing something that neatly exactly matched the parts of the example that he actually walked through, and I never got an answer.

Why can't a jumpbox at 0 be connected to a jumpbox at max_int? Those have the "smallest distance" after you follow his process.
Well, I get it now that this is wrong, but it's 3am.

>>107478519
>After making the ten shortest connections

>>107478532
yes, he stops at ten in order to tell how you how the process goes up to that point.
that doesn't suggest at all that 10 is the limit.

>>107478543
10/1000 is the limit for part 1

>>107478494
MST is not the right term because you can't use Prim's algorithm here. We want to process the edges in order.

File: Day-8.png (3.13 MB, 3624x9972)

3.13 MB PNG

washed zig. idiomatic? idts

usual ideas:
sort all edges
dsu with path compression
dsu with a single backing array for both parent and size
does not sort the entire component sizes list just to find the max 3
too lazy to quit early when the entire graph becomes connected

idc about washing it up further because it's just standard stuff. unless I come across a cooler idea

File: 25_D08_C#.png (122 KB, 828x1020)

122 KB PNG

That ended up not being the filter I thought it was

If you took the square root in your distance function, you are filtered.

>>107478555
Kruskal and Prim both find the MST, this is Kruskal (add edges by increasing size vs add edges to single component)

If you didn't use Manhattan distance, you're filtered.

>>107478472
The coordinates are small enough that euclid^2 fits into a single u64. It's an unwritten law of puzzles that u32 may overflow but u64 is safe.

>>107478250
I love when Eric throws in easter eggs for us to find

>>107478611
why

Funny, I kinda had a similar problem in a game, where I had to implement an octree. But with a proper data structure (a tree obviously lol) and abstraction.

>>107478029
>It's not, it's of the order of the inverse Ackermann function

Otherwise as O(1) shut the fuck up

>>107478665
what game?

>tfw you implement N*inverseAckermann(N) DSU but still have to calculate distances in N^2

import math

inp = open(0).read().split()
n = len(inp)
box = [[*map(int, coords.split(","))] for coords in inp]
dis = sorted(
    (math.dist(box[i], box[j]), i, j) for i in range(n) for j in range(i + 1, n)
)


def find_set(v: int) -> int:
    if v == p[v]:
        return v
    p[v] = find_set(p[v])
    return p[v]


def union_sets(a: int, b: int) -> int:
    a, b = map(find_set, (a, b))
    if a != b:
        if s[a] < s[b]:
            a, b = b, a
        p[b] = a
        s[a] += s[b]
    return s[a]


p = [i for i in range(n)]
s = [1] * n

p1 = p2 = 0

for k, (d, i, j) in enumerate(dis):
    if k == 1000:
        p1 = math.prod(sorted(s)[::-1][:3])
    if union_sets(i, j) == n and not p2:
        p2 = box[i][0] * box[j][0]

print(f"silver: {p1}, gold: {p2}")

>>107478698
and sort them O(n^2 log(n^2))
but it would be a lot worse without a dsu

>>107478628
yeah, but this is not a MST problem. there is nothing to be done with the min spanning tree here

>>107478723
cute

>>107478746
part 2 is just find longest edge in mst

>>107478610
>main drive is D:// and not C://
ngmi

>>107478775
That is not uniquely defined. You could have four nodes such that edges ab and cd to ac and bd keeps the same sum of weights.
It is specifically the longest edge in Kruskal's algorithm.
Nothing to do with the MST itself.

>>107478746
>use Prim to find MST
>extract edges
>use Kruskal on those edges
>avoid huge sort

>>107478785
The :C drive is sad and the :D is happy

Hope this answers your question

>>107478799
the D: drive is sad, anon

>>107478775
hmm, makes sense

>>107478796
prim's on dense graph is still O(n^2), and if you use a heap then it will end up being same as sorting with worse constant factor. ig that saves up the log factor

>>107478795
I think the inputs are such that there is a unique max edge. think of 3 pts forming an equilateral triangle. that won't be a valid input

>>107478395
Does it fit into 64bit if you don't sqrt?

>>107478825
1000 nodes on complete graph -> approx 1000000 edges.
If you find all MSTs with Prim you can put an upper limit on edge size.
You're discarding over 99% of edges for the slowest step (edge sort).

>>107478855
yes. max coord is 1e5. so max squared dist can be 3 * 1e5^2 = 3e10. u64 fits upto 19 digits

File: aoc08.png (334 KB, 1280x3298)

334 KB PNG

>The next two junction boxes are 431,825,988 and 425,690,689.
>Because these two junction boxes were already in the same circuit, nothing happens!

holy smokes I am mad
I interpreted this as move on to the next connection and dont count it
but this counts as a connection

but we were supposed to be sparing on wire??
I lost several hours to this

Day   -Part 1-   -Part 2-
  8   04:43:07   04:54:19

yes I upset

>>107477168
he needs to fucking stop with this
or include the parameter as the first line in the input file

Injested the positions into memory.
Calculated the distances.
Now to write a sorting routine in assembly to sort this list.
I don't think I have done quicksort in asm before...

>>107478746
>and sort them O(n^2 log(n^2))
you can use a heap to get O(N^2 + E*log(N)) where E is the number of edges you have to inspect until the tree is finished, which I strongly suspect is O(N) or O(N log(N)) on non-degenerate graphs

>>107477850
0 or negative numbers

File: Day08_CShart.png (162 KB, 1117x1458)

162 KB PNG

C#

Task 1: 140008
Task 2: 9253260633
Day 08 finished in 00:00:00.5415460

I don't know what DSU is but I made a dogshit solution that solves the problem anyways with vectors and sets and takes nearly a full second to run. Another algorithm I'll have to learn from this, thanks Eric for torturing fags without compsci degrees

File: carbon8.png (885 KB, 1346x4974)

885 KB PNG

> solution that terminates in a reasonable time does not require an octree
it's over

Ah fuck it I'll just bubble sort.

File: day8_unwashed.png (152 KB, 776x1270)

152 KB PNG

unwashed solution that is surprisingly effective.

File: AoC-08.png (149 KB, 858x1324)

149 KB PNG

Lazy unwashed solve.

File: 1756734447519718.gif (344 KB, 500x491)

344 KB GIF

>>107477687
It took me almost two full hours, but it,s done

Started late. Unwashed aside from removing debug prints, and combining part 1 into part 2 since part 2 was a trivial change

from itertools import combinations
data = open("Day 08 input.txt", "r").read().strip().split("\n")

circuits = []
boxes = []
for i in data:
    pos = tuple(map(int, i.split(",")))
    boxes.append(pos)
    circuits.append(set())
    circuits[-1].add(pos)

pairs = list(combinations(boxes, 2))
pairs.sort(reverse=True, key=lambda x: (x[0][0]-x[1][0])**2 + (x[0][1]-x[1][1])**2 + (x[0][2]-x[1][2])**2)

connections = 0
while len(circuits) > 1:
    pair = pairs.pop()
    fail = False
    for idx, c in enumerate(circuits):
        if pair[0] in c and pair[1] in c:
            fail = True
            break
        if pair[0] in c:
            idx1 = idx
        if pair[1] in c:
            idx2 = idx
    connections += 1
    if connections == 1000:
        ordered = sorted(circuits, reverse=True, key=lambda x:len(x))
        print "Part 1", len(ordered[0])*len(ordered[1])*len(ordered[2])
    if fail:
        continue
    if idx1 > idx2: idx1, idx2 = idx2, idx1
    circuits[idx1] |= circuits.pop(idx2)

print "Part 2", pair[0][0] * pair[1][0]

Inefficient use of data structures but the input was small enough for it to not matter.
First day that wasn't completely trivial, but not too bad.

How is everyone balancing this with work. Like if you spend 1-2 hours on it, that's cognitive space taken away from the code you have to write for work today. maybe im the only one who has to think really hard for my job and its rare to not just do crud? idk

>>107479168
Work?

>>107479168
>1-2 hours
m8

>>107479168
>1-2 hours
>maybe im the only one who has to think really hard for my job
hmm

>Because these two junction boxes were already in the same circuit, nothing happens!
except you still count it as a new connection for some reason
FFS ERIC

>>107479127
anon, bubble sort is O(N^4) and N=500000
at least use selection sort with a fixed prefix up to which you'll sort, like >>107477859, that way you only need 4 billion comparisons

>>107479201
>O(N^4) and N=500000
I mean O(N^4) = N=1000 or O(N^2) and N=500000, don't laugh at me

>>107479188
>>107479173
I'm talking about people like

>>107477337

who posted their time as 2 hours, not myself