Oh, the irony of writing about the day that people complained about most, on the day that people were about to complain about even more! Since the Day 19 puzzle has been released, I've seen cries everywhere from, "I'm tapping out," to, "End me." I also was not sure I was going to be able to solve it at first, but I dove in anyway, starting with my secret weapon: sleep.
Yes, instead of starting to code, I went to bed. As I read a book (though I'd love to pretend it was my fresh copy of Call Us What We Carry, by Amanda Gorman, it was in fact the more guilty-pleasurable Dead Hot Shot, by Victoria Houston), an idea came to me. I resisted the urge to try it. As I put the book down and turned off my light, a better idea revealed itself. Before I could fall asleep, two refinements came to mind. While I was afraid of losing them if I didn't write them down, I was sure I'd stay up stumbling through mistakes if I pulled out a computer.
This morning, though, the idea was almost fully baked. This is my first time trying to solve such a 3D space alignment task, and the following is what I came up with.
Just like on Day 17, each axis can be partially-solved independently. When comparing two scanner's readings, we need to determine two things: how far apart the scanners are, and their relative orientation. My solution learns both at the same time, but for each axis nearly independently.
The basic process is to compare only the values of one axis in the reference scanner's readings, to the values of each axis in the test scanner's reading, stepping through X, -X (the X axis flipped around), Y, -Y, Z, and -Z, one at a time, until one "matches". A match is defined as twelve beacons (or more) in the reference reading being the same distance (along this axis) from twelve beacons in the test reading.
Unlike Day 17, it pays off to use the knowledge of a match on one axis to constrain the search on the others. The search for the first matching axis might mean comparing all test beacons to all reference beacons up to six times (as we try each axis and its inverse). But if we know, for example, that test X aligns with reference X, then we only need to test alignments for reference Y against four test axes (Y, -Y, Z, -Z). And if we know two alignments, there is only one more to check: if test Y and reference Y align, test Z must align with reference Z, or the readings aren't related at all. So, we cut our search space from a static 6+6+6 = 18 to a worst-case 6+4+1 = 11. That's less than a 50% cut, but when the comparisons are all-to-all, each of them is somewhat costly.
As some people noted, though, while the concept is "simple", there are a lot of moving parts to keep track of. So let's look at the code.
-record(s, %% scanner
{n, %% number
a, %% alignment
bs}). %% beacons
-record(b, %% beacon
{x,
y,
z}).These are the two datastructures I'll be using. Records in erlang are syntactic sugar around tagged tuples. The scanner record s (I knew this code was going to be bulky, so I kept the datatype names short) is going to create a 4-tuple whose first element is the atom 's', and whose following three fields can be accessed by name. For example, when you see S1#s.bs below, I'm accessing the "beacons" field of the scanner tuple stored in variable S1. The number of the scanner is irrelevant, but was nice for debugging. The alignment started out as debugging, but became necessary in Part 2. The beacons field is a list of b records. I also ended up using b to record alignment, so I probably should have named it something like "vector".
find_overlap(S1, S2) ->
case find_overlap(S1#s.bs, S2#s.bs, #b.x, all_rotations()) of
[] ->
[];
XOverlaps ->
find_overlap_x(S1, S2, XOverlaps)
end.
find_overlap_x(S1, S2, [{XSel, XOffset}|Rest]) ->
case find_overlap(S1#s.bs, S2#s.bs, #b.y, rotations_for_selection(XSel)) of
[] ->
find_overlap_x(S1, S2, Rest);
YOverlaps ->
find_overlap_xy(S1, S2, {XSel, XOffset}, YOverlaps)
++ find_overlap_x(S1, S2, Rest)
end;
find_overlap_x(_, _, []) ->
[].
find_overlap_xy(S1, S2, XSO, [{YSel, YOffset}|Rest]) ->
case find_overlap(S1#s.bs, S2#s.bs, #b.z,
rotations_for_selection(element(1, XSO), YSel)) of
[] ->
find_overlap_xy(S1, S2, XSO, Rest);
ZOverlaps ->
find_overlap_xyz(S1, S2, XSO, {YSel, YOffset}, ZOverlaps)
++ find_overlap_xy(S1, S2, XSO, Rest)
end;
find_overlap_xy(_, _, _, []) ->
[].
find_overlap_xyz(S1, S2, XSO, YSO, [{ZSel, ZOffset}|Rest]) ->
ZS2 = move_beacons(#b{x=XSO, y=YSO, z={ZSel, ZOffset}}, S2#s.bs),
case length(find_matching(S1#s.bs, ZS2)) of
L when L >= 12 ->
[#b{x=XSO, y=YSO, z={ZSel, ZOffset}}]
++ find_overlap_xyz(S1, S2, XSO, YSO, Rest);
_ ->
find_overlap_xyz(S1, S2, XSO, YSO, Rest)
end;
find_overlap_xyz(_, _, _, _, []) ->
[].
find_matching(BS1, BS2) ->
ordsets:intersection(ordsets:from_list(BS1), ordsets:from_list(BS2)).We're looking for twelve beacons that match position between two scanners. I've called this twelve the overlap, so that's what my functions are trying to find. We start at the top in find_overlap/2, trying all rotations of S2 against S1's X axis. If we find enough matching measurements along one or more, we proceed to find_overlap_x, where we try the remaining rotations of S2 (given a matching choice of X alignment) against S1's Y axis. When we find another good match, we proceed to find_overlap_xy to test the only remaining choice in S2 against S1's Z axis.
It may seem like finding enough matching measurements at that point means we've found the answer. But, in each of these functions, I've been comparing the whole set of beacons. It's entirely possible that the Z measurements matched a different set of beacons than the X or Y measurements matched. On my first attempt to code this process, I thought I'd be able to pass just the set that matched in each step up through the stack, so that a match at Z would mean that the same set of beacons matched. But, that optimization was fraught with bugs, so instead we take our proposed alignment, move all the beacons in S2 to their S1-relative position, and then check if there are now 12 or more that are exactly the same. There is a ++ in this function, implying that there could be multiple Z offsets that might match. Later code asserts that there is exactly one, and solving the puzzle confirmed that this was the case.
find_overlap(BS1, BS2, FS1, [Sel|Rest]) ->
case maps:keys(
maps:filter(fun(_, V) -> V >= 12 end,
offset_histo(FS1, BS1, Sel, BS2))) of
[] ->
find_overlap(BS1, BS2, FS1, Rest);
Found ->
%% it's easier to find all overlaps on this axis now than
%% to come back to it if the first doesn't work
[{Sel, F} || F <- Found] ++ find_overlap(BS1, BS2, FS1, Rest)
end;
find_overlap(_, _, _, []) ->
[].
offset_histo(FBS1, BS1, {FBS2, M}, BS2) ->
lists:foldl(
fun(V, Acc) ->
Offsets = lists:usort([ element(FBS1, B) - V || B <- BS1 ]),
maps:merge_with(fun(_, C1, C2) -> C1 + C2 end,
maps:from_list([{O, 1} || O <- Offsets]),
Acc)
end,
#{},
[ M * element(FBS2, B) || B <- BS2 ]).Mentioned in the previous code snippet is one more find_overlap function that takes four arguments, not two. The clash in naming stems from an initial implementation when I thought the whole process would fit in one function. But, this one is what determines whether an axis alignment matches. It starts by calling offset_histo. That function computes the pair-wise difference between each beacon in FBS1 and each beacon in FBS2. It then creates a map from the unique distances found, to the number of beacons in S2 that are that distance from any beacon in S1. That is, if S1 has beacons at 1, 9, and 12, and S2 has beacons at 5 and 8, you'll get a histogram saying #{1 => 1, 4 => 2, 7=>2}, because both 5 and 8 are 4 away from some beacon, both are 7 away from others, and 8 is also 1 away from one beacon. When find_overlap continues, it selects the keys from this map that have values of 12 or more. It returns those keys along with the Selection of alignment that found them. This list may not be necessary. In small testing, I found no cases where multiple 12+ matches were found in a selection. But, speculative debugging led me to cover more cases.
All of this code, and all we've done is compare two sets of beacon readings. There are 33 sets in the full puzzle input! I really wanted to divide-and-conquer this a little more. It feels like one of those cases where you could split the scanners into two lists, align each of them, then align the combined groups, to save some comparisons. Alas, I don't think it's possible. Not all scanners have overlap with other scanners, so you can't expect to actually be able to merge those disjoint sets independently, and you wouldn't know how much overlap to expect in the big join afterward. So instead, I offer the following solution.
align_scanners(Scanners) ->
{value, S0, Rest} = lists:keytake(0, #s.n, Scanners),
align_scanners(Rest,
[S0#s{a=#b{x={{#b.x,1},0},
y={{#b.y,1},0},
z={{#b.z,1},0}}}],
[]).
align_scanners([S|Rest], Aligned, Retry) ->
case find_alignment(S, Aligned) of
none ->
align_scanners(Rest, Aligned, [{length(Aligned), S}|Retry]);
A ->
Moved = move_beacons(A, S#s.bs),
align_scanners(Rest, [S#s{a=A, bs=Moved}|Aligned], Retry)
end;
align_scanners([], Aligned, []) ->
Aligned;
align_scanners([], Aligned, Retry) ->
case lists:any(fun({L,_}) -> L < length(Aligned) end, Retry) of
true ->
align_scanners([S || {_, S} <- Retry], Aligned, []);
false ->
{Aligned, Retry}
end.
find_alignment(Su, [Sa|Rest]) ->
case find_overlap(Sa, Su) of
[] ->
find_alignment(Su, Rest);
[A] ->
%% this will fail to match if puzzle is designed such that
%% two scanners can line up in multiple ways
A
end;
find_alignment(_, []) ->
none.I chose to follow the puzzle description's example and shift all beacon positions into scanner 0's frame of reference. That made it easy to compare against the example solution. Because of that problem I mentioned earlier, that not all scanners have overlapping beacons with all other scanners, it takes multiple passes to get all scanners aligned to scanner 0. Each one has to have beacons in common with another scanner that is already aligned with scanner 0. It would be slightly more efficient to skip Aligned scanners that a Retry didn't match the first time. But, by the time I got to this code, I was several hours into the solution, and I was just happy it ran in a second-ish.
%% Scanners must be aligned
count_unique_beacons(Scanners) ->
length(ordsets:union([ordsets:from_list(S#s.bs) || S <- Scanners])).Once the scanners are aligned, counting the number of unique beacons is almost comically simple. The size of the set-union of their coordinates is all it takes.
79 = puzzle19:count_unique_beacons(puzzle19:align_scanners(ExampleScanners)).Part 2 asks for Manhattan Distance between scanners, which we just used on Day 15! And it needs the aligned scanner distances that I had been keeping around as debugging aids until now.
%% Scanners must be aligned
manhattan_distance(#s{a=#b{x={_,X1},y={_,Y1},z={_,Z1}}},
#s{a=#b{x={_,X2},y={_,Y2},z={_,Z2}}}) ->
abs(X1-X2) + abs(Y1-Y2) + abs(Z1-Z2).
%% Scanners must be aligned
largest_manhattan_distance(Scanners) ->
lists:foldl(fun(T, Acc) ->
lists:max([Acc|[manhattan_distance(T, S)
|| S <- Scanners]])
end,
0,
Scanners).Since the alignment process stashed away the offset, in each direction, that we moved each beacon, the manhattan distance between any two scanners is just the sum of the absolute differences of those offsets. A quick fold across the pairwise distances produces the answer.
3621 = puzzle19:largest_manhattan_distance(puzzle19:align_scanners(ExampleScanners)).This puzzle was, indeed, a major commitment. Even the 100th place on the leaderboard took over an hour on this one. I'm curious to see tomorrow whether this level continues, or if this puzzle happening to land on a Sunday gave the creators a little extra leeway in how much time was appropriate. I tried to solve this puzzle by coming up with a way to solve the problem myself. Are there libraries that have been written to answer this question for other domains? Is this something that drone swarms or IoT networks deal with? What did you come up with? Let me know on Twitter (@hobbyist). And if you'd like to see the all the code (there are a few small bits I skipped) all together (instead of the segmented format here), it's all on github.
Categories: Development AdventOfCode
Post Copyright © 2021 Bryan Fink