From 064cfef230e1b8dfa2ea5eccdbb857e93c6f9eef Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 3 Jan 2024 10:54:22 +0100
Subject: Lösung für Tag 12, Teil 2
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 src/day12.cpp | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 65 insertions(+), 8 deletions(-)

(limited to 'src/day12.cpp')

diff --git a/src/day12.cpp b/src/day12.cpp
index b01b2fb..11bd80b 100644
--- a/src/day12.cpp
+++ b/src/day12.cpp
@@ -1,5 +1,6 @@
 #include <fstream>
 #include <iostream>
+#include <map>
 #include <sstream>
 #include <string>
 #include <vector>
@@ -69,9 +70,9 @@ count_groups(string_view str)
 }
 
 long
-brute_force(string_view puzzle, const vector<long>& nums)
+brute_force(string_view springs, const vector<long>& groups)
 {
-	long counts = count_if(puzzle.begin(), puzzle.end(), [](char chr) { return chr == '?'; });
+	long counts = count_if(springs.begin(), springs.end(), [](char chr) { return chr == '?'; });
 
 	string test_pattern;
 
@@ -79,7 +80,7 @@ brute_force(string_view puzzle, const vector<long>& nums)
 	for ( size_t counter = 0; counter != (1U << size_t(counts)); ++counter ) {
 		auto bit_pattern = counter;
 
-		for ( char chr: puzzle ) {
+		for ( char chr: springs ) {
 			if ( chr == '?' ) {
 				if ( (bit_pattern & 1U) != 0U ) {
 					test_pattern += '.';
@@ -93,7 +94,7 @@ brute_force(string_view puzzle, const vector<long>& nums)
 				test_pattern += chr;
 			}
 		}
-		if ( nums == count_groups(test_pattern) ) {
+		if ( groups == count_groups(test_pattern) ) {
 			arrangements++;
 		}
 
@@ -103,16 +104,71 @@ brute_force(string_view puzzle, const vector<long>& nums)
 	return arrangements;
 }
 
+long
+count(const string& springs, const vector<long>& groups)
+{
+	map<tuple<string, vector<long>>, long> cache;
+
+	function<long(string, const vector<long>&)> count_rec = [&](string springs, const vector<long>& groups) -> long {
+		auto cached_value = cache.find(make_tuple(springs, groups));
+		if ( cached_value != cache.end() ) {
+			return cached_value->second;
+		}
+
+		springs.erase(0, springs.find_first_not_of('.'));
+
+		if ( springs.empty() ) {
+			return groups.empty() ? 1 : 0;
+		}
+
+		if ( groups.empty() ) {
+			return springs.find('#') == string_view::npos ? 1 : 0;
+		}
+
+		if ( springs[0] == '#' ) {
+			auto gidx = size_t(groups[0]);
+			if ( springs.length() < gidx || springs.substr(0, gidx).find('.') != string_view::npos || springs[gidx] == '#' ) {
+				return 0;
+			}
+
+			return count_rec(springs.substr(gidx + 1), { groups.begin() + 1, groups.end() });
+		}
+
+		auto value = count_rec(string("#") + springs.substr(1), groups) + count_rec(springs.substr(1), groups);
+
+		cache[make_tuple(springs, groups)] = value;
+
+		return value;
+	};
+
+	return count_rec(springs + ".", groups);
+}
+
 void
 part1(const vector<string>& input)
 {
 	auto sum = 0L;
 	for ( const auto& line: input ) {
-		auto parts  = split(line, ' ');
-		auto puzzle = parts[0];
-		auto nums   = read_ints(parts[1]);
+		auto parts   = split(line, ' ');
+		auto springs = parts[0];
+		auto groups  = read_ints(parts[1]);
+
+		sum += brute_force(springs, groups);
+		// sum += count(springs, groups);
+	}
+	cout << sum << endl;
+}
+
+void
+part2(const vector<string>& input)
+{
+	auto sum = 0L;
+	for ( const auto& line: input ) {
+		auto parts   = split(line, ' ');
+		auto springs = parts[0] + "?" + parts[0] + "?" + parts[0] + "?" + parts[0] + "?" + parts[0];
+		auto groups  = read_ints(parts[1] + "," + parts[1] + "," + parts[1] + "," + parts[1] + "," + parts[1]);
 
-		sum += brute_force(puzzle, nums);
+		sum += count(springs, groups);
 	}
 	cout << sum << endl;
 }
@@ -122,4 +178,5 @@ main()
 {
 	const auto input = read_file("data/day12.txt");
 	part1(input);
+	part2(input);
 }
-- 
cgit v1.3