Fork me on GitHub
#adventofcode
<
2021-05-20
>
Joe20:05:53

I'm trying to do https://adventofcode.com/2015/day/6 part 2 which involves a conceptually simple problem. Described one way, you have a 1kx1k array and given several 'boxes' of indices within that array you have to change the values at each of those indices in the array (+1, -1, +2 depending on the instruction). Part 1 was a simple binary on/off. I solved it using sets of coordinates and unions/intersections, but it was very slow (~30seconds). For part 2 I could go down the route of a double reduce with a map of coord->value, but I'm guessing that will also be very slow. The solutions I've seen in languages like Rust seems to handle just looping through the instructions and banging on an array no problem. Should I look at just using a 1kx1k array here, and would that be more performant (like in the sub-5 second range)? Or is there another way to think about this problem? https://github.com/RedPenguin101/aoc2015/blob/main/src/aoc2015/day6.clj

Joe20:05:46

Yeah, the map solution worked but took ~40 second

spfeiffer20:05:19

I remember using mutable primitive arrays there for performance reasons.

chrisblom08:05:40

making current transient might help

chrisblom08:05:34

but you would need to adapt union/difference/exclusive-union to work with a transient set

chrisblom08:05:41

the mutable array approach will be faster i think, hard to beat that approach

Joe09:05:41

Gotcha, thanks!