Skip to content

Instantly share code, notes, and snippets.

@bjorng
Created Dec 18, 2021
Embed
What would you like to do?
Solution for Advent of Code 2021 - Day 18
-module(aoc2021_day18).
-export([solve_part1/1, solve_part2/1]).
-include_lib("eunit/include/eunit.hrl").
solve_part1([H | T]) ->
N = lists:foldl(fun(N, Sum0) ->
Sum = add(Sum0, flatten_term(N)),
reduce(Sum)
end, flatten_term(H), T),
magnitude(N).
solve_part2(Numbers0) ->
Numbers = [flatten_term(N) || N <- Numbers0],
lists:max([magnitude(reduce(add(A, B))) ||
A <- Numbers,
B <- Numbers -- [A]]).
add(A, B) ->
[down] ++ A ++ B ++ [up].
reduce(N0) ->
case maybe_explode(N0) of
no ->
case maybe_split(N0, []) of
no ->
N0;
{yes, N} ->
reduce(N)
end;
{yes, N} ->
reduce(N)
end.
maybe_explode(N) ->
maybe_explode(N, 0, []).
maybe_explode([down, A, B, up | T0], 4, Rev0) ->
Rev = explode(Rev0, A),
T = explode(T0, B),
{yes, lists:reverse(Rev, [0 | T])};
maybe_explode([down | T], Level, Rev) ->
maybe_explode(T, Level + 1, [down | Rev]);
maybe_explode([up | T], Level, Rev) ->
maybe_explode(T, Level - 1, [up | Rev]);
maybe_explode([H | T], Level, Rev) ->
maybe_explode(T, Level, [H | Rev]);
maybe_explode([], _Level, _Rev) ->
no.
explode([H | T], N) when is_integer(H) ->
[H + N | T];
explode([H | T], N) ->
[H | explode(T, N)];
explode([], _N) ->
[].
maybe_split([H | T], Rev) when is_integer(H), H > 9 ->
Q = H / 2,
{yes, lists:reverse(Rev, [down, floor(Q), ceil(Q), up | T])};
maybe_split([H | T], Rev) ->
maybe_split(T, [H | Rev]);
maybe_split([], _Rev) ->
no.
magnitude(N) ->
magnitude(N, []).
magnitude([down | T], Stack) ->
magnitude(T, [up | Stack]);
magnitude([up | T], [up | Stack]) ->
magnitude(T, Stack);
magnitude([up | T], [N, up | Stack]) ->
magnitude(T, [N | Stack]);
magnitude([up | T], [N2, N1, up | Stack]) ->
magnitude(T, [3 * N1 + 2 * N2 | Stack]);
magnitude([H | T], Stack) when is_integer(H) ->
magnitude(T, [H | Stack]);
magnitude([], [Magnitude]) ->
Magnitude.
flatten_term([A, B]) ->
[down] ++ flatten_term(A) ++ flatten_term(B) ++ [up];
flatten_term(N) when is_integer(N) ->
[N].
-ifdef(EUNIT).
explode_test() ->
?assertEqual([[[[0,9],2],3],4],
flatten_explode([[[[[9,8],1],2],3],4])),
?assertEqual([[3,[2,[8,0]]],[9,[5,[7,0]]]],
flatten_explode([[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]])).
flatten_explode(N) ->
{yes, Exploded} = maybe_explode(flatten_term(N)),
unflatten(Exploded, []).
magnitude_test() ->
?assertEqual(143, flatten_magnitude([[1,2],[[3,4],5]])),
?assertEqual(3488, flatten_magnitude([[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]])).
part1_test() ->
?assertEqual(3488, solve_part1(example())),
?assertEqual(4088, solve_part1(input())).
part2_test() ->
?assertEqual(4536, solve_part2(input())).
flatten_magnitude(Term) ->
magnitude(flatten_term(Term)).
unflatten([down | T], Stack) ->
unflatten(T, [up | Stack]);
unflatten([up | T], [up | Stack]) ->
unflatten(T, Stack);
unflatten([up | T], [N, up | Stack]) ->
unflatten(T, [N | Stack]);
unflatten([up | T], [N2, N1, up | Stack]) ->
unflatten(T, [[N1, N2] | Stack]);
unflatten([H | T], Stack) when is_integer(H) ->
unflatten(T, [H | Stack]);
unflatten([], [Unflatten]) ->
Unflatten.
example() ->
[[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]],
[7,[[[3,7],[4,3]],[[6,3],[8,8]]]],
[[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]],
[[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]],
[7,[5,[[3,8],[1,4]]]],
[[2,[2,2]],[8,[8,1]]],
[2,9],
[1,[[[9,3],9],[[9,0],[0,7]]]],
[[[5,[7,4]],7],1],
[[[[4,2],2],6],[8,7]]].
input() ->
[[[0,6],[[[4,0],[6,6]],[[2,2],9]]],
[[9,[[1,6],[6,0]]],[[1,[0,8]],[[0,8],[9,8]]]],
[[[0,[2,1]],3],[[[2,4],[1,2]],[7,5]]],
[[[[8,3],[8,5]],[[7,8],[5,5]]],[9,2]],
[[8,[1,9]],[[[9,9],[9,2]],1]],
[[[[3,7],[2,1]],[0,9]],4],
[[[[3,8],[6,0]],[0,7]],[[[6,3],[2,0]],9]],
[[[9,[7,0]],[8,[9,6]]],[[5,6],4]],
[[[[3,6],[3,6]],[0,2]],[[[8,3],9],[[3,4],8]]],
[[7,[8,4]],1],
[6,[[3,[5,6]],[0,6]]],
[[[7,[4,7]],[[4,5],[4,3]]],[[5,5],[0,[4,2]]]],
[[[0,[2,9]],[[2,4],[4,8]]],[[8,[9,5]],[[9,6],0]]],
[[[[2,0],[9,7]],[[3,2],0]],[7,7]],
[[5,[2,1]],[[3,[5,1]],[[8,5],[1,8]]]],
[[[[9,7],6],[[7,8],7]],[[[6,8],9],[[9,5],7]]],
[[4,2],[[[0,1],[7,2]],[[0,2],[5,5]]]],
[[1,8],[[5,[7,9]],[[3,1],[7,1]]]],
[[[4,[4,6]],6],5],
[[[5,[3,6]],6],[[[8,0],[8,6]],[[3,3],[0,1]]]],
[[4,[[2,6],[0,9]]],[[0,6],[4,2]]],
[[[[9,4],[6,5]],7],[[[1,5],[0,9]],[4,[4,2]]]],
[[7,[[6,5],8]],[[[5,6],0],[6,[3,5]]]],
[[[5,[6,4]],[8,[0,4]]],[[3,[9,3]],4]],
[[[[4,0],6],[6,[6,5]]],[[9,[6,3]],[[9,6],7]]],
[[[[2,2],4],[8,[7,2]]],[2,1]],
[5,[9,[[5,9],4]]],
[[[1,[7,7]],[[2,2],8]],[[[9,7],5],[4,3]]],
[[[[6,8],1],1],[1,[[2,0],6]]],
[[[[0,5],8],[[8,9],[9,3]]],[[[5,5],[4,2]],2]],
[[[9,[2,5]],[6,[1,7]]],[5,[3,[2,2]]]],
[[[7,6],8],[[[1,9],3],[5,2]]],
[8,[[2,[0,7]],8]],
[[[[8,1],[0,0]],5],1],
[[1,[[4,8],0]],[[9,[7,8]],5]],
[[[[1,3],1],[[9,8],[6,6]]],5],
[[[3,2],[[0,5],[0,1]]],[[9,[9,3]],[4,9]]],
[[[0,[2,4]],[[3,3],[6,5]]],[[1,[2,1]],[[3,4],9]]],
[[2,[3,[7,6]]],[5,5]],
[[[[8,2],0],[[9,6],[9,0]]],[[[6,2],[5,0]],9]],
[7,[9,7]],
[3,[[[5,5],1],[8,5]]],
[[[5,5],[5,6]],[9,5]],
[[[9,7],[1,2]],[8,[5,[7,0]]]],
[[[1,[5,2]],[7,[8,9]]],[2,[[4,5],[2,3]]]],
[[[4,[2,2]],[5,[4,7]]],[[[0,3],2],[5,[2,6]]]],
[[0,[[6,5],5]],[[7,[7,2]],3]],
[[[4,[9,4]],[1,9]],[7,[[7,1],[6,1]]]],
[1,[0,2]],
[[[[5,1],[2,1]],[[7,8],6]],[[3,[4,9]],2]],
[[9,[[4,0],[8,8]]],[[[6,6],[2,8]],[1,[1,5]]]],
[[[1,2],[7,0]],[7,[[3,0],5]]],
[[[6,[0,8]],3],[[3,7],1]],
[[[[6,1],[1,0]],9],[[4,8],[3,[0,8]]]],
[[6,[3,[5,8]]],9],
[[[[5,0],[7,7]],[[3,1],[4,8]]],5],
[[[3,7],[9,0]],[[[0,2],7],0]],
[8,9],
[[8,[[0,8],4]],[1,[[4,6],2]]],
[[[5,5],3],[[6,6],[0,[6,3]]]],
[[[7,[3,7]],[[6,1],[9,4]]],[[[8,9],1],[[8,7],6]]],
[[6,[[0,9],[2,3]]],[[1,[5,3]],[8,4]]],
[[[3,5],8],[[[2,4],[7,5]],5]],
[[0,[[7,0],[9,4]]],[[[0,0],[6,7]],[6,5]]],
[[[[1,9],[6,4]],0],[6,[3,[4,8]]]],
[[[[1,6],[0,4]],8],[[8,8],6]],
[[[[7,4],[9,6]],7],[[1,6],[1,0]]],
[1,[[[6,8],5],5]],
[8,4],
[9,[[9,[3,9]],0]],
[5,[[[4,9],7],[[1,0],0]]],
[[[6,1],[0,[2,3]]],[[[7,8],[5,9]],9]],
[3,[[3,[3,4]],[6,[7,8]]]],
[[[7,[7,1]],[4,[2,0]]],[6,[7,3]]],
[[6,9],[[3,[4,7]],3]],
[1,[[9,[5,1]],[7,[7,5]]]],
[[3,2],[[9,[6,8]],[[1,0],2]]],
[[[[3,2],8],[7,6]],9],
[[3,[[9,5],6]],[5,9]],
[[[3,[6,3]],[[7,0],[5,7]]],[[3,3],[[4,9],[4,8]]]],
[[[0,[4,3]],2],[3,[0,[1,3]]]],
[[[7,[3,4]],[7,[3,1]]],[[0,[4,7]],6]],
[[[1,[7,4]],[[8,7],3]],4],
[[[5,5],[[0,3],2]],[1,[[9,4],6]]],
[[[[6,0],[8,8]],[6,[6,0]]],[5,6]],
[[[1,[5,4]],[[5,9],[1,7]]],[[5,[4,7]],[4,[4,4]]]],
[[0,[[2,6],0]],[[6,[4,3]],5]],
[[[1,[5,3]],[9,[1,2]]],[[[4,8],[5,6]],0]],
[[0,7],[1,[7,7]]],
[4,[[7,[7,2]],[[9,1],7]]],
[2,[[1,6],[6,9]]],
[[[4,[4,5]],9],[[[1,7],6],[3,[7,3]]]],
[[6,[[1,1],[7,8]]],[[[5,2],[8,1]],5]],
[[[5,5],[[4,1],[1,2]]],[[3,8],[3,4]]],
[[[[1,9],[0,3]],[4,[0,9]]],4],
[[[4,9],0],[[9,0],[8,[7,5]]]],
[[6,[5,3]],[[[6,6],4],[[6,8],4]]],
[[[[1,1],2],1],[1,[[6,4],2]]],
[[[[6,3],[1,5]],[6,[7,7]]],[6,6]],
[[[[3,0],[5,6]],1],[[[9,3],[1,7]],[[3,4],[2,7]]]]].
-endif.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment