Oops, I thought I had included that in my message. My apologies: NB. from https://code.jsoftware.com/wiki/Phrases/Matrices cross=:(1 _1 1 * 1 (-/ . *)\. ])@,.
Good question, thanks. -- Raul On Sun, Jan 9, 2022 at 9:49 AM 'Michael Day' via Programming <programm...@jsoftware.com> wrote: > > Raul, would you mind defining cross? I've tried */ and (+/ . *) but > neither seem to > work for me, and I'm not sure what you mean. > > As I said a few days ago, I gave up wondering why I'd found 48 > rotations when they > asked for 24, couldn't grasp what the meant by facing" and resorted to > matrix divide > with rounding to yield the orientation matrix in each case. > > Still stuck on day23 part 1!!! > > Cheers, > > Mike > > On 09/01/2022 02:14, Raul Miller wrote: > > https://adventofcode.com/2021/day/19 > > > > Like a variety of my work on previous days, my code here is rather > > bulky. Did I mention that Advent of Code was something of a bad habit > > for me? > > > > Anyways, here, not only is the code bulky, even the sample data is bulky. > > > > Basically, for this puzzle, we were given a bunch of coordinates > > beacons reported by a small set of scanners. These coordinates > > contained three "flaws": > > > > (1) They used a coordinate system which was centered on the scanner -- > > not a universal coordinate system. > > > > (2) Each scanner had limited range, so no single scan had locations > > for all beacons. > > > > (3) Each scanner had an undetermined orientation. > > > > Luckily for us, each probe "originally" had the same coordinate > > system, and each probe's rotations were multiples of 90 degrees along > > each axis. So there were only 24 possible orientations for each > > scanner. > > > > And, sample data looked like this: > > > > sample=:{{)n > > --- scanner 0 --- > > 404,-588,-901 > > 528,-643,409 > > -838,591,734 > > 390,-675,-793 > > -537,-823,-458 > > -485,-357,347 > > -345,-311,381 > > -661,-816,-575 > > -876,649,763 > > -618,-824,-621 > > 553,345,-567 > > 474,580,667 > > -447,-329,318 > > -584,868,-557 > > 544,-627,-890 > > 564,392,-477 > > 455,729,728 > > -892,524,684 > > -689,845,-530 > > 423,-701,434 > > 7,-33,-71 > > 630,319,-379 > > 443,580,662 > > -789,900,-551 > > 459,-707,401 > > > > --- scanner 1 --- > > 686,422,578 > > 605,423,415 > > 515,917,-361 > > -336,658,858 > > 95,138,22 > > -476,619,847 > > -340,-569,-846 > > 567,-361,727 > > -460,603,-452 > > 669,-402,600 > > 729,430,532 > > -500,-761,534 > > -322,571,750 > > -466,-666,-811 > > -429,-592,574 > > -355,545,-477 > > 703,-491,-529 > > -328,-685,520 > > 413,935,-424 > > -391,539,-444 > > 586,-435,557 > > -364,-763,-893 > > 807,-499,-711 > > 755,-354,-619 > > 553,889,-390 > > > > --- scanner 2 --- > > 649,640,665 > > 682,-795,504 > > -784,533,-524 > > -644,584,-595 > > -588,-843,648 > > -30,6,44 > > -674,560,763 > > 500,723,-460 > > 609,671,-379 > > -555,-800,653 > > -675,-892,-343 > > 697,-426,-610 > > 578,704,681 > > 493,664,-388 > > -671,-858,530 > > -667,343,800 > > 571,-461,-707 > > -138,-166,112 > > -889,563,-600 > > 646,-828,498 > > 640,759,510 > > -630,509,768 > > -681,-892,-333 > > 673,-379,-804 > > -742,-814,-386 > > 577,-820,562 > > > > --- scanner 3 --- > > -589,542,597 > > 605,-692,669 > > -500,565,-823 > > -660,373,557 > > -458,-679,-417 > > -488,449,543 > > -626,468,-788 > > 338,-750,-386 > > 528,-832,-391 > > 562,-778,733 > > -938,-730,414 > > 543,643,-506 > > -524,371,-870 > > 407,773,750 > > -104,29,83 > > 378,-903,-323 > > -778,-728,485 > > 426,699,580 > > -438,-605,-362 > > -469,-447,-387 > > 509,732,623 > > 647,635,-688 > > -868,-804,481 > > 614,-800,639 > > 595,780,-596 > > > > --- scanner 4 --- > > 727,592,562 > > -293,-554,779 > > 441,611,-461 > > -714,465,-776 > > -743,427,-804 > > -660,-479,-426 > > 832,-632,460 > > 927,-485,-438 > > 408,393,-506 > > 466,436,-512 > > 110,16,151 > > -258,-428,682 > > -393,719,612 > > -211,-452,876 > > 808,-476,-593 > > -575,615,604 > > -485,667,467 > > -680,325,-822 > > -627,-443,-432 > > 872,-547,-609 > > 833,512,582 > > 807,604,487 > > 839,-516,451 > > 891,-625,532 > > -652,-548,-490 > > 30,-46,-14 > > }} > > > > There will be a quiz later. (Ok, maybe not...) > > > > So, first thing we need here is a mechanism to parse this into > > something J can handle. And, it's not obvious here, but the number of > > beacons reported by each scanner was not the same. This means we need > > to put the scans in boxes so they are not padded. > > > > I decided I also wanted my parsing routine (which I named 'get') to be > > idempotent. This would let me use parsed or unparsed data on the > > command line -- if it was parsed already, 'get' would leave it alone. > > > > get=: {{ > > if. -.'literal'-:datatype y do. y return. end. > > s=. getscan;._2 rplc&(',';' ';(LF,'---');LF,'!---') y,'!' > > {:"1 s assert. (i.#s) -: ;{."1 s > > }} > > > > digits=: ".@([ -. -.)&(~.":i.10) > > > > getscan=: {{ > > (id=. digits 0{::lines); coords=. __&".@>@}. lines=. (<;._2 y)-.a: > > }} > > > > I could have made get and getscan a little simpler, by ignoring the > > reported scan number. But I was working on this puzzle late at night > > and it was easy for me to make mistakes. > > > > The next problem was to piece scans together to form the complete list > > of beacons (using the coordinate system of the scanner #0). > > > > There's a variety of approaches which could have been used here. Mine was > > this: > > > > (a) I would measure the distance between each pair of *beacons* > > reported by each scanner. The distance between any beacon pair was > > guaranteed to be fixed for every scanner which included both of those > > beacons. > > > > (b) For each pair of *scanners*, I would find and count the beacon > > distance lists which they had in common. Scanners which were closer > > together should have more beacons in common with each other than > > scanners which were farther apart. > > > > Looking at the data, I saw that most scanners had at least one other > > scanner which reported 67 or 68 of the same beacon distances, the next > > most frequent commonality was 17 or 18 of the same beacon distances. > > So, in code, I only concerned myself with scanners which had at least > > half as many beacons in common as the largest reported commonality. > > > > (c) For these pairs, I would find the orientation of the second based > > on the orientation of the first, using the beacons which they had in > > common (the ones whose distances were the in each of the pair of > > scans). > > > > In particular, I decided that I could ignore two problems: > > > > (*) I was not concerned with "spoofed distances". I had enough > > information that I believed that coincidental distance matches would > > not be a problem for me. > > > > (*) I was not concerned with "spoofed orientations". I had enough > > information that I believed that there would be one and only one > > orientation that best fit the beacons for the scanner pairs I was > > considering. > > > > That left me with the problem of representing intermediate results. > > > > The first step -- getting distance pairs between beacons reported by a > > single scanner -- was straightforward: > > > > signature=:{{+/&.:*: |:-"1/~ y}} > > > > usigs=: ~.@,@signature each scans > > rough=: +/@(e.,)&>/~ usigs > > > > The next step - identifying pairs of scanners which were close to each > > other - had one minor trick: each scanner was very, very close to > > itself. And I needed to ignore that. > > > > In other words, I multiplied by the logical negation of the identity matrix > > > > rough=: (* -.@=@i.@#)+/@(e.,)&>/~ usigs > > > > Actually, though, I did not need the counts of close beacons -- I just > > wanted to identify the scanners which had a lot of beacons in common > > > > rough=: (> -:@(>./)@,) (* -.@=@i.@#)+/@(e.,)&>/~ usigs > > > > Next, I wanted to visit those pairs in sequence, starting from scanner > > zero. There's a variety of ways of doing this, but one way is to use > > rough as a connection matrix. Then (+./ .*.)&rough given a selection > > mask would lead us to the connected scanners. These connections are > > bidirectional, and we want to know how soon we can visit a scanner. We > > can use ^: to iterate some number of times and then </\ to find the > > first 1 in each column. My approach here included a lot of extra blank > > rows, which I suppressed using ~. > > > > ~.</\(+./ .*)&rough^:(i.#rough) (#rough){.1 > > > > Finally, I can't sort on a list of bitmasks, but I can convert them to > > an ordered list of indices that represent the order I want to visit > > the scanners. > > > > order=: ;<@I. ~.</\(+./ .*)&rough^:(i.#rough) (#rough){.1 > > > > I'm not quite ready to compare scanner pairs yet, though -- I need to > > extract the "close scanner pair" list from rough, and sort them: > > > > close=: (/: order&i.) ($#:I.@,)rough > > > > But that approach actually lists each scanner pair twice (0 7 and 7 > > 0), and that's not necessary. So, I could do: > > > > close=: ~. /:~"1 (/: order&i.) ($#:I.@,)rough > > > > or > > > > close=: (/: order&i.) ($#:I.@,) (* </~@i.@#)rough > > > > With that setup, I am *almost* ready to walk through my scanner pairs. > > But I still need to represent their orientation and offset. > > > > Each scanner has both an offset from the global origin (scanner 0), > > and an orientation with respect to scanner 0. The offset is easy to > > represent -- that's just an x,y,z value. The orientation, though, ... > > that I represented as a permutation of the axis along with a sign > > (positive or negative) for each axis. > > > > reorient=:{{ > > 's a'=.8 6#:{.x > > off=. }.4{.x > > sign=. _1^2 2 2#:s > > off+"1 sign*"1 (a A. i.3) {"1 y > > }} > > > > Here, x is the orientation and offset for the scanner, and y is the > > list of beacon coordinates to be manipulated. > > > > This is not an optimal representation. The problem with this approach > > is that it can represent both right handed and left handed coordinate > > systems, and I only wanted coordinate systems which could result from > > a rotation of the origin coordinate system. > > > > I did not know whether that origin system was right handed or left > > handed (since I didn't have any external reference data), all I cared > > was that my alternate orientations matched. To solve this I did a dry > > run, using an identity matrix in place of beacon coordinates, and 0 > > offsets. If a cross product of the first two result coordinates > > matched the third, I had a viable orientation: > > > > plausible=: I.({:-:cross/@{.~&2)@reorient&(=i.3)"1 ,.i.48 > > > > Still with me? I got to this point mostly by trial and error, with > > lots of asserts in my code to make me aware of invalid assumptions. I > > have since deleted most of those mistakes and the assertions which > > made me aware of those problems. And, I've cleaned up some of my code > > a bit from my initial puzzle solution, so that it would be readable. > > But I am not sure how well I am explaining my resultant > > understanding... > > > > The next stage of puzzle solving was, for each pair of scans: > > > > (1) find the beacon coordinate pairs in each which share a distance > > between the scanner pair. > > > > (2) Try each of the plausible orientations (with zero offsets), > > subtracting the selected parts of the scanner set. Since the beacon > > coordinate pairs are ordered by distance between the pair, they are > > ordered the same for each scanner set. And, when I get the orientation > > right, distance between pairs from the two sets will mostly be the > > same distance apart (this will be the distance between the two > > scanners). > > > > My implementation is still a bit sloppy here, but it gets the job done: > > > > whichori=:{{ > > d=. #@~.@:(-&x)@reorient&y"1,.plausible > > plausible{~d i.<./d > > }} > > > > relori=: {{ > > 'c0 c1'=. y > > sigs=. signature@>y > > k=. +/4=#/.~,sigs > > ref=. k{.}. (~. \: #/.~),sigs > > ids=. (* k&>) ref i. sigs > > pairs0=. pairs1=. i.0 0 > > for_id. 1+i.k-1 do. > > j=. (}.$sigs)#:I.,id=ids > > assert.4=#j > > pairs0=. pairs0,(2{.j) { c0 > > pairs1=. pairs1,(2}.j) { c1 > > end. > > o=. pairs0 whichori pairs1 > > candidates=./:~(#/.~,.~.),/pairs0 -"1 o reorient pairs1 > > assert. ~:_2{.{."1 candidates > > off=.}.{:candidates > > o,off > > }} > > > > Note that when I wrote this code I was not completely sure that I > > would not have "spoofed distances". So I am not actually completely > > ignoring that problem -- the assert. 4=#j in the middle of relori > > would fail if I somehow had the same distance between more than a pair > > of beacons. (It's 4, rather than 2, because each pairing is > > represented twice -- I found the distance between each pair of beacons > > and beaconA is the same distance from beaconB that beaconB is from > > beaconA.) > > > > It would be fun working out how to express this more concisely, but I > > haven't thought enough about that issue. > > > > And, that's all the pieces I needed for part A, which was to count the > > total number of scanned beacons: > > > > a19=:{{ > > scans=: get y > > heritage=:(,;0);(<:#scans)#<i.0 0 > > usigs=: ~.@,@signature each scans > > rough=: (> -:@(>./)@,) (* -.@=@i.@#)+/@(e.,)&>/~ usigs > > order=: ;<@I. ~.</\(+./ .*)&rough^:(i.#rough) (#rough){.1 > > close=: ~. /:~"1 (/: order&i.) ($#:I.@,)rough > > known=:,:0 0 0 0 0 > > for_scanpair.close do. > > 'kid jid'=. scanpair /: (0,,scanpair_index{.close) i. scanpair > > kori=. }.(({."1 known) i.kid){known > > known=: known,jid,t=.relori (kori reorient kid{::scans); jid{::scans > > end. > > #~.>,each/(}."1/:~~.known) reorient L:0"_1 scans > > }} > > > > I've left a variety of global assignments here, because looking at > > example data really helps when understanding the code. Also > > > > For part B, the problem was to find the largest "manhattan distance" > > between two scanners. > > > > In other words, given the location of each scanner > > 2}."1~.known > > > > take the sum of the absolute values of the difference between each > > pair of locations, then find the largest of those sums > > > > b19=:{{ > > a19 y > > >./,+/"1|-"1/~2}."1~.known > > }} > > > > If there's something here which I should have explained better, and > > you can think of a way to phrase a question about it, let me know... > > > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
