Solution for Advent of Code 2021 - Day 12

aoc2021_day12.erl

-module(aoc2021_day12).
-export([solve_part1/1,solve_part2/1]).

-include_lib("eunit/include/eunit.hrl").

solve_part1(Input) ->
    solve(Input, 1).

solve_part2(Input) ->
    solve(Input, 2).

solve(Input0, MaxVisits) ->
    Input = [begin
                 [From, To] = string:split(Line, "-"),
                 {make_cave(From), make_cave(To)}
             end || Line <- Input0],

    S0 = sofs:relation(Input),
    S1 = sofs:converse(S0),
    S2 = sofs:union(S0, S1),
    S3 = sofs:relation_to_family(S2),
    S4 = sofs:to_external(S3),

    %% S4 is now: [{From, [To1, ..., ToN]}, ...]

    Map = maps:from_list(S4),

    Seen = maps:from_list([{Cave, 0} || {Cave, _} <- S4]),

    count_paths({small, start}, Map, Seen, MaxVisits).

count_paths({small, 'end'}, _, _, _) -> 1;
count_paths(From, Map, Seen0, MaxVisits) ->
    Seen = Seen0#{From := map_get(From, Seen0) + 1},
    F = fun(To, Acc) ->
                case To of
                    {small, start} ->
                        Acc;
                    {small, _} ->
                        NumVisits = map_get(To, Seen),
                        if
                            NumVisits =:= 0 ->
                                Acc + count_paths(To, Map, Seen, MaxVisits);
                            NumVisits =:= 1, MaxVisits =:= 2 ->
                                Acc + count_paths(To, Map, Seen, 1);
                            true ->
                                Acc
                        end;
                    {big, _} ->
                        Acc + count_paths(To, Map, Seen, MaxVisits)
                end
        end,
    lists:foldl(F, 0, map_get(From, Map)).

make_cave(Name) ->
    case string:uppercase(Name) of
        Name -> {big, list_to_atom(Name)};
        _ -> {small, list_to_atom(Name)}
    end.

-ifdef(EUNIT).

part1_test() ->
    ?assertEqual(3708, solve_part1(input())).

part2_test() ->
    ?assertEqual(93858, solve_part2(input())).

input() ->
    ["lg-GW",
    "pt-start",
    "pt-uq",
    "nx-lg",
    "ve-GW",
    "start-nx",
    "GW-start",
    "GW-nx",
    "pt-SM",
    "sx-GW",
    "lg-end",
    "nx-SM",
    "lg-SM",
    "pt-nx",
    "end-ve",
    "ve-SM",
    "TG-uq",
    "end-SM",
    "SM-uq"].

-endif.