Advent of Code 2022 Day 16 Walk-Through

Please attempt the problem on your own before watching this video!

[imthemass]

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 :)

[awwkaw]

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

[davidtimbwa]

Awesome solution. I especially liked the way you used a bitmask to represent open and closed valves. Looking foward to the Graph Theory video

[paulsmart]

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.

[flwi]

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.

[jakubblejder]

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!

[bennorton]

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.

[JoelKaneshiro]

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.

[werneraltewischer]

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.

[karolkurek]

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.

[xAlx]

Very nice, looking forward to seeing those videos of graphs of yours :)

[JJ-psvb]

Great video. I tried the naive five-state dp for part 2 and let it run overnight. Didn't work FeelsBadMan.

[jacoblewis]

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!

[phsopher]

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.

[romainbodec]

Thank you for the walkthrough, it helps me a lot

[hbb]

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?

[dominikkinkela]

Whats that terminal that you use to run and how did you time your code like that?

[oosterhuisf]

Off by one in my attempt, but only on the real data in part two. Not sure what I'm doing wrong.

[fredoverflow]

Does DFS + cache actually have less memory footprint than BFS?

[SuperNolane]

I would really like to know how fast it works without memoization. I feel like it doesn't help much