Advent of Code 2022 - Day 12 Discussions

Questions & Discussions Coding Challenges
,
1

This topic is about Day 12 of the Advent of Code 2022 .

Link to our leaderboard:

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

The entry code is:
370884-a6a71927

Good luck!

1 Like
2

Very similar to Day 15 of 2021, I took search function I had there and modified it a bit, turned out quite well:

main(File) ->
    {ok, RawData} = file:read_file(File),
    Data = [ [ X || X <- binary_to_list(Line) ]
             || Line <- binary:split(RawData, <<"\n">>, [global, trim]) ],
    Map = load(Data),
    io:format("part 1: ~p~n", [solve1(Map)]),
    io:format("part 2: ~p~n", [solve2(Map)]).

load(Data) ->
    maps:from_list([ {{X, Y}, N} || {Y, Line} <- enum(Data),
                                    {X, N}    <- enum(Line) ]).

enum(List) ->
    lists:zip(lists:seq(1, length(List)), List).

solve1(Map) ->
    search([$S], Map).

solve2(Map) ->
    search([$S, $a], Map).

search(StartingSquares, Map) ->
    Start    = [ {0, S, $a} || {S, X} <- maps:to_list(Map), lists:member(X, StartingSquares) ],
    [End]    = [ E || {E, $E} <- maps:to_list(Map) ],
    MaxCoord = lists:max(maps:keys(Map)),
    search(Start, End, MaxCoord, #{}, inf, Map).

search([], _, _, _Seen, Best, _) ->
    Best;
search([{Len, End, _}|Rest], End, MaxCoord, Seen, Best, Map) when Len < Best ->
    NewBest = case Len < Best of
                  true  -> Len;
                  false -> Best
              end,
    search(Rest, End, MaxCoord, Seen, NewBest, Map);
search([{Len, Coord, Value}|Rest], End, MaxCoord, Seen, Best, Map) ->
    case Len >= Best of
        true  -> search(Rest, End, MaxCoord, Seen, Best, Map);
        false ->
            NewSeen  = Seen#{Coord => ok},
            ToFollow = lists:sort([ {Len + 1, C, NewValue} || C <- adjacent_coords(Coord, MaxCoord, NewSeen),
                                    (Value + 1) >= (NewValue = to_val(maps:get(C, Map))) ]),
            search(ordsets:union(ToFollow, Rest), End, MaxCoord, NewSeen, Best, Map)
    end.

to_val($E) -> $z;
to_val($S) -> $a;
to_val(X)  -> X.

adjacent_coords({X, Y}, {EndX, EndY}, Seen) ->
    [ {A, B} || {A, B} <- [{X + 1, Y},
                           {X, Y + 1},
                           {X - 1, Y},
                           {X, Y - 1}],
      A =< EndX, B =< EndY,
      A >= 1,    B >= 1,
      not maps:is_key({A, B}, Seen) ].
2 Likes