-šŸŽ„- 2021 Day 22 Solutions -šŸŽ„-

  1. Python 3: Couldn't wrap my head around part 2 so I definitely had to peruse Reddit for hints the first time this year... Not too slow.

  2. crazy... using a custom intersect indeed made the difference in performance (several minutes to a second) also in my solution... However, I think you can narrow it down to only 5 cases or with max min ever shorter.

  3. thank you! this is the most easy and straightforward approach to this problem. the only downside is the speed ā€” it's not great. my

  4. I had the same issue and it was very frustrating (the slowness of my solution did not help). I did not find the bug - it's too late for me to even write this - but I split the calculation into subsets for the 8 quadrants and summed up the answers together. Luck helped.

  5. I had a bug in how I handled cube edges. For some reason it worked fine on the test data but failed on the real data. Maybe the real data has overlapping right edges where the test data did not.

  6. Ah I like the idea of just splitting the boxes along the intersections one at a time... that's simpler than the way I approached it (I generated the full 27 possible slices of the intersection and then discarded any with zero volume).

  7. I like reading newer Python coder's work because it's a lot easier to follow. I'm also one and it's helpful when variables actually say what they are and complex algorithms aren't condensed into a single line that recalls a function from a library.

  8. I gotta say, counting the 'anti-cuboid' took some time to visualize. It's such an odd step, but it made sense when I realized we weren't actually tracking state. Just adding up the amounts in the end. What an interesting solution!

  9. Many thanks for the excellent write up of the process here - I had stacking issues with my anti-cubes, and this helped me work it out.

  10. Reading your method, I thought I'd tried exactly that, but it didn't work out - I must have goofed. I then spent an age trying to reason about how the "offs" affect things. My final solution feels like a kludge, but it was easier to reason about.

  11. This is a really lovely and simple solution. I spent a lot of time trying to come up with something (spanning into hundreds of lines), and you do it with essentially two functions. Very tidy.

  12. I had the same reasoning, and many scribbled notes, but somehow couldn't get an implementation working. In the end I converted off volumes into a set of six volumes covering the entire space apart the off volume itself - kind of an inverse. Intersecting these with the working set of volumes did the trick. I'll have to look again to see what was wrong.

  13. Oh, wow, I like this so much :) You actually did what I contemplated for almost half an hour. The only thing that stopped me was lack of meaningful experience with 3D CAD.

  14. Really cool. I was close to finding a solution like this in my mind but I kept getting back to doing intersections, which was what I had already.

  15. I like the trick of adding one to the top end of each range to make them half-open! I followed a similar approach but stuck with closed intervals, which meant my index had to include single number ranges for each of the borders. Using your trick cut my memory usage and runtime by a factor of 8 :)

  16. I give a try on solving part 2 using Octree data structure, by subdividing space in 8 cube cells recursively, then adding on cubes in the octree. But it wasn't a good decision, because at first it would use more than 32GB of RAM and my machine would go out of memory, after some optimizing by trimming down the Octree node and adding dynamic size to its leafs, I was able to build Octree of part 2 under ~8GB of RAM and in 12 seconds. It worked but I don't recommend this way, however it was fun!

  17. Nice, this is by far the best solution I've seen. Really short on account of having no real data structures, but it exposes the simplicity of the problem.

  18. Your first idea wasn't that bad, if you just figured out a smarter way to generate less cuboids, like in

  19. If every time you put the value into the list, you also added n+1 to the same list, it would work. Any time you subtract a cube from inside another, the filled space restarts at N+1.

  20. Yeah, some others also took the coordinate-space compression approach. It seems to work, but takes a hefty chunk of memory (iirc, someone reported 500 MB) and (CPU) time.

  21. Hello, I originally attempted to do something similar, but then I got thrown off by the case where you get two "off" cubes in a row. How does your algo handle that?

  22. So this is what optimization in Rust looks like šŸ˜€ My first idea for part 2 was quite close to yours but because my skills in anti-optimizations (using HashSet and lots of vec merging), it took minutes to run.

  23. You don't need to split the box up, if you know how to compute the intersection of the boxes, you can use the inclusion-exclusion principle to calculate how many nodes they cover:

  24. Thanks, I was pretty much there but everytime doing something a little bit more complicating, simplicity is often the answer :)

  25. Nifty solution. I was trying to come up with something similar but couldn't quite figure it out. Thanks for sharing!

  26. I followed the approach of keeping track of a list of disjoint solids, but it runs in ~7-8 min (in Python). Can you share some details about how exactly you managed the disjoint regions, etc, for people that don't read Haskell, please?

  27. I have the same approach (I thought!?) but somehow mine takes 20 seconds on 1 year old hardware so you're more optimized than me! I end up with a list of 75k cuboids to sum their volumes (some negative some positive) at the end. I think you're doing something to keep that list smaller.

Leave a Reply

Your email address will not be published. Required fields are marked *