From 4aaf38359e7323f75fd55d28a330c665bb81a477 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 1 May 2024 13:00:14 +0200
Subject: day 7, advent of code 2022

---
 2022/src/day07.cpp | 176 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 176 insertions(+)
 create mode 100644 2022/src/day07.cpp

(limited to '2022/src')

diff --git a/2022/src/day07.cpp b/2022/src/day07.cpp
new file mode 100644
index 0000000..8a8decd
--- /dev/null
+++ b/2022/src/day07.cpp
@@ -0,0 +1,176 @@
+#include <cstdlib>
+#include <fstream>
+#include <iostream>
+#include <iterator>
+#include <map>
+#include <memory>
+#include <string>
+#include <vector>
+using namespace std;
+
+struct Node {
+	Node* parent = nullptr;
+
+	map<string, shared_ptr<Node>> sub;
+	map<string, long>             files;
+};
+
+Node
+read_file(string_view filename, ostream& debug)
+{
+	Node  root;
+	Node* current = &root;
+
+	fstream input{ filename };
+
+	string line;
+	getline(input, line);
+
+	while ( input ) {
+		if ( line.starts_with("$ ") ) {
+			if ( line == "$ cd /" ) {
+				debug << "cd root" << endl;
+				current = &root;
+				getline(input, line);
+			}
+			else if ( line == "$ cd .." ) {
+				debug << "cd one up" << endl;
+				current = current->parent;
+				getline(input, line);
+			}
+			else if ( line == "$ ls" ) {
+				debug << "list dir" << endl;
+				getline(input, line);
+
+				while ( input && !line.starts_with("$ ") ) {
+					if ( line.starts_with("dir ") ) {
+						const auto name    = line.substr(4);
+						const auto node    = make_shared<Node>();
+						node->parent       = current;
+						current->sub[name] = node;
+						debug << "new subdir " << name << endl;
+					}
+					else {
+						const auto pos       = line.find(' ');
+						const auto size      = stol(line.substr(0, pos));
+						const auto name      = line.substr(pos + 1);
+						current->files[name] = size;
+						debug << "new file " << name << " (" << size << ")" << endl;
+					}
+
+					getline(input, line);
+				}
+			}
+			else if ( line.starts_with("$ cd ") ) {
+				const auto dirname = line.substr(5);
+				current            = current->sub[dirname].get();
+				debug << "cd into " << dirname << endl;
+				getline(input, line);
+			}
+			else {
+				cerr << "error in line: " << line << endl;
+				exit(EXIT_FAILURE);
+			}
+		}
+		else {
+			cerr << "error II in line: " << line << endl;
+			exit(EXIT_FAILURE);
+		}
+	}
+
+	return root;
+}
+
+void
+print(const Node& node, const string& indent = "")
+{
+	if ( node.parent == nullptr ) {
+		cout << indent << "/" << endl;
+	}
+
+	for ( const auto& [name, sub]: node.sub ) {
+		cout << indent << name << endl;
+		print(*sub.get(), indent + "  ");
+	}
+
+	for ( const auto& [filename, filesize]: node.files ) {
+		cout << indent << filename << " (" << filesize << ")" << endl;
+	}
+}
+
+long
+part1_rec(const Node& node, long& all)
+{
+	long size = 0;
+
+	for ( const auto& [name, sub]: node.sub ) {
+		const auto sub_size = part1_rec(*sub.get(), all);
+		if ( sub_size <= 100000 ) {
+			all += sub_size;
+		}
+		size += sub_size;
+	}
+
+	for ( const auto& [filename, filesize]: node.files ) {
+		size += filesize;
+	}
+
+	return size;
+}
+
+void
+part1(const Node& node)
+{
+	long all = 0;
+	part1_rec(node, all);
+	cout << all << endl;
+}
+
+long
+part2_rec(const Node& node, vector<long>& sizes)
+{
+	long size = 0;
+
+	for ( const auto& [name, sub]: node.sub ) {
+		const auto sub_size = part2_rec(*sub.get(), sizes);
+		sizes.emplace_back(sub_size);
+		size += sub_size;
+	}
+
+	for ( const auto& [filename, filesize]: node.files ) {
+		size += filesize;
+	}
+
+	return size;
+}
+
+void
+part2(const Node& node)
+{
+	vector<long> sizes;
+	const auto   needed = 30000000 - (70000000 - part2_rec(node, sizes));
+
+	vector<long> candidates;
+	copy_if(begin(sizes), end(sizes), back_inserter(candidates), [&](auto size) {
+		return size >= needed;
+	});
+
+	sort(begin(candidates), end(candidates));
+	cout << candidates[0] << endl;
+}
+
+int
+main()
+{
+	struct NullBuffer : public streambuf {
+		int overflow(int chr) final { return chr; }
+	};
+
+	NullBuffer nullBuffer;
+	ostream    nullStream(&nullBuffer);
+
+	const auto node = read_file("data/day07.txt", nullStream);
+
+	part1(node);
+	part2(node);
+}
-- 
cgit v1.3