From cd1db7e2b8e41d36102a652e40d9ba9c36e8ed8b Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Mon, 9 Dec 2024 20:13:15 +0100
Subject: aoc 2024, day 9, part 2

---
 2024/src/day09.cpp | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 88 insertions(+)

diff --git a/2024/src/day09.cpp b/2024/src/day09.cpp
index dd25a9d..7787c5c 100644
--- a/2024/src/day09.cpp
+++ b/2024/src/day09.cpp
@@ -1,7 +1,10 @@
 #include <fstream>
 #include <iostream>
 #include <iterator>
+#include <list>
+#include <ranges>
 #include <string>
+#include <vector>
 using namespace std;
 
 vector<int>
@@ -50,9 +53,94 @@ part1(const vector<int>& data)
 	cout << sum << endl;
 }
 
+void
+part2(const vector<int>& data)
+{
+	// id, pos, len
+	vector<tuple<int, size_t, size_t>> files;
+
+	// pos, len
+	list<tuple<size_t, size_t>> spaces;
+
+	for ( size_t i = 0; i != data.size(); ) {
+		// skip space
+		auto j = i;
+		while ( j != data.size() && data.at(j) == -1 ) {
+			++j;
+		}
+		if ( i != j ) {
+			spaces.emplace_back(i, j - i);
+		}
+		i = j;
+
+		while ( j != data.size() && data.at(i) == data.at(j) ) {
+			++j;
+		}
+		if ( i != j ) {
+			files.emplace_back(data.at(i), i, j - i);
+		}
+		i = j;
+	}
+
+	for ( auto& file: std::ranges::reverse_view(files) ) {
+		for ( auto it = spaces.begin(); it != spaces.end(); ++it ) {
+			if ( get<0>(*it) >= get<1>(file) ) {
+				spaces.erase(it, spaces.end());
+				break;
+			}
+			if ( get<1>(*it) >= get<2>(file) ) {
+				// update pos
+				get<1>(file) = get<0>(*it);
+
+				// update space len
+				get<1>(*it) -= get<2>(file);
+
+				// update space pos
+				get<0>(*it) += get<2>(file);
+
+				if ( get<1>(*it) == 0 ) {
+					spaces.erase(it);
+				}
+				break;
+			}
+		}
+	}
+
+	/*
+	for ( auto& file: std::ranges::reverse_view(files) ) {
+	    auto space = ranges::find_if(spaces, [&](const auto& space) -> bool {
+	        return get<1>(space) >= get<2>(file)  && get<0>(space) < get<1>(file);
+	    });
+	    if ( space != spaces.end() ) {
+	        // update pos
+	        get<1>(file) = get<0>(*space);
+
+	        // update space len
+	        get<1>(*space) -= get<2>(file);
+
+	        // update space pos
+	        get<0>(*space) += get<2>(file);
+
+	        if ( get<1>(*space) == 0 ) {
+	            spaces.erase(space);
+	        }
+	    }
+	}
+	*/
+
+	long sum = 0;
+	for ( const auto& [fid, pos, size]: files ) {
+		for ( size_t x = pos; x != pos + size; ++x ) {
+			sum += long(x) * fid;
+		}
+	}
+	cout << sum << endl;
+}
+
 int
 main()
 {
 	auto data = read_file("data/day09.txt");
 	part1(data);
+	part2(data);
 }
-- 
cgit v1.3