101 lines
2.6 KiB
Erlang
101 lines
2.6 KiB
Erlang
%% to compile: erlc day3A.erl
|
|
%% to run: erl -noshell -s day5 solve
|
|
%%
|
|
-module(day12).
|
|
|
|
-export ([solve/0, solve/1, solve/2]).
|
|
-export ([read_input/0]).
|
|
|
|
solve() ->
|
|
solve(['1']),
|
|
solve(['2']),
|
|
init:stop().
|
|
|
|
solve(A) ->
|
|
solve(A, read_input()).
|
|
|
|
solve(['1'], D) ->
|
|
io:format("The solution to ~p puzzle1 is: ~p~n", [?MODULE, solve(1, D)]);
|
|
solve(1, D) ->
|
|
solution1(D);
|
|
solve(['2'], D) ->
|
|
io:format("The solution to ~p puzzle2 is: ~p~n", [?MODULE, solve(2, D)]);
|
|
solve(2, D) ->
|
|
solution2(D).
|
|
|
|
read_input() ->
|
|
{ok, IO} = file:open("input.txt", 'read'),
|
|
Data = read_input(IO),
|
|
file:close(IO),
|
|
Data.
|
|
|
|
read_input(IO) ->
|
|
read_input(IO, []).
|
|
|
|
read_input(IO, Input) ->
|
|
case read_line(IO) of
|
|
'eof' -> Input;
|
|
Line -> read_input(IO, Input ++ [Line])
|
|
end.
|
|
|
|
read_line(IO) ->
|
|
case file:read_line(IO) of
|
|
'eof' -> 'eof';
|
|
{ok, Line} -> parse_line(Line)
|
|
end.
|
|
|
|
parse_line(Line) ->
|
|
[Cave1, Cave2] = string:tokens(Line, "-\n"),
|
|
{Cave1, Cave2}.
|
|
|
|
solution1(Caves) ->
|
|
CaveMap = insert(Caves),
|
|
count_paths("start", #{}, 'some', CaveMap).
|
|
|
|
solution2(Caves) ->
|
|
CaveMap = insert(Caves),
|
|
count_paths("start", #{}, 'none', CaveMap).
|
|
|
|
|
|
insert(Caves) -> insert(Caves, maps:new()).
|
|
|
|
insert([], CaveMap) -> CaveMap;
|
|
insert([{Cave1, Cave2}|Rest], CaveMap) ->
|
|
NewMap =
|
|
case maps:is_key(Cave1, CaveMap) of
|
|
'false' -> maps:put(Cave1, [Cave2], CaveMap);
|
|
'true' -> maps:put(Cave1, [Cave2|maps:get(Cave1, CaveMap)], CaveMap)
|
|
end,
|
|
NewMap2 =
|
|
case maps:is_key(Cave2, NewMap) of
|
|
'false' -> maps:put(Cave2, [Cave1], NewMap);
|
|
'true' -> maps:put(Cave2, [Cave1|maps:get(Cave2, CaveMap)], NewMap)
|
|
end,
|
|
insert(Rest, NewMap2).
|
|
|
|
visit_vertex(Name, Visited, VisitedTwice, Graph) ->
|
|
NewVisited =
|
|
case hd(Name) >= $a of
|
|
true -> Visited#{Name => true};
|
|
false -> Visited
|
|
end,
|
|
#{Name := Neighbours} = Graph,
|
|
lists:sum([count_paths(N, NewVisited, VisitedTwice, Graph) || N <- Neighbours]).
|
|
|
|
count_paths("end", _, _, _) ->
|
|
% We have found an entire path through the graph.
|
|
1;
|
|
count_paths("start", Visited, _, _) when map_size(Visited) > 0 ->
|
|
% We cannot visit the start cave more than once.
|
|
0;
|
|
count_paths(Name, Visited, VisitedTwice, Graph) when hd(Name) >= $a andalso is_map_key(Name, Visited) ->
|
|
% We can visit only one small cave twice.
|
|
case VisitedTwice of
|
|
'none' -> visit_vertex(Name, Visited, Name, Graph);
|
|
_ -> 0
|
|
end;
|
|
count_paths(Name, Visited, VisitedTwice, Graph) ->
|
|
% Small caves can only be visited once, but large caves may be visited any
|
|
% number of times.
|
|
visit_vertex(Name, Visited, VisitedTwice, Graph).
|