From e733679389d4facd44055dc7844a0441c5bee02e Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sun, 15 Dec 2024 17:09:27 +0100 Subject: aoc 2024, day 15, part 2 & bugfixes --- 2024/src/day15.cpp | 216 ++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 205 insertions(+), 11 deletions(-) (limited to '2024') diff --git a/2024/src/day15.cpp b/2024/src/day15.cpp index 5c2449b..94b8a2b 100644 --- a/2024/src/day15.cpp +++ b/2024/src/day15.cpp @@ -1,3 +1,4 @@ +#include #include #include #include @@ -8,10 +9,12 @@ #include using namespace std; -using pos_type = tuple; -using room_type = set; -using boxes_type = set; -using puzzle_type = tuple; +using pos_type = tuple; +using room_type = set; +using boxes_type = set; +using boxes2_type = map; +using puzzle_type = tuple; +using puzzle2_type = tuple; puzzle_type read_file(string_view filename) @@ -51,12 +54,59 @@ read_file(string_view filename) return { room, boxes, movements, start }; } -/* +puzzle2_type +read_file2(string_view filename) +{ + fstream input{ filename }; + room_type room; + boxes2_type boxes; + string movements; + pos_type start; + + size_t yPos = 0; + for ( string line; getline(input, line); ) { + if ( line.empty() ) { + continue; + } + + if ( line[0] == '#' ) { + for ( size_t xPos = 0; xPos != line.size(); ++xPos ) { + auto chr = line.at(xPos); + if ( chr == '#' ) { + room.emplace(xPos * 2, yPos); + room.emplace(xPos * 2 + 1, yPos); + } + else if ( chr == 'O' ) { + boxes.insert({ pos_type(xPos * 2, yPos), true }); + boxes.insert({ pos_type(xPos * 2 + 1, yPos), false }); + } + else if ( chr == '@' ) { + start = { xPos * 2, yPos }; + } + } + ++yPos; + } + else { + movements += line; + } + } + + return { room, boxes, movements, start }; +} + void print(const room_type& room, const boxes_type& boxes, const pos_type& pos) { - for ( size_t yPos = 0; yPos != 10; ++yPos ) { - for ( size_t xPos = 0; xPos != 10; ++xPos ) { + size_t width = 0; + size_t height = 0; + + for ( const auto& [x, y]: room ) { + width = max(width, x + 1); + height = max(height, y + 1); + } + + for ( size_t yPos = 0; yPos != height; ++yPos ) { + for ( size_t xPos = 0; xPos != width; ++xPos ) { if ( pos == pos_type{ xPos, yPos } ) { cout << '@'; } @@ -67,14 +117,45 @@ print(const room_type& room, const boxes_type& boxes, const pos_type& pos) cout << 'O'; } else { - cout << ' '; + cout << '.'; + } + } + cout << '\n'; + } + cout << endl; +} + +void +print(const room_type& room, const boxes2_type& boxes, const pos_type& pos) +{ + size_t width = 0; + size_t height = 0; + + for ( const auto& [x, y]: room ) { + width = max(width, x + 1); + height = max(height, y + 1); + } + + for ( size_t yPos = 0; yPos != height; ++yPos ) { + for ( size_t xPos = 0; xPos != width; ++xPos ) { + if ( pos == pos_type{ xPos, yPos } ) { + cout << '@'; + } + else if ( room.contains({ xPos, yPos }) ) { + cout << '#'; + } + else if ( boxes.contains({ xPos, yPos }) ) { + auto value = boxes.at({ xPos, yPos }); + cout << (value ? '[' : ']'); + } + else { + cout << '.'; } } cout << '\n'; } cout << endl; } -*/ optional can_move(const room_type& room, const boxes_type& boxes, pos_type start, pos_type direction) // NOLINT @@ -132,9 +213,122 @@ part1(const puzzle_type& puzzle) }) << endl; } +tuple +get_both_parts(const boxes2_type& boxes, pos_type pos) +{ + const auto [x, y] = pos; + if ( boxes.at(pos) ) { + return { pos, { x + 1, y } }; + } + else { + return { { x - 1, y }, pos }; + } +} + +optional +can_move(const room_type& room, const boxes2_type& all_boxes, pos_type start, pos_type direction) // NOLINT +{ + function(const boxes2_type&, size_t)> can_move_up_down = [&room, &all_boxes, &can_move_up_down](const boxes2_type& boxes, size_t dy) -> optional { + boxes2_type candidates; + + for ( const auto& [pos, b]: boxes ) { + const auto [x, y] = pos; + pos_type try_pos(x, y + dy); + + if ( room.contains(try_pos) ) { + return nullopt; + } + + if ( all_boxes.contains(try_pos) ) { + const auto [lhs, rhs] = get_both_parts(all_boxes, try_pos); + + assert(all_boxes.contains(lhs) && all_boxes.at(lhs) == true); // NOLINT + assert(all_boxes.contains(rhs) && all_boxes.at(rhs) == false); // NOLINT + + candidates.emplace(lhs, true); + candidates.emplace(rhs, false); + } + } + + if ( candidates.empty() ) { + return boxes2_type{}; + } + + if ( auto results = can_move_up_down(candidates, dy) ) { + for ( const auto& result: results.value() ) { + candidates.insert(result); + } + return candidates; + } + + return nullopt; + }; + + const auto [x, y] = start; + const auto [dx, dy] = direction; + + if ( dy != 0 ) { + return can_move_up_down({ { start, false } }, dy); + } + + boxes2_type candidates; + + size_t steps = 1; + while ( all_boxes.contains({ x + dx * steps, y + dy * steps }) ) { + auto foo = all_boxes.at({ x + dx * steps, y + dy * steps }); + candidates.insert({ { x + dx * steps, y + dy * steps }, foo }); + ++steps; + } + + if ( room.contains({ x + dx * steps, y + dy * steps }) ) { + return nullopt; + } + + return candidates; +} + +void +part2(const puzzle2_type& puzzle) +{ + map deltas = { + { '<', { -1, 0 } }, // Left + { '^', { 0, -1 } }, // Up + { '>', { 1, 0 } }, // Right + { 'v', { 0, 1 } } // Down + }; + + auto [room, boxes, movements, start] = puzzle; + + for ( auto chr: movements ) { + const auto delta = deltas[chr]; + if ( auto bitw = can_move(room, boxes, start, delta) ) { + const auto [dx, dy] = delta; + + get<0>(start) += dx; + get<1>(start) += dy; + + for ( const auto& [box, b]: bitw.value() ) { + boxes.erase(box); + } + + for ( auto [pos, b]: bitw.value() ) { + const auto [x, y] = pos; + boxes.emplace(pos_type{ x + dx, y + dy }, b); + } + } + } + + cout << accumulate(boxes.begin(), boxes.end(), 0UL, [](auto init, const auto& box) { + const auto& [pos, b] = box; + if ( !b ) { + return init; + } + return init + get<0>(pos) + 100 * get<1>(pos); + }) << endl; +} int main() { - const auto data = read_file("data/day15.txt"); - part1(data); + part1(read_file("data/day15.txt")); + part2(read_file2("data/day15.txt")); } -- cgit v1.3