Thanks for the nice video 8-) I really liked the solution for part 2 (I ended up doing something similar, but slightly slower, due to using a set where you used a bitmask). You can optimise the search a bit more, if you compute the maximum theoretical flow before running the search, and pass the released amount at the time and the current flow through the recursion. If you then hit a state where remtime*maxflow +released < maxval, you know that you can cache your current state as that, and then return that for that branch
Please make a video on how to approach these questions and how you are coming up with logical solutions for these questions. What things we need to learn in order to solve them.. I'm very much a beginner and so It will be very helpful to me, Because I see a difference or let's say out of the box thinking and logical maths in your solutions. So kindly make a video on this 🙏 I hope this will also be much more useful for many Beginners like me :)
Thanks for the explanation! Very clever approach. I'm looking forward to your video on graphs. Didn't have time and mental capacity this week to participate, but videos like yours are always welcome to learn something.
Thank you for this video. Bitmask to use in cache for dfs were interesting concepts I haven't thought about. Hope you will be able to share videos for rest of the challenges. Keen on learning something!
Really useful video, much thanks for this. This algorithm worked for me in Javascript, for both parts, even without the bitmask - a 15 boolean key-value object, cloned for the DFS recursions and cycling through the necessary permutations in part 2, takes around just a minute.
This was a great video! I learnt a lot from this and I feel more confident that I can get a solution done myself :) thank you for taking time in the vid to explain the algorithm.
Thank you for posting this and explaining your approach. It gives me hope that I'll eventually understand all this stuff. I'm also looking forward to your video on graphs.
I'm sure you will get there sooner or later! Even if things don't fully make sense right now over time things will start to click together. I'm looking forward to making that video as well, glad you enjoyed!
Collapsing the graph into non-empty nodes was my plan B in case my brute force approach didn't work. Nice to see that it was a right idea, though the whole bit manipulation thing is all Greek to me. Luckily my brute force plan A worked well enough. Basically just considered naively all possible paths through all possible nodes, keeping track of global flow rate and pressure released so far for the path. Then, to optimize, sorted paths by pressure after each second, keeping only the most successful paths for the next iteration. That way the number of paths stays constant. The whole thing runs under a second for my input.
Yeah, the bit manipulation thing was a bit confusing, admittedly. You could most likely get away with just storing the list of opened valves in sorted order in a tuple instead; it'll just be more memory inefficient and slower but by an acceptable constant factor if you don't mind your code taking a bit longer. Also, that is a pretty clever way to do it!
I recently watched a very interesting video series by Sebastian Lague called "Exploring How computers work". It's a playlist on his channel here on youtube. Highly recommended if you're a visual learner like me. He put's in a lot of effort to create awesome animations. The last video is about a 7-segment-display and he does a lot of bit manipulation to make it work.
That's a great explanation! Thanks for the content and your speed is amazing. I managed to solve it myself with a 3 hour runtime for part 2, but was not satisfied obviously. The only thing I would improve is the parsing. I see so many people struggling with splitting, etc, while a simple regex match does it all: /Valve ([A-Z]+) has flow rate=(\d+); tunnels? leads? to valves? ([A-Z ,]+)/ An additional trick to speed up part two is to run the different paths in parallel, this sped it up roughly 4 times on my Macbook pro for a run time of 2.7 seconds.
In fact you don't need "AA": 0 in dists dict (line 24) and then deleting it (lines 40-41). The code: dists[valve] = {valve: 0} [...] del dists[valve][valve] works the same because of your condition above (valve != "AA" and not valves[valve]) :) Also I've checked your algorithm without cache and it is suprisingly fast (3 minutes on my computer for my input without for part 2 without the cache). Bit operations are the power here. After your video I changed just my cache-try (with caching strs like "AA,BB,KF") which was working more than hour and only by changing it to bitmask it works 3 times faster. Nice.
This one was so hard. I have a rough understanding of what the code does but I don't think I understand conceptually how this works. I'm not a super experienced programmer and dfs is new to me so maybe that's why. You did a great job tho!
If you're new then some of the concepts will be very challenging, but good for you for even getting a rough understanding of it considering today's was definitely not an easy challenge by any means!
Great stuff! Regarding the cache.. is it not a bit conservative? in my implementation I simply stored the time and maxVal per node, and if you had a node that was worse in both regards then I returned. I did not use the opened valves at all in the cache mechanism... thoughts?
Thanks so much for posting these. I'm watching to prep for the 2024 AoC! 🎄
Thanks for the nice video 8-)
I really liked the solution for part 2 (I ended up doing something similar, but slightly slower, due to using a set where you used a bitmask).
You can optimise the search a bit more, if you compute the maximum theoretical flow before running the search, and pass the released amount at the time and the current flow through the recursion.
If you then hit a state where remtime*maxflow +released < maxval, you know that you can cache your current state as that, and then return that for that branch
Please make a video on how to approach these questions and how you are coming up with logical solutions for these questions. What things we need to learn in order to solve them..
I'm very much a beginner and so It will be very helpful to me, Because I see a difference or let's say out of the box thinking and logical maths in your solutions. So kindly make a video on this 🙏
I hope this will also be much more useful for many Beginners like me :)
Awesome solution. I especially liked the way you used a bitmask to represent open and closed valves. Looking foward to the Graph Theory video
Thanks for the explanation! Very clever approach. I'm looking forward to your video on graphs.
Didn't have time and mental capacity this week to participate, but videos like yours are always welcome to learn something.
Looking forward to making that video as well :) Glad you enjoyed and could learn something!
Thank you for this video.
Bitmask to use in cache for dfs were interesting concepts I haven't thought about.
Hope you will be able to share videos for rest of the challenges. Keen on learning something!
Really useful video, much thanks for this. This algorithm worked for me in Javascript, for both parts, even without the bitmask - a 15 boolean key-value object, cloned for the DFS recursions and cycling through the necessary permutations in part 2, takes around just a minute.
This was a great video! I learnt a lot from this and I feel more confident that I can get a solution done myself :) thank you for taking time in the vid to explain the algorithm.
Thank you for posting this and explaining your approach. It gives me hope that I'll eventually understand all this stuff. I'm also looking forward to your video on graphs.
I'm sure you will get there sooner or later! Even if things don't fully make sense right now over time things will start to click together. I'm looking forward to making that video as well, glad you enjoyed!
Very nice, looking forward to seeing those videos of graphs of yours :)
Thank you, I'm looking forward to making it as well :)
Thank you for the walkthrough, it helps me a lot
Collapsing the graph into non-empty nodes was my plan B in case my brute force approach didn't work. Nice to see that it was a right idea, though the whole bit manipulation thing is all Greek to me. Luckily my brute force plan A worked well enough. Basically just considered naively all possible paths through all possible nodes, keeping track of global flow rate and pressure released so far for the path. Then, to optimize, sorted paths by pressure after each second, keeping only the most successful paths for the next iteration. That way the number of paths stays constant. The whole thing runs under a second for my input.
Yeah, the bit manipulation thing was a bit confusing, admittedly. You could most likely get away with just storing the list of opened valves in sorted order in a tuple instead; it'll just be more memory inefficient and slower but by an acceptable constant factor if you don't mind your code taking a bit longer.
Also, that is a pretty clever way to do it!
I recently watched a very interesting video series by Sebastian Lague called "Exploring How computers work". It's a playlist on his channel here on youtube. Highly recommended if you're a visual learner like me. He put's in a lot of effort to create awesome animations.
The last video is about a 7-segment-display and he does a lot of bit manipulation to make it work.
Great video. I tried the naive five-state dp for part 2 and let it run overnight. Didn't work FeelsBadMan.
Ah, unfortunate. I tried running my inefficient solution overnight. It... got SIGKILL'd because it ended up taking too much memory, lol.
very clever, well explained too
That's a great explanation! Thanks for the content and your speed is amazing. I managed to solve it myself with a 3 hour runtime for part 2, but was not satisfied obviously. The only thing I would improve is the parsing. I see so many people struggling with splitting, etc, while a simple regex match does it all:
/Valve ([A-Z]+) has flow rate=(\d+); tunnels? leads? to valves? ([A-Z ,]+)/
An additional trick to speed up part two is to run the different paths in parallel, this sped it up roughly 4 times on my Macbook pro for a run time of 2.7 seconds.
Very clear explanation!
In fact you don't need "AA": 0 in dists dict (line 24) and then deleting it (lines 40-41). The code:
dists[valve] = {valve: 0}
[...]
del dists[valve][valve]
works the same because of your condition above (valve != "AA" and not valves[valve])
:)
Also I've checked your algorithm without cache and it is suprisingly fast (3 minutes on my computer for my input without for part 2 without the cache). Bit operations are the power here. After your video I changed just my cache-try (with caching strs like "AA,BB,KF") which was working more than hour and only by changing it to bitmask it works 3 times faster. Nice.
Thank you very much for your video!
Thank you for a great walkthrough!
This one was so hard. I have a rough understanding of what the code does but I don't think I understand conceptually how this works. I'm not a super experienced programmer and dfs is new to me so maybe that's why. You did a great job tho!
If you're new then some of the concepts will be very challenging, but good for you for even getting a rough understanding of it considering today's was definitely not an easy challenge by any means!
Great stuff! Regarding the cache.. is it not a bit conservative? in my implementation I simply stored the time and maxVal per node, and if you had a node that was worse in both regards then I returned. I did not use the opened valves at all in the cache mechanism... thoughts?
Off by one in my attempt, but only on the real data in part two. Not sure what I'm doing wrong.
Whats that terminal that you use to run and how did you time your code like that?
Does DFS + cache actually have less memory footprint than BFS?
I would really like to know how fast it works without memoization. I feel like it doesn't help much
for part 1 there isn't much of a difference, but for part 2 in my machine without cache it take ~3 minutes and with cache it take ~20 second