Yes, it was late! Inversion, not transformation, but not directly relevant; just the alternating signs. And yes, I probably learnt about the intersecting sets but had forgotten. Googling intersecting rectangles or cuboids didn’t reveal much of use. So I was quite pleased with my (re)discovery.
It worked for me,anyway. I’ll have a look at the code later, not on this ipad(!), and share it if it’s not too dense. Cheers Mike Sent from my iPad > On 12 Jan 2022, at 00:51, Raul Miller <[email protected]> wrote: > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
