Advent of Code 2024 Day 5

[@Algorithmist]

How did you do today?

[@ProgrammingWithManojSharma]

solved part 1 successfully but stuck at part 2 just figuring out it , can you help me

[@Algorithmist]

@@ProgrammingWithManojSharma try the discord!

[@ArunGordon]

Thanks for the sesh, can we get the code links too?

[@jinyang4796]

I got tricked into thinking it is a topological sort question, until I found out the is-before relationship is cyclic. Too much leetcode 😂

[@shahzodshafizod]

Spent more then an hour to figure out that graph can be cyclic. I wanted to get topological order of nodes, assign to each node an index and then sort(key=lambda num: order[num]). The example graph is acyclic, but mine was cyclic(

[@oldmajor5240]

you did phenomenally on this! I solved this using toposort. For part one I tried to create a dag with all the rules but it turned out to be cyclical 😂 Then I knew the inputs had to be special.

[@_aryan_570]

How did toposort work here, when it is cyclic? how did you solve Part1 with toposort with cyclic input?

[@oldmajor5240]

​@@_aryan_570 it works out if you only consider the dependencies that are relevant to a given line

[@_aryan_570]

@@oldmajor5240 oh okay!! I was trying to apply kahn's algo , and create indegree and topo vector before processing any lines. Didn't work that way!!

[@Algorithmist]

ya, seems like a lot people read it your way with the transitive property - I was lucky because my method was even dumber haha

[@cursed_nerd]

Brute force is go to in AOC

[@Algorithmist]

The way to go is to solve the input in front of you and not the one you think you're getting

[@cursed_nerd]

how can someone even chatgpt in 14 seconds, but then again how can even someone read and solve in 14 seconds.

[@Ismail_Dagli]

I noticed that you primarly use Python for competitive programming. Why not C++? Isn't it faster? 🤔

[@alexley964]

Faster to run, once running. Slower to write and compile.

[@Algorithmist]

depends on what you mean by faster - if it is by submission time, it's limited by (for me) your familiarity with the tool, if you mean running time, it doesn't often matter, at least for AoC.

[@alexley964]

​@@Algorithmist yeah that was my point as well partially. If you're more familiar with python (as Larry may be) you'll write it a lot faster than C++ (assuming you're less familiar with that) and then also in general python is less verbose and requires often less keystrokes so even if you're familiar with both python and C++ it may still be faster to write python. Then to your point about running time, yes for the simpler problems it's the difference in milliseconds which doesn't matter compared to the time required to write the solution - again that was my point - C++ may be faster to "run" but if you took 3x as long to write it it doesn't matter. But for a more complex problem, if you're trying to write a quick solution you'll quite often end up brute forcing it and then python does become quite slow - e.g. day 6 and day 7 this year my brute force naive python solution took 15+ seconds. At that point you should either just write a more intelligent/performant solution (but that sometimes takes longer to write) or you could argue that the compilation time and writing time for Rust/C++ would be worth it (e.g. 3 seconds slower to write and compile but then runs 10 seconds faster etc.). As always "it depends" it's always a trade off.