DEV Community

Cover image for No Space Left On Device
Robert Mion
Robert Mion

Posted on

No Space Left On Device

Advent of Code 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
Enter fullscreen mode Exit fullscreen mode

After the first line, I might have this data structure:

{ '/' }
Enter fullscreen mode Exit fullscreen mode

The next line lists files and folders.

The next line lists a directory. I might now have this data structure:

{ '/': ['a'], 'a' }
Enter fullscreen mode Exit fullscreen mode

The next line lists a file. I realize I need to adjust my data structure:

{ 
  '/': {
    folders: ['a'],
    filesize: 14848514
  }
  'a'
}
Enter fullscreen mode Exit fullscreen mode

After the next line:

{ 
  '/': {
    folders: ['a'],
    filesize: 14848514 + 8504156
  }
  'a'
}
Enter fullscreen mode Exit fullscreen mode

The next line lists a directory. My data structure is now:

{ 
  '/': {
    folders: ['a', 'd'],
    filesize: 14848514 + 8504156
  }
  'a',
  'd'
}
Enter fullscreen mode Exit fullscreen mode

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

{ 
  '/': {
    folders: { 'a': {}, 'd': {} },
    filesize: 14848514 + 8504156
  }
}
Enter fullscreen mode Exit fullscreen mode

Here are the next few lines:

$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
Enter fullscreen mode Exit fullscreen mode

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'
Enter fullscreen mode Exit fullscreen mode

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

{ 
  '/': {
    folders: { 
      'a': {
         folders: { 'e': {} },
         filesize: 29116 + 2557 + 62596
      }, 
      'd': {} 
    },
    filesize: 14848514 + 8504156
  }
}
Enter fullscreen mode Exit fullscreen mode

After the next three lines:

$ cd e
$ ls
584 i
Enter fullscreen mode Exit fullscreen mode

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'
Enter fullscreen mode Exit fullscreen mode

I see that the use of folders is probably unnecessary:

{ 
  '/': {
    'a': {
      'e': {
        filesize: 584
      } 
      filesize: 29116 + 2557 + 62596
    }, 
    'd': {},
    filesize: 14848514 + 8504156
  }
}
Enter fullscreen mode Exit fullscreen mode

The next two lines move the cursor back to the parent directory:

$ cd ..
$ cd ..
Enter fullscreen mode Exit fullscreen mode

Which does this to my lineage:

lineage.pop() // ['/', 'a']
lineage.pop() // ['/']
let cursor = lineage[lineage.length - 1] // '/'
Enter fullscreen mode Exit fullscreen mode

Then, the remaining lines explore the other directory:

$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k
Enter fullscreen mode Exit fullscreen mode

Resulting in this data structure:

{ 
  '/': {
    'a': {
      'e': {
        filesize: 584
      } 
      filesize: 29116 + 2557 + 62596
    }, 
    'd': {
      filesize: 4060174 + 8033020 + 5626152 + 7214296
    },
    filesize: 14848514 + 8504156
  }
}
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
  }
}
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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:

let sum = 0
function explore(obj) {
  for (dir in obj) {
    if (obj[dir].filesize <= 100000) {
      sum += obj[dir].filesize
    }
    explore(obj[dir])
  }
}
Enter fullscreen mode Exit fullscreen mode

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])
  }
}
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)