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 ... :) --- .gitignore | 4 +- 2020/data/.gitkeep | 0 2020/src/day01.cpp | 55 ++++++++++ 2023/data/.gitkeep | 0 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 +++++++++++++++++++++++++ data/.gitkeep | 0 makefile | 42 +++----- src/day01.cpp | 82 --------------- src/day02.cpp | 100 ------------------ src/day03.cpp | 174 ------------------------------- src/day04.cpp | 114 --------------------- src/day05.cpp | 183 --------------------------------- src/day06.cpp | 74 -------------- src/day07.cpp | 189 ---------------------------------- src/day08.cpp | 110 -------------------- src/day09.cpp | 75 -------------- src/day10.cpp | 216 --------------------------------------- src/day11.cpp | 100 ------------------ src/day12.cpp | 182 --------------------------------- src/day13.cpp | 115 --------------------- src/day14.cpp | 239 ------------------------------------------- src/day15.cpp | 102 ------------------- src/day16.cpp | 132 ------------------------ src/day17.cpp | 112 -------------------- src/day18.cpp | 115 --------------------- src/day19.cpp | 183 --------------------------------- src/day20.cpp | 293 ----------------------------------------------------- src/day21.cpp | 148 --------------------------- src/day22.cpp | 157 ---------------------------- src/day23.cpp | 152 --------------------------- src/day24.cpp | 173 ------------------------------- src/day25.cpp | 140 ------------------------- 56 files changed, 3729 insertions(+), 3692 deletions(-) create mode 100644 2020/data/.gitkeep create mode 100644 2020/src/day01.cpp create mode 100644 2023/data/.gitkeep 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 delete mode 100644 data/.gitkeep delete mode 100644 src/day01.cpp delete mode 100644 src/day02.cpp delete mode 100644 src/day03.cpp delete mode 100644 src/day04.cpp delete mode 100644 src/day05.cpp delete mode 100644 src/day06.cpp delete mode 100644 src/day07.cpp delete mode 100644 src/day08.cpp delete mode 100644 src/day09.cpp delete mode 100644 src/day10.cpp delete mode 100644 src/day11.cpp delete mode 100644 src/day12.cpp delete mode 100644 src/day13.cpp delete mode 100644 src/day14.cpp delete mode 100644 src/day15.cpp delete mode 100644 src/day16.cpp delete mode 100644 src/day17.cpp delete mode 100644 src/day18.cpp delete mode 100644 src/day19.cpp delete mode 100644 src/day20.cpp delete mode 100644 src/day21.cpp delete mode 100644 src/day22.cpp delete mode 100644 src/day23.cpp delete mode 100644 src/day24.cpp delete mode 100644 src/day25.cpp diff --git a/.gitignore b/.gitignore index afa46c7..df07bbc 100644 --- a/.gitignore +++ b/.gitignore @@ -1,3 +1,3 @@ -bin/ -data/*.txt +*/bin/ +*/data/*.txt .gdb_history diff --git a/2020/data/.gitkeep b/2020/data/.gitkeep new file mode 100644 index 0000000..e69de29 diff --git a/2020/src/day01.cpp b/2020/src/day01.cpp new file mode 100644 index 0000000..d2d8629 --- /dev/null +++ b/2020/src/day01.cpp @@ -0,0 +1,55 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +auto +read_file(string_view filename) +{ + fstream input{ filename }; + vector data; + + for ( long value = 0; input >> value; ) { + data.emplace_back(value); + } + + return data; +} + +void +process(const vector& values) +{ + const long year = 2020; + + if (accumulate(values.begin(), values.end(), 0L) == year) { + cout << accumulate(values.begin(), values.end(), 1, multiplies<>()) << endl; + } +} + +void +combination(const vector& values, size_t r) +{ + vector v(values.size()); + fill(v.end() - long(r), v.end(), true); + vector set(r); + do { + set.clear(); + for ( size_t i = 0; i != values.size(); ++i ) { + if ( v[i] ) { + set.emplace_back(values[i]); + } + } + process(set); + } while ( std::next_permutation(v.begin(), v.end()) ); +} + +int +main() +{ + auto values = read_file("data/day01-sample1.txt"); + combination(values, 2); + combination(values, 3); +} diff --git a/2023/data/.gitkeep b/2023/data/.gitkeep new file mode 100644 index 0000000..e69de29 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); +} diff --git a/data/.gitkeep b/data/.gitkeep deleted file mode 100644 index e69de29..0000000 diff --git a/makefile b/makefile index 1849790..e1318c1 100644 --- a/makefile +++ b/makefile @@ -1,41 +1,23 @@ include config.mk -all: bin/day01 \ - bin/day02 \ - bin/day03 \ - bin/day04 \ - bin/day05 \ - bin/day06 \ - bin/day07 \ - bin/day08 \ - bin/day09 \ - bin/day10 \ - bin/day11 \ - bin/day12 \ - bin/day13 \ - bin/day14 \ - bin/day15 \ - bin/day16 \ - bin/day17 \ - bin/day18 \ - bin/day19 \ - bin/day20 \ - bin/day21 \ - bin/day22 \ - bin/day23 \ - bin/day24 \ - bin/day25 +all: $(patsubst 2020/src/%.cpp,2020/bin/%,$(wildcard 2020/src/*.cpp)) \ + $(patsubst 2023/src/%.cpp,2023/bin/%,$(wildcard 2023/src/*.cpp)) -bin: - mkdir $@ +%/bin: + mkdir -p $@ -bin/%: src/%.cpp | bin +# 2020 +2020/bin/%: 2020/src/%.cpp | 2020/bin c++ $(CPPFLAGS) $^ -o $@ -bin/day24: src/day24.cpp | bin +# 2023 +2023/bin/%: 2023/src/%.cpp | 2023/bin + c++ $(CPPFLAGS) $^ -o $@ + +2023/bin/day24: 2023/src/day24.cpp | 2023/bin c++ $(CPPFLAGS) -Wno-sign-conversion -I/usr/local/include $^ -L/usr/local/lib -lz3 -o $@ clean: - rm -rf bin + rm -rf 2020/bin 2023/bin .PHONY: all clean diff --git a/src/day01.cpp b/src/day01.cpp deleted file mode 100644 index ff357bc..0000000 --- a/src/day01.cpp +++ /dev/null @@ -1,82 +0,0 @@ -#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/src/day02.cpp b/src/day02.cpp deleted file mode 100644 index df560c3..0000000 --- a/src/day02.cpp +++ /dev/null @@ -1,100 +0,0 @@ -#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/src/day03.cpp b/src/day03.cpp deleted file mode 100644 index b266f59..0000000 --- a/src/day03.cpp +++ /dev/null @@ -1,174 +0,0 @@ -#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/src/day04.cpp b/src/day04.cpp deleted file mode 100644 index 0d3e552..0000000 --- a/src/day04.cpp +++ /dev/null @@ -1,114 +0,0 @@ -#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/src/day05.cpp b/src/day05.cpp deleted file mode 100644 index 42fda29..0000000 --- a/src/day05.cpp +++ /dev/null @@ -1,183 +0,0 @@ -#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/src/day06.cpp b/src/day06.cpp deleted file mode 100644 index 9a429c5..0000000 --- a/src/day06.cpp +++ /dev/null @@ -1,74 +0,0 @@ -#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/src/day07.cpp b/src/day07.cpp deleted file mode 100644 index 1f44ac5..0000000 --- a/src/day07.cpp +++ /dev/null @@ -1,189 +0,0 @@ -#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/src/day08.cpp b/src/day08.cpp deleted file mode 100644 index 3e1b6c9..0000000 --- a/src/day08.cpp +++ /dev/null @@ -1,110 +0,0 @@ -#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/src/day09.cpp b/src/day09.cpp deleted file mode 100644 index 4b30e6e..0000000 --- a/src/day09.cpp +++ /dev/null @@ -1,75 +0,0 @@ -#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/src/day10.cpp b/src/day10.cpp deleted file mode 100644 index 264e111..0000000 --- a/src/day10.cpp +++ /dev/null @@ -1,216 +0,0 @@ -#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/src/day11.cpp b/src/day11.cpp deleted file mode 100644 index e1a0882..0000000 --- a/src/day11.cpp +++ /dev/null @@ -1,100 +0,0 @@ -#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/src/day12.cpp b/src/day12.cpp deleted file mode 100644 index 11bd80b..0000000 --- a/src/day12.cpp +++ /dev/null @@ -1,182 +0,0 @@ -#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/src/day13.cpp b/src/day13.cpp deleted file mode 100644 index 549457b..0000000 --- a/src/day13.cpp +++ /dev/null @@ -1,115 +0,0 @@ -#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/src/day14.cpp b/src/day14.cpp deleted file mode 100644 index 8816ce1..0000000 --- a/src/day14.cpp +++ /dev/null @@ -1,239 +0,0 @@ -#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/src/day15.cpp b/src/day15.cpp deleted file mode 100644 index 6fcbfc2..0000000 --- a/src/day15.cpp +++ /dev/null @@ -1,102 +0,0 @@ -#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/src/day16.cpp b/src/day16.cpp deleted file mode 100644 index 93c7479..0000000 --- a/src/day16.cpp +++ /dev/null @@ -1,132 +0,0 @@ -#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/src/day17.cpp b/src/day17.cpp deleted file mode 100644 index 4098bba..0000000 --- a/src/day17.cpp +++ /dev/null @@ -1,112 +0,0 @@ -#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/src/day18.cpp b/src/day18.cpp deleted file mode 100644 index 3037739..0000000 --- a/src/day18.cpp +++ /dev/null @@ -1,115 +0,0 @@ -#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/src/day19.cpp b/src/day19.cpp deleted file mode 100644 index a1d4eab..0000000 --- a/src/day19.cpp +++ /dev/null @@ -1,183 +0,0 @@ -#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/src/day20.cpp b/src/day20.cpp deleted file mode 100644 index f85ac90..0000000 --- a/src/day20.cpp +++ /dev/null @@ -1,293 +0,0 @@ -#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/src/day21.cpp b/src/day21.cpp deleted file mode 100644 index c633155..0000000 --- a/src/day21.cpp +++ /dev/null @@ -1,148 +0,0 @@ -#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/src/day22.cpp b/src/day22.cpp deleted file mode 100644 index 1afb994..0000000 --- a/src/day22.cpp +++ /dev/null @@ -1,157 +0,0 @@ -#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/src/day23.cpp b/src/day23.cpp deleted file mode 100644 index d8c20d3..0000000 --- a/src/day23.cpp +++ /dev/null @@ -1,152 +0,0 @@ -#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/src/day24.cpp b/src/day24.cpp deleted file mode 100644 index 76f459b..0000000 --- a/src/day24.cpp +++ /dev/null @@ -1,173 +0,0 @@ -#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/src/day25.cpp b/src/day25.cpp deleted file mode 100644 index 1d5e19e..0000000 --- a/src/day25.cpp +++ /dev/null @@ -1,140 +0,0 @@ -#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