2021/day12/day12.erl

   1 %% to compile: erlc day3A.erl
   2 %% to run: erl -noshell -s day5 solve
   3 %%
   4 -module(day12).
   5
   6 -export ([solve/0, solve/1, solve/2]).
   7 -export ([read_input/0]).
   8
   9 solve() ->
  10     solve(['1']),
  11     solve(['2']),
  12     init:stop().
  13
  14 solve(A) ->
  15     solve(A, read_input()).
  16
  17 solve(['1'], D) ->
  18     io:format("The solution to ~p puzzle1 is: ~p~n", [?MODULE, solve(1, D)]);
  19 solve(1, D) ->
  20     solution1(D);
  21 solve(['2'], D) ->
  22     io:format("The solution to ~p puzzle2 is: ~p~n", [?MODULE, solve(2, D)]);
  23 solve(2, D) ->
  24     solution2(D).
  25
  26 read_input() ->
  27     {ok, IO} = file:open("input.txt", 'read'),
  28     Data = read_input(IO),
  29     file:close(IO),
  30     Data.
  31
  32 read_input(IO) ->
  33         read_input(IO, []).
  34
  35 read_input(IO, Input) ->
  36     case read_line(IO) of
  37         'eof' -> Input;
  38         Line -> read_input(IO, Input ++ [Line])
  39     end.
  40
  41 read_line(IO) ->
  42         case file:read_line(IO) of
  43                 'eof' -> 'eof';
  44                 {ok, Line} -> parse_line(Line)
  45         end.
  46
  47 parse_line(Line) ->
  48     [Cave1, Cave2] = string:tokens(Line, "-\n"),
  49     {Cave1, Cave2}.
  50
  51 solution1(Caves) ->
  52    CaveMap = insert(Caves),
  53    count_paths("start", #{}, 'some', CaveMap).
  54
  55 solution2(Caves) ->
  56    CaveMap = insert(Caves),
  57    count_paths("start", #{}, 'none', CaveMap).
  58
  59
  60 insert(Caves) -> insert(Caves, maps:new()).
  61
  62 insert([], CaveMap) -> CaveMap;
  63 insert([{Cave1, Cave2}|Rest], CaveMap) ->
  64         NewMap =
  65         case maps:is_key(Cave1, CaveMap) of
  66                 'false' -> maps:put(Cave1, [Cave2], CaveMap);
  67                 'true' -> maps:put(Cave1, [Cave2|maps:get(Cave1, CaveMap)], CaveMap)
  68         end,
  69         NewMap2 =
  70         case maps:is_key(Cave2, NewMap) of
  71                 'false' -> maps:put(Cave2, [Cave1], NewMap);
  72                 'true' -> maps:put(Cave2, [Cave1|maps:get(Cave2, CaveMap)], NewMap)
  73         end,
  74         insert(Rest, NewMap2).
  75
  76 visit_vertex(Name, Visited, VisitedTwice, Graph) ->
  77     NewVisited =
  78         case hd(Name) >= $a of
  79             true -> Visited#{Name => true};
  80             false -> Visited
  81         end,
  82     #{Name := Neighbours} = Graph,
  83     lists:sum([count_paths(N, NewVisited, VisitedTwice, Graph) || N <- Neighbours]).
  84
  85 count_paths("end", _, _, _) ->
  86     % We have found an entire path through the graph.
  87     1;
  88 count_paths("start", Visited, _, _) when map_size(Visited) > 0 ->
  89     % We cannot visit the start cave more than once.
  90     0;
  91 count_paths(Name, Visited, VisitedTwice, Graph) when hd(Name) >= $a andalso is_map_key(Name, Visited) ->
  92     % We can visit only one small cave twice.
  93     case VisitedTwice of
  94         'none' -> visit_vertex(Name, Visited, Name, Graph);
  95          _ -> 0
  96     end;
  97 count_paths(Name, Visited, VisitedTwice, Graph) ->
  98     % Small caves can only be visited once, but large caves may be visited any
  99     % number of times.
 100     visit_vertex(Name, Visited, VisitedTwice, Graph).