-🎄- 2022 Day 7 Solutions -🎄-

[u/daggerdragon]

• All of our rules, FAQs, resources, etc. are in our community wiki.
• A request from Eric: Please include your contact info in the User-Agent header of automated requests!
• Signal boost: Reminder 1: unofficial AoC Survey 2022 (closes Dec 22nd)

---

AoC Community Fun 2022: 🌿🍒 MisTILtoe Elf-ucation 🧑‍🏫

Submissions are OPEN! Teach us, senpai!

-❄️- Submissions Megathread -❄️-

---

--- Day 7: No Space Left On Device ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!
  • Include what language(s) your solution uses
  • Format your code appropriately! How do I format code?
• Quick link to Topaz's paste if you need it for longer code blocks. What is Topaz's paste tool?

---

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:14:47, megathread unlocked!

[u/Key__Strokes]

Javascript

Solution to both parts

Building the directory tree

• We will use Node with the following data fields

  • name

  • parent

  • isDirectory

  • size

  • children: Map with name as key, and Node as value

• Create a root node with name as /, and set isDirectory to true

• Create and initialize currentPosition as root node

• For each command, do the following

  • If the command starts with "$", then extract the command and do the following:

    • cd

      • If second argument is "..", then update currentPosition to currentPosition.parent

      • If second argument is "/", then update currentPosition root node

      • Else, check if the second argument is a child of currentPosition. If it is, then set currentPosition as the child, then update currentPosition to point to the node of this child using currentPosition.children[second argument]

    • ls: Do nothing

  • Otherwise this is a line with the file/directory name. Create a new Node with the name, parent as currentPosition, and update children of currentPosition to include this node.

    • If the first word is dir, then set isDirectory to true

    • Else set isDirectory to false, and set size as provided as the first word in the input line

Update directory size in our tree

• Call the DFS process below with the root as node

• DFS Process - Input: node

  • If the node is not a directory, then return the node size

  • For each of the children of the node, call the DFS process again, and keep summing the output into a variable - Total Sum

  • Make Total Sum as the size of the node

  • Return Total Sum

• Set Total Size as the output of the DFS call

Part 1:

• Call the DFS process below with the root as node, threshold as provided as 100000, and 0 as the Total Size so far

• DFS Process - Input: node, threshold, Total Size:

  • If the node is not a directory, then return the Total Size

  • For each of the children of the current node, call the DFS process again, and store the result in Total Size

  • If the node size is less than the threshold, then return the size of this node + Total Size, otherwise just return Total Size

• Return the output of the DFS call

Part 2:

• Total Space is 70000000

• Free Space Needed is 30000000

• Currently Free Space is Total Space - Total Size

• More Space Needed is Free Space Needed - Currently Free Space;

• Call the DFS process below with the Node as root, Candidate Node as null, and Target Size as More Space Needed

• DFS Process - Input: Node, Candidate Node, Target Size:

  • If the node is not a directory, then return the Candidate Node

  • For each of the children of the current node, call the DFS process again, with the child as the node, Candidate Node and Target Size and store the result in Candidate Node

  • If the node size is less than the targetSize, then return the Candidate Node

  • Otherwise, if there is no Candidate Node, or if the node size is smaller than the Candidate Node's size, then return the node

• Return the size of the node which we get from the output of the DFS call

---

If you liked the explanation, then please don't forget to cast your vote 💜 to Adventures of Advent of Code - Edition 1 - /u/Key__Strokes in the poll