Funny how the video started with “alright so let’s do the first thing you’d probably think of, just caching some states in a hashmap” and ended with “so now we get rid of the hashmap.”

I can verify this rule works. Whenever I do less myself (i.e., copy other people's code more) the code ends up being much faster.

The fact that you ended with removing the hashmap ... simply amazing! You started with the slowest possible approach and then worked your way up to the best where you were exploring so less that the hashmap became the overhead! That's some optimization! Don't be too scared to start with the slowest approach or use hashmaps, you might end up discarding them at the end like this guy. Amazing video!

Incredible video. I've been a professional software engineer for nearly 10 years but I don't often have to deal with optimization problems and as such my low-level optimization skills are relatively poor. Walking through all your steps so clearly and concisely really helps me understand some of the different techniques that can be used and is a great addition to my general skills as a programmer. The final optimization in this particular scenario being to merely remove the naive first pass at optimization (i.e. the hash map) was especially revealing.

The last optimization was just the perfect icing on the cake. I was thinking along the lines of "Oh, now is the time for multi-threading!" but never in a million years I would have guessed THAT. Subscribed!

This was definitely one of the most fun problems to optimize this season. I used a similar approach, but it looks pretty different (in particular, non-recursive) because I've had a lot of experience implementing search algorithms for these kinds of problems. They are basically pathfinding problems, where you try to find the path of moves (or sequence of actions) with the least cost (or the largest score). In my case, I just used BFS, where my score at each state is the "minimum achievable score": geodes_collected + (time_remaining * num_geode_robots) . I also added some simple best-case pruning - if it can't beat the best "minimum achievable score" so far, even if it built geode robots in every future turn, then it's not worth searching that branch. I also noticed that you can remove "waiting" from the list of actions, which significantly reduces the number of states. My logic goes: Waiting is a redundant state, because you always have a specific robot you want to build (unless you are running out of time), and you always want to build that robot as soon as possible. So my action becomes the question "what is the next robot I want to build?" and the waiting is built into the state transition, it fast-forwards until either time runs out or it can build that robot. 12:40: Another way to make this safe is to use the bytemuck crate, which encapsulates the unsafe transmute using a bunch of checks on the type layout - requiring #[repr(C)], ensuring there isn't any padding that would be uninitialized, etc. I use bytemuck a lot for shader bindings in graphics programming; since they (mostly) use the C memory layout, I can just specify all the shader variables in a struct and then easily convert it to a byte slice to write to a GPU buffer.

incredible explanation of branch-and-bound. I notice every year there are quite a few questions that don't have a fancy solution, but just require optimizing an okay one; for example the 2022 day 16 problem ("Proboscidea Volcanium") which is another branch-and-bound, or the 2020 day 15 ("Rambunctious Recitation") which just requires a slightly-optimized brute force solution (it's the Van Eck sequence and has no optimal solution) these sorts of questions i really like for aoc as it helps break the stigma to those i teach programming to in that you don't have to memorize 75 algorithms to be good at competitive programming: just need a propensity to sit down and solve a good puzzle! looking forward to your later videos

The number of times where I could just slam dunk a programming problem with math is quite high. Knowing that you are in the right complexity class is key. I like your theoretical analysis of the game.

I find myself continuously returning to this video because it is such a well-done video. it doesn't cover naive but commonly thought optimizations like multi-threading, which could lead to poor performance on older devices, nor does it delve into the process of optimizing the hashmap to the point of oblivion! What sets this video apart is that it demonstrates how to approach a problem and generalize it to enhance the algorithm. Many other videos that merely provide the memoization solution and call it a day, however this video goes the extra mile by presenting clear and concise steps for general optimization that could be used in any application. In my opinion, this video is an invaluable resource and explain in an entertaining manner that you have gained yourself a subscriber.

5 months ago KZfaq recommended me your video of why python is slower than your language, it's impressive to see someone that really puts effort in videos with those animations and good explanation of the topics, one of the best channels I've ever subscribed ❤

I had a very similar experience with AoC 2019 day 18, Many Worlds Interpretation (except that problem took me about 4 or 5 days to complete). Likewise went from a recursive solution that would DNF, to using a cache to getting it to finish in a couple of mins, and then improving it gradually by finding ways to identify clearly terrible strategies (like walking over a key but not picking it up in the 2019 case) and removing them from evaluation. Many of the advanced AoC problems are really great at teaching the "do less = go fast" principle in a very natural way

Fantastic final point! Always remember to *benchmark*, and then remove, any optimizations that for one reason or another, turn out to be premature optimizations overall.

