I should perhaps clarify -- since there's no actual physical coordinates involved here. I am using "left handed" and "right handed" to refer to what should maybe be labeled as the parity of the axes of the coordinate system.
I really need better vocabulary for talking about these distinctions. Thanks, -- Raul On Sun, Jan 9, 2022 at 11:52 PM Raul Miller <rauldmil...@gmail.com> wrote: > > 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
