Advent of Code 2023 Day 12: Hot Springs
Vložit
- čas přidán 1. 06. 2024
- Back to #4 for now!
My AoC repository: github.com/hyper-neutrino/adv...
Join my Discord! / discord
0:00 Part 1
8:08 Part 2
Want to improve your mastery or learn a new language? Try Codecrafters, a platform where you learn by building your own project! I've always believed that learning by doing is the best way to learn to code by far, so check them out with my link! app.codecrafters.io/join?via=.... You can sign up for free and try out some of their streams including full beta projects for free (no credit card required) and you'll get a 40% discount on annual subscriptions!
(Disclaimer: I receive commissions on paid memberships through my link, but Codecrafters is not a sponsor of this channel, does not endorse any of my content, and does not review any of my videos.)
This is my second take of today's video. I really didn't like my first solution as it was overcomplicated and inefficient, so I decided to do it again. You can find my unedited live solve VOD for today here: czcams.com/video/GVcER1GavNQ/video.html
I was on the old video and suddenly saw [OLD] after it, as I reloaded the site, the solution had changed, I thought I was witnessing a Mandela effect LOL
This was a remarkable solution. I was similarly stymied, but the damn finally broke when I saw that by tracking fewer moving parts in the recursive function, it made previous counts much more cacheable. Really well done, man.
Really appreciate the explanation. I understand recursion, but often have difficulty thinking of the base cases. I really struggle to break down the problem in the way you did. My understanding of dynamic programming is that it's essentially just recursion with memoization. Is there more to it than that? Found it interesting that you said you avoid DP, but I felt like your solution was basically DP. Thanks again for the upload and congrats on your high finish in 2023!
You are a gentleman and a scholar. Thanks for explaining so clearly and concisely.
tips for part two, just do this, it does the same :)
from functools import cache
@cache
def count(cfg,nums):
...
the best solution thats out there by far, i was super stuck with this one and looking through a lot of solutions but after i saw yours i just instantly knew this is the way to do it
That "cache" trick though! Wow! That made a huge difference to my time. Very nice hack! I wouldn't have ever thought of that! Not in that simple a way!
My Rust-based solution was very similar to yours, and it took 10.5 hours (multithreaded on eight cores, but it's really
Wow, what an elegant solution, thanks for sharing! I also like your visual style, as in colors and typography.
I finally solved part 2 of this yesterday (the last one missing to finish AOC 23), but bit less elegantly than this, by not processing a whole damaged cluster at once, but char by char instead, while passing along a requirement for the next char, such as Any, NotDamaged or DamageOfLength(remaining size).
And for a while I forgot to memo the parts that didn't have an arrangement and only remembered the good ones. Worked fine for part 2 examples, but not the real input.
The best explanation I have seen so far. The code was also quite understandable. Great work. I just added a simple optimization on top of your approach. Instead of mutating cfg, nums and using them as key in the cache, you can maintain indices i and j to see how far we have come in parsing cfg and nums respectively. And now, we can use (i, j) as the cache for the key.
I often have a very hard time trying to understand recursions just in general but you made it very clear in your explanations and solution. Thanks a lot
I'm working in javascript and was completely lost with how to approach day 12. I adopted your logic and built a cache using the Map() constructor and it worked beautifully! Thanks for making this video, helped me understand the problem better!
I just spent one hour understanding the first video haha thank you though for sharing your resolutions, I am learning a lot from it
Haha, yeah I wasn't thinking clearly today and didn't realize at first that my idea was totally overcomplicated xD glad to hear that my videos are helpful though! 🙌
Nicely explained! 2 questions:
(1) why not just use the @cache decorator (from functools) to memoize the count function?
(2) I was surprised by the not-equal and less-than-or-equal symbols that you used. What's inserting those into your code and does python recognize them as is? Or is it something just the IDE is doing?
Regarding #1, he very likely just didn't know about it. Regarding #2, that's a VSCode thing.
Brilliant solution, clearly explained. Does anyone know which font is being used for the editor here?
It's Monaspace Radon
Great tutorial! I've tried porting your solution to C# and was wondering how does Python handle cases like "?????????##????? 1,9,1"? My program runs for a couple of minutes and uses up all the available RAM (20 GB+) before completely hanging Windows :)
For part one, I (for each line of input) created every integer from 0 to 2^(number of "?"s in input), and converted the binary representation of each into "."s and "#"s instead of 0s and 1s. For each of those, I checked if replacing all the "?"s with the binary thing gave a valid solution. How did I check? With a regex generated like this:
"^\.*" + ("#" repeated N times for every N in the counts list) joined by "\.+" + "\.*$"
I am ashamed to commit it to my git history.
I did exactly the same.
I knew that brute forcing like this was clearly not the best solution, especially because part 2 would make the brute force useless. I spent a lot of time trying to make my brute force more efficient, using dynamic programming, but I failed.
To me, the challenges are an opportunity to learn a lot, should we be ashamed to have things to learn? :)
regex takes a lot of time, if you just split the string by '.', filter out empty spaces and then check to see if each group lengths corresponds to the grouping lengths. From 110sec with regex to 2sec without it.
@@code-kiwi I absolutely agree, it was a bit tounge in cheek. It's amazing how much I learn from this stuff!
@@piroliroblack1219 Hmm, I guess that depends on efficiency of the language used, and on the regex interpreter. The only extra thing the regex does is verify that the groups only have "#"s in them, and depending on the implementation, it could be run in highly efficient machine code, whereas the other solution could be wastefully interpreted. Anyway, I tried to change it in my solution and got a ~30% speedup, which isn't bad! But I do enjoy a good regex.
3:51 Windows :D
7:39 - isn't there an error here? If nums[0] is 5 and len(cfg) is also 5 when we enter the if block, then cfg[5 + 1:] will produce an invalid range into the cfg string.
Edit: ok apparently Python does not behave the same as other languages when it comes to array bounds checking. Yes the start of the string index is out of bounds but it doesn't matter in python as the result is always an empty string.
Yeah, slices work differently. If you try to access a single out-of-bounds index, you get an error, but if your slice lies out of range, it will just return an empty result. I find it very convenient TBH.
I think I'm going insane. Doesn't this solution allow for later lengths to be counted before prior ones had chance to fit in the segment? For example, wouldn't that count #.#.####.# as a valid solution for ???????????? 1, 4, 1, 1, 1? The task description says: "After the list of springs for a given row, the size of each contiguous group of damaged springs is listed in the order those groups appear in the row.", but it seems that this order isn't respected at all. I had somewhat similar solution that worked, though it was iterative instead of recursive, and my answer was accepted despite this apparent flaw. Is it just the input that never made this being relevant, or am I actually just going mad?
I don't think this flaw exists, at least not in my solution. When I see a # (or attempt to treat a ? as one), I check nums[0] so the block size must match the next existing block; you can't skip past # and you can't skip past a block size in the nums array.
what
ok, i got it