This topic is about Day 12 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
The most under-appreciated module in Erlang/OTP is probably sofs. The sofs module can be intimidating at first because of the huge list of functions that meet you when you look at the documentation. The best way to get started is probably to look at how sofs can solve a real-world problem, and then read the documentation for the sofs functions used in the example.
Here is an example how sofs can be used as part of the solution for today’s puzzle:
5 Likes
That’s pretty neat, although sofs operations essentially boil down to something like:
lists:foldl(fun ({F, T}, A) ->
A0 = maps:update_with(F, fun(V) -> [T|V] end, [T], A),
maps:update_with(T, fun(V) -> [F|V] end, [F], A0)
end,
#{},
Data).
I can see how useful that module can be.
My solution is less clever but does the job 
:
main(File) ->
{ok, RawData} = file:read_file(File),
Data = [ binary:split(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) ->
lists:foldl(fun ([F, T], A) ->
A0 = maps:update_with(F, fun(V) -> [T|V] end, [T], A),
maps:update_with(T, fun(V) -> [F|V] end, [F], A0)
end,
#{},
Data).
solve1(Graph) ->
length(paths(Graph, false)).
solve2(Graph) ->
length(paths(Graph, true)).
paths(Graph, HaveTime) ->
paths(maps:get(<<"start">>, Graph), Graph, HaveTime, #{}, [<<"start">>]).
paths([], _Graph, _HaveTime, _Visited, _PathAcc) ->
[];
paths([<<"start">>|Nodes], Graph, HaveTime, Visited, PathAcc) ->
paths(Nodes, Graph, HaveTime, Visited, PathAcc);
paths([<<"end">> = Node|Nodes], Graph, HaveTime, Visited, PathAcc) ->
[lists:reverse([Node|PathAcc])|paths(Nodes, Graph, HaveTime, Visited, PathAcc)];
paths([Node|Nodes], Graph, HaveTime, Visited, PathAcc)
when is_map_key(Node, Visited), not HaveTime ->
paths(Nodes, Graph, HaveTime, Visited, PathAcc);
paths([Node|Nodes], Graph, HaveTime, Visited, PathAcc) ->
{NewHaveTime, NewVisited}
= case string:titlecase(Node) of
Node -> {HaveTime, Visited};
_Other -> {HaveTime and not maps:is_key(Node, Visited), Visited#{Node => true}}
end,
paths(maps:get(Node, Graph), Graph, NewHaveTime, NewVisited, [Node|PathAcc])
++ paths(Nodes, Graph, HaveTime, Visited, PathAcc).
As a side note - it might be very useful to have maps:group_by (or lists:group_by) like Enum.group_by from Elixir in Erlang, it’s been too many times I’ve implemented same pattern of aggregation by key.
3 Likes
I haven’t translated mine to Erlang, but here’s the awk horror show:
As the comment mentions, since I can’t easily have immutable data structures (aside from strings) in Awk, and that copying arrays (and just using arrays) is a mess, I end up using a string and regexes to do my whole search.
On my small archlinux VPS with gawk, it takes ~10s to run both parts doing this, which is clearly less effective than having array lookups and immutable data for this.
5 Likes
Decided to translate the Erlang version since I had the spare time:
It does run sub-second for both parts!
4 Likes
Not as short as other solutions since I not only count paths but generate them and went a bit for readability that the usual quick hack.
p12() ->
p12_read("priv/p12.txt").
p12_read(Fn) ->
{ok, Bin} = file:read_file(Fn),
Tab = [ [ measure_size(E) || E <- string:split(L, "-") ]
|| L <- string:split(string:trim(Bin), "\n", all) ],
G = incidence(Tab),
{length(flatten(paths(G, {small, start}, [], fun visit_ok/2))),
length(flatten(paths(G, {small, start}, [], fun visit2/2)))}.
flatten([]) ->
[];
flatten([N|_]=L) when is_tuple(N) ->
[L];
flatten([N|R]) when is_list(N) ->
flatten(N) ++ flatten(R).
paths(_G, {small, 'end'}=E, Path, _V) ->
[E|Path];
paths(G, Node, Path, V) ->
P = [Node|Path],
[ paths(G,N,P,V) || N <- orddict:fetch(Node, G), V(N, P) ].
visit_ok({small, _}=N, P) ->
not lists:member(N, P);
visit_ok({large, _}, _) ->
true.
visit2({small, start}, _P) ->
false;
visit2({small, _}=N, P) ->
unique([ E || {small,E} <- P ]) orelse (not lists:member(N, P));
visit2({large, _}, _) ->
true.
unique(L) ->
length(lists:usort(L)) =:= length(L).
incidence(L) ->
lists:foldl(fun([From, To],A) ->
orddict:append(From, To, orddict:append(To, From,A))
end, orddict:new(), L).
measure_size(Bin) ->
case string:lowercase(Bin) of
L when L =:= Bin ->
{small, binary_to_atom(Bin)};
L ->
{large, binary_to_atom(L)}
end.
4 Likes