Very cool video! I remember bruteforcing this in 5 minutes and getting on the global leaderboard just to then spend 5 hours trying to optimize it down to milliseconds. I used most of the techniques used in the video, although it took me a while to realize especially the second to last one (although I implemented it in a slightly different way, i.e. for every kind of robot wait until you can build it and then do it; this means that exploring a node doesn't coindice with a single turn though). In the end I spent a lot of type trying to find even tigher upper bounds (it's surprising how many more nodes you can skip with that!)

That cache removal took me off guard but it makes so much sense and is a perfect example of unintuitive optimization processes. There will be solutions implemented that were only solutions at the time they were implemented.

Props for this video, this was a really interesting problem, and you explained your steps and reasoning behind them very well. For fun, I went back and reviewed my own code, and what I did for this day, and there's some more interesting optimizations: - I implemented "no idling" differently, and instead calculate the time until one robot could be produced with the current resources, and skip ahead to that frame. This cuts out all the "waiting states". - I set up a much tighter upper bound, by having two assumptions, and then calculating the time until we can start producing geodes, and how many it'd produce. The assumptions are: --- After the first clay robot has been produced, ore is infinite. --- After the first obsidian robot has been produced, clay is infinite. - I also compute: lower bound = owned geodes + geode robots * remaining time. - Instead of recursion, it uses a binary heap, with states ordered by highest upper bound first, and then highest lower bound. Once the upper bound is >= any previously seen lower bound, we know we are done, and the previously seen lower bound is the actual maximum. So we visit a state, to test paths where we produce any of the new robots, and then compute new bounds on the geode count for those states. For the example in the video, on part one (24 minutes), it visits 343, and computes bounds for 1246 states, which runs in 29µs. For part two (32 minutes), it visits 5373, and computes bounds for 21259 states, which runs in 865µs.

I think what's important to see here is that every optimization has it's cost, either code readability, complexity, or overhead (as with the HashMap). Balancing them is the most important task in my opinion. I think in many cases having easier to understand code can be more important than the speed increase. (And sometimes a seemingly better solution will result in a worse execution time, especially hard to notice in garbage collected languages)

One low-hanging fruit optimization is to use a faster hash function, like fnv. SipHash is only really necessary in cases where you have untrusted/user input as your key material, because it's HashDOS resistant

I wish I got to do more stuff like this at work. This is the kind of stuff that really excites me. There's something in me that just goes kind of crazy when I make something blazingly fast. I made a function go from taking 3 minutes to just below 2 seconds before, I could've done even more, but I couldn't really justify it. It was also fast enough by a long shot even if it had taken 30 seconds.

Realising what you had to do for that last step is the true wizardry of programming. I certainly wouldn't have figured that out

Love the step-by-step approach to optimisations used here. Great job! Love to see more of these types of videos. 🙌🏾

I just discovered your channel and this is such a great video. Very fun to watch and very inspiring. Great work, I'm looking forward for your future videos.

This was fantastic! What a great example of how to think about and tackle a complex problem systematically. How you walked through each step, the intuition behind each change, and built the solution up from parts was perfect. I would love to see more videos like this.

Absolutely incredible, your explanation as you went really helped to guide me through the thought process you used - hope to take advantage of this soon!

Best software video I've seen lately with a great ending, subscribed.

This is a really great video! So much information, learnt a lot. Thank you! Would love to see more aoc optimization videos in the future!

Your video style and clarity in the explanation is awesome! Thank you.

This is so cool. I didn't understand anything after a certain point but still interesting.

Nice, it's like checking the min-max score on a chess tree and then truncating the branches that will not give a higher score. How chess engines work. My solution was to simply randomly try different combinations and see what works, then store the learned preferred combination in the final production code. I wonder if this is "almost as good" as the binary tree approach here; of course it will by definition be suboptimal but it's easier to code for sure.

PLEASE UPLOAD MORE OF THESE VIDS this is the best someone has explained a DP problem ever i love this video❤❤

Great video! Here is one further state space optimization: remove 'idling' as an option. That is, instead of each child node being the parent node + 1 turn passes, make each child node be the result of a "what do I choose to build next?" choice. For each choice, calculate immediately how many turns it will take to build the thing (how many turns are needed to wait for resources + do the build) before recursing to the child. That is a generalization that should obviate the awkward can_build booleans and removes all "I idled" child nodes from the graph.

Just stumbled upon your channel. Great video! Explained gorgeous the ideas! Instant subscribe

I'm a novice programmer who has never used Rust but I watched this from start to finish. Superb piece of presenting, aside from anything else. I'm probably several years off implementing something like this, but as a novice its a nice way of being introduced to concepts.

