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 ... :) --- 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 ---------------------------- 25 files changed, 3660 deletions(-) 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 (limited to 'src') 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