No Space Left On Device
Tags: adventofcode, algorithms, javascript, programming
Published: 2022-12-08 15:28:27

## [Advent of Code 2022 Day 7](https://adventofcode.com/2022/day/7)

## Part 1
1. A surprisingly great CLI tutorial
2. Studying the terminal output
3. A walkthrough as an algorithm
4. Flattening my data structure
5. My algorithm in pseudocode
6. Discovering an obstacle
7. Back to using my initial data structure
8. I wasn't too far off

### A surprisingly great CLI tutorial
- CLI is short for `command line interface`
- Learning to use it is often a frustrating and confusing process
- Jargon-heavy tutorials don't help ease newcomers, either

Thankfully, today's puzzle covers the basics in effort to help puzzlers fully understand how to solve the challenge.

To any beginners reading this:
These commands are identical to the ones used in software like `Terminal` on a Mac.

### Studying the terminal output
- Only one line type starts with a number: a file
- Lines starting with `dir` should be catalogued
- Lines starting with `cd` move among folders
- Lines starting with `ls` preclude items to be catalogued

### A walkthrough as an algorithm
Using the first few lines of the example:
```
$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
```

After the first line, I might have this data structure:
```
{ '/' }
```

The next line lists files and folders.

The next line lists a directory. I might now have this data structure:
```
{ '/': ['a'], 'a' }
```

The next line lists a file. I realize I need to adjust my data structure:
```
{ 
  '/': {
    folders: ['a'],
    filesize: 14848514
  }
  'a'
}
```

After the next line:
```
{ 
  '/': {
    folders: ['a'],
    filesize: 14848514 + 8504156
  }
  'a'
}
```

The next line lists a directory. My data structure is now:
```
{ 
  '/': {
    folders: ['a', 'd'],
    filesize: 14848514 + 8504156
  }
  'a',
  'd'
}
```

I can probably avoid the redundant keys and instead associate nested objects to each string in `folders`.

```
{ 
  '/': {
    folders: { 'a': {}, 'd': {} },
    filesize: 14848514 + 8504156
  }
}
```

Here are the next few lines:
```
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
```

After processing the first line, I will need to track where I am in the filesystem:
```js
let lineage = ['/', 'a']
let cursor = lineage[lineage.length - 1] // 'a'
```

After processing the next four lines, I would have this data structure:
```js
{ 
  '/': {
    folders: { 
      'a': {
         folders: { 'e': {} },
         filesize: 29116 + 2557 + 62596
      }, 
      'd': {} 
    },
    filesize: 14848514 + 8504156
  }
}
```

After the next three lines:
```
$ cd e
$ ls
584 i
```

My data structure and tracking variables will store this:
```js
{ 
  '/': {
    folders: { 
      'a': {
         folders: { 
           'e': {
             filesize: 584
           } 
         },
         filesize: 29116 + 2557 + 62596
      }, 
      'd': {} 
    },
    filesize: 14848514 + 8504156
  }
}

let lineage = ['/', 'a', 'e']
let cursor = lineage[lineage.length - 1] // 'e'
```

I see that the use of `folders` is probably unnecessary:
```
{ 
  '/': {
    'a': {
      'e': {
        filesize: 584
      } 
      filesize: 29116 + 2557 + 62596
    }, 
    'd': {},
    filesize: 14848514 + 8504156
  }
}
```

The next two lines move the cursor back to the parent directory:
```
$ cd ..
$ cd ..
```

Which does this to my lineage:
```
lineage.pop() // ['/', 'a']
lineage.pop() // ['/']
let cursor = lineage[lineage.length - 1] // '/'
```

Then, the remaining lines explore the other directory:
```
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k
```

Resulting in this data structure:
```
{ 
  '/': {
    'a': {
      'e': {
        filesize: 584
      } 
      filesize: 29116 + 2557 + 62596
    }, 
    'd': {
      filesize: 4060174 + 8033020 + 5626152 + 7214296
    },
    filesize: 14848514 + 8504156
  }
}
```

### Flattening my data structure
I stepped away for a while. I reconsidered the resulting data structure above.

I feel like I could instead flatten the object into something more like this:
```
{
 '/': 48381165,
 'a': 94853,
 'e': 584,
 'd': 24933642
}
```