I don't usually comment, but that ending was the most satisfying ending I've seen in a long time.

Great video, keep it up! Would love to see more like this, specially in Rust

Never expected that last optimisation! Subbed!

This is an excellent video, thank you for putting the effort into making it.

Incredible explanations! Keep it up!

6:40 yes, i was wondering that too and it's awesome. the terminology used - hits/misses matches the terms used in paging and page replacement algorithms pretty well :)

this is brilliant. Well done and very interesting example

so much was deleted by the end, even your camera doing more with less

this is a masterpiece video. incredible

Thank you very much! This is profoundly useful.

It's like a magician's performance, that twist at the end. Brilliant!

Continue this style of video and you got yourself a long term viewer

Tips in the video: #1 (1:40): Try doing less #2 (4:13): Start with an algorithm that is definitely correct #3 (6:34): Use caches to avoid expensive work multiple times #4 (8:23): dynamic programming is just recursion + caching #5 (13:30): Understand how abstractions work, so you can use them effectively

The camera didn't die. It was just doing less

Great video, I didn't understand everything but still some of it made sense. Thank you,

I loved this, great job!

wow, I wish I could like a video twice, that ending was amazing

That was a satisfying ending! Tbh did not expect that, but it makes a lot of sense!

the last 2 software project i started are paused cuz i couldn't figure out a way to solve the problems i was having.. it's so nice to see someone reasoning trough a problem and solving it efficiently

I'm not even gonna pretend that I understood most of what you said, since I'm pretty much still at the very beginning of learning programming, but it was pretty interesting regardless. Thanks for making this video. Maybe it will help me one day in the future.

This is an insanely cool video.

amazing content, thank you for your time!

I think I now understand the point of memorization. Man what a round about way of realizing something

that was a lot of fun! I don't use Rust, but I've been curious about it for a while, and I really enjoyed this

incredible video, thanks a lot

The best way is to just return the correct answer immediately

Absolutely awesome vid!

I'm pretty sure the unsafe transmute is undefined behavior if you don't specify repr(C). As you said, the field layout is undefined, which also means there can be padding in between and reading padding is undefined behavior.

Pretty good video man!

This man talks like the engineer I want to be. He has an understanding of low-level processes that make me embarrassed to claim to be an engineer. How do I learn this kind of stuff? Is there a community?

Definitively worth a follow

babe wake up new leddoo video

This is amazing! Less is more until more is less.

Wonderful video!

This is a great video! Enjoy your other content too, but would love to get some more "tutorial"/"think like a programmer" videos!

That ending was just beautiful

that was just beautiful

A good lesson to take from this is to solve as much of a problem as possible before letting the machine take over. I can imagine someone working on this one long enough that they can practically solve it with pen and paper, then the final algorithm can be in the μs range

I watched this video a few days ago and decided to hold off on watching the rest so I could have a go at solving the problem on my own time. I spent too much time trying to do so and eventually caved to see what "the solution" was. Turns out, there is no "the solution"! That was exactly my problem. I was trying to find an elegant algo that would get the job done. But this video revealed this is nothing more than simply beginning with brute force, followed by a series of clever prunes to the space. Moral of the story - just start with the brute force!

That was beautiful

Nice content! Minecraft textures are a bonus :)

I would usually put "memory layout" under "doing less" as in doing less memory fetching.

This is exactly the kind of progressive optimization I love. You have me reconsidering my Rust solutions for Project Euler, wondering if there are more unseen optimizations to be had...

You forgot to mention that 12.7 million is approximately the population of Bavaria. Unforgettable omission.

My approach to optimization is always dfs and memoize and hope for the best haha. Been programming for 10+ years haha and clearly I haven’t progressed since year one.

Simply amazing

great video 🥇 well done 👍

This is excellent. I could watch 1000 of these. I was so bummed when I saw there weren't more. No pressure though (^・ω・^ )

there's no reason for a programming video to go this hard 🐐🐐🐐

One of the big reasons I love Lisp languages is that I can write a macro that memoizes functions for me.

whoa. subscribed 👍

