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