Mercurial > lbo > hg > aoc22
view 07/07.jl @ 14:4bad3ee77ef2
Day 09 part 2
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 11 Dec 2022 11:15:16 +0100 |
parents | e53d5f34cf17 |
children |
line wrap: on
line source
const input::String = "07/input.txt" import Base: push! using ParserCombinator abstract type Entry end struct File <: Entry name::String size::Int end struct Dir <: Entry name::String children::Vector{Entry} end function filename(f::File)::String f.name end function filesize(f::File)::Int f.size end function filename(f::Dir)::String f.name end function filesize(d::Dir)::Int sum(filesize(f) for f in d.children) end function push!(d::Dir, e::Entry) # Avoid duplication of entries if !isnothing(findnext((==)(e), d.children, 1)) return; end push!(d.children, e::Entry); end function cd(d::Dir, s::String)::Entry d.children[findnext(e -> filename(e) == s, d.children, 1)] end function count_dirs_belowsize(root::Dir; maxsize=100000)::Int sizes = [filesize(e) for e in root.children]; mysize = sum(sizes; init=0); subsizes = [count_dirs_belowsize(r) for r in root.children if isa(r, Dir)]; (mysize <= maxsize ? mysize : 0) + sum(subsizes; init=0) end # Parsing types abstract type TerminalLine end struct Cd <: TerminalLine dir::String end struct Ls <: TerminalLine contents::Vector{Entry} end # Parsers ParseFilename() = p"[a-z/\.]+" |> (x -> string(x[1])) ParseCd() = (E"cd " + ParseFilename()) |> (x -> Cd(x[1])) ParseLs() = (E"ls" + Eos()) |> (_ -> Ls([])) ParseCommandLine() = E"$ " + (ParseCd() | ParseLs()) + Eos() ParseLsEntry() = ((E"dir " + ParseFilename()) |> (d -> Dir(d[1], []))) | ((PInt() + E" " + ParseFilename()) |> (f -> File(f[2], f[1]))) + Eos() function build_filesystem(io::IO)::Entry root = Dir("/", []) current = root path = [] pcl = ParseCommandLine() ple = ParseLsEntry() state = "shell"; for line in eachline(io) parsed = false; while !parsed if state == "shell" cmd = parse_one(line, pcl)[1] parsed = true; if isa(cmd, Cd) if (cmd::Cd).dir == "/" current = root; path = []; elseif (cmd::Cd).dir == ".." current = pop!(path); else push!(path, current); oc = current; current = cd(current, (cmd::Cd).dir); end elseif isa(cmd, Ls) state = "ls"; else error("unknown type: ", line); end elseif state == "ls" try e = parse_one(line, ple)[1]::Entry; push!(current, e); parsed = true; catch exc state = "shell"; end else error("unknown state ", state); end end end root end function find_smallest_directory_larger_than(root::Entry, sz::Int)::Entry best_dir = root; best_difference = filesize(root) - sz; for e in best_dir.children if !isa(e, Dir) continue; end fs = filesize(e); if fs - sz >= 0 && fs - sz < best_difference best_dir = e; best_difference = fs - sz; end sub = find_smallest_directory_larger_than(e, sz); fs = filesize(sub); if fs - sz >= 0 && fs - sz < best_difference best_dir = sub; best_difference = fs - sz; end end best_dir end function collect_all_dirs(root::Entry)::Vector{Entry} queue = [root]; list = [root]; while length(queue) > 0 d = pop!(queue); for e in d.children if isa(e, Dir) push!(queue, e) push!(list, e); end end end list end open("07/input.txt"; read=true) do fh root = build_filesystem(fh); #println(root); #println(count_dirs_belowsize(root)); # total_size = filesize(root); capacity = 70_000_000; required_free = 30_000_000 - (capacity - total_size); println("Using $total_size out of $capacity - need $required_free of additional free space"); sdlt = find_smallest_directory_larger_than(root, required_free); println(sdlt.name, " ", filesize(sdlt)); # Serial algorithm: by_filesize = [(d.name, filesize(d)) for d in collect_all_dirs(root)]; best = 1; best_diff = by_filesize[1][2] - required_free; for (i, (n, s)) in enumerate(by_filesize) if (s-required_free) > 0 && (s-required_free) < best_diff best = i; best_diff = s - required_free; end end println(by_filesize[best], " ", best_diff); end