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.

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.

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.

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

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.

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!

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.

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.

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.

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.

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

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!

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.

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.

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.

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?

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.

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:

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?

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.

Python

Mathematica

My crusade to

Julia

Java

I'm super late to the party but Im happy with my Rust solution that runs in 300 ms.

Matlab

Python 3. Lovely! 12 Lines of Iteration & Set Theory. Simple/Commented/15 Seconds for Part 2.

Nice one

Thanks! Your solution helped me learn a new way to solve similar set theory questions.

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.

Go/Golang solution

Haskell.

R / Rlang / Rstats / Tidyverse

Late to the party, but here is my Kotlin solution:

Recursive cuboid-splitting solution in python3:

As per our posting guidelines in the wiki under

m4

Thanks to the megathread, I've rewritten an

Julia

Python3

Go! Golang!

Python 3

βββthe cuboids overlap whenβ¦βββ

easylang

Scala 3

Java

Typescript

Kotlin

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.

Rust

Python for

Rust Fast.

holy shit, your solution is amazing. It's so clear. It took me a day and a really complicated solution to get the answer in more than 5 mins runtime (

I was quite happy with my final solution, written in Swift.

I had same logic in my mind but what if new intersected cuboids (new steps) intersects each other?

PostgreSQL

Factor

Python 3

Holy shit I finally found my error by looking at your code. Bless you

Lines 55 to 61 can safely be replaced with "sign = -cuboid_2.sign", I think.

Javascript

Haskell

Rust

Elixir

Rockstar:

Rust

AWK

Post removed due to naughty language. Keep

Go

Rust

Kotlin

C#

F#

Javascript (golfed)

C++17

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

With the set intersection shenanigans it sounds like you've got most of the pieces figured out.

That is super awesome!!!

Python

This was exactly my approach. Takes about the same time.

GOlang

C++20

Swift

C++

[ΡΠ΄Π°Π»Π΅Π½ΠΎ]

Zig

Kotlin

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.

What answer do you get on your real input? I get 1236364099896881.

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.

Python 3.

Python

Thank you, that's a beautiful solution.

Rust

ReScript

Kotlin

Python

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

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.

PHP 8.1.1

Rust

Haskell

Python

How did you know that your star was in 2247th place?

Python

Kotlin ->

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!

GOLANG

Any thoughts on where I might be going wrong?

Clojure

C++:

Rust

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.

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.

Typescript. Runtime 20 min

This is also how I solved it. Simple.

PHP

C#

Javascript

why we have +1 in volume function ? can you please explain for real dummy

C#/Csharp

I think

My C# Solution

Mine in Rust:

Golang

Kotlin

Mine in

Rust

Common Lisp

Python 3.8, no exotic imports, <160ms

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.

- C -

I struggled a lot today.

Python 3

Nice. I also did the yield-six-sub-cuboids thing but missed two good simplifications of yours:

R / Rlang

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.

My solution today was, uhhhh, weird.

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.

Haskell

Please follow the

I love the outside-the-box approach. Clever!

[ΡΠ΄Π°Π»Π΅Π½ΠΎ]

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.

Golang

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

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!

Please follow the

Python

Hi! Thank you for sharing.

You're depressin*AHEM*inspiring me for the second time in a row... thanks!

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.

This is pure awesome. Thanks for sharing.

Python

Rust

My

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

Clojure

Excel w/ VBA

ELIXIR

Haskell

Haskell

Python 3, Null cubes

Swift:

Python

Python

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.

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.

C#

Dart

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?

R

python3

Solutions in C++:

RUST

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.

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:

Python

Python paste

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

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

GO

Postscript,

Today was super hard, probably the hardest day after day 19.

GNU Smalltalk

Egel

Common Lisp

Python 3

Very nice puzzle today, and also the hardest one so far (right?). Here's my

Raku

TypeScript

PHP

I used yours to verify my split/subtract version - and your "contiansFully" was a good touch for performance :) Thanks!

Swift

JavaScript

rust

Python, using numpy

Your NumPy solution uses the same approach as

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?

Python

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.

PHP

Golang

Python

I just wanna comment the fact that in your whole code you wrote Cubiod instead of Cuboid π€£

My

Nice, love the comment about it not being a cuboid :-)