Robert Mion

Posted on Dec 8, 2022

No Space Left On Device

#adventofcode #algorithms #javascript #programming

Advent of Code 2022 Day 7

Part 1

A surprisingly great CLI tutorial
Studying the terminal output
A walkthrough as an algorithm
Flattening my data structure
My algorithm in pseudocode
Discovering an obstacle
Back to using my initial data structure
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:

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

After processing the next four lines, I would have this data structure:

{ 
  '/': {
    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:

{ 
  '/': {
    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 filesizes 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:

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

The hard part is over
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:

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:

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.

DEV Community