From 56e890cec0a28c0a485212ccebfaf774235a79a2 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Wed, 3 Jan 2024 23:35:54 +0100 Subject: prepare for more puzzles ... :) --- 2023/src/day01.cpp | 82 +++++++++++++++ 2023/src/day02.cpp | 100 ++++++++++++++++++ 2023/src/day03.cpp | 174 +++++++++++++++++++++++++++++++ 2023/src/day04.cpp | 114 +++++++++++++++++++++ 2023/src/day05.cpp | 183 +++++++++++++++++++++++++++++++++ 2023/src/day06.cpp | 74 ++++++++++++++ 2023/src/day07.cpp | 189 ++++++++++++++++++++++++++++++++++ 2023/src/day08.cpp | 110 ++++++++++++++++++++ 2023/src/day09.cpp | 75 ++++++++++++++ 2023/src/day10.cpp | 216 +++++++++++++++++++++++++++++++++++++++ 2023/src/day11.cpp | 100 ++++++++++++++++++ 2023/src/day12.cpp | 182 +++++++++++++++++++++++++++++++++ 2023/src/day13.cpp | 115 +++++++++++++++++++++ 2023/src/day14.cpp | 239 +++++++++++++++++++++++++++++++++++++++++++ 2023/src/day15.cpp | 102 +++++++++++++++++++ 2023/src/day16.cpp | 132 ++++++++++++++++++++++++ 2023/src/day17.cpp | 112 ++++++++++++++++++++ 2023/src/day18.cpp | 115 +++++++++++++++++++++ 2023/src/day19.cpp | 183 +++++++++++++++++++++++++++++++++ 2023/src/day20.cpp | 293 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2023/src/day21.cpp | 148 +++++++++++++++++++++++++++ 2023/src/day22.cpp | 157 ++++++++++++++++++++++++++++ 2023/src/day23.cpp | 152 +++++++++++++++++++++++++++ 2023/src/day24.cpp | 173 +++++++++++++++++++++++++++++++ 2023/src/day25.cpp | 140 +++++++++++++++++++++++++ 25 files changed, 3660 insertions(+) create mode 100644 2023/src/day01.cpp create mode 100644 2023/src/day02.cpp create mode 100644 2023/src/day03.cpp create mode 100644 2023/src/day04.cpp create mode 100644 2023/src/day05.cpp create mode 100644 2023/src/day06.cpp create mode 100644 2023/src/day07.cpp create mode 100644 2023/src/day08.cpp create mode 100644 2023/src/day09.cpp create mode 100644 2023/src/day10.cpp create mode 100644 2023/src/day11.cpp create mode 100644 2023/src/day12.cpp create mode 100644 2023/src/day13.cpp create mode 100644 2023/src/day14.cpp create mode 100644 2023/src/day15.cpp create mode 100644 2023/src/day16.cpp create mode 100644 2023/src/day17.cpp create mode 100644 2023/src/day18.cpp create mode 100644 2023/src/day19.cpp create mode 100644 2023/src/day20.cpp create mode 100644 2023/src/day21.cpp create mode 100644 2023/src/day22.cpp create mode 100644 2023/src/day23.cpp create mode 100644 2023/src/day24.cpp create mode 100644 2023/src/day25.cpp (limited to '2023/src') diff --git a/2023/src/day01.cpp b/2023/src/day01.cpp new file mode 100644 index 0000000..ff357bc --- /dev/null +++ b/2023/src/day01.cpp @@ -0,0 +1,82 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +void +part1() +{ + string digits{ "0123456789" }; + fstream input{ "data/day01.txt" }; + + int sum = 0; + for ( string line; input >> line; ) { + auto first = find_first_of(begin(line), end(line), begin(digits), end(digits)); + auto last = find_first_of(rbegin(line), rend(line), begin(digits), end(digits)); + + auto value = (*first - '0') * 10 + (*last - '0'); + + sum += value; + } + cout << sum << endl; +} + +void +part2() +{ + map map{ + { "0", 0 }, + { "1", 1 }, + { "2", 2 }, + { "3", 3 }, + { "4", 4 }, + { "5", 5 }, + { "6", 6 }, + { "7", 7 }, + { "8", 8 }, + { "9", 9 }, + { "one", 1 }, + { "two", 2 }, + { "three", 3 }, + { "four", 4 }, + { "five", 5 }, + { "six", 6 }, + { "seven", 7 }, + { "eight", 8 }, + { "nine", 9 }, + }; + + fstream input{ "data/day01.txt" }; + + auto sum = 0; + for ( string line; input >> line; ) { + string sub; + vector digits; + + for ( auto ch: line ) { + sub += ch; + + for ( const auto& word: map ) { + if ( sub.ends_with(word.first) ) { + digits.push_back(word.second); + } + } + } + + auto first = digits.front(); + auto last = digits.back(); + + sum += (first * 10) + last; + } + cout << sum << endl; +} + +int +main() +{ + part1(); + part2(); +} diff --git a/2023/src/day02.cpp b/2023/src/day02.cpp new file mode 100644 index 0000000..aa3d5a2 --- /dev/null +++ b/2023/src/day02.cpp @@ -0,0 +1,100 @@ +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +vector +split(const string& line, char sep) +{ + vector parts; + stringstream input{ line }; + + for ( string part; getline(input, part, sep); ) { + parts.emplace_back(part); + } + + return parts; +} + +void +part1() +{ + fstream input{ "data/day02.txt" }; + + auto sum = 0; + for ( string line; getline(input, line); ) { + auto game = split(line, ':'); + + auto gameId = 0; + sscanf(game[0].data(), "Game %d", &gameId); // NOLINT + + auto subsets = split(game[1], ';'); + + auto fail = false; + + for ( const auto& subset: subsets ) { + auto cubes = split(subset, ','); + + map counts{}; + + for ( const auto& cube: cubes ) { + auto data = split(cube, ' '); + + auto count = stoi(data[1]); + auto color = data[2]; + + counts[color] += count; + } + + fail |= (counts["red"] > 12) || (counts["green"] > 13) || (counts["blue"] > 14); // NOLINT + } + + if ( !fail ) { + sum += gameId; + } + } + cout << sum << endl; +} + +void +part2() +{ + fstream input{ "data/day02.txt" }; + + auto sum = 0; + + for ( string line; getline(input, line); ) { + auto game = split(line, ':'); + + auto subsets = split(game[1], ';'); + + map colors{}; + + for ( const auto& subset: subsets ) { + auto cubes = split(subset, ','); + + for ( const auto& cube: cubes ) { + auto data = split(cube, ' '); + + auto count = stoi(data[1]); + auto color = data[2]; + + colors[color] = max(colors[color], count); + } + } + sum += colors["red"] * colors["green"] * colors["blue"]; + } + cout << sum << endl; +} + +int +main() +{ + part1(); + part2(); +} diff --git a/2023/src/day03.cpp b/2023/src/day03.cpp new file mode 100644 index 0000000..b266f59 --- /dev/null +++ b/2023/src/day03.cpp @@ -0,0 +1,174 @@ +#include +#include +#include +#include +#include +#include + +using namespace std; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +bool +is_digit(char chr) +{ + return std::isdigit(static_cast(chr)) != 0; +} + +vector> +positions(size_t row, size_t col) +{ + return { + { row - 1, col - 1 }, + { row - 0, col - 1 }, + { row + 1, col - 1 }, + + { row - 1, col }, + { row + 1, col }, + + { row - 1, col + 1 }, + { row - 0, col + 1 }, + { row + 1, col + 1 }, + }; +} + +void +part1() // NOLINT +{ + auto lines = read_file("data/day03.txt"); + + auto is_symbol = [&lines](size_t row, size_t col) -> bool { + static const string symbols{ "*#+$%=-@&/" }; + + if ( row >= lines.size() || col >= lines[row].size() ) { + return false; + } + + auto symbol = lines[row][col]; + + return symbols.find(symbol) != string::npos; + }; + + auto bordering = [&is_symbol](size_t row, size_t col) -> bool { + bool result = false; + + for (const auto& position: positions(row, col)) { + result |= is_symbol(get<0>(position), get<1>(position)); + } + + return result; + }; + + auto sum = 0; + for ( size_t row = 0; row != lines.size(); ++row ) { + const auto& line = lines[row]; + + string::size_type start = 0; + while ( start != line.size() ) { + while ( start != line.size() && !is_digit(line[start]) ) { + ++start; + } + + auto end = start; + while ( end != line.size() && is_digit(line[end]) ) { + ++end; + } + + if ( start != end ) { + auto result = false; + + for ( auto col = start; col != end; ++col ) { + result |= bordering(row, col); + } + + if ( result ) { + sum += stoi(line.substr(start, end - start)); + } + + start = end; + } + } + } + cout << sum << endl; +} + +void +part2() // NOLINT +{ + auto lines = read_file("data/day03.txt"); + + auto find_integer = [](vector& lines, size_t row, size_t col, int& value) -> bool { // NOLINT + if ( row >= lines.size() || col >= lines[row].size() ) { + return false; + } + + auto& line = lines[row]; + + if ( !is_digit(line[col]) ) { + return false; + } + + // Anfang der Zahl suchen + auto start = col; + for ( ; start != 0 && is_digit(line[start - 1]); --start ) // NOLINT + ; + + auto end = col; + for ( ; end != line.size() && is_digit(line[end]); ++end ) // NOLINT + ; + + value = stoi(line.substr(start, end - start)); + + for ( ; start != end; ++start ) { + line[start] = '.'; + } + + return true; + }; + + auto sum = 0; + for ( size_t row = 0; row != lines.size(); ++row ) { + const auto& line = lines[row]; + + auto col = line.find('*'); + while ( col != string::npos ) { + vector values; + + auto lines_copy{ lines }; + + for ( const auto& position: positions(row, col) ) { + auto value = 0; + + if ( find_integer(lines_copy, get<0>(position), get<1>(position), value) ) { + values.emplace_back(value); + } + } + + if ( values.size() == 2 ) { + auto ratio = values[0] * values[1]; + sum += ratio; + } + + col = line.find('*', col + 1); + } + } + cout << sum << endl; +} + +int +main() +{ + part1(); + part2(); +} diff --git a/2023/src/day04.cpp b/2023/src/day04.cpp new file mode 100644 index 0000000..0d3e552 --- /dev/null +++ b/2023/src/day04.cpp @@ -0,0 +1,114 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +vector +split(const string& line, char sep) +{ + stringstream input{ line }; + vector parts; + + for ( string part; getline(input, part, sep); ) { + parts.emplace_back(part); + } + + return parts; +} + +template +Container +read_ints(const string& line) +{ + Container container{}; + stringstream input{ line }; + + for ( typename Container::value_type value; input >> value; ) { + container.emplace(value); + } + + return container; +} + +auto +build_data_set(string_view filename) +{ + vector values; + + for ( const auto& line: read_file(filename) ) { + const auto cards = split(line, ':'); + const auto numbers = split(cards[1], '|'); + + const auto winning_numbers = read_ints>(numbers[0]); + const auto card_numbers = read_ints>(numbers[1]); + + auto count = 0U; + for ( auto number: winning_numbers ) { + if ( card_numbers.contains(number) ) { + ++count; + } + } + values.emplace_back(count); + } + + return values; +} + +void +pass1(const vector& values) +{ + auto sum = 0U; + for ( auto value: values ) { + if ( value != 0 ) { + sum += (1U << (value - 1)); + } + } + + cout << sum << endl; +} + +void +pass2(const vector& values) +{ + auto count = 0U; + + function process = [&](size_t start, size_t end) -> void { + for ( ; start != end; ++start ) { + auto value = values[start]; + + ++count; + + process(start + 1, start + value + 1); + } + }; + + process(0, values.size()); + + cout << count << endl; +} + +int +main() +{ + const auto values = build_data_set("data/day04.txt"); + pass1(values); + pass2(values); +} diff --git a/2023/src/day05.cpp b/2023/src/day05.cpp new file mode 100644 index 0000000..42fda29 --- /dev/null +++ b/2023/src/day05.cpp @@ -0,0 +1,183 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +struct Entry { + Entry(long destination, long source, long amount) // NOLINT + : destination_(destination) + , source_(source) + , amount_(amount) + { + } + + [[nodiscard]] bool in_range(long value) const + { + return source_ <= value && value < (source_ + amount_); + } + + [[nodiscard]] long get_destination(long value) const + { + auto delta = value - source_; + return destination_ + delta; + } + + long destination_; + long source_; + long amount_; +}; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +vector +split(const string& line, char sep) +{ + vector parts; + stringstream input{ line }; + + for ( string part; getline(input, part, sep); ) { + parts.emplace_back(part); + } + + return parts; +} + +void +part1(const vector& lines) +{ + auto read_ints = [](const string& line) { + stringstream iss{ line }; + return vector{ istream_iterator{ iss }, istream_iterator{} }; + }; + + auto seeds = read_ints(lines[0].substr(6)); + + map category_mapping; + map> range_mapping; + + // read blocks + for ( size_t idx = 1; idx < lines.size(); ) { + ++idx; // skip empty line + + auto description = lines[idx++]; + description.erase(description.find(' ')); + auto parts = split(description, '-'); + + category_mapping[parts[0]] = parts[2]; + + vector mapping; + + for ( ; idx < lines.size() && !lines[idx].empty(); ++idx ) { + auto values = read_ints(lines[idx]); + + auto destination = values[0]; + auto source = values[1]; + auto amount = values[2]; + + mapping.emplace_back(destination, source, amount); + } + + range_mapping[parts[0]] = mapping; + } + + auto min_value = numeric_limits::max(); + for ( auto seed: seeds ) { + for ( string category{ "seed" }; !category.empty(); category = category_mapping[category] ) { + const auto& ranges = range_mapping[category]; + + for (const auto& range: ranges) { + if (range.in_range(seed)) { + seed = range.get_destination(seed); + break; + } + } + } + min_value = min(min_value, seed); + } + cout << min_value << endl; +} + +void +part2(const vector& lines) +{ + auto read_ints = [](const string& line) { + stringstream iss{ line }; + return vector{ istream_iterator{ iss }, istream_iterator{} }; + }; + + auto seeds = read_ints(lines[0].substr(6)); + + map category_mapping; + map> range_mapping; + + // read blocks + for ( size_t idx = 1; idx < lines.size(); ) { + ++idx; // skip empty line + + auto description = lines[idx++]; + description.erase(description.find(' ')); + auto parts = split(description, '-'); + + category_mapping[parts[0]] = parts[2]; + + vector mapping; + + for ( ; idx < lines.size() && !lines[idx].empty(); ++idx ) { + auto values = read_ints(lines[idx]); + + auto destination = values[0]; + auto source = values[1]; + auto amount = values[2]; + + mapping.emplace_back(destination, source, amount); + } + + range_mapping[parts[0]] = mapping; + } + + // brute force -- slow, but works + auto min_value = numeric_limits::max(); + for ( size_t idx = 0; idx != seeds.size(); idx += 2 ) { + for ( auto start = seeds[idx]; start != seeds[idx] + seeds[idx+1]; ++start ) { + auto seed = start; + + for ( string category{ "seed" }; !category.empty(); category = category_mapping[category] ) { + const auto& ranges = range_mapping[category]; + + for (const auto& range: ranges) { + if (range.in_range(seed)) { + seed = range.get_destination(seed); + break; + } + } + } + min_value = min(min_value, seed); + } + } + cout << min_value << endl; +} + +int +main() +{ + auto lines = read_file("data/day05.txt"); + part1(lines); + part2(lines); +} diff --git a/2023/src/day06.cpp b/2023/src/day06.cpp new file mode 100644 index 0000000..9a429c5 --- /dev/null +++ b/2023/src/day06.cpp @@ -0,0 +1,74 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +template +vector +read_ints(const string& line) +{ + stringstream iss{ line }; + return vector{ istream_iterator{ iss }, istream_iterator{} }; +} + +long +solve(long time, long winningDistance) +{ + long counter = 0; + for ( long pushTime = 0; pushTime < time; ++pushTime ) { + auto distance = (time * pushTime - pushTime * pushTime); + counter += long(distance > winningDistance); + } + return counter; +} + +void +part1() +{ + fstream input{ "data/day06.txt" }; + string line; + + getline(input, line); + auto times = read_ints(line.substr(line.find(':') + 1)); + + getline(input, line); + auto distances = read_ints(line.substr(line.find(':') + 1)); + + long result = 1; + for ( size_t idx = 0; idx != times.size(); ++idx ) { + result *= solve(times[idx], distances[idx]); + } + cout << result << endl; +} + +string +join(const string& line) +{ + stringstream iss{ line }; + return accumulate(istream_iterator{ iss }, istream_iterator{}, string{}); +} + +void +part2() +{ + fstream input{ "data/day06.txt" }; + string line; + + getline(input, line); + auto time = stol(join(line.substr(line.find(':') + 1))); + + getline(input, line); + auto distance = stol(join(line.substr(line.find(':') + 1))); + + cout << solve(time, distance) << endl; +} + +int +main() +{ + part1(); + part2(); +} diff --git a/2023/src/day07.cpp b/2023/src/day07.cpp new file mode 100644 index 0000000..1f44ac5 --- /dev/null +++ b/2023/src/day07.cpp @@ -0,0 +1,189 @@ +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +enum kind_type { + five_kind, + four_kind, + full_house_kind, + three_kind, + two_pair_kind, + one_pair_kind, + high_card_kind +}; + +kind_type +kind1(string hand) +{ + map mapping{}; + + for ( auto chr: hand ) { + ++mapping[chr]; + } + + sort(hand.begin(), hand.end()); + hand.erase(unique(hand.begin(), hand.end()), hand.end()); + + if ( mapping.size() == 1 ) { + return five_kind; + } + if ( mapping.size() == 2 ) { + if ( mapping[hand[0]] == 4 || mapping[hand[1]] == 4 ) { + return four_kind; + } + return full_house_kind; + } + if ( mapping.size() == 3 ) { + if ( mapping[hand[0]] == 3 || mapping[hand[1]] == 3 || mapping[hand[2]] == 3 ) { + return three_kind; + } + return two_pair_kind; + } + if ( mapping.size() == 4 ) { + return one_pair_kind; + } + + return high_card_kind; +} + +kind_type +kind2(const string& hand) +{ + map mapping{}; + + for ( auto chr: hand ) { + ++mapping[chr]; + } + + auto joker_amount = mapping['J']; + mapping.erase('J'); + + vector amounts{}; + amounts.reserve(mapping.size()); + for ( const auto& entry: mapping ) { + amounts.emplace_back(entry.second); + } + + sort(amounts.begin(), amounts.end(), greater<>()); + if ( amounts.empty() ) { + amounts.emplace_back(joker_amount); + } + else { + amounts[0] += joker_amount; + } + + if ( amounts[0] == 5 ) { + return five_kind; + } + if ( amounts[0] == 4 ) { + return four_kind; + } + if ( amounts[0] == 3 and amounts[1] == 2 ) { + return full_house_kind; + } + if ( amounts[0] == 3 ) { + return three_kind; + } + if ( amounts[0] == 2 && amounts[1] == 2 ) { + return two_pair_kind; + } + if ( amounts[0] == 2 ) { + return one_pair_kind; + } + + return high_card_kind; +} + +void +solve(const function& kind, map weights) +{ + fstream input{ "data/day07.txt" }; + vector> values{}; + + string hand; + long bid = 0; + while ( input >> hand >> bid ) { + values.emplace_back(hand, kind(hand), bid); + } + + sort(values.begin(), values.end(), [&](const tuple& first, const tuple& second) { + const auto& first_hand = get<0>(first); + const auto& second_hand = get<0>(second); + + auto first_kind = get<1>(first); + auto second_kind = get<1>(second); + + if ( first_kind == second_kind ) { + for ( size_t idx = 0; idx != 5; ++idx ) { + const auto first_weight = weights[first_hand[idx]]; + const auto second_weight = weights[second_hand[idx]]; + + if ( first_weight != second_weight ) { + return first_weight < second_weight; + } + } + } + return first_kind > second_kind; + }); + + long total = 0; + long rank = 1; + for ( const auto& value: values ) { + total += rank * get<2>(value); + ++rank; + } + cout << total << endl; +} + +int +main() +{ + assert(kind1("AAAAA") == five_kind); + assert(kind1("AA8AA") == four_kind); + assert(kind1("23332") == full_house_kind); + assert(kind1("TTT98") == three_kind); + assert(kind1("23432") == two_pair_kind); + assert(kind1("A23A4") == one_pair_kind); + assert(kind1("23456") == high_card_kind); + + map weights1 = { + { '2', 2 }, + { '3', 3 }, + { '4', 4 }, + { '5', 5 }, + { '6', 6 }, + { '7', 7 }, + { '8', 8 }, + { '9', 9 }, + { 'T', 10 }, + { 'J', 11 }, + { 'Q', 12 }, + { 'K', 13 }, + { 'A', 14 }, + }; + + map weights2 = { + { 'J', 1 }, + { '2', 2 }, + { '3', 3 }, + { '4', 4 }, + { '5', 5 }, + { '6', 6 }, + { '7', 7 }, + { '8', 8 }, + { '9', 9 }, + { 'T', 10 }, + { 'Q', 11 }, + { 'K', 12 }, + { 'A', 13 }, + }; + + solve(kind1, weights1); + solve(kind2, weights2); +} diff --git a/2023/src/day08.cpp b/2023/src/day08.cpp new file mode 100644 index 0000000..3e1b6c9 --- /dev/null +++ b/2023/src/day08.cpp @@ -0,0 +1,110 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +struct Generator { + explicit Generator(string_view init) + : values_(init) + , iter_(values_.begin()) + + { + } + + size_t next() + { + size_t gen = (*iter_ == 'L') ? 0 : 1; + + ++iter_; + if ( iter_ == values_.end() ) { + iter_ = values_.begin(); + } + + return gen; + } + + string values_; + string::iterator iter_; +}; + +void +part1() +{ + fstream input{ "data/day08.txt" }; + + string line; + getline(input, line); + + Generator generator{ line }; + + map> puzzle; + + const regex pattern{ R"((.*) = \((.*), (.*)\))" }; + while ( getline(input, line) ) { + if ( line.empty() ) { + continue; + } + + smatch sub_match; + if ( regex_search(line, sub_match, pattern) ) { + puzzle[sub_match[1]] = { sub_match[2], sub_match[3] }; + } + } + + auto counter = 0; + for ( string str{ "AAA" }; str != "ZZZ"; str = puzzle[str][generator.next()] ) { + ++counter; + } + cout << counter << endl; +} + +void +part2() +{ + fstream input{ "data/day08.txt" }; + + string firstline; + getline(input, firstline); + + map> puzzle; + + const regex pattern{ R"((.*) = \((.*), (.*)\))" }; + for ( string line; getline(input, line); ) { + if ( line.empty() ) { + continue; + } + + smatch sub_match; + if ( regex_search(line, sub_match, pattern) ) { + puzzle[sub_match[1]] = { sub_match[2], sub_match[3] }; + } + } + + auto value = 1L; + for ( const auto& entry: puzzle ) { + if ( entry.first[2] != 'A' ) { + continue; + } + + Generator generator{ firstline }; + + auto counter = 0L; + + for ( string str{ entry.first }; str[2] != 'Z'; str = puzzle[str][generator.next()] ) { + ++counter; + } + + value = lcm(value, counter); + } + cout << value << endl; +} + +int +main() +{ + part1(); + part2(); +} diff --git a/2023/src/day09.cpp b/2023/src/day09.cpp new file mode 100644 index 0000000..4b30e6e --- /dev/null +++ b/2023/src/day09.cpp @@ -0,0 +1,75 @@ +#include +#include +#include +#include +#include +using namespace std; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +template +vector +read_ints(const string& line) +{ + stringstream iss{ line }; + return vector{ istream_iterator{ iss }, istream_iterator{} }; +} + +template +T +solve_rec(const vector& values) +{ + vector differences; + + for ( size_t idx = 1; idx < values.size(); ++idx ) { + differences.emplace_back(values[idx] - values[idx - 1]); + } + auto all_zeros = all_of(differences.begin(), differences.end(), [](T diff) { return diff == 0; }); + if ( !all_zeros ) { + return solve_rec(differences) + values.back(); + } + else { + return values.back(); + } +} + +void +part1(const vector& lines) +{ + long sum = 0; + for ( const auto& line: lines ) { + sum += solve_rec(read_ints(line)); + } + cout << sum << endl; +} + +void +part2(const vector& lines) +{ + long sum = 0; + for ( const auto& line: lines ) { + auto values = read_ints(line); + reverse(values.begin(), values.end()); + sum += solve_rec(values); + } + cout << sum << endl; +} + +int +main() +{ + auto lines = read_file("data/day09.txt"); + part1(lines); + part2(lines); +} diff --git a/2023/src/day10.cpp b/2023/src/day10.cpp new file mode 100644 index 0000000..264e111 --- /dev/null +++ b/2023/src/day10.cpp @@ -0,0 +1,216 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +using pos_t = tuple; +using puzzle_t = vector; + +puzzle_t +read_file(string_view filename) +{ + fstream input{ filename }; + puzzle_t data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +pos_t +find_start_pos(const puzzle_t& puzzle) +{ + for ( size_t y = 0; y != puzzle.size(); ++y ) { // NOLINT + auto x = puzzle[y].find('S'); // NOLINT + if ( x != string::npos ) { + return { x, y }; + } + } + + return { 0, 0 }; +}; + +bool +predict_direction(const puzzle_t& puzzle, pos_t& current, char& direction) +{ + auto [x, y] = current; + + if ( direction == 'S' ) { + ++y; + if ( y >= puzzle.size() ) { + return false; + } + const auto tile = puzzle[y][x]; + if ( tile != 'J' && tile != '|' && tile != 'L' ) { + return false; + } + if ( tile == 'J' ) { + direction = 'W'; + } + else if ( tile == 'L' ) { + direction = 'E'; + } + } + else if ( direction == 'N' ) { + --y; + if ( y >= puzzle.size() ) { + return false; + } + const auto tile = puzzle[y][x]; + if ( tile != '7' && tile != '|' && tile != 'F' ) { + return false; + } + if ( tile == '7' ) { + direction = 'W'; + } + else if ( tile == 'F' ) { + direction = 'E'; + } + } + else if ( direction == 'E' ) { + ++x; + if ( x >= puzzle[y].size() ) { + return false; + } + const auto tile = puzzle[y][x]; + if ( tile != 'J' && tile != '-' && tile != '7' ) { + return false; + } + if ( tile == 'J' ) { + direction = 'N'; + } + else if ( tile == '7' ) { + direction = 'S'; + } + } + else if ( direction == 'W' ) { + --x; + if ( x >= puzzle[y].size() ) { + return false; + } + const auto tile = puzzle[y][x]; + if ( tile != 'L' && tile != '-' && tile != 'F' ) { + return false; + } + if ( tile == 'L' ) { + direction = 'N'; + } + else if ( tile == 'F' ) { + direction = 'S'; + } + } + else { + cerr << "invalid direction " << direction << ")!" << endl; + return false; + } + + current = { x, y }; + return true; +}; + +void +part1(const puzzle_t& puzzle) +{ + const auto start_pos = find_start_pos(puzzle); + + auto max_steps = 0; + + for ( const auto direction: { 'N', 'S', 'E', 'W' } ) { + auto current_direction = direction; + auto current_pos = start_pos; + + auto steps = 0; + for ( ;; ) { + ++steps; + + if ( !predict_direction(puzzle, current_pos, current_direction) ) { + break; + } + } + + max_steps = max(max_steps, steps); + } + + cout << max_steps / 2 << endl; +} + +bool +flood_fill(puzzle_t& puzzle, size_t x, size_t y) +{ + if ( y >= puzzle.size() || x >= puzzle[0].size() ) { + return false; + } + + if ( puzzle[y][x] == ' ' ) { + puzzle[y][x] = 'o'; + if ( !flood_fill(puzzle, x, y + 1) || + !flood_fill(puzzle, x, y - 1) || + !flood_fill(puzzle, x + 1, y) || + !flood_fill(puzzle, x - 1, y) ) { + return false; + } + } + + return true; +}; + +void +part2(const puzzle_t& puzzle_original) +{ + puzzle_t puzzle{ puzzle_original.size(), string(puzzle_original[0].size(), ' ') }; + + const auto start_pos = find_start_pos(puzzle_original); + + for ( const auto direction: { 'N', 'S', 'E', 'W' } ) { + auto current_direction = direction; + auto current_pos = start_pos; + + for ( ;; ) { + auto [x, y] = current_pos; + + puzzle[y][x] = puzzle_original[y][x]; + + if ( !predict_direction(puzzle_original, current_pos, current_direction) ) { + break; + } + } + } + + for ( size_t y = 0; y != puzzle.size(); ++y ) { // NOLINT + for ( size_t x = 0; x != puzzle[y].size(); ++x ) { // NOLINT + auto test_puzzle{ puzzle }; + + if ( flood_fill(test_puzzle, x, y) ) { + puzzle = test_puzzle; + } + } + } + + auto sum = 0; + for ( auto& line: puzzle ) { + auto pipes = 0U; + for ( auto chr: line ) { + if ( chr == '|' || chr == 'L' || chr == 'J' ) { + ++pipes; + } + if ( chr == 'o' && (pipes & 1U) == 1U ) { + ++sum; + } + } + } + + cout << sum << endl; +} + +int +main() +{ + const auto puzzle = read_file("data/day10.txt"); + part1(puzzle); + part2(puzzle); +} diff --git a/2023/src/day11.cpp b/2023/src/day11.cpp new file mode 100644 index 0000000..e1a0882 --- /dev/null +++ b/2023/src/day11.cpp @@ -0,0 +1,100 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +vector> +find_points(const vector& input) +{ + vector> result; + + for ( size_t row = 0; row != input.size(); ++row ) { + const auto& line = input[row]; + + for ( size_t col = 0; col != line.size(); ++col ) { + if ( line[col] == '#' ) { + result.emplace_back(long(row), long(col)); + } + } + } + + return result; +} + +void +find_empty_rows_and_cols(const vector& input, set& cols, set& rows) +{ + for ( size_t row = 0; row != input.size(); ++row ) { + const auto& line = input[row]; + if ( line.find('#') == line.npos ) { + rows.insert(long(row)); + } + } + + for ( size_t col = 0; col != input[0].size(); ++col ) { + bool empty_col = true; + for ( const auto& line: input ) { + if ( line[col] == '#' ) { + empty_col = false; + } + } + if ( empty_col ) { + cols.insert(long(col)); + } + } +} + +long +solve(const vector& input, long scale) +{ + auto points = find_points(input); + + set cols; + set rows; + + find_empty_rows_and_cols(input, cols, rows); + + for ( auto& point: points ) { + const auto row = get<0>(point) + count_if(rows.begin(), rows.end(), [&](long row) { return row < get<0>(point); }) * (scale - 1); + const auto col = get<1>(point) + count_if(cols.begin(), cols.end(), [&](long col) { return col < get<1>(point); }) * (scale - 1); + + point = { row, col }; + } + + auto sum = 0L; + for ( size_t i = 0; i != points.size(); ++i ) { + for ( size_t j = i + 1; j != points.size(); ++j ) { + const auto& from = points[i]; + const auto& to = points[j]; + + sum += abs(get<0>(from) - get<0>(to)) + abs(get<1>(from) - get<1>(to)); + } + } + + return sum; +} + +int +main() +{ + const auto input = read_file("data/day11.txt"); + + cout << "Part1: " << solve(input, 2) << endl; + cout << "Part2: " << solve(input, 1000000) << endl; +} diff --git a/2023/src/day12.cpp b/2023/src/day12.cpp new file mode 100644 index 0000000..11bd80b --- /dev/null +++ b/2023/src/day12.cpp @@ -0,0 +1,182 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +vector +split(const string& line, char sep) +{ + vector parts{}; + stringstream input{ line }; + + for ( string part; getline(input, part, sep); ) { + parts.emplace_back(part); + } + + return parts; +} + +template +vector +read_ints(const string& line) +{ + vector parts{}; + stringstream input{ line }; + + for ( string part; getline(input, part, ','); ) { + parts.emplace_back(stol(part)); + } + + return parts; +} + +vector +count_groups(string_view str) +{ + vector groups; + + size_t idx = 0U; + while ( idx != str.length() ) { + while ( idx != str.length() && str[idx] == '.' ) { + ++idx; + } + if ( idx != str.length() && str[idx] == '#' ) { + auto num = 0L; + while ( idx != str.length() && str[idx] == '#' ) { + ++num; + ++idx; + } + groups.emplace_back(num); + } + } + + return groups; +} + +long +brute_force(string_view springs, const vector& groups) +{ + long counts = count_if(springs.begin(), springs.end(), [](char chr) { return chr == '?'; }); + + string test_pattern; + + auto arrangements = 0L; + for ( size_t counter = 0; counter != (1U << size_t(counts)); ++counter ) { + auto bit_pattern = counter; + + for ( char chr: springs ) { + if ( chr == '?' ) { + if ( (bit_pattern & 1U) != 0U ) { + test_pattern += '.'; + } + else { + test_pattern += '#'; + } + bit_pattern >>= 1U; + } + else { + test_pattern += chr; + } + } + if ( groups == count_groups(test_pattern) ) { + arrangements++; + } + + test_pattern.clear(); + } + + return arrangements; +} + +long +count(const string& springs, const vector& groups) +{ + map>, long> cache; + + function&)> count_rec = [&](string springs, const vector& groups) -> long { + auto cached_value = cache.find(make_tuple(springs, groups)); + if ( cached_value != cache.end() ) { + return cached_value->second; + } + + springs.erase(0, springs.find_first_not_of('.')); + + if ( springs.empty() ) { + return groups.empty() ? 1 : 0; + } + + if ( groups.empty() ) { + return springs.find('#') == string_view::npos ? 1 : 0; + } + + if ( springs[0] == '#' ) { + auto gidx = size_t(groups[0]); + if ( springs.length() < gidx || springs.substr(0, gidx).find('.') != string_view::npos || springs[gidx] == '#' ) { + return 0; + } + + return count_rec(springs.substr(gidx + 1), { groups.begin() + 1, groups.end() }); + } + + auto value = count_rec(string("#") + springs.substr(1), groups) + count_rec(springs.substr(1), groups); + + cache[make_tuple(springs, groups)] = value; + + return value; + }; + + return count_rec(springs + ".", groups); +} + +void +part1(const vector& input) +{ + auto sum = 0L; + for ( const auto& line: input ) { + auto parts = split(line, ' '); + auto springs = parts[0]; + auto groups = read_ints(parts[1]); + + sum += brute_force(springs, groups); + // sum += count(springs, groups); + } + cout << sum << endl; +} + +void +part2(const vector& input) +{ + auto sum = 0L; + for ( const auto& line: input ) { + auto parts = split(line, ' '); + auto springs = parts[0] + "?" + parts[0] + "?" + parts[0] + "?" + parts[0] + "?" + parts[0]; + auto groups = read_ints(parts[1] + "," + parts[1] + "," + parts[1] + "," + parts[1] + "," + parts[1]); + + sum += count(springs, groups); + } + cout << sum << endl; +} + +int +main() +{ + const auto input = read_file("data/day12.txt"); + part1(input); + part2(input); +} diff --git a/2023/src/day13.cpp b/2023/src/day13.cpp new file mode 100644 index 0000000..549457b --- /dev/null +++ b/2023/src/day13.cpp @@ -0,0 +1,115 @@ +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +string +read_file(string_view filename) +{ + fstream input{ filename }; + return { istreambuf_iterator{ input }, istreambuf_iterator{} }; +} + +vector +split(string_view line, string_view delimiter) +{ + size_t pos_start = 0; + size_t pos_end = 0; + + vector res; + + while ( (pos_end = line.find(delimiter, pos_start)) != std::string::npos ) { + auto token = line.substr(pos_start, pos_end - pos_start); + pos_start = pos_end + delimiter.length(); + + res.emplace_back(token); + } + + res.emplace_back(line.substr(pos_start)); + return res; +} + +vector +transpose(const vector& lines) +{ + vector result(lines[0].size()); + + for ( const auto& line: lines ) { + for ( size_t i = 0; i < line.size(); ++i ) { + result[i] += line[i]; + } + } + return result; +} + +long +find_mirror(const vector& input) +{ + for ( size_t idx = 1; idx < input.size(); ++idx ) { + bool equal = true; + for ( size_t cnt = 0; cnt != min(idx, input.size() - idx); ++cnt ) { + if ( !(input[idx + cnt] == input[idx - 1 - cnt]) ) { + equal = false; + break; + } + } + if ( equal ) { + return long(idx); + } + } + return 0; +} + +long +count_differences(string_view str1, string_view str2) +{ + long diffs = 0; + for ( size_t idx = 0; idx != str1.size(); ++idx ) { + diffs += long(str1[idx] != str2[idx]); + } + return diffs; +} + +long +find_mirror_part2(const vector& input) +{ + for ( size_t idx = 1; idx < input.size(); ++idx ) { + long errs = 0; + for ( size_t i = 0; i != min(idx, input.size() - idx); ++i ) { + errs += count_differences(input[idx + i], input[idx - 1 - i]); + } + if ( errs == 1 ) { + return long(idx); + } + } + return 0; +} + +void +solve(const function&)>& find_mirror) +{ + static const long multiplier = 100; + + auto contents = read_file("data/day13.txt"); + auto parts = split(contents, "\n\n"); + + long sum = 0; + for ( const auto& part: parts ) { + auto lines = split(part, "\n"); + + sum += find_mirror(transpose(lines)); + sum += find_mirror(lines) * multiplier; + } + cout << sum << endl; +} + +int +main() +{ + solve(find_mirror); + solve(find_mirror_part2); +} diff --git a/2023/src/day14.cpp b/2023/src/day14.cpp new file mode 100644 index 0000000..8816ce1 --- /dev/null +++ b/2023/src/day14.cpp @@ -0,0 +1,239 @@ +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +void +part1(const vector& lines) +{ + auto start = chrono::steady_clock::now(); + + size_t sum = 0; + for ( size_t col = 0; col != lines[0].size(); ++col ) { + size_t counter = lines.size(); + + for ( size_t row = 0; row != lines.size(); ++row ) { + if ( lines[row][col] == 'O' ) { + sum += counter; + --counter; + } + if ( lines[row][col] == '#' ) { + counter = lines.size() - row - 1; + } + } + } + + auto duration = chrono::duration_cast(chrono::steady_clock::now() - start).count(); + + cout << sum << " (" << duration << " μs)" << endl; +} + +void +tilt_north(vector& lines) +{ + for ( size_t col = 0; col != lines[0].size(); ++col ) { + size_t row = 0; + while ( row != lines.size() ) { + size_t stones = 0; + size_t empty = 0; + + for ( size_t idx = row; idx != lines.size() && lines[idx][col] != '#'; ++idx ) { + if ( lines[idx][col] == '.' ) { + ++empty; + } + if ( lines[idx][col] == 'O' ) { + ++stones; + } + } + + while ( stones-- != 0 ) { + lines[row++][col] = 'O'; + } + + while ( empty-- != 0 ) { + lines[row++][col] = '.'; + } + + while ( row != lines.size() && lines[row][col] == '#' ) { + ++row; + } + } + } +} + +void +tilt_south(vector& lines) +{ + for ( size_t col = 0; col != lines[0].size(); ++col ) { + size_t row = 0; + while ( row != lines.size() ) { + size_t stones = 0; + size_t empty = 0; + + for ( size_t idx = row; idx != lines.size() && lines[idx][col] != '#'; ++idx ) { + if ( lines[idx][col] == '.' ) { + ++empty; + } + if ( lines[idx][col] == 'O' ) { + ++stones; + } + } + + while ( empty-- != 0 ) { + lines[row++][col] = '.'; + } + + while ( stones-- != 0 ) { + lines[row++][col] = 'O'; + } + + while ( row != lines.size() && lines[row][col] == '#' ) { + ++row; + } + } + } +} + +void +tilt_west(vector& lines) +{ + for ( size_t row = 0; row != lines.size(); ++row ) { + size_t col = 0; + while ( col != lines[0].size() ) { + size_t stones = 0; + size_t empty = 0; + + for ( size_t idx = col; idx != lines[0].size() && lines[row][idx] != '#'; ++idx ) { + if ( lines[row][idx] == '.' ) { + ++empty; + } + if ( lines[row][idx] == 'O' ) { + ++stones; + } + } + + while ( stones-- != 0 ) { + lines[row][col++] = 'O'; + } + + while ( empty-- != 0 ) { + lines[row][col++] = '.'; + } + + while ( col != lines[0].size() && lines[row][col] == '#' ) { + ++col; + } + } + } +} + +void +tilt_east(vector& lines) +{ + for ( size_t row = 0; row != lines.size(); ++row ) { + size_t col = 0; + while ( col != lines[0].size() ) { + size_t stones = 0; + size_t empty = 0; + + for ( size_t idx = col; idx != lines[0].size() && lines[row][idx] != '#'; ++idx ) { + if ( lines[row][idx] == '.' ) { + ++empty; + } + if ( lines[row][idx] == 'O' ) { + ++stones; + } + } + + while ( empty-- != 0 ) { + lines[row][col++] = '.'; + } + + while ( stones-- != 0 ) { + lines[row][col++] = 'O'; + } + + while ( col != lines[0].size() && lines[row][col] == '#' ) { + ++col; + } + } + } +} + +void +tilt(vector& lines) +{ + for ( auto tilt: { tilt_north, tilt_west, tilt_south, tilt_east } ) { + tilt(lines); + } +} + +size_t +calc(const vector& lines) +{ + size_t sum = 0; + size_t counter = lines.size(); + for ( const auto& line: lines ) { + sum += counter * static_cast(count_if(line.begin(), line.end(), [](char chr) { return chr == 'O'; })); + --counter; + } + return sum; +} + +void +part2(vector lines) +{ + auto start = chrono::steady_clock::now(); + map, long> cache; + + const long dest = 1'000'000'000; + + for ( long index = 0;; ++index ) { + auto iter = cache.find(lines); + if ( iter != cache.end() ) { + auto offset = iter->second; + auto cycle_length = index - offset; + + auto moves_required = (dest - offset) % cycle_length; + + while ( moves_required-- != 0 ) { + tilt(lines); + } + + auto duration = chrono::duration_cast(chrono::steady_clock::now() - start).count(); + + cout << calc(lines) << " (" << duration << " ms)" << endl; + break; + } + else { + cache[lines] = index; + } + + tilt(lines); + } +} + +int +main() +{ + const auto lines = read_file("data/day14.txt"); + part1(lines); + part2(lines); +} diff --git a/2023/src/day15.cpp b/2023/src/day15.cpp new file mode 100644 index 0000000..6fcbfc2 --- /dev/null +++ b/2023/src/day15.cpp @@ -0,0 +1,102 @@ +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +string +read_file(string_view filename) +{ + fstream input{ filename }; + return { istreambuf_iterator{ input }, istreambuf_iterator{} }; +} + +void +rtrim(string& str) +{ + str.erase(find_if(str.rbegin(), str.rend(), [](auto chr) { return !isspace(chr); }).base(), str.end()); +} + +vector +split(const string& line, char sep) +{ + vector parts{}; + stringstream input{ line }; + + for ( string part; getline(input, part, sep); ) { + rtrim(part); + parts.emplace_back(part); + } + + return parts; +} + +unsigned int +calculate_hash(string_view str) +{ + unsigned int value = 0; + for ( auto chr: str ) { + value += static_cast(chr); + value *= 17; + } + return value % 256; +} + +void +part1() +{ + const auto parts = split(read_file("data/day15.txt"), ','); + cout << accumulate(parts.begin(), parts.end(), 0UL, [](auto init, const auto& str) { return init + calculate_hash(str); }) << endl; +} + +void +part2() +{ + vector>> boxes(256); + + const auto line = read_file("data/day15.txt"); + const auto parts = split(line, ','); + for ( const auto& part: parts ) { + const auto pos = part.find_first_of("=-"); + const auto lens = part.substr(0, pos); + auto& box = boxes[calculate_hash(lens)]; + + if ( part[pos] == '=' ) { + const auto value = stol(part.substr(pos + 1)); + + auto iter = find_if(box.begin(), box.end(), [&lens](const auto& element) { return get<0>(element) == lens; }); + if ( iter == box.end() ) { + box.emplace_back(lens, value); + } + else { + get<1>(*iter) = value; + } + } + else { + box.remove_if([&lens](const auto& element) { return get<0>(element) == lens; }); + } + } + + long value = 0; + for ( size_t idx = 0; idx != boxes.size(); ++idx ) { + const auto& box = boxes[idx]; + + long lens_number = 1; + for ( const auto& lens: box ) { + value += static_cast(idx + 1) * lens_number * get<1>(lens); + ++lens_number; + } + } + cout << value << endl; +} + +int +main() +{ + part1(); + part2(); +} diff --git a/2023/src/day16.cpp b/2023/src/day16.cpp new file mode 100644 index 0000000..93c7479 --- /dev/null +++ b/2023/src/day16.cpp @@ -0,0 +1,132 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +const unsigned DIR_UP = 0; +const unsigned DIR_RIGHT = 1; +const unsigned DIR_DOWN = 2; +const unsigned DIR_LEFT = 3; + +size_t +solve(const vector& lines, tuple start) +{ + static const array, 4> movement{ + make_tuple(0, -1), + make_tuple(1, 0), + make_tuple(0, 1), + make_tuple(-1, 0), + }; + + map, bool> visited; + + queue> positions; + + positions.emplace(start); + + while ( !positions.empty() ) { + auto [row, col, dir] = positions.front(); + positions.pop(); + + while ( true ) { + col += get<0>(movement.at(dir % 4)); + row += get<1>(movement.at(dir % 4)); + + if ( row >= lines.size() || col >= lines[0].size() ) { + break; + } + + if ( visited[{ row, col, dir }] ) { + break; + } + + visited[{ row, col, dir }] = true; + + const auto chr = lines[row][col]; + + if ( (chr == '|' && (dir == DIR_LEFT || dir == DIR_RIGHT)) || + (chr == '-' && (dir == DIR_UP || dir == DIR_DOWN)) ) { + dir = dir + 1; + positions.emplace(row, col, dir + 2); + } + else if ( (chr == '/' && (dir == DIR_LEFT || dir == DIR_RIGHT)) || + (chr == '\\' && (dir == DIR_UP || dir == DIR_DOWN)) ) { + dir = dir + 3; + } + else if ( (chr == '\\' && (dir == DIR_LEFT || dir == DIR_RIGHT)) || + (chr == '/' && (dir == DIR_UP || dir == DIR_DOWN)) ) { + dir = dir + 1; + } + + dir %= 4; + } + } + + set> foo; + for ( const auto& bar: visited ) { + foo.emplace(get<0>(bar.first), get<1>(bar.first)); + } + return foo.size(); +} + +void +part1(const vector& lines) +{ + auto start = chrono::steady_clock::now(); + + auto sum = solve(lines, { 0, -1, DIR_RIGHT }); + + auto duration = chrono::duration_cast(chrono::steady_clock::now() - start).count(); + + cout << sum << " (" << duration << "ms)" << endl; +} + +void +part2(const vector& lines) +{ + const auto rows = lines.size(); + const auto cols = lines[0].size(); + + auto start = chrono::steady_clock::now(); + + size_t sum = 0; + for ( size_t row = 0; row != rows; ++row ) { + sum = max(sum, solve(lines, { row, -1, DIR_RIGHT })); + sum = max(sum, solve(lines, { row, cols, DIR_LEFT })); + } + for ( size_t col = 0; col != cols; ++col ) { + sum = max(sum, solve(lines, { -1, col, DIR_DOWN })); + sum = max(sum, solve(lines, { rows, col, DIR_UP })); + } + + auto duration = chrono::duration_cast(chrono::steady_clock::now() - start).count(); + + cout << sum << " (" << duration << "ms)" << endl; +} + +int +main() +{ + const auto lines = read_file("data/day16.txt"); + part1(lines); + part2(lines); +} diff --git a/2023/src/day17.cpp b/2023/src/day17.cpp new file mode 100644 index 0000000..4098bba --- /dev/null +++ b/2023/src/day17.cpp @@ -0,0 +1,112 @@ +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +using puzzle_t = vector>; + +puzzle_t +read_file(string_view filename) +{ + fstream input{ filename }; + puzzle_t data; + + for ( string line; getline(input, line); ) { + puzzle_t::value_type numbers; + for ( auto chr: line ) { + numbers.emplace_back(chr - '0'); + } + data.emplace_back(numbers); + } + + return data; +} + +int +solve(const puzzle_t& puzzle, size_t min_steps, size_t max_steps) +{ + using pos_t = tuple; + using dir_t = tuple; + using entry = tuple; + + static const array directions = { + make_tuple(0, 1), + make_tuple(0, -1), + make_tuple(1, 0), + make_tuple(-1, 0) + }; + + priority_queue, greater<>> queue; + + set> seen; + + const pos_t target = { puzzle.size() - 1, puzzle[0].size() - 1 }; + + queue.emplace(0, pos_t(0, 0), dir_t(0, 0)); + + while ( !queue.empty() ) { + const auto [heat, pos, dir] = queue.top(); + queue.pop(); + + if ( pos == target ) { + return heat; + } + + const auto key = make_tuple(pos, dir); + if ( seen.contains(key) ) { + continue; + } + seen.emplace(key); + + const dir_t inv_dir = { -get<0>(dir), -get<1>(dir) }; + + for ( const auto& next_dir: directions ) { + if ( next_dir == dir || next_dir == inv_dir ) { + continue; + } + + auto heat_so_far = heat; + + for ( size_t steps = 1; steps <= max_steps; ++steps ) { + const pos_t next_pos = { get<0>(pos) + get<0>(next_dir) * steps, + get<1>(pos) + get<1>(next_dir) * steps }; + + if ( get<0>(next_pos) >= puzzle.size() || get<1>(next_pos) >= puzzle[0].size() ) { + continue; + } + + heat_so_far += puzzle[get<0>(next_pos)][get<1>(next_pos)]; + + if ( steps >= min_steps ) { + queue.emplace(heat_so_far, next_pos, next_dir); + } + } + } + } + return -1; +} + +void +part1(const puzzle_t& puzzle) +{ + cout << solve(puzzle, 1, 3) << endl; +} + +void +part2(const puzzle_t& puzzle) +{ + cout << solve(puzzle, 4, 10) << endl; +} + +int +main() +{ + const auto puzzle = read_file("data/day17.txt"); + part1(puzzle); + part2(puzzle); +} diff --git a/2023/src/day18.cpp b/2023/src/day18.cpp new file mode 100644 index 0000000..3037739 --- /dev/null +++ b/2023/src/day18.cpp @@ -0,0 +1,115 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +using puzzle_t = vector>; + +puzzle_t +read_file_part1(string_view filename, long& border_steps) +{ + static map> movement = { + { 'U', { 0, -1 } }, // up + { 'D', { 0, 1 } }, // down + { 'L', { -1, 0 } }, // left + { 'R', { 1, 0 } }, // right + }; + + border_steps = 0; + + fstream input{ filename }; + puzzle_t data; + + data.emplace_back(0, 0); + + for ( string line; getline(input, line); ) { + char dir{}; + long steps{}; + stringstream sstrm{ line }; + + if ( sstrm >> dir >> steps ) { + data.emplace_back(get<0>(data.back()) + get<0>(movement[dir]) * steps, + get<1>(data.back()) + get<1>(movement[dir]) * steps); + + border_steps += steps; + } + } + + return data; +} + +puzzle_t +read_file_part2(string_view filename, long& border_steps) +{ + static map> movement = { + { '0', { 1, 0 } }, // right + { '1', { 0, 1 } }, // down + { '2', { -1, 0 } }, // left + { '3', { 0, -1 } }, // up + }; + + border_steps = 0; + + fstream input{ filename }; + puzzle_t data; + + data.emplace_back(0, 0); + + for ( string line; getline(input, line); ) { + char dir{}; + long steps{}; + string hexcode; + stringstream sstrm{ line }; + + if ( sstrm >> dir >> steps >> hexcode ) { + steps = stol(hexcode.substr(2, 5), nullptr, 16); + dir = hexcode[7]; + + data.emplace_back(get<0>(data.back()) + get<0>(movement[dir]) * steps, + get<1>(data.back()) + get<1>(movement[dir]) * steps); + + border_steps += steps; + } + } + + return data; +} + +long +shoelace(const puzzle_t& puzzle, const long border_steps) +{ + long area = 0; + for ( size_t i = 1; i < puzzle.size(); ++i ) { + const auto [x1, y1] = puzzle[i - 1]; + const auto [x2, y2] = puzzle[i]; + + area += (x1 * y2 - y1 * x2); + } + return (border_steps + area) / 2 + 1; +} + +void +part1() +{ + long border_steps = 0; + auto puzzle = read_file_part1("data/day18.txt", border_steps); + cout << shoelace(puzzle, border_steps) << endl; +} + +void +part2() +{ + long border_steps = 0; + auto puzzle = read_file_part2("data/day18.txt", border_steps); + cout << shoelace(puzzle, border_steps) << endl; +} + +int +main() +{ + part1(); + part2(); +} diff --git a/2023/src/day19.cpp b/2023/src/day19.cpp new file mode 100644 index 0000000..a1d4eab --- /dev/null +++ b/2023/src/day19.cpp @@ -0,0 +1,183 @@ +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +string +read_file(string_view filename) +{ + fstream input{ filename }; + return { istreambuf_iterator{ input }, istreambuf_iterator{} }; +} + +vector +split(string_view line, string_view delimiter) +{ + size_t pos_start = 0; + size_t pos_end = 0; + + vector res; + + while ( (pos_end = line.find(delimiter, pos_start)) != string::npos ) { + auto token = line.substr(pos_start, pos_end - pos_start); + pos_start = pos_end + delimiter.length(); + + res.emplace_back(token); + } + + if ( pos_start != line.size() ) { + res.emplace_back(line.substr(pos_start)); + } + return res; +} + +void +part1(map>, string>> rules, const vector& parts) +{ + long sum = 0; + for ( const auto& part: parts ) { + static const regex parts_pattern{ R"(\{x=(\d*),m=(\d*),a=(\d*),s=(\d*)\})" }; + + smatch smatch; + if ( !regex_search(part, smatch, parts_pattern) ) { + continue; + } + + map values = { + { "x", stol(smatch[1]) }, + { "m", stol(smatch[2]) }, + { "a", stol(smatch[3]) }, + { "s", stol(smatch[4]) }, + }; + + string rule = "in"; + while ( rule != "A" && rule != "R" ) { + auto [sub_rules, next_rule] = rules[rule]; + + for ( const auto& sub_rule: sub_rules ) { + const auto [field, cmp, value, dest] = sub_rule; + + if ( values.contains(field) && ((cmp == ">" && values[field] > value) || (cmp == "<" && values[field] < value)) ) { + next_rule = dest; + break; + } + } + + rule = next_rule; + } + + if ( rule == "A" ) { + sum += values["x"]; + sum += values["m"]; + sum += values["a"]; + sum += values["s"]; + } + } + cout << sum << endl; +} + +void +part2(map>, string>> rules) +{ + function>, string)> count = [&](map> ranges, const string& name) -> long { + if ( name == "R" ) { + return 0; + } + + if ( name == "A" ) { + long result = 1; + for ( const auto& range: ranges ) { + const auto [lo, hi] = range.second; + result *= hi - lo + 1; + } + return result; + } + + const auto [sub_rules, fallback] = rules[name]; + + long result = 0; + + bool run_trough = true; + for ( const auto& [key, cmp, value, target]: sub_rules ) { + const auto [lo, hi] = ranges[key]; + pair T; // NOLINT + pair F; // NOLINT + if ( cmp == "<" ) { + T = { lo, min(value - 1, hi) }; + F = { max(value, lo), hi }; + } + else { + T = { max(value + 1, lo), hi }; + F = { lo, min(value, hi) }; + } + if ( T.first <= T.second ) { + auto copy = ranges; + copy[key] = T; + result += count(copy, target); + } + if ( F.first <= F.second ) { + ranges[key] = F; + } + else { + run_trough = false; + break; + } + } + if ( run_trough ) { + result += count(ranges, fallback); + } + + return result; + }; + + cout << count({ + { "x", { 1, 4000 } }, + { "m", { 1, 4000 } }, + { "a", { 1, 4000 } }, + { "s", { 1, 4000 } }, + }, + "in") + << endl; +} + +int +main() +{ + const auto input = split(read_file("data/day19.txt"), "\n\n"); + const auto rules_string = split(input[0], "\n"); + const auto parts = split(input[1], "\n"); + + map>, string>> rules; + + for ( const auto& rule: rules_string ) { + static const regex rules_pattern{ R"((.*)\{(.*),(.*)\})" }; + + smatch smatch; + if ( !regex_search(rule, smatch, rules_pattern) ) { + continue; + } + + string name = smatch[1]; + string default_rule = smatch[3]; + + vector> sub_rules; + + for ( const auto& sub_rule: split(smatch[2].str(), ",") ) { + static const regex sub_rules_pattern{ R"((.)(.)(\d*):(.*))" }; + + std::smatch smatch2; + if ( regex_search(sub_rule, smatch2, sub_rules_pattern) ) { + sub_rules.emplace_back(smatch2[1], smatch2[2], stol(smatch2[3]), smatch2[4]); + } + } + + rules[name] = make_tuple(sub_rules, default_rule); + } + + part1(rules, parts); + part2(rules); +} diff --git a/2023/src/day20.cpp b/2023/src/day20.cpp new file mode 100644 index 0000000..f85ac90 --- /dev/null +++ b/2023/src/day20.cpp @@ -0,0 +1,293 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +vector +split(string_view line, string_view delimiter) +{ + size_t pos_start = 0; + size_t pos_end = 0; + + vector res; + + while ( (pos_end = line.find(delimiter, pos_start)) != string::npos ) { + auto token = line.substr(pos_start, pos_end - pos_start); + pos_start = pos_end + delimiter.length(); + + res.emplace_back(token); + } + + if ( pos_start != line.size() ) { + res.emplace_back(line.substr(pos_start)); + } + return res; +} + +struct Module { // NOLINT +protected: + explicit Module(string_view name, queue>& queue) + : name_(name) + , queue_(queue) + { + } + virtual ~Module() = default; + +public: + virtual void trigger(string_view sender, int signal) = 0; + + void register_sender(string_view sender) { senders_.emplace(sender, 0); } + +protected: + void send_signal(int signal) const + { + for ( const auto& link: links_ ) { + queue_.emplace(name_, signal, link); + } + } + +public: + void add_link(string_view link) { links_.emplace_back(link); } + +protected: + const string name_; + queue>& queue_; + +public: + vector links_; + map senders_; +}; + +struct BroadcasterModuler : public Module { + explicit BroadcasterModuler(string_view name, queue>& queue) + : Module(name, queue) + { + } + void trigger(string_view, int signal) override + { + send_signal(signal); + } +}; + +struct FlipFlopModule : public Module { + explicit FlipFlopModule(string_view name, queue>& queue) + : Module(name, queue) + { + } + void trigger(string_view, int signal) override + { + if ( signal == 1 ) { + return; + } + state_ = (state_ + 1) % 2; + send_signal(state_); + } + int state_{ 0 }; +}; + +struct ConjunctionModule : public Module { + explicit ConjunctionModule(string_view name, queue>& queue) + : Module(name, queue) + { + } + void trigger(string_view sender, int signal) override + { + senders_[string(sender)] = signal; + if ( all_of(senders_.begin(), senders_.end(), [](const auto& link) { return link.second == 1; }) ) { + send_signal(0); + } + else { + send_signal(1); + } + } +}; + +struct OutputModule : public Module { + explicit OutputModule(string_view name, queue>& queue) + : Module(name, queue) + { + } + void trigger(string_view, int) override + { + } +}; + +void +part1(const vector& input) +{ + queue> queue; + map> modules; + + modules["output"] = make_shared("output", queue); + + for ( const auto& line: input ) { + const auto parts = split(line, " -> "); + auto module = parts[0]; + const auto dests = split(parts[1], ", "); + + shared_ptr ptr; + if ( module == "broadcaster" ) { + ptr = make_shared(module, queue); + } + else if ( module.starts_with('%') ) { + module.erase(0, 1); + ptr = make_shared(module, queue); + } + else if ( module.starts_with('&') ) { + module.erase(0, 1); + ptr = make_shared(module, queue); + } + else { + cerr << "unknown module type: " << module << endl; + return; + } + + for ( const auto& dest: dests ) { + ptr->add_link(dest); + } + + modules[module] = ptr; + } + + // register senders + for ( auto& module: modules ) { + auto [name, ptr] = module; + + for ( const auto& link: ptr->links_ ) { + if ( modules.contains(link) ) { + modules[link]->register_sender(name); + } + } + } + + long sums[2] = { 0, 0 }; + for ( int i = 0; i != 1000; ++i ) { + queue.emplace("button", 0, "broadcaster"); + while ( !queue.empty() ) { + const auto [sender, signal, receiver] = queue.front(); + queue.pop(); + + sums[signal]++; + + if ( modules.contains(receiver) ) { + modules[receiver]->trigger(sender, signal); + } + } + } + cout << sums[0] * sums[1] << endl; +} + +void +part2(const vector& input) +{ + queue> queue; + map> modules; + + modules["output"] = make_shared("output", queue); + + for ( const auto& line: input ) { + const auto parts = split(line, " -> "); + auto module = parts[0]; + const auto dests = split(parts[1], ", "); + + shared_ptr ptr; + if ( module == "broadcaster" ) { + ptr = make_shared(module, queue); + } + else if ( module.starts_with('%') ) { + module.erase(0, 1); + ptr = make_shared(module, queue); + } + else if ( module.starts_with('&') ) { + module.erase(0, 1); + ptr = make_shared(module, queue); + } + else { + cerr << "unknown module type: " << module << endl; + return; + } + + for ( const auto& dest: dests ) { + ptr->add_link(dest); + } + + modules[module] = ptr; + } + + // register senders + string to_rx; + for ( auto& module: modules ) { + auto [name, ptr] = module; + + for ( const auto& link: ptr->links_ ) { + if ( modules.contains(link) ) { // link == "rx" + modules[link]->register_sender(name); + } + else { + to_rx = name; + } + } + } + + map cycle_modules; + for ( auto& module: modules ) { + auto [name, ptr] = module; + const auto links = ptr->links_; + + if ( find(links.begin(), links.end(), to_rx) != links.end() ) { + cycle_modules[name] = 0; + } + } + + for ( long i = 1;; ++i ) { + queue.emplace("button", 0, "broadcaster"); + while ( !queue.empty() ) { + const auto [sender, signal, receiver] = queue.front(); + queue.pop(); + + if ( signal == 1 && cycle_modules.contains(sender) ) { + cycle_modules[sender] = i; + } + + if ( modules.contains(receiver) ) { + modules[receiver]->trigger(sender, signal); + } + } + if ( all_of(cycle_modules.begin(), cycle_modules.end(), [](const auto& module) { return module.second != 0; }) ) { + long result = 1; + for ( const auto& module: cycle_modules ) { + result = lcm(result, module.second); + } + cout << result << endl; + break; + } + } +} + +int +main() +{ + const auto input = read_file("data/day20.txt"); + part1(input); + part2(input); +} diff --git a/2023/src/day21.cpp b/2023/src/day21.cpp new file mode 100644 index 0000000..c633155 --- /dev/null +++ b/2023/src/day21.cpp @@ -0,0 +1,148 @@ +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +using position = tuple; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +position +find_start_position(const vector& lines) +{ + for ( size_t row = 0; row != lines.size(); ++row ) { + for ( size_t col = 0; col != lines[row].size(); ++col ) { + if ( lines[row][col] == 'S' ) { + return { row, col }; + } + } + } + return {}; +} + +set +find_neighbours(position pos, const vector& lines) +{ + static const vector movements = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; + + set neighbours; + const auto [row, col] = pos; + + for ( const auto& [drow, dcol]: movements ) { + const auto nrow = row + drow; + const auto ncol = col + dcol; + + if ( nrow < lines.size() && ncol < lines[0].size() && (lines[nrow][ncol] == '.' || lines[nrow][ncol] == 'S') ) { + neighbours.emplace(nrow, ncol); + } + } + + return neighbours; +} + +size_t +count(vector lines, position start, size_t rounds) +{ + queue positions; + positions.emplace(start); + + size_t sum = 0; + for ( size_t round = 0; round != rounds; ++round ) { + set next_positions; + + sum = 0; + while ( !positions.empty() ) { + const auto [curr_row, curr_col] = positions.front(); + lines[curr_row][curr_col] = '.'; + + const auto neighbours = find_neighbours(positions.front(), lines); + positions.pop(); + + for ( const auto& [row, col]: neighbours ) { + lines[row][col] = 'O'; + next_positions.emplace(row, col); + ++sum; + } + } + + for ( const auto& position: next_positions ) { + positions.emplace(position); + } + } + return sum; +} + +void +part1(const vector& lines) +{ + const auto start = find_start_position(lines); + cout << count(lines, start, 64) << endl; +} + +void +part2(const vector& lines) +{ + const auto start = find_start_position(lines); + const auto [row, col] = start; + + const auto pow2 = [](size_t val) -> size_t { + return val * val; + }; + + const auto size = lines.size(); + const size_t steps = 26501365; + const auto grid_width = steps / size - 1; + + const auto num_odd_tiles = pow2(grid_width / 2 * 2 + 1); + const auto num_even_tiles = pow2((grid_width + 1) / 2 * 2); + const auto num_odd_points = count(lines, start, size * 2 + 1); + const auto num_even_points = count(lines, start, size * 2); + + auto sum = num_odd_tiles * num_odd_points + num_even_tiles * num_even_points; + + const auto corner_top = count(lines, { size - 1, col }, size - 1); + const auto corner_right = count(lines, { row, 0 }, size - 1); + const auto corner_bottom = count(lines, { 0, col }, size - 1); + const auto corner_left = count(lines, { row, size - 1 }, size - 1); + + sum += corner_top + corner_right + corner_bottom + corner_left; + + const auto small_top_right = count(lines, { size - 1, 0 }, size / 2 - 1); + const auto small_top_left = count(lines, { size - 1, size - 1 }, size / 2 - 1); + const auto small_bottom_right = count(lines, { 0, 0 }, size / 2 - 1); + const auto small_bottom_left = count(lines, { 0, size - 1 }, size / 2 - 1); + + sum += (grid_width + 1) * (small_top_right + small_top_left + small_bottom_right + small_bottom_left); + + const auto large_top_right = count(lines, { size - 1, 0 }, size * 3 / 2 - 1); + const auto large_top_left = count(lines, { size - 1, size - 1 }, size * 3 / 2 - 1); + const auto large_bottom_right = count(lines, { 0, 0 }, size * 3 / 2 - 1); + const auto large_bottom_left = count(lines, { 0, size - 1 }, size * 3 / 2 - 1); + + sum += grid_width * (large_top_right + large_top_left + large_bottom_right + large_bottom_left); + + cout << sum << endl; +} + +int +main() +{ + auto lines = read_file("data/day21.txt"); + part1(lines); + part2(lines); +} diff --git a/2023/src/day22.cpp b/2023/src/day22.cpp new file mode 100644 index 0000000..1afb994 --- /dev/null +++ b/2023/src/day22.cpp @@ -0,0 +1,157 @@ +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +struct piece { + int x1, y1, z1; + int x2, y2, z2; +}; + +vector +read_file(string_view filename) +{ + static const regex pattern{ R"((\d+),(\d+),(\d+)~(\d+),(\d+),(\d+))" }; + + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + smatch matches; + if ( regex_search(line, matches, pattern) ) { + data.emplace_back(piece{ + stoi(matches[1]), + stoi(matches[2]), + stoi(matches[3]), + stoi(matches[4]), + stoi(matches[5]), + stoi(matches[6]) }); + } + } + sort(data.begin(), data.end(), [](const auto& lhs, const auto& rhs) { return lhs.z1 < rhs.z1; }); + + return data; +} + +void +part1(vector puzzle) +{ + map> grid; + + map> supported_by; + map> supports; + + for ( size_t idx = 0; idx != puzzle.size(); ++idx ) { + auto& piece = puzzle[idx]; + + int max_z = 0; + for ( auto x = piece.x1; x <= piece.x2; ++x ) { + for ( auto y = piece.y1; y <= piece.y2; ++y ) { + max_z = max(max_z, grid[x][y]); + } + } + + auto height = piece.z2 - piece.z1 + 1; + + for ( auto x = piece.x1; x <= piece.x2; ++x ) { + for ( auto y = piece.y1; y <= piece.y2; ++y ) { + grid[x][y] = max_z + height; + } + } + + piece.z1 = max_z + 1; + piece.z2 = max_z + height; + + for ( size_t idx2 = idx; idx2-- > 0; ) { + if ( piece.x1 > puzzle[idx2].x2 || puzzle[idx2].x1 > piece.x2 ) { + continue; + } + if ( piece.y1 > puzzle[idx2].y2 || puzzle[idx2].y1 > piece.y2 ) { + continue; + } + if ( puzzle[idx].z1 == puzzle[idx2].z2 + 1 ) { + supports[idx2].emplace_back(idx); + supported_by[idx].emplace_back(idx2); + } + } + } + + long number = 0; + for ( size_t idx = 0; idx != puzzle.size(); ++idx ) { + if ( all_of(supports[idx].begin(), supports[idx].end(), [&](const auto& idx2) { return supported_by[idx2].size() > 1; }) ) { + ++number; + } + } + cout << number << endl; +} + +void +part2(vector puzzle) +{ + map> grid; + + for ( auto& piece: puzzle ) { + int max_z = 0; + for ( auto x = piece.x1; x <= piece.x2; ++x ) { + for ( auto y = piece.y1; y <= piece.y2; ++y ) { + max_z = max(max_z, grid[x][y]); + } + } + + auto height = piece.z2 - piece.z1 + 1; + + for ( auto x = piece.x1; x <= piece.x2; ++x ) { + for ( auto y = piece.y1; y <= piece.y2; ++y ) { + grid[x][y] = max_z + height; + } + } + + piece.z1 = max_z + 1; + piece.z2 = max_z + height; + } + + int num = 0; + for ( size_t idx = 0; idx != puzzle.size(); ++idx ) { + map> grid; + + for ( size_t idx2 = 0; idx2 != puzzle.size(); ++idx2 ) { + if ( idx == idx2 ) { + continue; + } + + const auto& piece = puzzle[idx2]; + + int max_z = 0; + for ( auto x = piece.x1; x <= piece.x2; ++x ) { + for ( auto y = piece.y1; y <= piece.y2; ++y ) { + max_z = max(max_z, grid[x][y]); + } + } + + auto height = piece.z2 - piece.z1 + 1; + + for ( auto x = piece.x1; x <= piece.x2; ++x ) { + for ( auto y = piece.y1; y <= piece.y2; ++y ) { + grid[x][y] = max_z + height; + } + } + + if ( piece.z1 != max_z + 1 ) { + ++num; + } + } + } + cout << num << endl; +} + +int +main() +{ + const auto puzzle = read_file("data/day22.txt"); + part1(puzzle); + part2(puzzle); +} diff --git a/2023/src/day23.cpp b/2023/src/day23.cpp new file mode 100644 index 0000000..d8c20d3 --- /dev/null +++ b/2023/src/day23.cpp @@ -0,0 +1,152 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +using position_t = tuple; + +vector +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( string line; getline(input, line); ) { + data.emplace_back(line); + } + + return data; +} + +set +get_neighbours(const vector& maze, position_t possition) +{ + static const position_t deltas[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // NOLINT + + static const auto SYM_UP = '^'; + static const auto SYM_RIGHT = '>'; + static const auto SYM_DOWN = 'v'; + static const auto SYM_LEFT = '<'; + + const auto [row, col] = possition; + + switch ( maze[row][col] ) { + case SYM_UP: + return { make_tuple(row - 1, col) }; + case SYM_RIGHT: + return { make_tuple(row, col + 1) }; + case SYM_DOWN: + return { make_tuple(row + 1, col) }; + case SYM_LEFT: + return { make_tuple(row, col - 1) }; + } + + set positions; + + for ( const auto& delta: deltas ) { + const auto new_row = row + get<0>(delta); + const auto new_col = col + get<1>(delta); + + if ( new_row >= maze.size() || new_col >= maze[0].size() ) { + continue; + } + + if ( maze[new_row][new_col] == '#' ) { + continue; + } + + if ( new_row < row && maze[new_row][new_col] == SYM_DOWN ) { + continue; + } + if ( new_row > row && maze[new_row][new_col] == SYM_UP ) { + continue; + } + if ( new_col < col && maze[new_row][new_col] == SYM_RIGHT ) { + continue; + } + if ( new_col > col && maze[new_row][new_col] == SYM_LEFT ) { + continue; + } + + positions.emplace(new_row, new_col); + } + + return positions; +} + +set +get_neighbours2(const vector& maze, position_t possition) +{ + static const position_t deltas[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // NOLINT + + const auto [row, col] = possition; + + set positions; + + for ( const auto& delta: deltas ) { + const auto new_row = row + get<0>(delta); + const auto new_col = col + get<1>(delta); + + if ( new_row >= maze.size() || new_col >= maze[0].size() ) { + continue; + } + + if ( maze[new_row][new_col] == '#' ) { + continue; + } + + positions.emplace(new_row, new_col); + } + + return positions; +} + +void +solve(const vector& maze, function(const vector&, position_t)> neighbours) +{ + const position_t start = { 0, maze[0].find('.') }; + const position_t end = { maze.size() - 1, maze[maze.size() - 1].find('.') }; + + vector> visited(maze.size(), vector(maze[0].size())); + + function find_longest_path = [&](position_t position, long current) -> long { + const auto [row, col] = position; + + if ( visited[row][col] ) { + return 0; + } + + if ( position == end ) { + return current; + } + + long value = 0; + + visited[row][col] = true; + for ( const auto& neighbour: neighbours(maze, position) ) { + value = max(value, find_longest_path(neighbour, current + 1)); + } + visited[row][col] = false; + + return value; + }; + + auto value = find_longest_path(start, 0); + cout << value << endl; +} + +int +main() +{ + const auto maze = read_file("data/day23.txt"); + solve(maze, get_neighbours); + solve(maze, get_neighbours2); +} diff --git a/2023/src/day24.cpp b/2023/src/day24.cpp new file mode 100644 index 0000000..76f459b --- /dev/null +++ b/2023/src/day24.cpp @@ -0,0 +1,173 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +using line_type = tuple; +using point_type = tuple; +using puzzle_type = vector; + +template +int +sgn(T val) +{ + return (T(0) < val) - (val < T(0)); +} + +puzzle_type +read_file(string_view filename) +{ + fstream input{ filename }; + puzzle_type result; + + for ( string line; getline(input, line); ) { + const auto NFIELDS = 6; + + double x, y, z, dx, dy, dz; // NOLINT + + if ( sscanf(line.data(), "%lf, %lf, %lf @ %lf, %lf, %lf", &x, &y, &z, &dx, &dy, &dz) != NFIELDS ) { + continue; + } + + result.emplace_back(make_tuple(x, y, z, dx, dy, dz)); + } + + return result; +} + +point_type +get_direction(line_type line) +{ + const auto [x, y, z, dx, dy, dz] = line; + + return make_tuple(sgn(dx), sgn(dy)); +} + +point_type +get_direction(line_type from, point_type to) +{ + const auto [x, y, z, dx, dy, dz] = from; + const auto [to_x, to_y] = to; + + return make_tuple(sgn(to_x - x), sgn(to_y - y)); +} + +bool +lint(line_type stone_a, line_type stone_b, point_type& cross_point) +{ + const auto p_1 = make_tuple(get<0>(stone_a), get<1>(stone_a)); + const auto p_2 = make_tuple(get<0>(stone_a) + get<3>(stone_a), get<1>(stone_a) + get<4>(stone_a)); + + const auto p_3 = make_tuple(get<0>(stone_b), get<1>(stone_b)); + const auto p_4 = make_tuple(get<0>(stone_b) + get<3>(stone_b), get<1>(stone_b) + get<4>(stone_b)); + + const auto a_1 = get<1>(p_2) - get<1>(p_1); + const auto b_1 = get<0>(p_1) - get<0>(p_2); + const auto c_1 = a_1 * (get<0>(p_1)) + b_1 * (get<1>(p_1)); + + const auto a_2 = get<1>(p_4) - get<1>(p_3); + const auto b_2 = get<0>(p_3) - get<0>(p_4); + const auto c_2 = a_2 * (get<0>(p_3)) + b_2 * (get<1>(p_3)); + + const auto determinant = a_1 * b_2 - a_2 * b_1; + + if ( determinant == 0 ) { + return false; + } + + auto p_x = (b_2 * c_1 - b_1 * c_2) / determinant; + auto p_y = (a_1 * c_2 - a_2 * c_1) / determinant; + + cross_point = make_tuple(p_x, p_y); + + return true; +} + +void +part1(const puzzle_type& input) +{ + const auto in_range = [](point_type point) -> bool { + static const auto lower_limit = 200000000000000.0; + static const auto upper_limit = 400000000000000.0; + + const auto [x, y] = point; + + return x > lower_limit && x < upper_limit && y > lower_limit && y < upper_limit; + }; + + const auto in_future = [](line_type stone, point_type point) -> bool { + const auto sgn_stone = get_direction(stone); + const auto sgn_point = get_direction(stone, point); + + return sgn_stone == sgn_point; + }; + + long sum = 0; + for ( size_t idx = 0; idx != input.size(); ++idx ) { + const auto& stone_a = input[idx]; + + for ( size_t idx2 = idx + 1; idx2 < input.size(); ++idx2 ) { + const auto& stone_b = input[idx2]; + + point_type cross_point; + if ( lint(stone_a, stone_b, cross_point) && in_range(cross_point) && in_future(stone_a, cross_point) && in_future(stone_b, cross_point) ) { + ++sum; + } + } + } + cout << sum << endl; +} + +void +part2(const puzzle_type& input) +{ + auto config = z3::config(); + auto context = z3::context(config); + auto solver = z3::solver(context); + + const auto px = context.int_const("px"); + const auto py = context.int_const("py"); + const auto pz = context.int_const("pz"); + const auto vx = context.int_const("vx"); + const auto vy = context.int_const("vy"); + const auto vz = context.int_const("vz"); + + for ( size_t i = 0; i != input.size(); ++i ) { + const auto& stone = input[i]; + + const auto pxn = context.int_val(int64_t(get<0>(stone))); + const auto pyn = context.int_val(int64_t(get<1>(stone))); + const auto pzn = context.int_val(int64_t(get<2>(stone))); + const auto vxn = context.int_val(int64_t(get<3>(stone))); + const auto vyn = context.int_val(int64_t(get<4>(stone))); + const auto vzn = context.int_val(int64_t(get<5>(stone))); + const auto tn = context.int_const(to_string(i+1).c_str()); + + solver.add(tn >= 0); + solver.add(pxn + vxn * tn == px + vx * tn); + solver.add(pyn + vyn * tn == py + vy * tn); + solver.add(pzn + vzn * tn == pz + vz * tn); + } + + solver.check(); + + auto model = solver.get_model(); + + cout << model.eval(px).as_int64() + model.eval(py).as_int64() + model.eval(pz).as_int64() << endl; +} + +int +main() +{ + const auto input = read_file("data/day24.txt"); + + part1(input); + part2(input); +} diff --git a/2023/src/day25.cpp b/2023/src/day25.cpp new file mode 100644 index 0000000..1d5e19e --- /dev/null +++ b/2023/src/day25.cpp @@ -0,0 +1,140 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +using graph_type = map>; + +vector +split(const string& line, char sep) +{ + vector parts; + stringstream input{ line }; + + for ( string part; getline(input, part, sep); ) { + parts.emplace_back(part); + } + + return parts; +} + +graph_type +read_file(string_view filename) +{ + fstream input{ filename }; + graph_type graph; + + for ( string line; getline(input, line); ) { + const auto components = split(line.erase(line.find(':'), 1), ' '); + + for ( size_t i = 1; i < components.size(); ++i ) { + graph[components[0]].insert(components[i]); + graph[components[i]].insert(components[0]); + } + } + + return graph; +} + +bool +bfs(graph_type graph, const string& source, const string& dest, function visit) // NOLINT +{ + set visited; + + queue queue; + queue.emplace(source); + + while ( !queue.empty() ) { + auto candidate = queue.front(); + queue.pop(); + + if ( candidate == dest ) { + return true; + } + + for ( const auto& neighbour: graph[candidate] ) { + if ( !visited.contains(neighbour) ) { + queue.emplace(neighbour); + + visit(candidate, neighbour); + visited.emplace(neighbour); + } + } + } + return false; +} + +auto +random_node(const graph_type& graph) +{ + static random_device dev; + static mt19937 generator(dev()); + + uniform_int_distribution distribute(0, graph.size()-1); + + auto iter = graph.begin(); + advance(iter, distribute(generator)); + return iter->first; +} + +void +part1(graph_type graph) +{ + map, int> frequencies; + for ( size_t idx = 0; idx != 2; ++idx ) { + for ( const auto& second: graph ) { + bfs(graph, random_node(graph), second.first, [&](const string& candidate, const string& neighbour) { + if ( candidate < neighbour ) { + frequencies[make_tuple(candidate, neighbour)]++; + } + else { + frequencies[make_tuple(neighbour, candidate)]++; + } + }); + } + } + + vector, int>> sorted_frequencies{ frequencies.begin(), frequencies.end() }; + + sort(sorted_frequencies.begin(), sorted_frequencies.end(), [](const auto& lhs, const auto& rhs) { + return get<1>(lhs) > get<1>(rhs); + }); + + sorted_frequencies.erase(sorted_frequencies.begin() + 3, sorted_frequencies.end()); + + for ( const auto& link: sorted_frequencies ) { + const auto [left, right] = get<0>(link); + + graph[left].erase(right); + graph[right].erase(left); + } + + auto reachable = [&graph](const string& start_node) { + set nodes; + bfs(graph, start_node, "", [&nodes](const string& candidate, const string& neighbour) { + nodes.insert(candidate); + nodes.insert(neighbour); + }); + return nodes.size(); + }; + + const auto [left, right] = get<0>(sorted_frequencies[0]); + + cout << reachable(left) * reachable(right) << endl; +} + +int +main() +{ + auto graph = read_file("data/day25.txt"); + part1(graph); +} -- cgit v1.3