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,
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