It would require:
- A tracker for the ordered list of directories, with the last one being the current directory
- A loop through that list to increment each enclosing directory's total file size

### My algorithm in pseudocode
```
Create an empty dictionary to store the directory list
Create an empty ordered list to store the location of the working directory

For each line of terminal output
  Do one of the following:
    1. Update the ordered list so that the last item reflects the working directory
    2. Add a key to the dictionary for the working or nested directory
    3. Increment the amount associated with the working directory and each of its parent directories

Generate an array of from each key-value pair in the dictionary
  Filter it to only include items where the value is less than or equal to 100000
    Calculate the sum of all items

Return the sum
```

I'm excited to try and write this!

I anticipate a lot of debugging.

### Discovering an obstacle
- I wrote an algorithm that generated the correct answer from the example input
- I ran that algorithm on my puzzle input
- It generated an answer, but one that was too low
- I wondered how that could be

After some closer analysis of my puzzle input, I found these lines:
```
$ cd qsdlvr
$ ls
dir nzjfwdt
dir qsdlvr
```

Note the nested directory of the same name as its parent.

Sadly, my algorithm relied on unique keys in a dictionary.

I must now account for directories with the same name, sometimes contained in an identically-named parent directory.

Ugh!

### Back to using my initial data structure
Remember this 'ol thing:
```
{ 
  '/': {
    'a': {
      'e': {
        filesize: 584
      } 
      filesize: 29116 + 2557 + 62596
    }, 
    'd': {},
    filesize: 14848514 + 8504156
  }
}
```

I was able to build it!

I then wrote a quasi-recursive function that:
- iterates through each key-value pair
- increments a `sum` if the object's `filesize` value is `<= 100000`

After running it on my puzzle input, I got an answer higher than my previous one.

Sadly, it was too high.

Thankfully, I now have boundaries for the correct answer for my puzzle input!

And I know what I'm not accounting for:
- I need to process each nested key-value pair
- And increment each parent directory's `filesize` to account for the `filesize`s of each child directory

This will likely require a more complex recursive function.

Off I go...again!

### I wasn't too far off
After some head-scratching, trial and error, and plethora of `console.log()` statements, I wrote this successful recursive function:
```js
let answer = 0
function explore(obj) {
  let sum = 0
  for (key in obj) {
    if (typeof obj[key] == 'object') {
      sum += explore(obj[key])
    }
  }
  obj.filesize += sum
  if (obj.filesize <= 100000) {
    answer += obj.filesize
  }
  return obj.filesize
}
```

My correct answer is only about 30k less than my `Too high` answer. I thought that was interesting.

I'm so proud that I finally solved Part 1!

It took a lot of code and even more exploration, but I did it!

## Part 2
1. The hard part is over
2. Re-purposing my failed function for success

### The hard part is over
- With Part 1 done, I have an object that details the file size of each directory's files and sub-directory's files
- And I'm pretty sure I can re-use a function I wrote in Part 1 that didn't work for that purpose but will suit me well now!

### Re-purposing my failed function for success
The original function incorrectly matched too many directories:
```js
let sum = 0
function explore(obj) {
  for (dir in obj) {
    if (obj[dir].filesize <= 100000) {
      sum += obj[dir].filesize
    }
    explore(obj[dir])
  }
}
```

But this slightly refactored function identifies the correct directory for Part 2:
```js
let smallest = Infinity
function findSmallest(obj) {
  for (dir in obj) {
    if (
      obj[dir].filesize >= (
        30000000 - (70000000 - dirs.filesize)
      ) && obj[dir].filesize < smallest) {
      smallest = obj[dir].filesize
    }
    findSmallest(obj[dir])
  }
}
```

Phew! My hard work paid off to make Part 2 a much smaller challenger!

## I did it!!
- I solved both parts!
- I got tripped up several times throughout Part 1, but persisted until I eventually wrote an algorithm that generated the correct answer!
- I leveraged some code that didn't work in Part 1 to more quickly solve Part 2!

Clearly I still get flustered when building and traversing data structures that resemble trees.

I'm not thrilled about how much code it took to solve this puzzle.

But I *am* thrilled that I earned both stars today!

Now, as this article's cover image implies, I'd like to delete this puzzle from my memory.