From ccf0e4ab6360b0038ed9a8c44dad840f5979230e Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 17 Nov 2024 15:54:02 +0100
Subject: aoc 2015, day 17

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

(limited to '2015/src/day17.cpp')

diff --git a/2015/src/day17.cpp b/2015/src/day17.cpp
new file mode 100644
index 0000000..df70a31
--- /dev/null
+++ b/2015/src/day17.cpp
@@ -0,0 +1,118 @@
+#include <algorithm>
+#include <fstream>
+#include <iostream>
+#include <set>
+#include <vector>
+using namespace std;
+
+auto
+read_file(string_view filename)
+{
+	fstream      input{ filename };
+	vector<long> records;
+
+	for ( long value{}; input >> value; ) {
+		records.emplace_back(value);
+	}
+	return records;
+}
+
+// https://stackoverflow.com/a/1617797
+template<typename Iterator>
+bool
+next_combination(const Iterator first, Iterator k, const Iterator last)
+{
+	if ( (first == last) || (first == k) || (last == k) )
+		return false;
+	Iterator i1 = first;
+	Iterator i2 = last;
+	++i1;
+	if ( last == i1 )
+		return false;
+	i1 = last;
+	--i1;
+	i1 = k;
+	--i2;
+	while ( first != i1 ) {
+		if ( *--i1 < *i2 ) {
+			Iterator j = k;
+			while ( !(*i1 < *j) )
+				++j;
+			std::iter_swap(i1, j);
+			++i1;
+			++j;
+			i2 = k;
+			std::rotate(i1, j, last);
+			while ( last != j ) {
+				++j;
+				++i2;
+			}
+			std::rotate(k, i2, last);
+			return true;
+		}
+	}
+	std::rotate(first, k, last);
+	return false;
+}
+
+void
+part1(const vector<long>& values)
+{
+	vector<size_t> indicies;
+	for ( size_t idx = 0; idx != values.size(); ++idx ) {
+		indicies.emplace_back(idx);
+	}
+
+	long count = 0;
+	for ( size_t comp_size = 1; comp_size != values.size(); ++comp_size ) {
+		sort(indicies.begin(), indicies.end());
+
+		do {
+			long sum = 0;
+			for ( size_t idx = 0; idx != comp_size; ++idx ) {
+				sum += values[indicies[idx]];
+			}
+			if ( sum == 150 ) {
+				count++;
+			}
+		} while ( next_combination(indicies.begin(), indicies.begin() + (long) comp_size, indicies.end()) );
+	}
+	cout << count << endl;
+}
+
+void
+part2(const vector<long>& values)
+{
+	vector<size_t> indicies;
+	for ( size_t idx = 0; idx != values.size(); ++idx ) {
+		indicies.emplace_back(idx);
+	}
+
+	long count = 0;
+	for ( size_t comp_size = 1; comp_size != values.size(); ++comp_size ) {
+		sort(indicies.begin(), indicies.end());
+
+		do {
+			long sum = 0;
+			for ( size_t idx = 0; idx != comp_size; ++idx ) {
+				sum += values[indicies[idx]];
+			}
+			if ( sum == 150 ) {
+				count++;
+			}
+		} while ( next_combination(indicies.begin(), indicies.begin() + (long) comp_size, indicies.end()) );
+
+		if ( count != 0 ) {
+			cout << count << endl;
+			return;
+		}
+	}
+}
+
+int
+main()
+{
+	auto records = read_file("data/day17.txt");
+	part1(records);
+	part2(records);
+}
-- 
cgit v1.3