Also, ... I believe that that cross product is a right handed cross product. It would be interesting to think about what would need to change to make a left handed cross product work (for example, the cross product implementation in the complete tensor essay in the wiki).
(I had thought that I was agnostic to the handedness of the coordinate system, but it looks like that was not the case.) (A trivial fix would be to negate all beacon coordinates along one axis. But I am wondering if there is a simple algorithmic fix which would retain the original coordinate values...) Thanks again, -- Raul On Sun, Jan 9, 2022 at 8:36 PM Raul Miller <rauldmil...@gmail.com> wrote: > > 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
