Briefly for now, as the pub quiz went on far too long & it’s midnight... I hope my hint wasn’t too much of a spoiler; unintended if it was.
My insight was somewhat mathematical, and is similar in a way to the Moebius transform. I worked through a 2-d analogue looking at intersecting rectangles last Wednesday while sitting in the Natural History Museum’s cafe for 90 odd minutes! So- if you consider the area from the addition of two intersecting rectangles, A & B, you can sum their areas and subtract their area of intersection. So A (+) B = A + B - A.B . ( where A stands for its area, A.B stands for the area of the intersection of A & B, and (+) means the operation of switching on B after A. If, however, we’re switching off B, we have A (-) B = A - A.B , where (-) means the operation of switching off B . Now add rectangle C. I found that A (+) B (+) C = A + B + C - A.B - B.C - C.A + A.B.C In general, intersections of n objects have a sign of (-1)^n. It’s quite tricky to work out the coordinates of the intersections of cuboids. Sticking with rectangles for now, suppose A has diagonals (1 1), (3 4), & B is (2 2), (4 5) . Then the intersection A.B is (2 2), (3 4) That leaves us with 2 non-rectangles, but they’re made up of 6 rectangles of same level, or parity (?), as their parent: A - A.B comprises (1 1), (2 2) & (1 2), (2 4) & (2 1), (3 2), while B - A.B is (3 2), (4 4) & (3 4), (4 5) & (2 4), (3 5) So when C comes along, it’s much easier to consider its intersections with all these derived rectangles than with the irregular polyhedra of which they are components. I didn’t mess with the ordering of the operations; they seemed highly non-commutative! Way past bedtime. Cheers, Mike Sent from my iPad > On 11 Jan 2022, at 22:21, Raul Miller <[email protected]> wrote: > > 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, > > -- > Raul > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
