I've now modified reboot2a - it's now reboot2b (!) - to accumulate volumes of repeated intersection cuboids. It performs significantly better than reboot2a, whose time & space I reported earlier, in the msg below this one:
ts'reboot2b data' NB. ~6x faster, ~5x smaller 0.229044 1.25469e6 ts'reboot2a data' 1.87207 6.33331e6Perhaps the code is worth sharing given its better performance; I think it's self-contained apart from
the reference to the data filename. It's reasonably aligned given a fixed-width font:
NB. start of script load 'strings' load'files'readsteps =: ". @:(-.&'xyz=')@:(rplc&('-';'_'))@:(rplc&('..';','))@:(rplc&('off';'0'))@:(rplc&('on';'1')) every
NB. The input format with on/off x X y Y z Z is a pain - on reflection, it might have been better to
NB. reorder to on/off x y z X Y Z , but I didn't .....data =: readsteps dtb each rawdata =: LF cut raw =: fread '~user/aoc2122.txt'
rawdata =: >rawdata NB. The input is a numeric array with 7 columns output by readsteps reboot2b =: 3 : 0 ops =. y NB. Initialise with first cuboid and its volumecubs =. ,: }. {.ops NB. I assume first step is an "on" - no sense otherwise
vols =. ,volop1 {.ops
size =: 1 NB. count of number of intersection cuboids
'onoffs ops' =. (}.@:({."1);}."1) ops
for_op. }. ops do. NB. work on next operation
'onoff onoffs' =. ({.;}.)onoffs
ok =. op&doescuboidisx cubs NB. boolean array of
existing cuboids intersecting with current one
newcubs =. op&cuboidisx6 ok#cubs NB. For those that do,
find those intersections, also cuboids
newvols =. -(*ok#vols)*volop1 newcubs NB. assign opposite sign
to next generation of cuboids
if. onoff do. NB. Only need to add the
current cuboid if it's "on"
newcubs =. op, newcubs newvols =. newvols,~ volop1 op end.cubs =. cubs, newcubs NB. add new cuboids to the saved list
vols =. cubs +//. vols, newvols NB. }cubs =. ~. cubs NB. }These two lines accumulate the volumes of identical cuboids NB. } ... This saves time and space
size =: size >. # vols NB. diagnostic
end.
CUBSB =: cubs NB. diagnostic
+/vols NB. answer
)
NB. volumes of an m x 6 or m x 7 array of coords {on or off} xX yY zZ
volop1 =: 3 : '(_2 */@:>:@(-~/\) ])"1 ] _6{."1 y'
NB. Function returns boolean answering: does cuboid x intersect with
list of cuboids y,
NB. x & y in {on/off} xX yY zZ format
doescuboidisx =: 3 : 0
:
pqr =. x{~ -6 4 2 NB. negative indices allow the on/off boolean to
be present or absent
PQR =. x{~ -5 3 1
A =. pqr >."1 y{~"1 ] -6 4 2
B =. PQR <."1 y{~"1 ] -5 3 1
A */"1 @: <: B
)
NB. Reasonably efficient function to return diagonal bounds of
intersection
NB. of cuboids x & y which are in {on/off} xX yY zZ format
cuboidisx6 =: 3 : 0
:
pqr =. x{~ -6 4 2 NB. negative indices allow the on/off boolean to be
present or absent
PQR =. x{~ -5 3 1
A =. pqr >."1 y{~"1 ] -6 4 2
B =. PQR <."1 y{~"1 ] -5 3 1
0 3 1 4 2 5{"1 A,.B
)
NB. end of script
My earlier remarks about the signs of intersections of different levels
or generations still apply,
but it wasn't necessary to break up a contributing cuboid into 3
sub-cuboids; we only need to
keep the intersections which are always cuboids.I'm still clueless on day 23, part 2. I'm going to have to ignore Raul's next post on that one!
Mike On 12/01/2022 14:02, 'Michael Day' via Programming wrote:
OK, sorry about the alarm just now. I'd misunderstood how to apply parse.FWIW, I ran b22 and my "reboota" on "sample" which I'd called "bigexsteps" (big example steps) and on my bespoke data set, called "data" for some reason. "reboot2a" is a much slimmer version of "reboot2". reboot2 performs similarly to b22, while reboot2a outperforms both.NB. "timer" just reports the uncorrected runtime.timer'b22 bigexsteps' NB. I've removed the top and bottom lines of boxing here│0.2990036│39769202357779│ timer'<.reboot2 bigexsteps' │0.43900299│39769202357779│ timer'reboot2a bigexsteps' │0.11200714│39769202357779│ ts 6!:2 , 7!:2@] ts'reboot2a bigexsteps' 0.1109503 3138464 ts'reboot2 bigexsteps' 0.412317 3038368 ts'b22 bigexsteps' 0.3132198 19483040 ts'reboot2a data' 1.8453615 6333312 timer'reboot2 data' NB. 69... seconds - too slow for ts │1 9.0530014│1.2372642e15│ ts'b22 data' |attention interrupt: b22 NB. I gave up waiting.... | b22 data timer'b22 data' NB. 62.6... seconds │1 2.6440048│1237264238382479│I've just spotted that the 43325 intermediate cuboids produced for my data have only 6954 unique members, which suggests I could have worked with counts and ~. , perhaps reducingthe time and space further. Cheers, Mike On 11/01/2022 22:21, Raul Miller 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,
-- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
