This topic is about Day 9 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
This topic is about Day 9 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
Today’s puzzle seems to be waaay easier than yesterday’s :
main(File) ->
{ok, RawData} = file:read_file(File),
Data = [ [ N - $0 || N <- 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) ->
maps:fold(fun (XY, V, Acc) ->
case is_low_point(XY, V, Map) of
true -> 1 + V + Acc;
false -> Acc
end
end, 0, Map).
is_low_point(XY, Value, Map) ->
Adjacent = [ maps:get(A, Map) || A <- adjacent_coords(XY),
maps:is_key(A, Map) ],
lists:all(fun (AdjValue) -> AdjValue > Value end, Adjacent).
adjacent_coords({X, Y}) ->
[{X - 1, Y},
{X + 1, Y},
{X, Y - 1},
{X, Y + 1}].
solve2(Map) ->
Basins = maps:fold(fun (XY, V, Acc) ->
case is_low_point(XY, V, Map) of
true -> [basin(XY, V, #{}, Map)|Acc];
false -> Acc
end
end, [], Map),
lists:foldl(fun erlang:'*'/2, 1,
[ maps:size(X) || X <- lists:sublist(lists:reverse(lists:sort(Basins)), 3) ]).
basin(XY0, V0, Acc0, Map) ->
ToFollow = [ {A, N} || A <- adjacent_coords(XY0),
maps:is_key(A, Map),
not maps:is_key(A, Acc0),
N <- [maps:get(A, Map)],
N > V0,
N =/= 9 ],
lists:foldl(fun ({XY, V}, Acc) -> basin(XY, V, Acc, Map) end, Acc0#{XY0 => V0}, ToFollow).
Man I hate it when puzzle 2 requires a completely different data structure than the one picked for puzzle 1
Interesting, I used the same datastructure for both parts.
Yes, it was easier, @danilagamma. How do I know that? I was able to do it by myself:
main() ->
main("input_from_description.txt"),
main("input.txt").
main(File) ->
Data = parse_file(file:read_file(File)),
io:format("Part 1 (9, 514) for ~p: ~p~n", [File, part1(Data)]),
io:format("Part 2 (1134, 1103130) for ~p: ~p~n", [File, part2(Data)]).
part2(Data) ->
Basins = [lists:sort(X) || X <- find_three_largest_basins(Data)],
[B1, B2, B3 | _] =
lists:sort(fun(X, Y) -> length(X) > length(Y) end, remove_dups(Basins)),
LBasins = [length(X) || X <- [B1, B2, B3]],
lists:foldl(fun(X, Y) -> X * Y end, 1, LBasins).
remove_dups([]) ->
[];
remove_dups([H | T]) ->
[H | [X || X <- remove_dups(T), X /= H]].
find_three_largest_basins(Data) ->
find_three_largest_basins(create_map(Data), length(Data), length(hd(Data)), []).
find_three_largest_basins(Map, Lines, Columns, _ThreeLargest) ->
[basin_size({Line, Column}, Map, [])
|| Line <- lists:seq(1, Lines), Column <- lists:seq(1, Columns)].
basin_size({Line, Column}, Map, Basin) ->
Value = maps:get({Line, Column}, Map, $9),
case (Value =/= $9) and not lists:member({Line, Column}, Basin) of
true ->
basin_size_rec({Line, Column}, Map, [{Line, Column} | Basin]);
false ->
Basin
end.
basin_size_rec({Line, Column}, Map, Basin) ->
B2 = basin_size({Line - 1, Column}, Map, Basin),
B3 = basin_size({Line + 1, Column}, Map, B2),
B4 = basin_size({Line, Column - 1}, Map, B3),
B5 = basin_size({Line, Column + 1}, Map, B4),
B5.
part1(Data) ->
LowPoints = find_low_points(Data),
lists:sum([X - 48 + 1 || X <- LowPoints]).
find_low_points(Data) ->
find_low_points(create_map(Data), length(Data), length(hd(Data))).
find_low_points(Map, Lines, Columns) ->
[maps:get({Line, Column}, Map)
|| Line <- lists:seq(1, Lines),
Column <- lists:seq(1, Columns),
is_low_point(Map, Line, Column)].
is_low_point(Map, Line, Column) ->
Value = maps:get({Line, Column}, Map),
(Value < maps:get({Line - 1, Column}, Map, 100))
and (Value < maps:get({Line + 1, Column}, Map, 100))
and (Value < maps:get({Line, Column - 1}, Map, 100))
and (Value < maps:get({Line, Column + 1}, Map, 100)).
create_map(Data) ->
create_map(Data, #{}, 1).
create_map([], Map, _) ->
Map;
create_map([Head | Tail], Map, X) ->
create_map(Tail, create_map_from_line(Head, Map, X), X + 1).
create_map_from_line(Line, Map, X) ->
{_, NewMap} =
lists:foldl(fun(Height, {Y, M}) -> {Y + 1, M#{{X, Y} => Height}} end, {1, Map}, Line),
NewMap.
parse_file({ok, RawData}) ->
[unicode:characters_to_list(Line) || Line <- re:split(RawData, "[\n]+"), Line =/= <<>>];
parse_file({error, _}) ->
"No file with that name!".
For puzzle 1 today I thought I be smart and use something other than the obvious map from coordinates to depths: built a lists sliding window function and applied it to both dimensions giving me a nice 9x9 2d sliding window.
Then puzzle 2 was impossible to save with this method and required the aforementioned maps
So for puzzle 2 I started over and basically have two different implementations for puzzle 1 without wanting to
p9_1() ->
Tab = p9_read("priv/p09.txt"),
Blocks = lists:flatten([ lists:zip3(A,B,C)
|| [A,B,C] <- sliding(3, [ sliding(3, L)
|| L <- Tab ])]),
Low = [ C || {[_,A1,_],[A2,C,A3],[_,A4,_]} <- Blocks,
C < lists:min([A1,A2,A3,A4]) ],
lists:sum(lists:map(fun(X) -> X+1 end, Low)).
p9_2() ->
T1 = p9_read("priv/p09.txt"),
M = lists:foldl(fun({E,X,Y}, M) -> M#{{X,Y} => E} end, #{},
lists:flatten(add_coords(T1))),
Low = [ R || {{X,Y}, E}=R <- maps:to_list(M),
E < 10 andalso E < lists:min(maps:values(surround(X,Y,M))) ],
Basins = [ maps:size(basin(M, #{K => E})) || {K, E} <- Low ],
[A,B,C|_] = lists:reverse(lists:sort(Basins)),
A*B*C.
basin(M, B) ->
Exp = maps:fold(fun({X,Y},_,B1) ->
M1 = maps:filter(fun(_,E) -> E < 9 end,
surround(X,Y,M)),
maps:merge(B1,M1)
end, B, B),
case Exp of
B -> B;
_ -> basin(M, Exp)
end.
surround(X,Y,M) ->
maps:with([{X-1,Y},{X+1,Y},{X,Y-1},{X,Y+1}], M).
mget(Key, M) ->
{Key, maps:get(Key, M)}.
add_coords(LoL) ->
H = length(LoL),
W = length(hd(LoL)),
[ [ {E, X, Y} || {E, X} <- lists:zip(L, lists:seq(1,W)) ]
|| {L, Y} <- lists:zip(LoL, lists:seq(1,H)) ].
p9_read(Fn) ->
{ok, Bin} = file:read_file(Fn),
border(10, [ [ C - $0 || <<C:8>> <= L ]
|| L <- string:split(string:trim(Bin), "\n", all) ]).
border(V, LoL) ->
Len = length(hd(LoL)) + 2,
Tb = lists:duplicate(Len, V),
[Tb] ++ [ [V] ++ L ++ [V] || L <- LoL ] ++ [Tb].
sliding(N, L) when length(L) < N->
[];
sliding(N, [_|R]=List) ->
[element(1,lists:split(N, List))|sliding(N, R)].