From 8c96639ec1f6757570510fc27f1c5fabece35eaf Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sun, 16 Nov 2025 13:23:34 +0100 Subject: aoc 2018, days 1-11 --- 2018/data/.gitkeep | 0 2018/src/day01.cpp | 58 ++++++++++++++++ 2018/src/day02.cpp | 87 ++++++++++++++++++++++++ 2018/src/day03.cpp | 95 ++++++++++++++++++++++++++ 2018/src/day04.cpp | 135 +++++++++++++++++++++++++++++++++++++ 2018/src/day05.cpp | 101 ++++++++++++++++++++++++++++ 2018/src/day06.cpp | 152 +++++++++++++++++++++++++++++++++++++++++ 2018/src/day07.cpp | 194 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2018/src/day08.cpp | 88 ++++++++++++++++++++++++ 2018/src/day09.cpp | 113 +++++++++++++++++++++++++++++++ 2018/src/day10.cpp | 137 +++++++++++++++++++++++++++++++++++++ 2018/src/day11.cpp | 143 +++++++++++++++++++++++++++++++++++++++ 12 files changed, 1303 insertions(+) create mode 100644 2018/data/.gitkeep create mode 100644 2018/src/day01.cpp create mode 100644 2018/src/day02.cpp create mode 100644 2018/src/day03.cpp create mode 100644 2018/src/day04.cpp create mode 100644 2018/src/day05.cpp create mode 100644 2018/src/day06.cpp create mode 100644 2018/src/day07.cpp create mode 100644 2018/src/day08.cpp create mode 100644 2018/src/day09.cpp create mode 100644 2018/src/day10.cpp create mode 100644 2018/src/day11.cpp (limited to '2018') diff --git a/2018/data/.gitkeep b/2018/data/.gitkeep new file mode 100644 index 0000000..e69de29 diff --git a/2018/src/day01.cpp b/2018/src/day01.cpp new file mode 100644 index 0000000..d57a187 --- /dev/null +++ b/2018/src/day01.cpp @@ -0,0 +1,58 @@ +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector values; + + for ( long value = 0; file >> value; ) { + values.emplace_back(value); + } + + return values; +} + +void +part1(const vector& values) +{ + auto sum = accumulate(values.begin(), values.end(), 0L); + cout << "Part1: " << sum << '\n'; +} + +void +part2(const vector& values) +{ + unordered_set seen; + + long sum = 0; + for ( size_t idx = 0;; ++idx ) { + sum += values.at(idx % values.size()); + + if ( seen.contains(sum) ) { + cout << "Part2: " << sum << '\n'; + return; + } + + seen.emplace(sum); + } +} + +} // namespace + +int +main() +{ + auto values = read_file("data/day01.txt"); + part1(values); + part2(values); +} diff --git a/2018/src/day02.cpp b/2018/src/day02.cpp new file mode 100644 index 0000000..5dc6c7f --- /dev/null +++ b/2018/src/day02.cpp @@ -0,0 +1,87 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector +read_lines(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector lines; + + for ( string line; getline(file, line); ) { + lines.emplace_back(line); + } + + return lines; +} + +void +part1(const vector& lines) +{ + int twos = 0; + int threes = 0; + for ( const auto& line: lines ) { + map foo; + for ( const auto chr: line ) { + foo[chr]++; + } + + set counts; + for ( const auto& [chr, count]: foo ) { + counts.insert(count); + } + + if ( counts.contains(2) ) { + ++twos; + } + if ( counts.contains(3) ) { + ++threes; + } + } + cout << "Part 1: " << twos * threes << '\n'; +} + +void +part2(const vector& lines) +{ + for ( size_t i = 0; i != lines.size(); ++i ) { + for ( size_t j = i + 1; j != lines.size(); ++j ) { + const auto& lhs = lines.at(i); + const auto& rhs = lines.at(j); + + if ( lhs.length() != rhs.length() ) { + throw runtime_error("invalid data"); + } + + string result; + for ( size_t k = 0; k != lhs.length(); ++k ) { + if ( lhs[k] == rhs[k] ) { + result += lhs[k]; + } + } + + if ( result.length() + 1 == lhs.length() ) { + cout << "Part 2: " << result << '\n'; + return; + } + } + } +} + +} // namespace + +int +main() +{ + auto lines = read_lines("data/day02.txt"); + part1(lines); + part2(lines); +} diff --git a/2018/src/day03.cpp b/2018/src/day03.cpp new file mode 100644 index 0000000..bed3acb --- /dev/null +++ b/2018/src/day03.cpp @@ -0,0 +1,95 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +struct Claim { + int id; + int left; + int top; + int width; + int height; +}; + +#if 0 +ostream& +operator<<(ostream& ostrm, const Claim& claim) +{ + ostrm << "id: " << claim.id + << " (" << claim.left << ", " << claim.top << ": " << claim.width << "x" << claim.height; + return ostrm; +} +#endif + +vector +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector claims; + + regex pattern(R"#((\d+) @ (\d+),(\d+): (\d+)x(\d+))#"); + smatch match; + + for ( string line; getline(file, line); ) { + if ( !regex_search(line, match, pattern) ) { + continue; + } + + Claim claim{}; + claim.id = stoi(match[1]); + claim.left = stoi(match[2]); + claim.top = stoi(match[3]); + claim.width = stoi(match[4]); + claim.height = stoi(match[5]); + + claims.emplace_back(claim); + } + + return claims; +} + +void +solve(const vector& claims) +{ + map, vector> fabric; + set allIds; + + for ( const auto& claim: claims ) { + for ( int x = claim.left; x < claim.left + claim.width; ++x ) { + for ( int y = claim.top; y < claim.top + claim.height; ++y ) { + fabric[{ x, y }].emplace_back(claim.id); + } + } + allIds.emplace(claim.id); + } + + int overlapCount = 0; + for ( const auto& [pos, ids]: fabric ) { + if ( ids.size() > 1 ) { + ++overlapCount; + for ( const auto& id: ids ) { + allIds.erase(id); + } + } + } + + cout << "Part 1: " << overlapCount << '\n'; + cout << "Part 2: " << *allIds.begin() << '\n'; +} + +} // namespace + +int +main() +{ + auto claims = read_file("data/day03.txt"); + solve(claims); +} diff --git a/2018/src/day04.cpp b/2018/src/day04.cpp new file mode 100644 index 0000000..ea3c69f --- /dev/null +++ b/2018/src/day04.cpp @@ -0,0 +1,135 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +struct Record { + int guard_id; + long start_sleep; + long stop_sleep; +}; + +long +to_timestamp(const string& line) +{ + long year = stol(line.substr(1, 4)); + long mon = stol(line.substr(6, 2)); + long day = stol(line.substr(9, 2)); + long hour = stol(line.substr(12, 2)); + long min = stol(line.substr(15, 2)); + + auto timestamp = (year * 100'000'000) + (mon * 1'000'000) + (day * 10'000) + (hour * 100) + min; // NOLINT + + return timestamp; +} + +vector +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector lines; + + for ( string line; getline(file, line); ) { + lines.emplace_back(line); + } + + ranges::sort(lines); + + vector records; + + int guard = -1; + long start_sleep = -1; + long stop_sleep = -1; + for ( const auto& line: lines ) { + if ( line.find(" Guard #") != string::npos ) { + guard = stoi(line.substr(26)); + } + else if ( line.find(" falls asleep") != string::npos ) { + start_sleep = to_timestamp(line); + } + else if ( line.find(" wakes up") != string::npos ) { + stop_sleep = to_timestamp(line); + records.emplace_back(guard, start_sleep, stop_sleep); + } + } + + return records; +} + +void +part1(const vector& records) +{ + map sleep_amounts; + + for ( const auto& record: records ) { + sleep_amounts[record.guard_id] += record.stop_sleep - record.start_sleep; + } + + auto max_amount = ranges::max_element(sleep_amounts, + [](const auto& lhs, const auto& rhs) { + return lhs.second < rhs.second; + }); + + map sleep_counts; + + for ( const auto& record: records ) { + if ( record.guard_id != max_amount->first ) { + continue; + } + + for ( auto timestamp = record.start_sleep; timestamp != record.stop_sleep; ++timestamp ) { + sleep_counts[timestamp % 10'000]++; + } + } + + auto max_count = ranges::max_element(sleep_counts, + [](const auto& lhs, const auto& rhs) { + return lhs.second < rhs.second; + }); + + cout << "Part 1: " << max_amount->first * (max_count->first % 100) << '\n'; +} + +void +part2(const vector& records) +{ + map> sleep_counts; + + for ( const auto& record: records ) { + for ( auto timestamp = record.start_sleep; timestamp != record.stop_sleep; ++timestamp ) { + sleep_counts[record.guard_id][timestamp % 10'000]++; + } + } + + int found_guard = -1; + long found_min = -1; + unsigned max_count = 0; + for ( const auto& [id, times]: sleep_counts ) { + for ( const auto& [min, count]: times ) { + if ( count > max_count ) { + max_count = count; + found_guard = id; + found_min = min % 100; + } + } + } + + cout << "Part 2: " << found_guard * found_min << '\n'; +} + +} // namespace + +int +main() +{ + auto records = read_file("data/day04.txt"); + part1(records); + part2(records); +} diff --git a/2018/src/day05.cpp b/2018/src/day05.cpp new file mode 100644 index 0000000..9de484d --- /dev/null +++ b/2018/src/day05.cpp @@ -0,0 +1,101 @@ +#include +#include +#include +#include + +using namespace std; + +namespace { + +string +read_line(const filesystem::path& filename) +{ + ifstream file{ filename }; + string line; + getline(file, line); + return line; +} + +bool +xorEqual(char lhs, char rhs) +{ + return (lhs ^ (1 << 5)) == rhs; +} + +#if 0 +void +part1(string str) +{ + size_t idx = 1; + while ( idx < str.length() ) { + if ( xorEqual(str[idx - 1], str[idx]) ) { + str.erase(idx - 1, 2); + idx = 1; + } + else { + ++idx; + } + } + + cout << "Part 1: " << str.length() << '\n'; +} +#endif + +void +part1_opti(string_view str) +{ + string result; + + for ( const auto chr: str ) { + if ( !result.empty() && xorEqual(result.back(), chr) ) { + result.pop_back(); + } + else { + result.push_back(chr); + } + } + + cout << "Part 1: " << result.length() << '\n'; +} + +void +part2(string_view str) +{ + size_t min_length = str.size(); + for ( auto ch = 'a'; ch != 'z'; ++ch ) { + string result; + + for ( const auto chr: str ) { + if ( tolower(chr) == ch ) { + // nichts + } + else if ( !result.empty() && xorEqual(result.back(), chr) ) { + result.pop_back(); + } + else { + result.push_back(chr); + } + } + min_length = min(min_length, result.length()); + } + + cout << "Part 2: " << min_length << '\n'; +} + +} // namespace + +int +main() +{ + auto line = read_line("data/day05.txt"); + // part1(line); + part1_opti(line); + part2(line); + /* + cout << reduce("aA") << '\n'; + cout << reduce("abBA") << '\n'; + cout << reduce("abAB") << '\n'; + cout << reduce("aabAAB") << '\n'; + cout << reduce("dabAcCaCBAcCcaDA") << '\n'; + */ +} diff --git a/2018/src/day06.cpp b/2018/src/day06.cpp new file mode 100644 index 0000000..8701cbe --- /dev/null +++ b/2018/src/day06.cpp @@ -0,0 +1,152 @@ +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +using Point = tuple; + +set +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + set points; + + int x{}; + int y{}; + char sep{}; + + while ( file >> x >> sep >> y ) { + points.insert({ x, y }); + } + + return points; +} + +void +getBoundingBox(const set& points, Point& topLeft, Point& bottomRight) +{ + auto minX = numeric_limits::max(); + auto minY = numeric_limits::max(); + auto maxX = numeric_limits::min(); + auto maxY = numeric_limits::min(); + + for ( const auto [x, y]: points ) { + minX = min(minX, x); + minY = min(minY, y); + maxX = max(maxX, x); + maxY = max(maxY, y); + } + + topLeft = { minX, minY }; + bottomRight = { maxX, maxY }; +} + +int +manhattanDistance(const Point& lhs, const Point& rhs) +{ + int distance = abs(get<0>(lhs) - get<0>(rhs)) + abs(get<1>(lhs) - get<1>(rhs)); + + return distance; +} + +void +part1(const set& points) +{ + Point topLeft{}; + Point bottomRight{}; + getBoundingBox(points, topLeft, bottomRight); + + const auto [minX, minY] = topLeft; + const auto [maxX, maxY] = bottomRight; + + map areaCount; + set infinite; + + static const int offset = 1; + + for ( auto posX = minX - offset; posX <= maxX + offset; ++posX ) { + for ( auto posY = minY - offset; posY <= maxY + offset; ++posY ) { + int bestDistance = numeric_limits::max(); + Point bestPoint{}; + bool tie = false; + + for ( const auto& point: points ) { + int distance = manhattanDistance(point, { posX, posY }); + if ( distance < bestDistance ) { + bestDistance = distance; + bestPoint = point; + tie = false; + } + else if ( distance == bestDistance ) { + tie = true; + } + } + + if ( !tie ) { + areaCount[bestPoint]++; + + if ( posX < minX || posX > maxX || posY < minY || posY > maxY ) { + infinite.insert(bestPoint); + } + } + } + } + + int maxSize = 0; + for ( const auto& [point, size]: areaCount ) { + if ( infinite.contains(point) ) { + continue; + } + maxSize = max(maxSize, size); + } + + cout << "Part 1: " << maxSize << '\n'; +} + +void +part2(const set& points, const int threshold) +{ + Point topLeft{}; + Point bottomRight{}; + getBoundingBox(points, topLeft, bottomRight); + + const auto [minX, minY] = topLeft; + const auto [maxX, maxY] = bottomRight; + + static const int offset = 100; + + unsigned int regionSize = 0; + + for ( auto posX = minX - offset; posX <= maxX + offset; ++posX ) { + for ( auto posY = minY - offset; posY <= maxY + offset; ++posY ) { + int sum = 0; + + for ( const auto& point: points ) { + int distance = manhattanDistance(point, { posX, posY }); + sum += distance; + } + + if ( sum < threshold ) { + ++regionSize; + } + } + } + + cout << "Part 2: " << regionSize << '\n'; +} + +} // namespace + +int +main() +{ + auto points = read_file("data/day06.txt"); + part1(points); + part2(points, 10000); +} diff --git a/2018/src/day07.cpp b/2018/src/day07.cpp new file mode 100644 index 0000000..e6147d6 --- /dev/null +++ b/2018/src/day07.cpp @@ -0,0 +1,194 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector +split(const string& line) +{ + stringstream strm{ line }; + vector words; + + for ( string word; getline(strm, word, ' '); ) { + words.emplace_back(word); + } + + return words; +} + +map> +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + map> graph; + + for ( string line; getline(file, line); ) { + auto words = split(line); + graph[words.at(1)].emplace(words.at(7)); + } + + return graph; +} + +vector +topologicalSort(const map>& graph) +{ + map indegree; + + // Eingangsgrade initialisieren + for ( const auto& [node, neighbors]: graph ) { + if ( !indegree.contains(node) ) { + indegree[node] = 0; + } + for ( const auto& neighbor: neighbors ) { + indegree[neighbor]++; + } + } + + // Queue mit Knoten, deren Eingangsgrad 0 ist + priority_queue, greater<>> queue; + for ( const auto& [node, deg]: indegree ) { + if ( deg == 0 ) { + queue.push(node); + } + } + + vector sorted; + + // Kahn's Algorithmus + while ( !queue.empty() ) { + string node = queue.top(); + queue.pop(); + + sorted.push_back(node); + + if ( !graph.contains(node) ) { + continue; + } + + for ( const auto& neighbor: graph.at(node) ) { + indegree[neighbor]--; + if ( indegree[neighbor] == 0 ) { + queue.push(neighbor); + } + } + } + + // Prüfen auf Zyklus + if ( sorted.size() != indegree.size() ) { + throw runtime_error("Zyklus im Graph gefunden! Keine topologische Sortierung möglich."); + } + + return sorted; +} + +void +part1(const map>& graph) +{ + auto sorted = topologicalSort(graph); + + cout << "Part 1: "; + ranges::copy(sorted, ostream_iterator(cout)); + cout << '\n'; +} + +void +part2(const map>& graph, const int workers, const int base) +{ + map indegree; + + // Eingangsgrade initialisieren + for ( const auto& [node, neighbors]: graph ) { + if ( !indegree.contains(node) ) { + indegree[node] = 0; + } + for ( const auto& neighbor: neighbors ) { + indegree[neighbor]++; + } + } + + set available; + for ( const auto& [node, deg]: indegree ) { + if ( deg == 0 ) { + available.insert(node); + } + } + + set> finishing; + + int active_workers = 0; + int time = 0; + + while ( !indegree.empty() ) { + while ( !finishing.empty() && finishing.begin()->first == time ) { + auto [finish_time, node] = *finishing.begin(); + finishing.erase(finishing.begin()); + + active_workers--; + + indegree.erase(node); + + if ( !graph.contains(node) ) { + continue; + } + + for ( const auto& neighbor: graph.at(node) ) { + indegree[neighbor]--; + if ( indegree[neighbor] == 0 ) { + available.insert(neighbor); + } + } + } + + while ( active_workers < workers && !available.empty() ) { + auto node = *available.begin(); + available.erase(available.begin()); + + int duration = base + (node.at(0) - 'A' + 1); + int finish_time = time + duration; + + finishing.emplace(finish_time, node); + active_workers++; + } + + if ( finishing.empty() ) { + if ( available.empty() ) { + break; + } + else { + time++; + } + } + else { + time = finishing.begin()->first; + } + } + + cout << "Part 2: " << time << '\n'; +} + +} // namespace + +int +main() +{ + auto graph = read_file("data/day07.txt"); + try { + part1(graph); + + static const int WORKERS = 5; + static const int BASE = 60; + part2(graph, WORKERS, BASE); + } + catch ( exception& e ) { + cerr << "Fehler: " << e.what() << '\n'; + } +} diff --git a/2018/src/day08.cpp b/2018/src/day08.cpp new file mode 100644 index 0000000..9c2a093 --- /dev/null +++ b/2018/src/day08.cpp @@ -0,0 +1,88 @@ +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector data; + + for ( int number{}; file >> number; ) { + data.emplace_back(number); + } + + return data; +} + +void +part1(const vector& data) +{ + size_t idx = 0; + int sum = 0; + + function func = [&] { + auto count_child = data.at(idx++); + auto count_meta = data.at(idx++); + + while ( count_child-- > 0 ) { + func(); + } + + while ( count_meta-- > 0 ) { + sum += data.at(idx++); + } + }; + + func(); + + cout << "Part 1: " << sum << '\n'; +} + +void +part2(const vector& data) +{ + size_t idx = 0; + + function func = [&] { + const auto count_child = data.at(idx++); + const auto count_meta = data.at(idx++); + + vector child_values; + for ( int i = 0; i != count_child; ++i ) { + child_values.emplace_back(func()); + } + + int value = 0; + for ( int i = 0; i != count_meta; ++i ) { + auto meta = data.at(idx++); + if ( count_child == 0 ) { + value += meta; + } + else { + meta--; + if ( meta >= 0 && meta < count_child ) { + value += child_values[static_cast(meta)]; + } + } + } + return value; + }; + + cout << "Part 2: " << func() << '\n'; +} + +} // namespace + +int +main() +{ + auto data = read_file("data/day08.txt"); + part1(data); + part2(data); +} diff --git a/2018/src/day09.cpp b/2018/src/day09.cpp new file mode 100644 index 0000000..d1b4eb0 --- /dev/null +++ b/2018/src/day09.cpp @@ -0,0 +1,113 @@ +#include +#include + +using namespace std; + +namespace { + +struct Marble { + explicit Marble(long score) + : score{ score } + { + } + + Marble(long score, Marble* prev, Marble* next) + : score{ score } + , prev{ prev } + , next{ next } + { + } + + [[nodiscard]] + Marble* insert_after_two(long value) const + { + auto* insert_after = this->next; + + auto* new_marble = new Marble(value, insert_after, insert_after->next); // NOLINT + + insert_after->next->prev = new_marble; + insert_after->next = new_marble; + + return new_marble; + } + + [[nodiscard]] + pair remove_seventh_back() + { + auto* to_remove = this; + for ( int i = 0; i != 7; ++i ) { + to_remove = to_remove->prev; + } + + to_remove->prev->next = to_remove->next; + to_remove->next->prev = to_remove->prev; + + auto* new_current = to_remove->next; + auto score = to_remove->score; + + delete to_remove; // NOLINT + + return { new_current, score }; + } + + long score; + Marble* prev{ this }; + Marble* next{ this }; +}; + +long +solve(const size_t players, const long last_marble) +{ + auto current = new Marble(0); // NOLINT + + vector scores(players, 0); + size_t player = 0; + + for ( long marble = 1; marble <= last_marble; ++marble ) { + if ( marble % 23 != 0 ) { + current = current->insert_after_two(marble); + } + else { + auto [new_current, removed_score] = current->remove_seventh_back(); + + scores[player] += marble + removed_score; + current = new_current; + } + + player += 1; + player %= players; + } + + Marble* start = current; + do { + Marble* next = start->next; + delete start; // NOLINT + start = next; + } while ( start != current ); + + return ranges::max(scores); +} + +void +part1(const size_t players, const long last_marble) +{ + cout << "Part 1: " << solve(players, last_marble) << '\n'; +} + +void +part2(const size_t players, const long last_marble) +{ + cout << "Part 2: " << solve(players, last_marble * 100) << '\n'; +} + +} // namespace + +int +main() +{ + static const size_t players = 400; + static const long points = 71864; + + part1(players, points); + part2(players, points); +} diff --git a/2018/src/day10.cpp b/2018/src/day10.cpp new file mode 100644 index 0000000..43de95c --- /dev/null +++ b/2018/src/day10.cpp @@ -0,0 +1,137 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +struct Point { + long x; + long y; + long vx; + long vy; +}; + +vector +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + + static const regex pattern{ R"(position=<\s*(-?\d+)\s*,\s*(-?\d+)\s*>\s*velocity=<\s*(-?\d+)\s*,\s*(-?\d+)\s*>)" }; + + vector data; + for ( string line; getline(file, line); ) { + smatch match; + if ( regex_match(line, match, pattern) ) { + auto x = stol(match[1]); + auto y = stol(match[2]); + auto vx = stol(match[3]); + auto vy = stol(match[4]); + + data.emplace_back(x, y, vx, vy); + } + } + + return data; +} + +void +get_bounding_box(const vector& points, long& min_x, long& min_y, long& max_x, long& max_y) +{ + min_x = numeric_limits::max(); + min_y = numeric_limits::max(); + max_x = numeric_limits::min(); + max_y = numeric_limits::min(); + + for ( const auto& point: points ) { + min_x = min(min_x, point.x); + min_y = min(min_y, point.y); + max_x = max(max_x, point.x); + max_y = max(max_y, point.y); + } +} + +long +bounding_area(const vector& points) +{ + long min_x = 0; + long min_y = 0; + long max_x = 0; + long max_y = 0; + get_bounding_box(points, min_x, min_y, max_x, max_y); + return 1L * (max_x - min_x + 1) * (max_y - min_y + 1); +} + +void +update(vector& points) +{ + for ( auto& point: points ) { + point.x += point.vx; + point.y += point.vy; + } +} + +tuple> +get_best(vector points) +{ + auto best_area = numeric_limits::max(); + + vector best; + int best_t = 0; + + for ( int i = 0; i != 100'000; ++i ) { + update(points); + + auto area = bounding_area(points); + if ( area < best_area ) { + best_area = area; + best = points; + best_t = i + 1; + } + } + return { best_t, best }; +} + +void +print(const vector& points) +{ + set> grid; + for ( const auto [x, y, vx, vy]: points ) { + grid.emplace(x, y); + } + + long min_x = 0; + long min_y = 0; + long max_x = 0; + long max_y = 0; + get_bounding_box(points, min_x, min_y, max_x, max_y); + + for ( long y = min_y; y <= max_y; ++y ) { + for ( long x = min_x; x <= max_x; ++x ) { + cout << (grid.contains({ x, y }) ? '#' : ' '); + } + cout << '\n'; + } +} + +void +solve(const vector& points) +{ + auto [time, best_points] = get_best(points); + print(best_points); + cout << "Part 2: " << time << '\n'; +} + +} // namespace + +int +main() +{ + auto data = read_file("data/day10.txt"); + solve(data); +} diff --git a/2018/src/day11.cpp b/2018/src/day11.cpp new file mode 100644 index 0000000..1f8f9e2 --- /dev/null +++ b/2018/src/day11.cpp @@ -0,0 +1,143 @@ +#include +#include + +using namespace std; + +namespace { + +const int WIDTH = 300; +const int HEIGHT = 300; + +using Grid = map, int>; + +int +power_level(int x, int y, int serial) +{ + auto rack_id = x + 10; + auto level = rack_id * y; + level += serial; + level *= rack_id; + level /= 100; + level %= 10; + level -= 5; + return level; +} + +Grid +build_grid(int serial) +{ + Grid grid; + for ( int x = 1; x <= WIDTH; ++x ) { + for ( int y = 1; y <= HEIGHT; ++y ) { + grid[{ x, y }] = power_level(x, y, serial); + } + } + return grid; +} + +int +sum3x3(const Grid& grid, int x, int y) +{ + auto sum = 0; + for ( int dx = 0; dx != 3; ++dx ) { + for ( int dy = 0; dy != 3; ++dy ) { + sum += grid.at({ x + dx, y + dy }); + } + } + return sum; +} + +void +part1(const int serial) +{ + auto grid = build_grid(serial); + + auto best_sum = numeric_limits::min(); + auto best_x = 0; + auto best_y = 0; + + for ( int x = 1; x <= WIDTH - 2; ++x ) { + for ( int y = 1; y <= HEIGHT - 2; ++y ) { + if ( auto sum = sum3x3(grid, x, y); sum > best_sum ) { + best_sum = sum; + best_x = x; + best_y = y; + } + } + } + + cout << "Part 1: " << best_x << ',' << best_y << '\n'; +} + +Grid +pre_process(const Grid& grid) +{ + Grid sat; + + for ( int y = 1; y <= HEIGHT; ++y ) { + for ( int x = 1; x <= WIDTH; ++x ) { + const auto a = grid.at({ x, y }); + const auto b = (x > 1) ? sat.at({ x - 1, y }) : 0; + const auto c = (y > 1) ? sat.at({ x, y - 1 }) : 0; + const auto d = (x > 1 && y > 1) ? sat.at({ x - 1, y - 1 }) : 0; + + sat[{ x, y }] = a + b + c - d; + } + } + + return sat; +} + +int +get_safe(const Grid& grid, int x, int y) +{ + return (x < 1 || y < 1) ? 0 : grid.at({ x, y }); +} + +int +square_sum(const Grid& grid, int x, int y, int s) +{ + int x2 = x + s - 1; + int y2 = y + s - 1; + + return get_safe(grid, x2, y2) - get_safe(grid, x - 1, y2) - get_safe(grid, x2, y - 1) + get_safe(grid, x - 1, y - 1); +} + +void +part2(const int serial) +{ + static const int MAX_SIZE = 100; + + auto grid = pre_process(build_grid(serial)); + + auto best_sum = numeric_limits::min(); + auto best_x = 0; + auto best_y = 0; + auto best_s = 0; + + for ( int s = 1; s <= MAX_SIZE; ++s ) { + for ( int x = 1; x <= WIDTH - s + 1; ++x ) { + for ( int y = 1; y <= HEIGHT - s + 1; ++y ) { + if ( auto sum = square_sum(grid, x, y, s); sum > best_sum ) { + best_sum = sum; + best_x = x; + best_y = y; + best_s = s; + } + } + } + } + + cout << "Part 2: " << best_x << ',' << best_y << "," << best_s << '\n'; +} + +} // namespace + +int +main() +{ + static const int SERIAL = 7989; + + part1(SERIAL); + part2(SERIAL); +} -- cgit v1.3