Day 7 is about parsing terminal output, mainly the output of ls command. We can’t run system output on the device received from Elves, because there is no space left. We are running some terminal commands to found out what is the directory structure:
$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k
We need to find good candidates for deletion and to do that we need to determine total size of each directory and output total size of all directories that are less than 100000. In the example above the answer is 95437, directory a is 94853 and directory e is 584.
We can start with a class representing single node (directory or file):
class Node
attr_reader :name, :parent, :children
def initialize(parent, name, type, size)
@name = name
@type = type
@size = size
@parent = parent
@children = []
end
def add(name, type, size)
@children.push(Node.new(self, name, type, size))
end
def get(name)
@children.find { |child| child.name == name }
end
def size
if @type == "file"
@size
else
@size ||= @children.map(&:size).sum
end
end
def traverse(&block)
block.call(self)
children.each do |child|
child.traverse(&block)
end
end
def dir?
@type == "dir"
end
end
It will store node name, type, size and child nodes in case of a directory. Then we have a method to add new child node, to find child node by name and recursive method to calculate the size of a node. I also added a convenient method traverse to iterate over all nodes and pass them to a block.
Having the class for representing single node we now need to parse the input and build directory structure:
data = File.readlines("7.txt", chomp: true)
root = Node.new(nil, "/", "dir", nil)
current = nil
data.each do |line|
if line.start_with?("$")
line.gsub!("$ ", "")
command, argument = line.split(" ")
if command == "cd"
if argument == "/"
current = root
elsif argument == ".."
current = current.parent
else
current = current.get(argument)
end
end
else
parts = line.split(" ")
type = parts[0] == "dir" ? "dir" : "file"
size = parts[0] == "dir" ? nil : parts[0].to_i
current.add(parts[1], type, size)
end
end
We are iterating over each line of input. Variable command will maintain the current directory, kind like output of pwd terminal command. If it starts with $ sign it is a command line and we need to process it accordingly. We mainly should care about cd commands, because this will change the current variable.
If line does not start with $ sign it means it is an output from ls command, so we need to parse it into nodes and add all of them to the current one.
At this point we have a tree of nodes. The last thing is to traverse this tree and sum size of all nodes that are directories and have size at most 100000.
sum = 0
root.traverse do |node|
if node.dir? && node.size <= 100_000
sum += node.size
end
end
puts sum
Here is the full code:
class Node
attr_reader :name, :parent, :children
def initialize(parent, name, type, size)
@name = name
@type = type
@size = size
@parent = parent
@children = []
end
def add(name, type, size)
@children.push(Node.new(self, name, type, size))
end
def get(name)
@children.find { |child| child.name == name }
end
def size
if @type == "file"
@size
else
@size ||= @children.map(&:size).sum
end
end
def traverse(&block)
block.call(self)
children.each do |child|
child.traverse(&block)
end
end
def dir?
@type == "dir"
end
end
data = File.readlines("7.txt", chomp: true)
root = Node.new(nil, "/", "dir", nil)
current = nil
data.each do |line|
if line.start_with?("$")
line.gsub!("$ ", "")
command, argument = line.split(" ")
if command == "cd"
if argument == "/"
current = root
elsif argument == ".."
current = current.parent
else
current = current.get(argument)
end
end
else
parts = line.split(" ")
type = parts[0] == "dir" ? "dir" : "file"
size = parts[0] == "dir" ? nil : parts[0].to_i
current.add(parts[1], type, size)
end
end
sum = 0
root.traverse do |node|
if node.dir? && node.size <= 100_000
sum += node.size
end
end
puts sum
Now we need to run the system update. Total available disk space is 70000000 and we need to have 30000000 of free space.
In the example input the root has size of 48381165, so there is 21618835 left on the device. We are still short of 8381165. The task is to find the smallest directory to delete that will free up enough space to install system update.
We can reuse most of the code from Part A and add this:
directories = {}
root.traverse do |node|
if node.dir?
directories[node.name] = node.size
end
end
total_space = 70_000_000
free_space_required = 30_000_000
total_used_space = directories["/"]
to_remove = free_space_required - (total_space - total_used_space)
min = Float::INFINITY
directories.each do |_, size|
if size > to_remove && size < min
min = size
end
end
puts min
Now we are traversing our directory tree and caching directory sizes in directories hash. We calculate total used space and calculate how much space we need to remove. Finally we can select the smallest directory that will remove enough space.
Here is the full code:
class Node
attr_reader :name, :parent, :children
def initialize(parent, name, type, size)
@name = name
@type = type
@size = size
@parent = parent
@children = []
end
def add(name, type, size)
@children.push(Node.new(self, name, type, size))
end
def get(name)
@children.find { |child| child.name == name }
end
def size
if @type == "file"
@size
else
@size ||= @children.map(&:size).sum
end
end
def traverse(&block)
block.call(self)
children.each do |child|
child.traverse(&block)
end
end
def dir?
@type == "dir"
end
end
data = File.readlines("7.txt").map(&:strip)
root = Node.new(nil, "/", "dir", nil)
current = nil
data.each do |line|
if line.start_with?("$")
line.gsub!("$ ", "")
command, argument = line.split(" ")
if command == "cd"
if argument == "/"
current = root
elsif argument == ".."
current = current.parent
else
current = current.get(argument)
end
end
else
parts = line.split(" ")
type = parts[0] == "dir" ? "dir" : "file"
size = parts[0] == "dir" ? nil : parts[0].to_i
current.add(parts[1], type, size)
end
end
directories = {}
root.traverse do |node|
if node.dir?
directories[node.name] = node.size
end
end
total_space = 70_000_000
free_space_required = 30_000_000
total_used_space = directories["/"]
to_remove = free_space_required - (total_space - total_used_space)
min = Float::INFINITY
directories.each do |_, size|
if size > to_remove && size < min
min = size
end
end
puts min