Hey Neil, great to see your videos again this year (and nice to have them same day). For part 2, perhaps you just check what happens when you place objects in the “seen” spaces rather than the whole grid? 😀
A colleague of mine recommended me checking out your AoC videos and I must say this was really nice to watch. Thanks for uploading that. Will from now on also check out your other videos.
The algorithm I wrote for part 2 only took 20 minutes to compute 😆 Part of the reason why was that as you might have imagined I'm replacing every single dot with an obstacle and checking if that causes a loop, but what may be even worse is that I'm not storing the position of the guard at all - at every iteration I have to find where the guard is and then update the map accordingly. So the two obvious optimizations are: "just store the coordinates of the guard's current position you dingus", and instead of testing every single possible obstacle position, run the part 1 algorithm once while storing the position of where the guard is looking at after every step or turn, and then only replace those with obstacles.
Hey, I mean if it works it works! One of the things I love about Advent of Code is that you can get away with lots of different levels of optimization, so if it's net faster to write some slower code by skipping some optimization, then you can do it. And IMO this is a very real-world tradeoff, because developer/researcher time is expensive! Obviously there's a limit to this and in the real-world you need to think about the actual costs of your slow code, but still this isn't something you get in more traditional competitive programming contests. Although, 20 minutes is a pretty long time, so writing the first optimization at least does sound pretty helpful :P
For part 2, since it's essentially a functional graph, addition of an obstacle updates upto 4 of the outgoing edges, and you can quickly compute the jumps to just before an updated node, similar to CSES Planet Queries. Overall O(N*M)
Well, technically just ruined it for people competing for leaderboard, but yeah it is kinda sad. Obviously you're always going to get some people who don't care about respecting Eric's wishes and not leaderboarding with LLMs, but it's surprising to me how many of these people there are this year, and that they include relatively well-known people like geohot.
I don't, but that's a neat idea! I think changing languages on the fly might be a bit too slow competitively for me, and PyPy already exists, but there definitely are good reasons to use other languages for these problems.
Nice videos, impressive to see your speed. Were you just luck that in your input the direction is downwards as you chose cd = 0 ? If your starting position would be not looking towards (-1,0) your solution would have been wrong? Did you check what was the starting direction in the input visually?
If you really want it, I do usually post my code on the subreddit megathreads (here's a day 6 link: www.reddit.com/r/adventofcode/comments/1h7tovg/comment/m0nyj8k/?), although - the code I post is pretty messy and isn't always fully general - it also needs my helper library in the same directory to run (gist.github.com/nthistle/5244b04be6a2eae545e6908369d39592) - you don't learn anything if you just use someone else's code! I'd really encourage you to try to solve yourself, even if it just means re-writing your own code after seeing the general approach somewhere else
Hey Neil, great to see your videos again this year (and nice to have them same day). For part 2, perhaps you just check what happens when you place objects in the “seen” spaces rather than the whole grid? 😀
Yep, it sounds like this is the big easy optimization - it brings my PyPy solution down to 5 seconds or so once I do this.
Awesome advice!
you discovering bugs has a very humoristic touch
Haha, glad you're enjoying it
A colleague of mine recommended me checking out your AoC videos and I must say this was really nice to watch. Thanks for uploading that. Will from now on also check out your other videos.
The algorithm I wrote for part 2 only took 20 minutes to compute 😆
Part of the reason why was that as you might have imagined I'm replacing every single dot with an obstacle and checking if that causes a loop, but what may be even worse is that I'm not storing the position of the guard at all - at every iteration I have to find where the guard is and then update the map accordingly.
So the two obvious optimizations are: "just store the coordinates of the guard's current position you dingus", and instead of testing every single possible obstacle position, run the part 1 algorithm once while storing the position of where the guard is looking at after every step or turn, and then only replace those with obstacles.
Hey, I mean if it works it works! One of the things I love about Advent of Code is that you can get away with lots of different levels of optimization, so if it's net faster to write some slower code by skipping some optimization, then you can do it. And IMO this is a very real-world tradeoff, because developer/researcher time is expensive! Obviously there's a limit to this and in the real-world you need to think about the actual costs of your slow code, but still this isn't something you get in more traditional competitive programming contests.
Although, 20 minutes is a pretty long time, so writing the first optimization at least does sound pretty helpful :P
For part 2, since it's essentially a functional graph, addition of an obstacle updates upto 4 of the outgoing edges, and you can quickly compute the jumps to just before an updated node, similar to CSES Planet Queries. Overall O(N*M)
I think you just need to check for points in the path in first part , so list(seen) and remove start, then its much faster
Nice, yeah, this is a pretty big improvement.
This year GPT users have ruined it for everybody.
Well, technically just ruined it for people competing for leaderboard, but yeah it is kinda sad. Obviously you're always going to get some people who don't care about respecting Eric's wishes and not leaderboarding with LLMs, but it's surprising to me how many of these people there are this year, and that they include relatively well-known people like geohot.
Hey neil !
Do you know Julia ? It could be useful in those pypy situations, where you'd want interpreted syntax but "compiled performance"
I don't, but that's a neat idea! I think changing languages on the fly might be a bit too slow competitively for me, and PyPy already exists, but there definitely are good reasons to use other languages for these problems.
Nice videos, impressive to see your speed. Were you just luck that in your input the direction is downwards as you chose cd = 0 ? If your starting position would be not looking towards (-1,0) your solution would have been wrong? Did you check what was the starting direction in the input visually?
Thanks! I did visually check what it was, that was why I initially wrote the check as "^>
How did I get a different answer for part 2? Do we get different inputs?
Yep, everyone gets their own unique input.
hy can you give code for part 2 am not able to complete
If you really want it, I do usually post my code on the subreddit megathreads (here's a day 6 link: www.reddit.com/r/adventofcode/comments/1h7tovg/comment/m0nyj8k/?), although
- the code I post is pretty messy and isn't always fully general
- it also needs my helper library in the same directory to run (gist.github.com/nthistle/5244b04be6a2eae545e6908369d39592)
- you don't learn anything if you just use someone else's code! I'd really encourage you to try to solve yourself, even if it just means re-writing your own code after seeing the general approach somewhere else