aoc

commit 2882d009b115657afad463fadaa103ea54a920d8
parent 6bf92f2a2517f8eebddbdb139a877dcffd381edc
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Thu, 19 Dec 2024 06:32:23 +0100

Day 19 2024

Diffstat:
A
2024/19/.day19b.cpp.swp
 | 
0

A
2024/19/Makefile
 | 
24
++++++++++++++++++++++++
A
2024/19/day19a.cpp
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
2024/19/day19b.cpp
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++

4 files changed, 132 insertions(+), 0 deletions(-)
diff --git a/2024/19/.day19b.cpp.swp b/2024/19/.day19b.cpp.swp
Binary files differ.
diff --git a/2024/19/Makefile b/2024/19/Makefile
@@ -0,0 +1,24 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+	${CC} -o a.out day19a.cpp
+
+b:
+	${CC} -o b.out day19b.cpp
+
+clean:
+	rm -f a b
+
+atest: a
+	./a.out
+
+btest: b
+	./b.out
+
+arun: a
+	./a.out < input
+
+brun: b
+	./b.out < input
+
+.PHONY: a b clean atest btest arun brun
diff --git a/2024/19/day19a.cpp b/2024/19/day19a.cpp
@@ -0,0 +1,54 @@
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <ranges>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+vector<string> gettowels(const string& line) {
+	vector<string> ret;
+	int j = 0;
+	for (int i = 0; j != -1; i = j+2) {
+		j = line.find(",", i);
+		ret.push_back(line.substr(i, (j == -1 ? line.size() : j)-i));
+	}
+	return ret;
+}
+
+bool ispossible(const string& p, const vector<string>& towels, vector<int>& mem) {
+	if (p.size() == 0)
+		return true;
+	if (mem[p.size()] != -1)
+		return mem[p.size()];
+	for (auto t : towels) {
+		if (t == p.substr(0, t.size()))
+			if((mem[p.size()] = ispossible(p.substr(
+			    t.size(), p.size() - t.size()), towels, mem)))
+				return true;
+	}
+	return (mem[p.size()] = false);
+}
+
+int main() {
+	string line;
+	getline(cin, line);
+	auto towels = gettowels(line);
+	getline(cin, line);
+	vector<string> patterns;
+	while (getline(cin, line))
+		patterns.push_back(line);
+	vector<int> mem(1000);
+	int count = 0;
+	for (auto p : patterns) {
+		for (auto& m : mem) m = -1;
+		count += ispossible(p, towels, mem);
+	}
+	cout << count << endl;
+	return 0;
+}
diff --git a/2024/19/day19b.cpp b/2024/19/day19b.cpp
@@ -0,0 +1,54 @@
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <ranges>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+vector<string> gettowels(const string& line) {
+	vector<string> ret;
+	int j = 0;
+	for (int i = 0; j != -1; i = j+2) {
+		j = line.find(",", i);
+		ret.push_back(line.substr(i, (j == -1 ? line.size() : j)-i));
+	}
+	return ret;
+}
+
+int64_t countpossible(const string& p, const vector<string>& towels, vector<int64_t>& mem) {
+	if (p.size() == 0)
+		return 1;
+	if (mem[p.size()] != -1)
+		return mem[p.size()];
+	int64_t ret = 0;
+	for (auto t : towels) {
+		if (t == p.substr(0, t.size()))
+			ret += countpossible(p.substr(
+			    t.size(), p.size() - t.size()), towels, mem);
+	}
+	return (mem[p.size()] = ret);
+}
+
+int main() {
+	string line;
+	getline(cin, line);
+	auto towels = gettowels(line);
+	getline(cin, line);
+	vector<string> patterns;
+	while (getline(cin, line))
+		patterns.push_back(line);
+	vector<int64_t> mem(1000);
+	int64_t count = 0;
+	for (auto p : patterns) {
+		for (auto& m : mem) m = -1;
+		count += countpossible(p, towels, mem);
+	}
+	cout << count << endl;
+	return 0;
+}