Well, I was using my right hand/ lh/ 2 fingers & thumb, a la Faraday, for insight! Didn’t help! Mike
Sent from my iPad > On 10 Jan 2022, at 04:54, Raul Miller <rauldmil...@gmail.com> wrote: > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
