107 lines
2.9 KiB
C++
107 lines
2.9 KiB
C++
//
|
|
// Created by Matthew Gretton-Dann on 07/12/2022.
|
|
//
|
|
|
|
#include <cassert>
|
|
#include <iostream>
|
|
#include <list>
|
|
#include <map>
|
|
#include <numeric>
|
|
#include <regex>
|
|
#include <string>
|
|
|
|
using UInt = std::uint64_t;
|
|
|
|
struct DirectoryInfo
|
|
{
|
|
[[nodiscard]] auto total_size() const noexcept -> UInt
|
|
{
|
|
UInt const file_size{std::accumulate(files_.begin(), files_.end(), UInt{0},
|
|
[](UInt a, auto const& b) { return a + b.second; })};
|
|
UInt const directory_size{
|
|
std::accumulate(dirs_.begin(), dirs_.end(), UInt{0},
|
|
[](UInt a, auto const& b) { return a + b.second.total_size(); })};
|
|
return file_size + directory_size;
|
|
}
|
|
|
|
auto find_dir(std::string const& name)
|
|
{
|
|
auto it{dirs_.find(name)};
|
|
assert(it != dirs_.end());
|
|
return it;
|
|
}
|
|
|
|
auto add_dir(std::string const& name) { dirs_.insert({name, DirectoryInfo()}); }
|
|
|
|
auto add_file(std::string const& name, UInt size) { files_.insert({name, size}); }
|
|
|
|
std::map<std::string, UInt> files_;
|
|
std::map<std::string, DirectoryInfo> dirs_;
|
|
};
|
|
|
|
using DirIt = std::map<std::string, DirectoryInfo>::iterator;
|
|
|
|
auto size_to_free(DirIt root, UInt min) -> UInt
|
|
{
|
|
UInt result{std::numeric_limits<UInt>::max()};
|
|
|
|
auto root_size = root->second.total_size();
|
|
if (root_size >= min) {
|
|
result = std::min(result, root_size);
|
|
}
|
|
for (auto it = root->second.dirs_.begin(); it != root->second.dirs_.end(); ++it) {
|
|
auto t{size_to_free(it, min)};
|
|
if (t >= min) {
|
|
result = std::min(result, t);
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
auto main() -> int
|
|
{
|
|
std::string line;
|
|
|
|
std::list<DirIt> its;
|
|
std::map<std::string, DirectoryInfo> dirs;
|
|
auto root{dirs.insert({"/", DirectoryInfo()}).first};
|
|
while (std::getline(std::cin, line) && !line.empty()) {
|
|
if (line == "$ cd /") {
|
|
its.clear();
|
|
its.push_back(root);
|
|
}
|
|
else if (line == "$ cd ..") {
|
|
assert(!its.empty());
|
|
its.pop_back();
|
|
}
|
|
else if (line == "$ ls") {
|
|
continue;
|
|
}
|
|
else if (line.substr(0, 5) == "$ cd ") {
|
|
auto sub_dir{line.substr(5)};
|
|
assert(!its.empty());
|
|
auto it{its.back()->second.find_dir(sub_dir)};
|
|
its.push_back(it);
|
|
}
|
|
else if (line.substr(0, 4) == "dir ") {
|
|
its.back()->second.add_dir(line.substr(4));
|
|
}
|
|
else {
|
|
static std::regex const re{R"((\d+) ([a-z]+))"};
|
|
std::smatch m;
|
|
if (!std::regex_search(line, m, re)) {
|
|
std::cerr << "Unable to interpret: " << line << "\n";
|
|
return EXIT_FAILURE;
|
|
}
|
|
its.back()->second.add_file(m.str(2), std::stoul(m.str(1)));
|
|
}
|
|
}
|
|
|
|
UInt constexpr disk_size{70000000};
|
|
UInt constexpr needed_space{30000000};
|
|
UInt const current_space{disk_size - root->second.total_size()};
|
|
UInt const min_space_to_free(needed_space - current_space);
|
|
std::cout << "Size to free: " << size_to_free(root, min_space_to_free) << '\n';
|
|
return 0;
|
|
}
|