Sign up at app.codecrafters.io/join?via=hyper-neutrino and try out Codecrafters today! You can get a taste of their many learning streams and try out their beta courses all completely for free (no credit card needed), and when you go to sign up, you'll get 40% off at checkout and support the channel! Thank you for watching :) (Codecrafters has not sponsored this video directly and they did not have the opportunity to review any of this video, including the promotional segment.)
Difficulty is all over the place this year. I was recommending 2022 for people who wanted to learn a new language because of the gradual difficulty increase
That's a good idea. Also removes the pressure of the leaderboard but I definitely agree that the difficulty levels made a lot more sense than this year...
Wow I really feel ashamed not to Even be able to complete part 1 when I see such clever solutions and so many people doing them. Thanks for the explanation
This was very helpful. I've almost given up when I saw this one and I just left the part 2 for later. I've solved it today thanks to your explanation. I'm new to the channel but I'll deffinitely stay longer because your videos are very clear
My naive solution was not going to finish anytime soon. I watched your video and then started implementing the solution based on a vague understanding of ranges/intervals and their mapping. I was able to get the sample solution right though. Still there were issues with my final implementation. I rewatched the explanation for part two of this video a couple of times, still nothing. Then I saw your "short" on intervals. That gave me some idea about the calculation of offset intervals and I was able to get the offsets and limits right. I had to draw the complete mapping of intervals on paper for the sample input while debugging my code. While rewatching the video again I noticed I wasn't using the queues, as once the seed interval is split into two, the non overlapping interval needs to be mapped again. And finally I was able to get the correct answer. Thank you for the clear explanations, nice visuals and printing out the intermediate variable values as you implemented+explained your code in the video.
i did everything exactly the same but then got stuck on calcualting those intersections. The idea to add back into seeds the outer parts of the interval intersection is very elegant
I don't usually comment on videos, but your explanation was extremely helpful after this problem fried my brain xD. Massive props, keep doing what you're doing!
I appreciate the drawings of the intersections they really helped visualise the problem, I did it using the start and length rather than start and end and also used recursion when the range got split into 2 and it took maybe 2-3 hours to solve but seeing your solution just makes it look so easy and elegant lol
Wow man, I managed to pull something that works today but had real performance issues (my script ran for 10000sec on part 2), you provides really good insights on Python in your explanation and I see I have much space for improvment. Keep up the good work and thx very much !
Great video! Excellent solution which is both simple to understand and also sophisticated. I had already spent around 6 hours trying to work through part 2 and kept getting close but not quite there yet. Your drawings really helped visualize the problem as well. Subbed and looking forward to the rest of your 2023 videos!
Learned a few new tricks so thank you very much! My initial run at part 2 took about 2 min to complete which I thought was ok .... until I found your video and learned just how fast you can make it!
Glad to hear! Yeah, with interval manipulation it runs literally instantly because the input size is actually very small if you aren't constructing the ranges themselves; the numbers are big but the size is not. Thanks for watching!
Finally, I have finished the part 2. It took me 1 hour to do the part 1 and 8 hour to make the part 2 working even though it still takes 2 minutes for my program to solve the part 2 thanks to Rust's Release Mode (since my objective doing AOC is to learn rust). If I'm using Python, JS, or other interpreted language maybe it will be very slow.
Great video, helped me understand how to approach the second part. One thing that could be helpful to understand what exactly are you doing and what do variables mean - could you try to use more descriptive names for variables instead of a, b, c? Like source, destination, length or something. Other than that, thank you very much!
This is an obviously very clear explanation that I don't really understand, at least part 2. How is it that range overlaps help us get to the final answer? I'm so confused. 🙂 I think I just don't grasp the basic idea of the part 2 solution at all.
OK, so I think I'm starting to understand this. Let me see if I can articulate what you've done. (Sorry, I'm not a programmer, so I'm new to concepts like this.) Just thinking about the first step here for simplicity: For each seed range, you are looking for segments of that seed range that are within the corresponding ranges of the next step (soil in this case). Then, you are applying the transformation (source - destination) to that seed segment into the next (soil) segment? And then the unmapped segments go into the next step unchanged? I think I'm still kind of confusing myself.
The part of the code that took me the longest to understand was the if os > s: and if e > oe: Sorry, I know I'm probably spamming UA-cam comments, but maybe this might help someone else? The code block is popping off the seed at the start of the loop, then it takes out any overlaps, shifts them, and then adds them to the output. Then the if statements at the end "clean up" the rest of the seed range and add them back into the input for evaluation in the next loop (since they might get picked up by another range in the current set of ranges.) This video has been invaluable to me. That said, the second case you drew with the overlap of the input range confused me because you have to do this "cleanup" operation whether the overlap is on the left, right, or entirely inside the input range. Maybe this was just obvious to everyone else though.
Yeah, I was caught off guard with the difficulty spike too. If it were a weekend, it would be a bit less surprising, but this seemed unusually difficult for a weekday day 5
Wasted too much time on bruteforce solutions for part 2, ended up solving it using reverse lookup starting from location '0' with jump search of decreasing steps, which can still give wrong minimum with large steps... Wonder how many solved or even thought of solving it this way 😄 You found a way better solution and made a perfect video explanation for it! Amazing work!👍
Also interestingly enough, in my input the maximum location value is a perfect square (√4294967296 = 65536) which makes it very convenient to find optimal step for jump search = √n, can jump search actually be intended? 🤔
That's an interesting approach; I thought of that afterwards but it doesn't sound like it would be the most straightforward way to do it, but it might be faster, and it's definitely a good strategy to keep in mind in general (working backwards is a good trick to keep in mind)
@@TheIronmanJourney all i can say is my jump search with steps from 100k to 1 with progression of 1/10 (devide by 10) finds it in 0.714 msec with 1028 lookups 😃 What went wrong with yours? 20s is a lot!
In part two wouldn't the overlapping ranges be solved if when you appended the seed range on the end of seeds you added or subtracted 1? (ie: (s, os -1) and (oe + 1, e))
Nice walkthrough and explanation 😊 Could you shed some light at other problems that are like this that you've encountered? What's the real world application in other words 😊
Would it be quicker or slower to take the input, start at the end, find the lowest “destination” and see the range that the source needs to be in, then walk backwards up the input redoing that process to basically have it output the optimal “range” the starting seeds need to be in? Then you’d just check the starting seeds + offset and see which seeds fulfill the criteria then take their minimum?
This is what my thought process was when solving, although I kept getting myself messed up trying to walk through the input backwards so I ended up brute forcing it just so I can move on hahaha. But I really want to know if doing it that way would also be “fast”.
I think it would be a lot more complicated, since the potential range of locations is infinite so you don't really have a starting point because not all locations can necessarily be reached and the way the seeds map to the locations may not be able to be determined just from the last map input.
@@hyper-neutrino Edit: oh I see what you mean the starting seeds might not necessarily map to the lowest possible destination. Disregard I see what you're saying, but I think it's still feasible, even though yes it probably is way more complicated. If you start from the final set of maps, sort them by the "destination" value so then you can find which range of inputs maps to the lowest destination value on the last step. Now that you have the input range you need, you go back a level then find the maps that contain your range, if none of them fit your range then you just keep bubbling up the previous range that was required. So the first iteration you just want to sort by the minimum output value and get the range you need to do that. All the rest of the steps are just trying to match your range to one of their maps. If it matches you update your range that bubbles up to the next level, if it doesn't match you bubble up the same range you already have. Once you get to the top then you can find which seed + offset pairs fit within that range and take the minimum. Like it seems very possible to do to me unless I'm completely overlooking a condition hahaha
How do you get to a level where you are able to comprehend your code this well? Is it just practice? Its honestly incredible how you can look at all the variables in the range and understand exactly what they are and where they go.
It's just practice; I've been coding for over a decade now so I've gotten a pretty intuitive understanding of code as I literally don't remember much of my life before I started. Let me know if anything's confusing or if my pace is too fast to easily understand!
Haha, yeah there's a reason I use Python. Lower level languages are just too much of a pain to work with with parsing and typing and similar things; it's nice to just be able to throw together some higher level ideas and worry less about implementation specifics. Also better for teaching because even people with less experience can more or less read what's going on
Maybe I'm missing something, but for part 2 what happens if a seed range overlaps with two different ranges? I would think this code wouldn't work since the break would cause the second range to not get checked. I'm imagining the scenario you show in the drawing at 12:07
If it overlaps two different ranges, it will match one, the remainder will get chopped off and reinserted, and then later on that remainder will get checked again, and it will match the other map range.
I did an inverse search from location to check if seed present, reducing the range by checking overlap is an optimization but it would still be costly to know what the eventual location is for ALL of them. Since you're using Python, how much time did it take you to get a return without multi-threading?
My solution for part 2 runs instantly. Because the mapping is just a linear transformation on the ranges, you can store all of the seeds as ranges and then just manipulate them as such. There may be a more efficient way but the runtime of my solution is totally negligible.
For part 1 is there a guarantee that the source ranges don't overlap? I was under the impression you would have to take the min of all source values rather than just taking the first match and breaking? (Guess in hindsight it's easy to verify)
I don't think the problem states that it's guaranteed, but it also doesn't define how to handle that. I think it's safe to assume that there will be no overlap in the source ranges.
Overlapping ranges didn't make sense in my mind given the explanation. I think technically the explanation does disallow overlapping ranges as it mentions that it a map converts "a seed number" into "a soil number" so it wouldn't make sense for a seed number to be mapped to multiple soil numbers
@@hyper-neutrino I found a line of code that wasn't indented to the same level as yours. That made it return a number below 27000. I fixed that and the program returned the correct answer.
![Northeastern CY 5770 Fall 2024 [Week 12 Lecture 1 Heap Exploitation]](/img/n.gif)
Sign up at app.codecrafters.io/join?via=hyper-neutrino and try out Codecrafters today! You can get a taste of their many learning streams and try out their beta courses all completely for free (no credit card needed), and when you go to sign up, you'll get 40% off at checkout and support the channel! Thank you for watching :)
(Codecrafters has not sponsored this video directly and they did not have the opportunity to review any of this video, including the promotional segment.)
What makes the explanation so good is that you print the result of most code changes. Thanks!
Glad you find that helpful! I'll be sure to keep doing that to make my solutions easier to understand. Thanks for the feedback!
Difficulty is all over the place this year. I was recommending 2022 for people who wanted to learn a new language because of the gradual difficulty increase
That's a good idea. Also removes the pressure of the leaderboard but I definitely agree that the difficulty levels made a lot more sense than this year...
Thanks, I solved it but I had an 08:22:46.998 run I went through all the seeds as in part 1. This was enlightning.
I appreciate that your are posting of your solutions here. I'm learning quite a few new Python tricks.
Wow I really feel ashamed not to Even be able to complete part 1 when I see such clever solutions and so many people doing them. Thanks for the explanation
We all start somewhere; nothing to be ashamed of! Thanks for watching :)
THANK YOU!
This was very helpful. I've almost given up when I saw this one and I just left the part 2 for later. I've solved it today thanks to your explanation.
I'm new to the channel but I'll deffinitely stay longer because your videos are very clear
Thanks for sharing!
Now, I understand why my approach didn't work ... I only considered the overlap and discarded the remaining! 😅
My naive solution was not going to finish anytime soon. I watched your video and then started implementing the solution based on a vague understanding of ranges/intervals and their mapping. I was able to get the sample solution right though. Still there were issues with my final implementation. I rewatched the explanation for part two of this video a couple of times, still nothing. Then I saw your "short" on intervals. That gave me some idea about the calculation of offset intervals and I was able to get the offsets and limits right. I had to draw the complete mapping of intervals on paper for the sample input while debugging my code. While rewatching the video again I noticed I wasn't using the queues, as once the seed interval is split into two, the non overlapping interval needs to be mapped again. And finally I was able to get the correct answer.
Thank you for the clear explanations, nice visuals and printing out the intermediate variable values as you implemented+explained your code in the video.
i did everything exactly the same but then got stuck on calcualting those intersections. The idea to add back into seeds the outer parts of the interval intersection is very elegant
I don't usually comment on videos, but your explanation was extremely helpful after this problem fried my brain xD. Massive props, keep doing what you're doing!
I like your big-brain-words big-brain-man. Converting this to C++ will be fun...
I appreciate the drawings of the intersections they really helped visualise the problem, I did it using the start and length rather than start and end and also used recursion when the range got split into 2 and it took maybe 2-3 hours to solve but seeing your solution just makes it look so easy and elegant lol
Good to hear! Recursion is a good approach as well; I hadn't actually thought of that. Thanks for the feedback!
Wow man, I managed to pull something that works today but had real performance issues (my script ran for 10000sec on part 2), you provides really good insights on Python in your explanation and I see I have much space for improvment. Keep up the good work and thx very much !
good vid, thanks.
Great video! Excellent solution which is both simple to understand and also sophisticated. I had already spent around 6 hours trying to work through part 2 and kept getting close but not quite there yet. Your drawings really helped visualize the problem as well. Subbed and looking forward to the rest of your 2023 videos!
Learned a few new tricks so thank you very much! My initial run at part 2 took about 2 min to complete which I thought was ok .... until I found your video and learned just how fast you can make it!
Glad to hear! Yeah, with interval manipulation it runs literally instantly because the input size is actually very small if you aren't constructing the ranges themselves; the numbers are big but the size is not. Thanks for watching!
Thank you. I would really love it if you can create another explainer for part 2. Preferbely by running some example numbers in excalidraw.
Finally, I have finished the part 2. It took me 1 hour to do the part 1 and 8 hour to make the part 2 working even though it still takes 2 minutes for my program to solve the part 2 thanks to Rust's Release Mode (since my objective doing AOC is to learn rust). If I'm using Python, JS, or other interpreted language maybe it will be very slow.
8 Hours? it took me far more than that lol
Thanks a lot man! The explanation was so clear
This was an excellent description. Very much appreciated!
Beautiful
Great video, helped me understand how to approach the second part. One thing that could be helpful to understand what exactly are you doing and what do variables mean - could you try to use more descriptive names for variables instead of a, b, c? Like source, destination, length or something. Other than that, thank you very much!
Sure, that's a good suggestion! I can also maybe leave some comments to help with keeping track of everything in longer solutions.
I agree... following a, b, c etc becomes pretty difficult
agree with this, more descriptive variable names would be very helpful.
I just checked every seed in the ranges. Writing it in Rust, it took about 2 mins to find the solution.
So helpful. Thank you!
I don't understand the b
This is an obviously very clear explanation that I don't really understand, at least part 2. How is it that range overlaps help us get to the final answer? I'm so confused. 🙂 I think I just don't grasp the basic idea of the part 2 solution at all.
OK, so I think I'm starting to understand this. Let me see if I can articulate what you've done. (Sorry, I'm not a programmer, so I'm new to concepts like this.)
Just thinking about the first step here for simplicity: For each seed range, you are looking for segments of that seed range that are within the corresponding ranges of the next step (soil in this case). Then, you are applying the transformation (source - destination) to that seed segment into the next (soil) segment? And then the unmapped segments go into the next step unchanged? I think I'm still kind of confusing myself.
The part of the code that took me the longest to understand was the if os > s: and if e > oe:
Sorry, I know I'm probably spamming UA-cam comments, but maybe this might help someone else?
The code block is popping off the seed at the start of the loop, then it takes out any overlaps, shifts them, and then adds them to the output. Then the if statements at the end "clean up" the rest of the seed range and add them back into the input for evaluation in the next loop (since they might get picked up by another range in the current set of ranges.)
This video has been invaluable to me. That said, the second case you drew with the overlap of the input range confused me because you have to do this "cleanup" operation whether the overlap is on the left, right, or entirely inside the input range. Maybe this was just obvious to everyone else though.
this was so hard for being day 5, did part 1 just fine but couldn't even think about doing part 2
Yeah, I was caught off guard with the difficulty spike too. If it were a weekend, it would be a bit less surprising, but this seemed unusually difficult for a weekday day 5
Wasted too much time on bruteforce solutions for part 2, ended up solving it using reverse lookup starting from location '0' with jump search of decreasing steps, which can still give wrong minimum with large steps... Wonder how many solved or even thought of solving it this way 😄
You found a way better solution and made a perfect video explanation for it! Amazing work!👍
Also interestingly enough, in my input the maximum location value is a perfect square (√4294967296 = 65536) which makes it very convenient to find optimal step for jump search = √n, can jump search actually be intended? 🤔
That's an interesting approach; I thought of that afterwards but it doesn't sound like it would be the most straightforward way to do it, but it might be faster, and it's definitely a good strategy to keep in mind in general (working backwards is a good trick to keep in mind)
I come up with the exact same solution. 😅 runs for about 20 sec on my side … depends abit on how „big“ the answer is
@@TheIronmanJourney all i can say is my jump search with steps from 100k to 1 with progression of 1/10 (devide by 10) finds it in 0.714 msec with 1028 lookups 😃
What went wrong with yours? 20s is a lot!
In part two wouldn't the overlapping ranges be solved if when you appended the seed range on the end of seeds you added or subtracted 1? (ie: (s, os -1) and (oe + 1, e))
Never seen bluetooth parierd if-else in my life before (15:18) I will never write a flag again
Nice walkthrough and explanation 😊 Could you shed some light at other problems that are like this that you've encountered? What's the real world application in other words 😊
I honestly can't really think of any situations in which I've needed interval manipulation outside of programming challenges, lol
@@hyper-neutrino thanks! :D
By the time you do min(seeds) at the end to find the result, how many entries would you expect in the seeds array?
Well done. I failed part 2 because I thought ranges could overlap
I left my solution for part 2 running all night and it wasn't even close to finish when I woke up 😅
Would it be quicker or slower to take the input, start at the end, find the lowest “destination” and see the range that the source needs to be in, then walk backwards up the input redoing that process to basically have it output the optimal “range” the starting seeds need to be in? Then you’d just check the starting seeds + offset and see which seeds fulfill the criteria then take their minimum?
This is what my thought process was when solving, although I kept getting myself messed up trying to walk through the input backwards so I ended up brute forcing it just so I can move on hahaha. But I really want to know if doing it that way would also be “fast”.
I think it would be a lot more complicated, since the potential range of locations is infinite so you don't really have a starting point because not all locations can necessarily be reached and the way the seeds map to the locations may not be able to be determined just from the last map input.
@@hyper-neutrino
Edit: oh I see what you mean the starting seeds might not necessarily map to the lowest possible destination.
Disregard
I see what you're saying, but I think it's still feasible, even though yes it probably is way more complicated. If you start from the final set of maps, sort them by the "destination" value so then you can find which range of inputs maps to the lowest destination value on the last step.
Now that you have the input range you need, you go back a level then find the maps that contain your range, if none of them fit your range then you just keep bubbling up the previous range that was required.
So the first iteration you just want to sort by the minimum output value and get the range you need to do that. All the rest of the steps are just trying to match your range to one of their maps. If it matches you update your range that bubbles up to the next level, if it doesn't match you bubble up the same range you already have. Once you get to the top then you can find which seed + offset pairs fit within that range and take the minimum.
Like it seems very possible to do to me unless I'm completely overlooking a condition hahaha
Since the range in [s,e) e non inclusive, shouldn't you take min(e-1, b+c-1)?
How do you get to a level where you are able to comprehend your code this well? Is it just practice? Its honestly incredible how you can look at all the variables in the range and understand exactly what they are and where they go.
It's just practice; I've been coding for over a decade now so I've gotten a pretty intuitive understanding of code as I literally don't remember much of my life before I started. Let me know if anything's confusing or if my pace is too fast to easily understand!
No its perfect, your a gret teacher and your skills are very impressive@@hyper-neutrino
Your entire solution for this problem has less lines of code than my input parsing section in Java, lol
Haha, yeah there's a reason I use Python. Lower level languages are just too much of a pain to work with with parsing and typing and similar things; it's nice to just be able to throw together some higher level ideas and worry less about implementation specifics. Also better for teaching because even people with less experience can more or less read what's going on
Can you please make a youtube short about how to merge those intervals?
Sure! ua-cam.com/users/shortsIaPaQ5heqZs Hope this helps :)
@@hyper-neutrino thank you so much.
Maybe I'm missing something, but for part 2 what happens if a seed range overlaps with two different ranges? I would think this code wouldn't work since the break would cause the second range to not get checked. I'm imagining the scenario you show in the drawing at 12:07
If it overlaps two different ranges, it will match one, the remainder will get chopped off and reinserted, and then later on that remainder will get checked again, and it will match the other map range.
I did an inverse search from location to check if seed present, reducing the range by checking overlap is an optimization but it would still be costly to know what the eventual location is for ALL of them.
Since you're using Python, how much time did it take you to get a return without multi-threading?
My solution for part 2 runs instantly. Because the mapping is just a linear transformation on the ranges, you can store all of the seeds as ranges and then just manipulate them as such. There may be a more efficient way but the runtime of my solution is totally negligible.
@@hyper-neutrino I might have missed part of the video, if you’re mapping ranges from one source to the next it’s quite linear yeah.
For part 1 is there a guarantee that the source ranges don't overlap? I was under the impression you would have to take the min of all source values rather than just taking the first match and breaking? (Guess in hindsight it's easy to verify)
I don't think the problem states that it's guaranteed, but it also doesn't define how to handle that. I think it's safe to assume that there will be no overlap in the source ranges.
Overlapping ranges didn't make sense in my mind given the explanation.
I think technically the explanation does disallow overlapping ranges as it mentions that it a map converts "a seed number" into "a soil number" so it wouldn't make sense for a seed number to be mapped to multiple soil numbers
2:42 Isn't python already taking care of that?
I don't think so; I ran into this issue last year and that's why I only got #300 on P1. Maybe I'm using the wrong built-in though?
Yo, what font do you use?
This is Monaspace Radon from GitHub Next
Gracias @@hyper-neutrino
Your code on this video gives me a number too low according to AoC. Guess I'll just have to live with a silver star on day 5.
send me your input and I can take a look
@@hyper-neutrino I found a line of code that wasn't indented to the same level as yours. That made it return a number below 27000. I fixed that and the program returned the correct answer.
pls dont use new as a var name, gives me anxiety ahahah, good video
os.linesep instead of
or
Interesting!