From 21afde1f9f9e5869775c7c0b0b9e6ceb2d889ef9 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Mon, 6 Jan 2025 12:33:11 +0100
Subject: aoc 2015, day 24

---
 2015/src/day24.cpp | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 76 insertions(+)
 create mode 100644 2015/src/day24.cpp

(limited to '2015')

diff --git a/2015/src/day24.cpp b/2015/src/day24.cpp
new file mode 100644
index 0000000..e9966bb
--- /dev/null
+++ b/2015/src/day24.cpp
@@ -0,0 +1,76 @@
+#include <fstream>
+#include <iostream>
+#include <numeric>
+#include <vector>
+using namespace std;
+
+vector<long>
+read_file(string_view filename)
+{
+	fstream input{ filename };
+	return { istream_iterator<long>{ input }, {} };
+}
+
+template<typename Process>
+void
+combination(const vector<long>& values, size_t r, Process process)
+{
+	vector<bool> marker(values.size());
+
+	fill(marker.end() - ptrdiff_t(r), marker.end(), true);
+
+	vector<long> subset(r);
+
+	do {
+		subset.clear();
+		for ( size_t i = 0; i != values.size(); ++i ) {
+			if ( marker[i] ) {
+				subset.emplace_back(values[i]);
+			}
+		}
+		process(subset);
+	} while ( std::next_permutation(marker.begin(), marker.end()) );
+}
+
+void
+solve(const vector<long>& weights, long num)
+{
+	auto totalWeight = accumulate(weights.begin(), weights.end(), 0L);
+	auto groupWeight = totalWeight / num;
+
+	auto min_so_far = numeric_limits<long>::max();
+
+	for ( size_t i = 1; i < weights.size(); ++i ) {
+		combination(weights, i, [&](const vector<long>& subset) {
+			auto subWeight = accumulate(subset.begin(), subset.end(), 0L);
+			if ( subWeight == groupWeight ) {
+				auto product = accumulate(subset.begin(), subset.end(), 1L, multiplies<>());
+				min_so_far   = min(min_so_far, product);
+			}
+		});
+		if ( min_so_far != numeric_limits<long>::max() ) {
+			cout << min_so_far << endl;
+			return;
+		}
+	}
+}
+
+void
+part1(const vector<long>& weights)
+{
+	solve(weights, 3);
+}
+
+void
+part2(const vector<long>& weights)
+{
+	solve(weights, 4);
+}
+
+int
+main()
+{
+	auto weights = read_file("data/day24.txt");
+	part1(weights);
+	part2(weights);
+}
-- 
cgit v1.3