advent_of_code_2022

My (attempted) solutions to the 2022 Advent of Code
git clone https://git.eamoncaddigan.net/advent_of_code_2022.git
Log | Files | Refs | README

day_7.jl (3977B)


      1 #!/usr/bin/env julia
      2 # https://adventofcode.com/2022/day/7
      3 using AdventOfCode
      4 
      5 example = readlines(IOBuffer(raw"""
      6     $ cd /
      7     $ ls
      8     dir a
      9     14848514 b.txt
     10     8504156 c.dat
     11     dir d
     12     $ cd a
     13     $ ls
     14     dir e
     15     29116 f
     16     2557 g
     17     62596 h.lst
     18     $ cd e
     19     $ ls
     20     584 i
     21     $ cd ..
     22     $ cd ..
     23     $ cd d
     24     $ ls
     25     4060174 j
     26     8033020 d.log
     27     5626152 d.ext
     28     7214296 k"""))
     29 input = readlines("data/day_7.txt")
     30 
     31 # Finally diving into Julia's object orientation. I could do this without OO,
     32 # and if I was using R I definitely would, but since this is a learning
     33 # exercise I figured it was a good time to learn this. Cool stuff! I like how
     34 # methods aren't object members, they're just rely on polymorphism like
     35 # everything else. I like inner and outer constructors too. I don't really need
     36 # to save object names (at least not for part 1), but I'm just doing OOP over
     37 # here.
     38 # 
     39 # One thing I didn't like: I'm developing in a REPL, and updating my code with
     40 # `include` doesn't work if you don't wrap structs in a module. That's really
     41 # the only reason to use a module here.
     42 
     43 module FileSystem
     44     struct File
     45         name::AbstractString
     46         size::Int
     47     end
     48 
     49     struct Directory
     50         parent::Union{Nothing, Directory}
     51         name::AbstractString
     52         contents::Dict{AbstractString, Union{File, Directory}}
     53     end
     54     Directory(parent, name) = Directory(parent, name, Dict())
     55 end
     56 
     57 function build_directory(input::Vector{<:AbstractString})::FileSystem.Directory
     58     fs = FileSystem.Directory(nothing, "/")
     59     currdir::FileSystem.Directory = fs
     60     @assert input[1] == "\$ cd /"
     61 
     62     for line = input[2:end]
     63         if line == "\$ ls"
     64             # No need to do anything, the next line(s) will list directory
     65             # contents
     66             nothing
     67         elseif line == "\$ cd .."
     68             # Change to the parent directory
     69             currdir = currdir.parent
     70         elseif line[1:5] == "\$ cd "
     71             # Change to specified subdirectry
     72             currdir = currdir.contents[line[6:end]]
     73         else
     74             # Receive directory contents
     75             sizeortype, name = split(line, " ")
     76             if sizeortype == "dir"
     77                 # A directory!
     78                 currdir.contents[name] = FileSystem.Directory(currdir, name)
     79             else
     80                 # A file!
     81                 currdir.contents[name] = FileSystem.File(name, 
     82                                                          parse(Int, sizeortype))
     83             end
     84         end
     85     end
     86 
     87     fs
     88 end
     89 
     90 # Create a dictionary with the size of the given directory and every directory
     91 # it contains
     92 function size_directories(fs::FileSystem.Directory)::Dict{FileSystem.Directory, Int}
     93     dirsizes = Dict()
     94 
     95     # Recursively calculate the size of a directory, filling dirsizes[] as a
     96     # side effect (I know, I know). We get memoization though!
     97     function size_directory(d::FileSystem.Directory)::Int
     98         if !haskey(dirsizes, d)
     99             dirsizes[d] = 0
    100             for item = values(d.contents)
    101                 if typeof(item) == FileSystem.File
    102                     dirsizes[d] += item.size
    103                 else
    104                     dirsizes[d] += size_directory(item)
    105                 end
    106             end
    107         end
    108         dirsizes[d]
    109     end
    110 
    111     size_directory(fs)
    112     dirsizes
    113 end
    114 
    115 function part_1(input)
    116     sum([x for x in values(size_directories(build_directory(input)))
    117          if x < 100000])
    118 end
    119 @assert part_1(example) == 95437
    120 @info part_1(input)
    121 
    122 function part_2(input)
    123     # The total disk space available is 70000000, and we need at least 30000000
    124     # available. Find out how much we need to free:
    125     fs = build_directory(input)
    126     dirsizes = size_directories(fs)
    127     needtofree = dirsizes[fs] - (70000000 - 30000000)
    128 
    129     # Find the smallest directory, if deleted, that would free up enough space
    130     minimum([x for x in values(dirsizes) if x > needtofree])
    131 end
    132 @assert part_2(example) == 24933642
    133 @info part_2(input)