# Advent of Code 2021 - Day 19

This topic is about Day 19 of the Advent of Code 2021.

We have a private leaderboard (shared with users of the elixir forum):

The entry code is:
`370884-a6a71927`

3 Likes

Very cool challenge today, came up with idea of a solution relatively quickly, but made a huge mistake about how rotation/orientation work and spent absolutely forever figuring that part out, and then spent another eternity ironing all the bugs because I was hasty and not careful, so in total it took me 4.5 hours , but when it finally produced correct answer I was so glad:

``````main(File) ->
Data = [ lists:sort([ list_to_tuple([ binary_to_integer(C) || C <- binary:split(RawC, <<",">>, [global, trim]) ])
|| RawC <- tl(binary:split(Scanner, <<"\n">>, [global, trim])) ])
|| Scanner <- binary:split(RawData, <<"\n\n">>, [global, trim]) ],
io:format("part 1: ~p~n", [solve1(Data)]),
io:format("part 2: ~p~n", [solve2(Data)]).

solve1(Data) ->
{Beacons, _} = realign_all(Data),
length(Beacons).

solve2(Data) ->
{_, Scanners} = realign_all(Data),
lists:max([ distance(X, Y) || X <- Scanners, Y <- Scanners ]).

orientations() ->
Circle = lists:seq(0, 3),
[ [{x, 0}, {y, Y}, {z, Z}] || Y <- Circle, Z <- Circle ]
++ [ [{x, 1}, {y, Y}, {z, Z}] || Y <- [0, 2], Z <- Circle ].

orient(Coords, Ps) ->
[ lists:foldl(fun rotate/2, C, Ps) || C <- Coords ].

rotate({P, S}, {X, Y, Z}) ->
case {P, S} of
%% along X
{x, 0} -> { X,  Y,  Z};
{x, 1} -> { X,  Z, -Y};
{x, 2} -> { X, -Y, -Z};
{x, 3} -> { X, -Z,  Y};
%% along Y
{y, 0} -> { X,  Y,  Z};
{y, 1} -> { Z,  Y, -X};
{y, 2} -> {-X,  Y, -Z};
{y, 3} -> {-Z,  Y,  X};
%% along Z
{z, 0} -> { X,  Y,  Z};
{z, 1} -> { Y, -X,  Z};
{z, 2} -> {-X, -Y,  Z};
{z, 3} -> {-Y,  X,  Z}
end.

realign_all(Scanners) ->
realign_all([hd(Scanners)], tl(Scanners), [], []).

realign_all([],    [],       BeaconAcc, ScannerAcc) -> {lists:usort(lists:append(BeaconAcc)), ScannerAcc};
realign_all([H|T], Scanners, BeaconAcc, ScannerAcc) ->
{Follow, Retry, NewScannerAcc} = realign(H, Scanners, ScannerAcc),
realign_all(T ++ Follow, Retry, [H|BeaconAcc], NewScannerAcc).

realign(Left, Scanners, CAcc) ->
lists:foldl(fun (Right, {Follow, Retry, CoordAcc}) ->
case maybe_share_beacons(Left, Right) of
{true, {C, NewRight}} -> {[NewRight|Follow], Retry, [C|CoordAcc]};
false                 -> {Follow, [Right|Retry], CoordAcc}
end
end,
{[], [], CAcc},
Scanners).

maybe_share_beacons(A, B) ->
maybe_share_beacons(A, B, orientations()).

maybe_share_beacons(_Left, _Right, [])               -> false;
maybe_share_beacons( Left,  Right, [O|Orientations]) ->
NewRight = orient(Right, O),
case common_difference(Left, NewRight, 12) of
[K] -> {true, {K, [ add(C, K) || C <- NewRight ]}};
[ ] -> maybe_share_beacons(Left, Right, Orientations)
end.

common_difference(Left, Right, N) ->
Freq = freq([ K || R <- Right,
K <- [ subtract(L, R) || L <- Left ] ]),
[ K || {K, V} <- maps:to_list(Freq), V >= N ].

freq(L) ->
lists:foldl(fun incr_count/2, #{}, L).

incr_count(Key, Map) ->
Map#{Key => maps:get(Key, Map, 0) + 1}.

subtract({X1, Y1, Z1}, {X2, Y2, Z2}) ->
{X1 - X2, Y1 - Y2, Z1 - Z2}.

add({X1, Y1, Z1}, {X2, Y2, Z2}) ->
{X1 + X2, Y1 + Y2, Z1 + Z2}.

distance({X1, Y1, Z1}, {X2, Y2, Z2}) ->
abs(X1 - X2) + abs(Y1 - Y2) + abs(Z1 - Z2).
``````

I have no doubt there is way more elegant solution than this, but I’m still happy I even got that one 3 Likes

A cruel task. Euclidean distance is invariant to involved transformations and it helps to find common beacons. From common beacons we can filter out bad transforms and find a needed one. Then traverse scanners moving between scanners with common beacons, changing origin and points.

I had a hope to solve this without rotations and moves, just by distances and it was a big error that consumed my yesterday. We need both distances and transformations in this case.

3 Likes

Ah so this bit I was missing in my solution. Checking Euclidean distance sets of two scanners to see if they have common beacons before brute forcing orientations speeds up whole thing from 3s to 150ms 2 Likes