https://adventofcode.com/2021/day/22
The day 22 puzzle was about "rebooting the reactor".
Here, we have a sequence of steps which consist of turning on, or off,
a rectangular cuboid in our coordinate system. In this puzzle each
x,y,z coordinate value was referred to as a cube.
s=: sample=:{{)n
on x=-20..26,y=-36..17,z=-47..7
on x=-20..33,y=-21..23,z=-26..28
on x=-22..28,y=-29..23,z=-38..16
on x=-46..7,y=-6..46,z=-50..-1
on x=-49..1,y=-3..46,z=-24..28
on x=2..47,y=-22..22,z=-23..27
on x=-27..23,y=-28..26,z=-21..29
on x=-39..5,y=-6..47,z=-3..44
on x=-30..21,y=-8..43,z=-13..34
on x=-22..26,y=-27..20,z=-29..19
off x=-48..-32,y=26..41,z=-47..-37
on x=-12..35,y=6..50,z=-50..-2
off x=-48..-32,y=-32..-16,z=-15..-5
on x=-18..26,y=-33..15,z=-7..46
off x=-40..-22,y=-38..-28,z=23..41
on x=-16..35,y=-41..10,z=-47..6
off x=-32..-23,y=11..30,z=-14..3
on x=-49..-5,y=-3..45,z=-29..18
off x=18..30,y=-20..-8,z=-3..13
on x=-41..9,y=-7..43,z=-33..15
on x=-54112..-39298,y=-85059..-49293,z=-27449..7877
on x=967..23432,y=45373..81175,z=27513..53682
}}
At the start of this process, every cube in the reactor is off.
Our part A puzzle asked us how many cubes would be on with values _50
.. 50 for x, y and z.
Simple enough:
use=: parse;._2
parse=:{{
f=. 'on'-:2{.y
good=. y e.'-',":i.10
t=. f,__ ". good #inv good # y
assert. 7=#t-._ __
assert. 1e9 >>./t
assert. _1e9 <<./t
}}
thru=: [ ~.@, <. + i.@(+*)@-~
a22=:{{
Y=. _51 >. 51 <. use y
r=. 101 101 101 $0
for_op. Y do.
'f x0 x1 y0 y1 z0 z1'=. op
I=. >,{(x0 thru x1);(y0 thru y1);z0 thru z1
I=. 50+(#~ 51 -.@e."1 |) I
r=. f I} r
end.
+/,r
}}
Here, I clipped coordinate values to the range _51 .. 51, found all
values inside the possibly clipped coordinates, stripped out any
references to cubes with a coordinate magnitude of 51 and set or reset
a bit for each remaining cube reference. Simple, straightforward, and
totally inadequate for part B.
Part B removes the constraint on range, and with the puzzle data
requires us to count a number of cubes in the vicinity of 1e15.
For part B, my approach was to track cuboid regions that were 'on',
and split them into smaller cuboids when this intersected with an
'off' cuboid. Conceptually, this might result in up to 26 new cuboids
(for example on -30..30,-30..30,-30..30 followed by off
-10..10,-10..10,-10..10). But, usually, we had partial overlaps which
created fewer fragments.
I could not think of a quick way of identifying arbitrary overlaps
when computing the sum I needed for the result here, so I decided I
should also split cuboids when 'on' regions overlapped.
Anyways, this meant I was storing the locations of the corners of the
cubes, and lead me to this implementation:
b22=:{{
Y=. use y
r=. i.0 3 2
for_op. Y do.
'f x0 x1 y0 y1 z0 z1'=. op
t=. r I."1"2 (x0,x1),(y0,y1),:z0,z1
F=.i.0
ok=. (0 0 e."2 t)+.2 2 e."2 t
if. 0 e. ok do.
splits=.((-.ok)#r) split((<:x0),x1),((<:y0),y1),:(<:z0),z1
assert. 3=#$splits
assert. 3 2-:}.$splits
r=.(ok#r),splits
end.
if. f do.
r=.r,((<:x0),x1),((<:y0),y1),:(<:z0),z1
end.
end.
cubesum r
}}
NB. sum the volumes of all cuboids
cubesum=: {{
+/*/"1-~/"1 x:y
}}
NB. split cubes in x based on cube y
split=: {{
;x <@split2"2 y
}}
NB. split a cube by splitting coordinates
NB. discard split cubes where all coordinates are discarded
split2=: {{
(([: +./"1 {."1) # }."1) >>,{x <@ahand"1 y
}}
NB. coordinate range x into pieces which exclude y
NB. retain the part of y within x
NB. prefix each segment with 1 (keep) or 0 (discard)
ahand=:{{
'LO HI'=. x
'lo hi'=. y
assert. hi >: LO
assert. HI >: lo
lo=. lo >. LO
hi=. h i<. HI
((lo~:LO),LO,lo);(0,lo,hi);(hi~:HI),hi,HI
}}
I do not remember what 'ahand' meant.
Is there a better way?
If I had assigned to each statement a "sequence order" such that
statements with a higher order would override statements with a lower
order, and constructed a conflict map for each statement, I might have
been able to sum expanding subregions 'directly' based on a
topological sort (or perhaps using some variant on graph traversal)
which put minimum complexity items first. I say this because of the
hint Mike Day provides in
http://jsoftware.com/pipermail/programming/2022-January/059547.html
Thanks,
