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)