As someone who has worked quite a bit on optimization problems like this, I also enjoyed this particular problem of AOC and your video about it! Branch and bound is a classic technique and this is a nice and simple example of how powerful it can be. Just for fun I benchmarked my own solution that I wrote a couple months ago against yours. Averaging over 10 runs I get: Part 1 | Part 2 Mine | 1.3 ms | 47 ms Yours | 6.3 ms | 107 ms Our approaches are a bit different. You use DFS whereas I use BFS with a lower bound heuristic (build the most expensive robot possible). These are both okay (usually best-first search ala A* is better but I was too lazy for that). You use some domain knowledge to prune like only building geode robots when possible but I didn't bother with any pruning outside of comparing the lower and upper bounds. On the other hand, I put in more work into my upper bound which often gives the biggest bang per buck for branch and bound algorithms. Usually a good strategy for an upper bound is to relax the problem to something simpler that you can solve exactly. The relaxation I came up with is the following. Given a starting state of resources, create a copy of the resources for each type of robot - lets call this their personal inventory. Building a robot takes resources from their personal inventory. But when a robot *produces* a resource, that resource is added to *each* robot type's personal inventory. Each minute, you're allowed to build up to one robot of *each* type at once. This is clearly a relaxation because each robot type's personal inventory is an upper bound on the resources that you would have if they all shared resources. And since you can always decide to just build one robot, a solution to the original problem is a feasible solution to the relaxation. On the other hand, it is easy to construct an optimal solution to this relaxation: simply build robots whenever possible. So that is the upper bound that I used for branch and bound. Less is more, but sometimes more is less! In this case, doing a lot more work per state reduces the number of states to ~2300 in part 1 and ~81600 in part 2. Code: gist.github.com/t-troebst/466cb7017a295ab4d4a571238876f0a8

Nice work, please consider making more like this, I think it is a category of coding information that is under represented on KZfaq. If anyone has suggestions for other sources of such information, please do share :D

i was struggling with aoc22 d19 for months now. ofc i thought of brute forcing it but instantly disregarded this method cause i was determined to fine some more logic way to solve this. i tunnlevisioned this ideal solution and at the end couldn't find it. finally i watched this video, which i had saved for a month after i watched it a little and realized it's about the same problem which i was stuck on. this is incredible stuff. im so glad i stopped being stubborn. i let go of my self assigned goal of 'if i do this it will be by my own force'. the _smartest brute force_ is an incredible method and i am so glad to have learned it. thank you

great video. thanks.

this is brilliant

it is so satisfying to see those numbers drop

How cool is that please, Wie cool ist das bitte

THANK YOUUU

One way I optimized this problem was building a better state tree. Instead of having actions like if can build robot, build robot, or wait, I changed my actions to be: Either build a x robot at t2 or build a y robot at t4. There is no wait action at all. I believe your no idling pruning is in the end equivalent to this, but I am mentioning this as just a different way of thinking.

At 12:06, technically it is safe to transmute this into a u64, but Rust doesn’t guarantee preserving field order for structs, only drop order. You’d ideally want to annotate Pack with #[repr(C)] to prevent rustc from reordering fields. Also, it may be a good idea to explicitly align the struct too ( with #[repr(C, align(8))] ). Struct alignment is calculated as the max alignment of each of its fields. Since Pack is a struct of u8’s, it has an alignment of 1, but u64 has an alignment of 8. mem::transmute()’s docs says the compiler will take care of ensuring compatible alignment, but I am not 100% sure if adjusting the unaligned value adds any overhead so explicitly aligning couldn’t hurt. EDIT: unpaused and saw you addressed the field ordering and repr. Hopefully this comment is still helpful for anyone interested

That ending was wild.

Great work optimizing the code. There is still an open question. How do you know that you will need only one a certain amount of robots before you produce only geode robots? Is that an assumption or did you actually optimized for geodes.

Great video! Only thing that confused me was you saying that `std::mem::transmute` would raise an error if the source and target types are of different sizes. I assume you mean it will panic, but I can't see that in the documentation. Wouldn't it just be Undefined Behaviour and therefore definitely *less* robust than the safe version?

This is really cool, it's a very nice demonstration of how using a couple of key techniques in a spiral of improvements can whittle down a problem. But after seeing this, I wonder if you can't draw out this approach to optimizing even further? The rules of this game say you can build only one robot per turn. So once you hit time X the point where you can make one geode robot every turn, everything else after that should be expressible as a simple function of Y time -> Z geodes. And it only takes a finite number of steps to get to that point in the fastest possible way. Essentially, each moment in time until the takeoff point is a special case with a knowable geode value. So you could also just hard-code all those special cases for time < X, and the general function for time >= X. That's a bit banal solution, but then, the problem itself has no real randomness or surprises that require dynamic adaptation; the only variable is how many time steps you get. And it's in keeping with the general way of optimization here: aggressively use domain knowledge to do less. It's just kinda the big brother to optimizing a fixed-length loop by unrolling it.

Pretty good, you'll probably get big soon

My first thought was to explore the tree using A*. I'd have to actually work through it more thoroughly to be sure, but think it would be equivalent to all of your optimizations except "u8" and "enough bots".

Branch-and-bound and symmetry breaking are overpowered