This was a big jump up from yesterday's problem. The bulk of the work was in the parsing of the input. I pattern matched on each line, keeping track of the current directory and the filesystem scanned so far. I skipped all lines with the ls command because they did not add any information. I also kept track of the total size of each directory. Every time I came across a file, I added its size to the total size of every parent folder. The resulting data structure from the example input looks like this:
After scanning the entire filesystem, each part just required traversing the tree again to determine the answer. Turns out that I didn't really need to keep track of the files at all. Since mapping over the keys of the folder would include the total size and files, I had to remove them to recursively check the other folders.
defmoduleDay07douseAOC@node%{files:%{},total_size:0}defparse_filesystem()doinput(7)|>String.trim|>String.split("\n")|>Enum.reduce({[],%{"/"=>@node}},&process_line/2)|>elem(1)enddefprocess_line("$ ls",acc),do:accdefprocess_line("$ cd ..",{[_|ancestors],fs}),do:{ancestors,fs}defprocess_line("$ cd "<>dir,{current_dir,fs}),do:{[dir|current_dir],fs}defprocess_line("dir "<>dir,{current_dir,fs}),do:{current_dir,put_in(fs,Enum.reverse([dir|current_dir]),@node)}defprocess_line(file,{current_dir,fs})do[size,filename]=String.split(file)new_fs=update_total_size(fs,current_dir,String.to_integer(size))|>put_in(Enum.reverse([filename,:files|current_dir]),String.to_integer(size)){current_dir,new_fs}enddefupdate_total_size(fs,[],_),do:fsdefupdate_total_size(fs,[_|ancestors]=path,file_size)doget_and_update_in(fs,Enum.reverse([:total_size|path]),fntotal_size->{total_size,total_size+file_size}end)|>(fn{_,fs}->update_total_size(fs,ancestors,file_size)end).()enddeftotal_size_under_100000(folder)do{total_size,without_size}=Map.pop(folder,:total_size,0){_,without_files}=Map.pop(without_size,:files)added_size=if(total_size<=100000,do:total_size,else:0)added_size+(Enum.map(without_files,fn{_,v}->total_size_under_100000(v)end)|>Enum.sum)enddeflarge_enough(folder,space_needed)do{total_size,without_size}=Map.pop(folder,:total_size,0){_,without_files}=Map.pop(without_size,:files)conddototal_size>space_needed->[total_size|Enum.flat_map(without_files,fn{_,v}->large_enough(v,space_needed)end)]true->[]endenddefpart1,do:parse_filesystem()|>(fn%{"/"=>root}->total_size_under_100000(root)end).()defpart2do%{"/"=>%{total_size:used_space}=root}=parse_filesystem()space_needed=30000000-(70000000-used_space)large_enough(root,space_needed)|>Enum.min()endend
Top comments (0)
Subscribe
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)