From d396dc3221fcf893c885bd9a370b9a30f25b31dd Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 12 Jan 2025 17:36:26 +0100
Subject: aoc 2016, days 4, 5, 6

---
 2016/src/day04.cpp | 102 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 2016/src/day05.cpp |  74 ++++++++++++++++++++++++++++++++++++++
 2016/src/day06.cpp |  52 +++++++++++++++++++++++++++
 makefile           |   3 ++
 4 files changed, 231 insertions(+)
 create mode 100644 2016/src/day04.cpp
 create mode 100644 2016/src/day05.cpp
 create mode 100644 2016/src/day06.cpp

diff --git a/2016/src/day04.cpp b/2016/src/day04.cpp
new file mode 100644
index 0000000..713b16f
--- /dev/null
+++ b/2016/src/day04.cpp
@@ -0,0 +1,102 @@
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <regex>
+#include <set>
+#include <sstream>
+#include <string>
+#include <tuple>
+#include <vector>
+
+using namespace std;
+
+vector<string>
+split(const string& line, const regex& sep)
+{
+	return { sregex_token_iterator(line.begin(), line.end(), sep, -1), {} };
+}
+
+vector<tuple<vector<string>, long, string>>
+read_file(string_view filename)
+{
+	fstream input{ filename };
+
+	vector<tuple<vector<string>, long, string>> result;
+
+	for ( string line; getline(input, line); ) {
+		static const regex sep{ "[\\[\\]-]" };
+
+		auto parts = split(line, sep);
+
+		auto checksum = parts.at(parts.size() - 1);
+		parts.pop_back();
+
+		auto selector = stol(parts.at(parts.size() - 1));
+		parts.pop_back();
+
+		result.emplace_back(parts, selector, checksum);
+	}
+
+	return result;
+}
+
+void
+part1(const vector<tuple<vector<string>, long, string>>& data)
+{
+	long sum = 0;
+	for ( const auto& [ids, selector, checksum]: data ) {
+		map<char, long> counts;
+		for ( const auto& id: ids ) {
+			for ( const auto chr: id ) {
+				++counts[chr];
+			}
+		}
+
+		set<tuple<long, char>> tops;
+		for ( const auto& [chr, count]: counts ) {
+			tops.emplace(-count, chr);
+		}
+
+		string result;
+		for ( const auto& [count, chr]: tops ) {
+			result += chr;
+		}
+
+		if ( result.starts_with(checksum) ) {
+			sum += selector;
+		}
+	}
+	cout << sum << endl;
+}
+
+void
+part2(const vector<tuple<vector<string>, long, string>>& lines)
+{
+	auto rot = [](string str, int n) {
+		for ( auto& chr: str ) {
+			chr = ((chr - 'a' + n) % 26) + 'a';
+		}
+		return str;
+	};
+
+	auto is_northpole = [&](const string& str, int n) {
+		return rot(str, n) == "northpole";
+	};
+
+	for ( const auto& line: lines ) {
+		const auto& ids      = get<0>(line);
+		const auto  selector = get<1>(line);
+		if ( ranges::any_of(ids, [&](auto& str) { return is_northpole(str, (int) selector); }) ) {
+			cout << selector << endl;
+			return;
+		}
+	}
+}
+
+int
+main()
+{
+	auto data = read_file("data/day04.txt");
+	part1(data);
+	part2(data);
+}
diff --git a/2016/src/day05.cpp b/2016/src/day05.cpp
new file mode 100644
index 0000000..dfce653
--- /dev/null
+++ b/2016/src/day05.cpp
@@ -0,0 +1,74 @@
+// Standard C++
+#include <array>
+#include <fstream>
+#include <iostream>
+#include <string>
+
+// Standard C
+#include <cstdlib> // memcmp
+
+// System
+#include <md5.h>
+
+using namespace std;
+
+void
+part1(string_view puzzle)
+{
+	array<char, MD5_DIGEST_STRING_LENGTH> digest{};
+
+	string result;
+
+	string input;
+	for ( unsigned long counter = 0;; ++counter ) {
+		input = puzzle;
+		input += to_string(counter);
+		MD5Data(input.data(), input.size(), digest.data());
+
+		if ( memcmp(digest.data(), "00000", 5) == 0 ) {
+			result += digest.at(5);
+			if ( result.length() == 8 ) {
+				cout << result << endl;
+				return;
+			}
+		}
+	}
+}
+
+void
+part2(string_view puzzle)
+{
+	array<char, MD5_DIGEST_STRING_LENGTH> digest{};
+
+	string result = "________";
+
+	string input;
+	for ( unsigned long counter = 0;; ++counter ) {
+		input = puzzle;
+		input += to_string(counter);
+		MD5Data(input.data(), input.size(), digest.data());
+
+		if ( memcmp(digest.data(), "00000", 5) == 0 ) {
+			auto position = digest.at(5) - '0';
+			if ( position < 0 || position > 7 ) {
+				continue;
+			}
+			if ( result.at(size_t(position)) != '_' ) {
+				continue;
+			}
+			result.at(size_t(position)) = digest.at(6);
+			if ( result.find('_') == string::npos ) {
+				cout << result << endl;
+				return;
+			}
+		}
+	}
+}
+
+int
+main()
+{
+	auto puzzle = "reyedfim"s;
+	part1(puzzle);
+	part2(puzzle);
+}
diff --git a/2016/src/day06.cpp b/2016/src/day06.cpp
new file mode 100644
index 0000000..5bd0f93
--- /dev/null
+++ b/2016/src/day06.cpp
@@ -0,0 +1,52 @@
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <regex>
+#include <set>
+#include <sstream>
+#include <string>
+#include <tuple>
+#include <vector>
+
+using namespace std;
+
+vector<string>
+read_file(string_view filename)
+{
+	fstream input{ filename };
+
+	vector<string> lines;
+
+	for ( string line; getline(input, line); ) {
+		lines.emplace_back(line);
+	}
+
+	return lines;
+}
+
+void
+solve(const vector<string>& lines)
+{
+	string part1;
+	string part2;
+
+	for ( size_t col = 0; col != lines[0].length(); ++col ) {
+		map<char, size_t> counts;
+		for ( const auto& line: lines ) {
+			++counts[line[col]];
+		}
+
+		part1 += max_element(counts.begin(), counts.end(), [](auto lhs, auto rhs) { return lhs.second < rhs.second; })->first;
+		part2 += min_element(counts.begin(), counts.end(), [](auto lhs, auto rhs) { return lhs.second < rhs.second; })->first;
+	}
+
+	cout << part1 << '\n'
+	     << part2 << endl;
+}
+
+int
+main()
+{
+	auto lines = read_file("data/day06.txt");
+	solve(lines);
+}
diff --git a/makefile b/makefile
index 5ce2c9a..ffd0a23 100644
--- a/makefile
+++ b/makefile
@@ -21,6 +21,9 @@ all: $(patsubst 2015/src/%.cpp,2015/bin/%,$(wildcard 2015/src/*.cpp)) \
 2016/bin/%: 2016/src/%.cpp | 2016/bin
 	c++ $(CPPFLAGS) $^ -o $@
 
+2016/bin/day05: 2016/src/day05.cpp | 2016/bin
+	c++ $(CPPFLAGS) $^ -lmd -o $@
+
 # 2020
 2020/bin/%: 2020/src/%.cpp | 2020/bin
 	c++ $(CPPFLAGS) $^ -o $@
-- 
cgit v1.3