Huh... well... I suspect you are talking more about https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula than about https://en.wikipedia.org/wiki/M%C3%B6bius_transformation
And, maybe specifically https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle That said, I'm not yet seeing how to turn this into a useful algorithm. Thanks, -- Raul On Tue, Jan 11, 2022 at 7:42 PM 'Mike Day' via Programming <[email protected]> wrote: > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
