From 3f1e9844dbe58428e3b9528e9418c363266ceae4 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Wed, 19 Nov 2025 23:18:20 +0100 Subject: aoc 2018, days 13 & 14 --- 2018/src/day13.cpp | 217 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2018/src/day14.cpp | 88 ++++++++++++++++++++++ 2 files changed, 305 insertions(+) create mode 100644 2018/src/day13.cpp create mode 100644 2018/src/day14.cpp diff --git a/2018/src/day13.cpp b/2018/src/day13.cpp new file mode 100644 index 0000000..c764f7f --- /dev/null +++ b/2018/src/day13.cpp @@ -0,0 +1,217 @@ +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +enum class Direction : uint8_t { + Up, + Right, + Down, + Left +}; + +struct Cart { + size_t x; + size_t y; + Direction direction; + unsigned long intersection{}; +}; + +using Grid = vector; +using Carts = vector; + +tuple +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + + Grid data; + Carts carts; + + size_t y = 0; + for ( string line; getline(file, line); ) { + for ( size_t x = 0; x != line.size(); ++x ) { + using enum Direction; + + const char chr = line[x]; + if ( chr == '^' || chr == 'v' ) { + carts.emplace_back(x, y, chr == '^' ? Up : Down); + } + else if ( chr == '<' || chr == '>' ) { + carts.emplace_back(x, y, chr == '<' ? Left : Right); + } + } + data.emplace_back(line); + ++y; + } + + return { data, carts }; +} + +void +sort_carts(Carts& carts) +{ + ranges::sort(carts, + [](auto& lhs, auto& rhs) { + return tie(lhs.y, lhs.x) < tie(rhs.y, rhs.x); + }); +} + +void +move_cart(Cart& cart) +{ + using enum Direction; + + switch ( cart.direction ) { + case Up: + --cart.y; + break; + case Right: + ++cart.x; + break; + case Down: + ++cart.y; + break; + case Left: + --cart.x; + break; + } +} + +void +apply_direction_rules(const Grid& grid, Cart& cart) +{ + using enum Direction; + + const char chr = grid[cart.y][cart.x]; + switch ( chr ) { + case '/': + if ( cart.direction == Up ) { + cart.direction = Right; + } + else if ( cart.direction == Right ) { + cart.direction = Up; + } + else if ( cart.direction == Down ) { + cart.direction = Left; + } + else if ( cart.direction == Left ) { + cart.direction = Down; + } + break; + case '\\': + if ( cart.direction == Up ) { + cart.direction = Left; + } + else if ( cart.direction == Right ) { + cart.direction = Down; + } + else if ( cart.direction == Down ) { + cart.direction = Right; + } + else if ( cart.direction == Left ) { + cart.direction = Up; + } + break; + case '+': + switch ( cart.intersection++ % 3 ) { + case 0: + cart.direction = static_cast((static_cast(cart.direction) + 3) % 4); + break; + case 2: + cart.direction = static_cast((static_cast(cart.direction) + 1) % 4); + break; + default: + break; + }; + break; + default: + break; + } +} + +void +part1(const Grid& grid, Carts carts) +{ + while ( true ) { + sort_carts(carts); + + for ( size_t i = 0; i != carts.size(); ++i ) { + auto& cart = carts[i]; + + move_cart(cart); + apply_direction_rules(grid, cart); + + for ( size_t j = 0; j != carts.size(); ++j ) { + if ( i == j ) { + continue; + } + + const auto& other = carts[j]; + + if ( cart.x == other.x && cart.y == other.y ) { + cout << "Part 1: " << cart.x << ',' << cart.y << '\n'; + return; + } + } + } + } +} + +void +part2(const Grid& grid, Carts carts) +{ + while ( true ) { + sort_carts(carts); + + vector carts_to_be_removed; + + for ( size_t i = 0; i != carts.size(); ++i ) { + auto& cart = carts[i]; + + move_cart(cart); + apply_direction_rules(grid, cart); + + for ( size_t j = 0; j != carts.size(); ++j ) { + if ( i == j ) { + continue; + } + + const auto& other = carts[j]; + + if ( cart.x == other.x && cart.y == other.y ) { + carts_to_be_removed.emplace_back(i); + carts_to_be_removed.emplace_back(j); + } + } + } + + // remove carts + ranges::sort(carts_to_be_removed); + ranges::reverse(carts_to_be_removed); + + for ( auto num: carts_to_be_removed ) { + carts.erase(carts.begin() + static_cast(num)); + } + + if ( carts.size() == 1 ) { + cout << "Part 2: " << carts[0].x << ',' << carts[0].y << '\n'; + return; + } + } +} + +} // namespace + +int +main() +{ + auto [grid, carts] = read_file("data/day13.txt"); + part1(grid, carts); + part2(grid, carts); +} diff --git a/2018/src/day14.cpp b/2018/src/day14.cpp new file mode 100644 index 0000000..95d0717 --- /dev/null +++ b/2018/src/day14.cpp @@ -0,0 +1,88 @@ +#include +#include + +using namespace std; + +namespace { + +void +part1(const size_t n) +{ + vector v{ 3, 7 }; + size_t first = 0; + size_t second = 1; + + while ( v.size() < n + 10 ) { + auto value = v[first] + v[second]; + if ( value >= 10 ) { + v.emplace_back(1); + value -= 10; + } + v.emplace_back(value); + + first = (first + v[first] + 1) % v.size(); + second = (second + v[second] + 1) % v.size(); + } + + cout << "Part 1: "; + for ( size_t i = n; i != n + 10; ++i ) { + cout << v[i]; + } + cout << '\n'; +} + +void +part2(const size_t n) +{ + vector v{ 3, 7 }; + size_t first = 0; + size_t second = 1; + + const size_t len = to_string(n).length(); + + auto check = [&] { + if ( v.size() < len ) { + return false; + } + + size_t value = 0; + for ( size_t i = len; i > 0; --i ) { + value *= 10; + value += v[v.size() - i]; + } + + return value == n; + }; + + for ( ;; ) { + auto value = v[first] + v[second]; + if ( value >= 10 ) { + v.emplace_back(1); + if ( check() ) { + break; + } + + value -= 10; + } + + v.emplace_back(value); + if ( check() ) { + break; + } + + first = (first + v[first] + 1) % v.size(); + second = (second + v[second] + 1) % v.size(); + } + + cout << "Part 2: " << v.size() - len << '\n'; +} + +} // namespace + +int +main() +{ + const size_t input = 607331; + part1(input); + part2(input); +} -- cgit v1.3