Function aoc::y22d07::y22d07

pub fn y22d07(input: &str, part: u32) -> u32

The solution for the day seven challenge.

Given the usual parameters of the input as a string and which part 1 or 2 we start by parsing the input to build a representation of the total file size contained in each directory as described above.

We start by analyzing each line (skipping the first line which we assume will be changing into the root directory which we’ve used to setup the initial state i.e., set the current path to the root and initialize its size to zero). If we have a change directory command then simply we update the current path marker. If we have a list directory command then we insert the path into a list of directories that we have already visited. We do this to ensure that we don’t double count any directories if we list them more than once. The provided input doesn’t actually do this but I wasn’t sure if that was the case or not when I started and wanted a guard. In theory it’s possible to remove it now, but it doesn’t hurt to keep around (just increases the memory requirements).

Otherwise, we can assume that we’re reading the results from listing the directory. Other directories start with the string dir which we can use to then initialize those directories with size 0 in our sizes map. If we don’t have a directory then we must have a file so we add its size to the current directory and then explode the directory and add its size to every component back up to the root which gives us the desired cumulative size for each directory part.

After computing the (cumulative) size of each directory we can respond to the challenge prompt. In part one we just loop through all of the directories and if their total size is greater than 1000000 (provided by the prompt) then we add the size to the total. In part two we instead compute the free space (total space minus the total size of the root directory) and then loop through our directories. If deleting the directory would give us enough free space (both total space and required space are provided by the prompt) then we add the directory size to a min-heap. Finally, we can simply pop the smallest directory that satisfies the minimum space requirements.

Example

// probably read this from the input file...
let input = concat![
   "$ cd /\n",
   "$ ls\n",
   "39950000 a\n",
   "dir b\n",
   "dir c\n",
   "$ cd b\n",
   "$ ls\n",
   "50000 d\n",
   "$ cd ..\n",
   "$ cd c\n",
   "$ ls\n",
   "10000000 e",
];
assert_eq!(y22d07(&input, 1), 50000);
assert_eq!(y22d07(&input, 2), 10000000);