Advent of Code Day 7 - Discussions

Questions & Discussions Coding Challenges
,
1

This topic is about Day 7 of the Advent of Code 2022 .

December 7 comes in less than 3 hours! Good luck solving today’s challenge.

Link to our leaderboard:

https://adventofcode.com/2022/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

Good luck!

2 Likes
2

Got a bit stuck today, initially I just build a list of full paths of files with their sizes and iterated over that, but made a mistake when I calculated directory sizes from that list, after quite a while I just changed whole thing to calculating directory sizes as I’m reading the input file and that worked:

main(File) ->
    {ok, RawData} = file:read_file(File),
    Data = [ binary_to_list(X) || X <- binary:split(RawData, <<"\n">>, [global, trim]) ],
    io:format("part 1: ~p~n", [solve1(Data)]),
    io:format("part 2: ~p~n", [solve2(Data)]).

solve1(Data) ->
    Dirs = dir_sizes(Data),
    lists:sum([ S || S <- maps:values(Dirs), S =< 100000 ]).

solve2(Data) ->
    Dirs = dir_sizes(Data),
    lists:min([ S || S <- maps:values(Dirs), S >= maps:get(["/"], Dirs) - 40000000 ]).

dir_sizes(Data) ->
    {_, Dirs} = lists:foldl(fun fold_files/2, {[], #{}}, Data),
    Dirs.

fold_files("$ cd ..",        {Current, Dirs}) -> {lists:droplast(Current), Dirs};
fold_files("$ cd " ++ Where, {Current, Dirs}) -> {Current ++ [Where], Dirs};
fold_files("$ ls",           State)           -> State;
fold_files("dir " ++ _,      State)           -> State;
fold_files(File,             {Current, Dirs}) ->
    [RawSize, _] = string:tokens(File, " "),
    Size         = list_to_integer(RawSize),
    {Current, lists:foldl(fun (P, Acc) -> maps:update_with(P, fun (V) -> V + Size end, Size, Acc) end,
                          Dirs,
                          path_to_subdirs(Current))}.

path_to_subdirs([])   -> [];
path_to_subdirs(Path) -> [Path|path_to_subdirs(lists:droplast(Path))].
2 Likes
3

I might be using this opportunity to apply GenServer in Erlang. I have done similar things with in the past with Elixir, so might be fun to do it in the OG lang.

1 Like
4

No gen_server, not there yet. I did it though, in sequential Erlang last night. The gen_server version could come on weekend.

-module(day_7).

-export([solve/0]).

input() ->
  {ok, Listing} = file:read_file("data/7.txt"),
  Listing.

solve() ->
  Directory = parse(input()),
  {solve1(Directory), solve2(Directory)}.

solve1(Directory) ->
  Sizes = maps:values(Directory),
  AtMost100_000 = lists:filter(fun(X) -> X =< 100_000 end, Sizes),
  lists:sum(AtMost100_000).

solve2(Directory) ->
  Sizes = maps:values(Directory),
  Available = 70_000_000 - lists:max(Sizes),
  Needed = 30_000_000 - Available,
  lists:min(
    lists:filter(fun(Size) -> Size - Needed > 0 end, Sizes)).

parse(Listing) ->
  Commands =
    [Command
     || Command
          <- [parse_command(List) || List <- binary:split(Listing, <<"\n">>, [global, trim])],
        Command /= no_op],
  Files = get_files(Commands),
  build_dir_map(Files).

get_files(Commands) ->
  Init = {[], ["/"]},
  Reducer =
    fun(Cmd, {Files, [_ | Rest] = Path}) ->
       case Cmd of
         root -> {Files, ["/"]};
         up -> {Files, Rest};
         {cd, Dir} -> {Files, [[Dir | Path] | Path]};
         {Size, FileName} -> {[{FileName, build_dir_map(Path, Size)} | Files], Path}
       end
    end,
  {Files, _} = lists:foldl(Reducer, Init, Commands),
  lists:uniq(Files).

build_dir_map(Directories, Size) ->
  lists:foldl(fun(Directory, Acc) -> maps:put(Directory, Size, Acc) end,
              maps:new(),
              Directories).

build_dir_map(Files) ->
  lists:foldl(fun({_, Dirs}, Acc) ->
                 maps:merge_with(fun(_, V1, V2) -> V1 + V2 end, Dirs, Acc)
              end,
              maps:new(),
              Files).

parse_command(List) ->
  case List of
    <<"$ cd /", _/binary>> ->
      root;
    <<"$ cd ..", _/binary>> ->
      up;
    <<"$ cd ", Directory/binary>> ->
      {cd, binary_to_list(Directory)};
    <<"dir ", _/binary>> ->
      no_op;
    <<"$ ls">> ->
      no_op;
    File ->
      [Size, Name] = binary:split(File, <<" ">>),
      {binary_to_integer(Size), binary_to_list(Name)}
  end.
2 Likes