Advent of Code 2021 - Day 18

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

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

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

3 Likes

This was my least favorite challenge so far :man_shrugging: :

main(File) ->
    {ok, RawData} = file:read_file(File),
    Data = [ begin
                 {ok, Tokens, _} = erl_scan:string(binary_to_list(<<X/binary, ".">>)),
                 {ok, Term} = erl_parse:parse_term(Tokens),
                 Term
             end
             || X <- binary:split(RawData, <<"\n">>, [global, trim]) ],
    io:format("part 1: ~p~n", [solve1(Data)]),
    io:format("part 2: ~p~n", [solve2(Data)]).

solve1(Data) ->
    magnitude(lists:foldl(fun (A, B) -> reduce([B, A]) end, hd(Data), tl(Data))).

solve2(Data) ->
    lists:max([ magnitude(reduce([A, B])) || A <- Data,
                                             B <- Data -- [A] ]).

reduce(N) ->
    case maybe_explode(N) of
        {_, _, NewN}         -> reduce(NewN);
        NewN when NewN =/= N -> reduce(NewN);
        N ->
            case maybe_split(N) of
                N    -> N;
                NewN -> reduce(NewN)
            end
    end.

maybe_split(A) when is_integer(A), A > 9 -> [trunc(A / 2), ceil(A / 2)];
maybe_split(A) when is_integer(A)        -> A;
maybe_split([A, B]) ->
    case maybe_split(A) of
        A    -> [A, maybe_split(B)];
        NewA -> [NewA, B]
    end.

maybe_explode([A, B]) ->
    maybe_explode([A, B], 0).

maybe_explode([A, B], N) when is_list(A); is_list(B) ->
    case maybe_explode(A, N + 1) of
        {true, [Left, Right]}      -> {carry_left, Left, [0, add_left(Right, B)]};
        {carry_left,  Left,  NewA} -> {carry_left, Left, [NewA, B]};
        {carry_right, Right, NewA} -> [NewA, add_left(Right, B)];
        NewA when NewA =/= A       -> [NewA, B];
        A ->
            case maybe_explode(B, N + 1) of
                {true, [Left, Right]}      -> {carry_right, Right, [add_right(Left, A), 0]};
                {carry_right, Right, NewB} -> {carry_right, Right, [A, NewB]};
                {carry_left,  Left,  NewB} -> [add_right(Left, A), NewB];
                NewB                       -> [A, NewB]
            end
    end;
maybe_explode([A, B], N) when N >= 4, is_integer(A), is_integer(B) ->
    {true, [A, B]};
maybe_explode(A, _N) ->
    A.

add_left(N, A) when is_integer(A) -> N + A;
add_left(N, [A, B])               -> [add_left(N, A), B].

add_right(N, A) when is_integer(A) -> N + A;
add_right(N, [A, B])               -> [A, add_right(N, B)].

magnitude([A, B]) -> 3 * magnitude(A) + 2 * magnitude(B);
magnitude(A)      -> A.

perm(List) ->
    [ magnitude(reduce([A, B])) || A <- List, B <- List -- [A] ].

Is there an easy way to do:

{ok, Tokens, _} = erl_scan:string(binary_to_list(<<X/binary, ".">>)),
{ok, Term} = erl_parse:parse_term(Tokens),
Term

in Erlang?

3 Likes

As far as I know, no.

3 Likes

My Elixir solution is similar to @danilagamma’s solution in that operates on the terms exactly as they are read from input file. That complicates the explode operation.

Browsing the solution thread on reddit, I saw that some of the solutions operates on a string or flat list, which simplifies the explode operation. Here is my solution in Erlang that uses that approach:

The explode and split operations becomes easier, while the magnitude and add operations become slightly more complicated. I also needed to implement a flatten operation, and an unflatten operation for testing.

3 Likes