<Advent of Code 2021 day 22> :thread:

# advent-of-code

[Advent of Code 2021 day 22]

Advent of Code 2021 day 22 🧵

[Jintin]

https://github.com/Jintin/AdventCode2021/blob/main/src/Day22.kt
Part 2 is quite interesting for me.

[Jakub Gwóźdź]

I failed to solve today in pure kotlin and needed to use java.util.BitSet . Apparently Kotlin has BitSet only in native stdlib…

[Jintin]

What is BitSet used for btw?

[Jakub Gwóźdź]

Array<Boolean> but better 🙂

[elizarov]

I am totally puzzled. How does BitSet help here?

[Jintin]

I guess it is used to generate 3d on/off map

[elizarov]

It is not that big to need a bitset. BooleanArray works just fine.

[Jakub Gwóźdź]

I brute forced part2 and turned cube on and off (used bitset to represent the state in memory)

example
00:00:00.266: parsed 60 commands
00:00:00.279: split into 116*116*118 cubes
00:00:00.377: commands executed
00:00:00.386: 460960 cubes turned on
00:00:01.818: 2758514936282235

memory
00:00:01.820: parsed 420 commands
00:00:01.825: split into 830*829*824 cubes
00:00:03.159: commands executed
00:00:03.165: 149763891 cubes turned on
00:00:52.981: 1387966280636636

[Jakub Gwóźdź]

oh geez… there’s a BooleanArray 🤦 (I tried ByteArray and heap was complaining)

[Jakub Gwóźdź]

but BitSet helps with

return generateSequence(result.nextSetBit(0)) { index ->
            result.nextSetBit(index + 1).let { if (it >= 0) it else null }
        }
            .sumOf { index ->
                val xx = index / 1000000
                val yy = index / 1000 % 1000
                val zz = index % 1000
...

so it’s not a waste 🙂

[Jintin]

for part 2 I encounter memory issue too, so I solve it by join section by section. I think it's around 1 sec for part 2 in this way.

[phldavies]

https://github.com/tKe/aoc-21/blob/main/kotlin/src/main/kotlin/year2021/Day22.kt I’m quite happy with this, solves part2 in ~65ms

[phldavies]

I was surprised IntRange doesn’t have a .size property

[Michael Böiers]

Quite happy with my solution today. I guess it’s somewhat unique, but I haven’t looked at any other except for Jonathan Paulson’s, so we shall see … https://github.com/MikeEnRegalia/AdventOfCode2021/blob/main/kotlin/src/main/kotlin/Day22.kt

[elizarov]

There’s a significantly simpler way to solve it via a technique known as “coordinate compression”.

[phldavies]

@Michael Böiers I was going to write a cuboid “difference” method that returns a set of non-overlapping cuboids but found it wasn’t needed if you count the size of the cuboid taking the overlaps into account

[phldavies]

@elizarov I’d love to see a 3d coordinate compression solution to this - if anything to see how the data structure would be defined and used

[Michael Böiers]

Cool - of course I completely over-engineered it again. 😆

[phldavies]

I don’t know - your solution is definitely simpler still than my initial attempts to make my initial per-coordinate part1 scale to the larger number of nodes 🤣

[phldavies]

I started doing a bitset per axis direction (-x, x, -y, y, -z, z) and track it that way … 🤷

[Ruud Wiegers]

@phldavies @elizarov I was inspired to try this, so here's a quick and dirty implementation of the idea:
https://github.com/Ruud-Wiegers/advent-of-code/blob/master/y2021/src/main/kotlin/adventofcode/y2021/Day22Compressed.kt

[phldavies]

Awesome, I won't peek just yet as I might give it a go myself later (if I understand the concept anyway)

[elizarov]

@phldavies See https://github.com/elizarov/AdventOfCode2021/blob/f2756ee130bcff8aaf6e0228d16eb8d0428a751c/src/Day22_2.kt

[ephemient]

https://github.com/ephemient/aoc2021/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2021/Day22.kt I went down a huge rabbit-hole of trying to build my own octree library, but it turned to be full of annoying cases to handle and also not fast enough. then I realized I could just slice by space instead of by time, and then everything just worked instantly (25ms for part 2)

[ephemient]

… now that I see it, reducing the cardinality of the space like that Roman did is much simpler …

[todd.ginsberg]

My original solution was really overcomplicated. I was doing far more work than was needed to avoid a solution that involved busting big cubes into smaller cubes. I just wanted to deal with intersections and add up volumes and do some subtraction but I made a huge mess of it. I went to Reddit for advice and figured out why I was seriously overthinking things. Maybe I’m distracted or just getting burnt out on AoC. I dunno. Anyway, I’m happy with what I ended up with.

• Code
• Blog

[Dan Fingal-Surma]

https://github.com/dfings/advent-of-code/blob/main/src/2021/problem_22.main.kts

[Fredrik Rødland]

@todd.ginsberg thanks again for a great blog post with a very nice explanation! Always a joy to read up on your solutions! neat trick with the negative volumes…

[phldavies]

https://github.com/tKe/aoc-21/blob/main/kotlin/src/main/kotlin/year2021/Day22CoordCompression.kt @elizarov I'm glad to see my solution was similar - I'm surprised at how much slower it is though than my other solution

[Dan Fingal-Surma]

Negative volume is a neat idea

[todd.ginsberg]

Thanks @Fredrik Rødland! I wish I could take credit for negative volume. Originally I had two lists of positive volumes that I was summing and subtracting and doing way more work than needed to juggle the states.

[phldavies]

@Ruud Wiegers I've seen your solution now I've attempted it - I like the approach of pre-compressing the instructions too 👌

[Jintin]

for part 2 I encounter memory issue too, so I solve it by join section by section. I think it's around 1 sec for part 2 in this way.

By changing List to IntRange the performance is increasing a lot, data structure is really important here, haha.

[ephemient]

I tried out the compression thing and (unless I'm doing something wrong) I think the partitioning approach I took is still a lot faster… but it's also pretty repetitious. I still have to think about how to clean it up

[phldavies]

I tidied up my coordinate compression solution again, and got the runtime down to ~500ms. Still not at the 30-40ms I get from my main solution though