Solution for Advent of Code 2021 - Day 18

aoc2021_day18.erl

-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.