Day 6 part 2: my biggest mistake was that I placed obstacles on the path before where the guard was at that moment in my calculations and then just kept going from where I was. But I neeed to check if I had been there earlier because then it wouldn’t be a valid obstacle leading to a cycle because the guard would have taken a different path
2 Likes
Python! I think if I get into it a bit earlier next year I’d try to pick up javascript again or something I’m less familiar with.
3 Likes
Part 2
Mine appears to have interference from more than just the 3 top bits. It’s causing me quite a bit of confusion.
Additionally, I despise these stages where you have to do optimizations with information outside of what’s provided on the puzzle page
1 Like
Nevermind. Got it figured out. I had lingering debugging logic that was interfering with program execution.
Day 17 in the bag.
2 Likes
Advent of Code – Day 18 – Part 2
part 2
~/dev/adventofcode/2024/day18(main)$ time ./part2.py
[redacted]
real 2m1.673s
It could be better. Could be worse.
1 Like
This is where an actual compiled language shines: release-mode Rust, 3.1 seconds. I’m guessing you moved the pathfind inside the removal loop, as I did? If I’d had to, I’d have done a binary chop to pin down the relevant cycle.
1 Like
AoC Day 18 Part 2
Yeah. I wrote a bespoke Dijkstra-like for part 1, so for part 2, I just short-circuited the entire logic as soon as any path was found between start and end. And then I just naively iterated through the corruption until pathfinding failed. I was about to add a small optimization to start at the 1025-th corruption… But it finished before I could be bothered
1 Like
I cut the run-time in half by only checking for pathfinding after the 1025th corruption cycle
~/dev/adventofcode/2024/day18(main)$ time ./part2.py
[redacted]
real 0m56.885s
I may continue to poke at this… week before Christmas means it’s busy at work, but finding the right people to accomplish tasks makes everything move slow.
1 Like
Day 18.1 would have been helpful if I had finished reading the problem description before running off and simulating 12 bytes for production instead of 1024. Oh well…
Day 18.2 I am a lazy someone and just waited for my Dijkstra to check everything beyond 1024. I was starting to worry when it completed in just under 6 seconds. It gives a star so it is a solution. This must have been my fastest part 2 this year measured in developer time.
I am really enjoying that I build my own classes for a few repeat-problems:
fallingBytes.stream().limit(time).forEach(c -> memorySpace.setValue(c, CORRUPT));
Path bestPath = new Path(0,0);
while(bestPath!=null && time< fallingBytes.size()){
time++;
memorySpace.setValue(fallingBytes.get(time), CORRUPT);
bestPath = new Dijkstra<>(new Path(0, 0)).findBestPath(memorySpace);
}
Coordinates lastByte = fallingBytes.get(time);
return String.format("%d,%d",lastByte.x,lastByte.y);
2 Likes
Advent of Code 2023 Day 23
I’ve returned to last year’s challenges. These I’m doing for academic reasons, so I don’t feel as much pressure to get them done.
I did some visualization of part 2 to help me conceptualize and brainstorm my next approach:
2 Likes
I’m starting to think I should generalise my grid and pathfinding code, but having it all there in the main file makes tweaking it easier.
2 Likes
Thanks to AoC and a little copy/paste, I can throw together pathfinding code in about 5 minutes or less.
2 Likes
Day 19 part 1 … I felt a bit lazy 
instead … Sadly for part 2 I will to actually do more than a 1 liner I think.
1 Like
Rust memoize is asking for things I don’t understand. So I did it by hand with a HashMap. That doesn’t seem to be helping with part 2 though, which is chugging away on the same line the un-memoised part 1 did.
1 Like
Day19. I was actually planning on using some kind of memoization for part 2. I am still giggling when I look at my part 1 solution though.
Major spoiler for part 1: Pattern.compile(String.format("(%s)+",firstLine.replace(" ,","|"))) (look at your own risk, you won’t be able to unsee it but I also cannot figure out to reuse it for part 2)
2 Likes
Just ported my part 2 code to Perl, where that functionality is something I understand, and it works perfectly and finishes in a little over a second. Huh.
2 Likes
Finally! Kept removing bits that the crate was complaining about and ultimately I have something that works. Not sure I understand it any better…
2 Likes
General question to everyone here: what does “dynamic programming” mean to you? I think I may do some of it already, but I want to get a clearer picture of what it is.
1 Like
I’m not sure I know the working meaning of DP because the descriptions I’ve seen just look like software design. Breaking down problems into component problems, solving each sub-problem, and then glueing it all together- that’s just called software development in my book.
But the way people talk about it makes it sound like Zen; something ineffable
3 Likes
I’ve seen “Dynamic Programming” on reddit a number of times and it seems to be mentioned whenever someone uses an advanced not brute force solution. as @pillbox says it seems to involve using OO or other means to break problems into smaller pieces and not using one long spaghetti method with lots of for loops.
This not a word I’ve ever heard as a software dev at work or in comp science AFAIK.
PS: the chatbot says this
Dynamic programming (DP) is a method often used in computer science and mathematics to solve complex problems by breaking them into smaller, overlapping sub-problems and solving each of these sub-problems just once. Its key idea is to optimize recursion by avoiding redundant calculations, typically by storing the results of sub-problems and reusing them as needed.
PPS: this is how I approach all my code. in particular for AoC though because these problems are largely “understand the text” problems in part 1 and it helps modeling along the text.
2 Likes