From ae1e96f10b399266825e275ca4a8100ceede9cad Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Thu, 23 Oct 2025 19:28:20 +0200 Subject: days 19-25, aoc 2016 --- 2016/src/day19.cpp | 45 +++++++++ 2016/src/day20.cpp | 128 ++++++++++++++++++++++++ 2016/src/day21.cpp | 222 +++++++++++++++++++++++++++++++++++++++++ 2016/src/day22.cpp | 166 +++++++++++++++++++++++++++++++ 2016/src/day23.cpp | 287 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2016/src/day24.cpp | 153 ++++++++++++++++++++++++++++ 2016/src/day25.cpp | 210 +++++++++++++++++++++++++++++++++++++++ 7 files changed, 1211 insertions(+) create mode 100644 2016/src/day19.cpp create mode 100644 2016/src/day20.cpp create mode 100644 2016/src/day21.cpp create mode 100644 2016/src/day22.cpp create mode 100644 2016/src/day23.cpp create mode 100644 2016/src/day24.cpp create mode 100644 2016/src/day25.cpp (limited to '2016/src') diff --git a/2016/src/day19.cpp b/2016/src/day19.cpp new file mode 100644 index 0000000..2d7282f --- /dev/null +++ b/2016/src/day19.cpp @@ -0,0 +1,45 @@ +#include +#include + +using namespace std; + +namespace { + +template +T +fn(T N) + requires std::is_integral_v +{ + return T(1) << static_cast(floor(log2(N))); +} + +void +part1(unsigned N) +{ + cout << (2 * (N - fn(N))) + 1 << '\n'; +} + +void +part2(unsigned N) +{ + auto log_3 = [](double x) { return log(x) / log(3); }; + + auto threes = pow(3, floor(log_3(N - 1))); + if ( N <= 2 * threes ) { + cout << static_cast(N - threes); + } + else { + cout << static_cast(N - threes + N - (2 * threes)); + } + cout << '\n'; +} + +} // namespace + +int +main() +{ + const unsigned puzzle = 3017957; + part1(puzzle); + part2(puzzle); +} diff --git a/2016/src/day20.cpp b/2016/src/day20.cpp new file mode 100644 index 0000000..49a9ec1 --- /dev/null +++ b/2016/src/day20.cpp @@ -0,0 +1,128 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +struct Range { + long long start; + long long end; +}; + +vector +readFile(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector ranges; + + for ( string line; getline(file, line); ) { + stringstream stream{ line }; + char dash{}; + long long start{}; + long long end{}; + + stream >> start >> dash >> end; + + ranges.emplace_back(start, end); + } + + return ranges; +} + +void +sortRanges(vector& ranges) +{ + ranges::sort(ranges, [](const auto& lhs, const auto& rhs) { + if ( lhs.start != rhs.start ) { + return lhs.start < rhs.start; + } + return lhs.end < rhs.end; + }); +} + +void +mergeRanges(vector& ranges) +{ + if ( ranges.empty() ) { + return; + } + + vector mergedRanges; + + auto current = ranges[0]; + for ( size_t i = 1; i != ranges.size(); ++i ) { + if ( ranges[i].start <= current.end + 1 ) { + current.end = max(current.end, ranges[i].end); + } + else { + mergedRanges.emplace_back(current); + current = ranges[i]; + } + } + mergedRanges.emplace_back(current); + + ranges.swap(mergedRanges); +} + +long long +findLowestAllowedIP(const vector& ranges) +{ + if ( ranges.empty() || ranges[0].start > 0 ) { + return 0; + } + return ranges[0].end + 1; +} + +long long +countAllowedIPs(const vector& ranges, long long max_ip) +{ + long long allowed_count = 0; + + for ( size_t i = 0; i < ranges.size() - 1; ++i ) { + allowed_count += ranges[i + 1].start - ranges[i].end - 1; + } + + if ( !ranges.empty() && ranges.back().end < max_ip ) { + allowed_count += max_ip - ranges.back().end; + } + + if ( ranges.empty() ) { + allowed_count = max_ip + 1; + } + + return allowed_count; +} + +void +part1(vector ranges) +{ + sortRanges(ranges); + mergeRanges(ranges); + + cout << findLowestAllowedIP(ranges) << '\n'; +} + +void +part2(vector ranges, long long max_ip = 4294967295) +{ + sortRanges(ranges); + mergeRanges(ranges); + + cout << countAllowedIPs(ranges, max_ip) << '\n'; +} + +} // namespace + +int +main() +{ + auto ranges = readFile("data/day20.txt"); + part1(ranges); + part2(ranges); +} diff --git a/2016/src/day21.cpp b/2016/src/day21.cpp new file mode 100644 index 0000000..7e8fed7 --- /dev/null +++ b/2016/src/day21.cpp @@ -0,0 +1,222 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +void +swap_at_pos(string& str, size_t x, size_t y) +{ + if ( str.empty() ) { + return; + } + + swap(str.at(x), str.at(y)); +} + +void +swap_letter(string& str, char x, char y) +{ + if ( str.empty() ) { + return; + } + + for ( auto& chr: str ) { + if ( chr == x ) { + chr = y; + } + else if ( chr == y ) { + chr = x; + } + } +} + +void +rotate_left(string& str, size_t n) +{ + if ( str.empty() ) { + return; + } + + ranges::rotate(str, str.begin() + static_cast(n % str.size())); +} + +void +rotate_right(string& str, size_t n) +{ + if ( str.empty() ) { + return; + } + + rotate_left(str, str.size() - n); +} + +void +rotate(string& str, char chr) +{ + if ( str.empty() ) { + return; + } + + const auto idx = str.find(chr); + if ( idx == string::npos ) { + return; + } + + const auto steps = 1 + idx + (idx >= 4 ? 1 : 0); + rotate_right(str, steps % str.size()); +} + +void +reverse(string& str, size_t x, size_t y) +{ + if ( str.empty() ) { + return; + } + + if ( x > y ) { + swap(x, y); + } + + reverse(str.begin() + static_cast(x), + str.begin() + static_cast(y) + 1); +} + +void +move(string& str, size_t x, size_t y) +{ + if ( str.empty() ) { + return; + } + + const auto chr = str.at(x); + + str.erase(x, 1); + str.insert(y, 1, chr); +} + +vector +readLines(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector lines; + + for ( string line; getline(file, line); ) { + lines.emplace_back(line); + } + + return lines; +} + +vector +split(const string& line, char sep = ' ') +{ + vector words; + stringstream input{ line }; + + for ( string word; getline(input, word, sep); ) { + words.emplace_back(word); + } + + return words; +} + +void +part1(const vector& lines, string str) +{ + for ( const auto& line: lines ) { + auto words = split(line); + + if ( line.starts_with("swap position") ) { + swap_at_pos(str, stoull(words.at(2)), stoull(words.at(5))); + } + else if ( line.starts_with("swap letter") ) { + swap_letter(str, words.at(2).at(0), words.at(5).at(0)); + } + else if ( line.starts_with("rotate left") ) { + rotate_left(str, stoull(words.at(2))); + } + else if ( line.starts_with("rotate right") ) { + rotate_right(str, stoull(words.at(2))); + } + else if ( line.starts_with("rotate based") ) { + rotate(str, words.at(6).at(0)); + } + else if ( line.starts_with("reverse") ) { + reverse(str, stoull(words.at(2)), stoull(words.at(4))); + } + else if ( line.starts_with("move") ) { + move(str, stoull(words.at(2)), stoull(words.at(5))); + } + else { + cerr << "unknown command: " << line << '\n'; + return; + } + } + cout << str << '\n'; +} + +void +part2(const vector& lines, string str) +{ + for ( const auto& line: ranges::reverse_view(lines) ) { + auto words = split(line); + + if ( line.starts_with("swap position") ) { + swap_at_pos(str, stoull(words.at(2)), stoull(words.at(5))); + } + else if ( line.starts_with("swap letter") ) { + swap_letter(str, words.at(2).at(0), words.at(5).at(0)); + } + else if ( line.starts_with("rotate left") ) { + rotate_right(str, stoull(words.at(2))); + } + else if ( line.starts_with("rotate right") ) { + rotate_left(str, stoull(words.at(2))); + } + else if ( line.starts_with("rotate based") ) { + auto chr = words.at(6).at(0); + for ( size_t i = 0; i != str.size(); ++i ) { + string tmp = str; + rotate_left(tmp, i); + + auto idx = tmp.find(chr); + auto steps = (1 + idx + (idx >= 4 ? 1 : 0)); + + if ( ((steps - i + str.size()) % str.size()) == 0 ) { + str = tmp; + break; + } + } + } + else if ( line.starts_with("reverse") ) { + reverse(str, stoull(words.at(2)), stoull(words.at(4))); + } + else if ( line.starts_with("move") ) { + move(str, stoull(words.at(5)), stoull(words.at(2))); + } + else { + cerr << "unknown command: " << line << '\n'; + return; + } + } + cout << str << '\n'; +} + +} // namespace + +int +main() +{ + auto lines = readLines("data/day21.txt"); + + part1(lines, "abcdefgh"); + part2(lines, "fbgdceah"); +} diff --git a/2016/src/day22.cpp b/2016/src/day22.cpp new file mode 100644 index 0000000..c4d1642 --- /dev/null +++ b/2016/src/day22.cpp @@ -0,0 +1,166 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +struct Node { + int x, y; + int size, used, avail, percent; + + [[nodiscard]] + tuple pos() const + { + return { x, y }; + } +}; + +vector +readNodes(const filesystem::path& filename) +{ + static const regex line_regex(R"(^/dev/grid/node-x(\d+)-y(\d+)\s+(\d+)T\s+(\d+)T\s+(\d+)T\s+(\d+)%$)"); + + ifstream file{ filename }; + vector nodes; + + for ( string line; getline(file, line); ) { + smatch match; + + if ( !regex_match(line, match, line_regex) ) { + continue; + } + + Node node{ + .x = stoi(match[1].str()), // x + .y = stoi(match[2].str()), // y + .size = stoi(match[3].str()), // size + .used = stoi(match[4].str()), // used + .avail = stoi(match[5].str()), // avail + .percent = stoi(match[6].str()) // percent + }; + + nodes.emplace_back(node); + } + + return nodes; +} + +void +part1(const vector& nodes) +{ + long count = 0; + + for ( size_t i = 0; i != nodes.size(); ++i ) { + if ( nodes[i].used == 0 ) { + continue; + } + + for ( size_t j = 0; j != nodes.size(); ++j ) { + if ( i == j ) { + continue; + } + + if ( nodes[i].used < nodes[j].avail ) { + ++count; + } + } + } + + cout << count << '\n'; +} + +void +part2(const vector& nodes) +{ + using pos_type = tuple; + + map grid; + +#ifdef PRINT + const auto max_y = ranges::max_element(nodes, {}, &Node::y)->y; +#endif + const auto max_x = ranges::max_element(nodes, {}, &Node::x)->x; + const auto largest = ranges::max_element(nodes, {}, &Node::avail)->avail; + + const pos_type g_pos = { max_x, 0 }; + const pos_type s_pos = { 0, 0 }; + + pos_type start{}; + + for ( const auto& node: nodes ) { + auto pos = node.pos(); + if ( pos == s_pos ) { + grid[pos] = 'S'; + } + else if ( pos == g_pos ) { + grid[pos] = 'G'; + } + else if ( node.used == 0 ) { + grid[pos] = '_'; + start = pos; + } + else if ( node.used >= largest ) { + grid[pos] = '#'; + } + else { + grid[pos] = '.'; + } + } + +#ifdef PRINT + string result{}; + for ( int pos_y = 0; pos_y <= max_y; ++pos_y ) { + for ( int pos_x = 0; pos_x <= max_x; ++pos_x ) { + result += grid[{ pos_x, pos_y }]; + } + result += '\n'; + } + + cout << result << '\n'; +#endif + + set seen; + queue> queue; // position, #Schritte + + queue.emplace(start, 0); + while ( !queue.empty() ) { + const auto [pos, steps] = queue.front(); + queue.pop(); + + if ( pos == g_pos ) { + cout << steps + (5 * (max_x - 1)) << '\n'; + return; + } + + static const pos_type dirs[]{ { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; + + for ( const auto [dx, dy]: dirs ) { + const auto [x, y] = pos; + const pos_type new_pos{ x + dx, y + dy }; + + if ( !grid.contains(new_pos) || grid.at(new_pos) == '#' || seen.contains(new_pos) ) { + continue; + } + + seen.insert(new_pos); + queue.emplace(new_pos, steps + 1); + } + } +} + +} // namespace + +int +main() +{ + auto nodes = readNodes("data/day22.txt"); + part1(nodes); + part2(nodes); +} diff --git a/2016/src/day23.cpp b/2016/src/day23.cpp new file mode 100644 index 0000000..81bffe4 --- /dev/null +++ b/2016/src/day23.cpp @@ -0,0 +1,287 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +enum class OpCode : uint8_t { + CPY, + INC, + DEC, + JNZ, + TGL +}; + +using memory_type = map; + +struct Argument { + explicit Argument(string value) + : value{ std::move(value) } + { + } + + [[nodiscard]] + int eval(const memory_type& memory) const + { + const auto chr = value.at(0); + + if ( chr >= 'a' && chr <= 'z' ) { + return memory.at(chr); + } + else { + return stoi(value); + } + } + + [[nodiscard]] + char reg() const + { + if ( !is_reg() ) { + throw runtime_error("invalid register access! "s + value); + } + + return value.at(0); + } + + [[nodiscard]] + bool is_reg() const + { + const auto chr = value.at(0); + + return chr >= 'a' && chr <= 'z'; + } + + string value; +}; + +struct Instruction { + Instruction(OpCode opCode, const Argument& x) + : opCode{ opCode } + , x{ x } + { + } + + Instruction(OpCode opCode, const Argument& x, const Argument& y) + : opCode{ opCode } + , x{ x } + , y{ y } + { + } + + OpCode opCode; + optional x; + optional y; +}; + +vector +split_words(const string& line, char sep = ' ') +{ + vector words; + stringstream strm{ line }; + + for ( string word; getline(strm, word, sep); ) { + words.emplace_back(word); + } + + return words; +} + +vector +read_file(const filesystem::path& filename) +{ + ifstream input{ filename }; + + vector instructions; + + for ( string line; getline(input, line); ) { + const auto words = split_words(line); + + if ( words.at(0) == "cpy" ) { + instructions.emplace_back(OpCode::CPY, Argument(words.at(1)), Argument(words.at(2))); + } + else if ( words.at(0) == "inc" ) { + instructions.emplace_back(OpCode::INC, Argument(words.at(1))); + } + else if ( words.at(0) == "dec" ) { + instructions.emplace_back(OpCode::DEC, Argument(words.at(1))); + } + else if ( words.at(0) == "jnz" ) { + instructions.emplace_back(OpCode::JNZ, Argument(words.at(1)), Argument(words.at(2))); + } + else if ( words.at(0) == "tgl" ) { + instructions.emplace_back(OpCode::TGL, Argument(words.at(1))); + } + else { + cerr << "unknown opcode..." << '\n'; + } + } + + return instructions; +} + +#define JIT + +void +execute(memory_type& memory, vector instructions) +{ + for ( size_t ip = 0; ip < instructions.size(); ) { +#if defined(JIT) + if ( ip + 2 < instructions.size() ) { + const auto& i0 = instructions[ip]; + const auto& i1 = instructions[ip + 1]; + const auto& i2 = instructions[ip + 2]; + + if ( i0.opCode == OpCode::INC && + i1.opCode == OpCode::DEC && + i2.opCode == OpCode::JNZ && + i2.x && i2.x->value == i1.x->value && + i2.y && i2.y->value == "-2" ) { + char X = i0.x->reg(); + char Y = i1.x->reg(); + memory[X] += memory[Y]; + memory[Y] = 0; + ip += 3; + continue; + } + } +#endif + +#if defined(JIT) + if ( ip + 5 < instructions.size() ) { + const auto& i0 = instructions[ip]; + const auto& i1 = instructions[ip + 1]; + const auto& i2 = instructions[ip + 2]; + const auto& i3 = instructions[ip + 3]; + const auto& i4 = instructions[ip + 4]; + const auto& i5 = instructions[ip + 5]; + + if ( i0.opCode == OpCode::CPY && + i1.opCode == OpCode::INC && + i2.opCode == OpCode::DEC && + i3.opCode == OpCode::JNZ && + i4.opCode == OpCode::DEC && + i5.opCode == OpCode::JNZ && + i3.x && i3.y && i3.x->value == i2.x->value && i3.y->value == "-2" && + i5.x && i5.y && i5.x->value == i4.x->value && i5.y->value == "-5" && + i0.y->is_reg() && i1.x->is_reg() && i2.x->is_reg() && i4.x->is_reg() ) { + char X = i0.x->is_reg() ? i0.x->reg() : 0; + int valX = i0.x->is_reg() ? memory[X] : stoi(i0.x->value); + + char Y = i0.y->reg(); + char Z = i1.x->reg(); + char W = i4.x->reg(); + + memory[Z] += valX * memory[W]; + memory[Y] = 0; + memory[W] = 0; + ip += 6; + continue; + } + } +#endif + + const auto& instruction = instructions.at(ip); + + // cout << "#" << ip << " - " << memory['a'] << ", " << memory['b'] << ", " << memory['c'] << ", " << memory['d'] << ": " << (int) instruction.opCode << '\n'; + + switch ( instruction.opCode ) { + using enum OpCode; + case CPY: + memory[instruction.y->reg()] = instruction.x->eval(memory); + ++ip; + break; + case INC: + memory[instruction.x->reg()]++; + ++ip; + break; + case DEC: + memory[instruction.x->reg()]--; + ++ip; + break; + case JNZ: + if ( instruction.x->eval(memory) != 0 ) { + ip += static_cast(instruction.y->eval(memory)); + } + else { + ++ip; + } + break; + case TGL: + if ( auto foo = ip + static_cast(instruction.x->eval(memory)); foo < instructions.size() ) { + switch ( instructions[foo].opCode ) { + case CPY: + instructions[foo].opCode = JNZ; + break; + case INC: + instructions[foo].opCode = DEC; + break; + case DEC: + instructions[foo].opCode = INC; + break; + case JNZ: + instructions[foo].opCode = CPY; + break; + case TGL: + instructions[foo].opCode = INC; + break; + } + } + + ++ip; + break; + } + } +} + +void +part1(const vector& instructions) +{ + map memory; + + memory['a'] = 7; + memory['b'] = 0; + memory['c'] = 0; + memory['d'] = 0; + + execute(memory, instructions); + + cout << "Part1: " << memory['a'] << '\n'; +} + +void +part2(const vector& instructions) +{ + map memory; + + memory['a'] = 12; + memory['b'] = 0; + memory['c'] = 0; + memory['d'] = 0; + + execute(memory, instructions); + + cout << "Part2: " << memory['a'] << '\n'; +} + +} // namespace + +int +main() +{ + const auto instructions = read_file("data/day23.txt"); + try { + part1(instructions); + part2(instructions); + } + catch ( exception& e ) { + cerr << e.what() << '\n'; + } +} diff --git a/2016/src/day24.cpp b/2016/src/day24.cpp new file mode 100644 index 0000000..936f216 --- /dev/null +++ b/2016/src/day24.cpp @@ -0,0 +1,153 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +using pos_type = tuple; +using grid_type = map; +using points_type = map; +using dists_type = map, size_t>; + +tuple +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + + grid_type grid; + points_type points; + + size_t row = 0; + for ( string line; getline(file, line); ) { + for ( size_t col = 0; col != line.size(); ++col ) { + auto chr = line[col]; + pos_type pos{ col, row }; + + grid[pos] = chr; + + if ( isdigit(chr) != 0 ) { + points[chr] = pos; + } + } + + ++row; + } + return { grid, points }; +} + +size_t +bfs(const grid_type& grid, const pos_type src, const pos_type dest) +{ + set seen; + queue> queue; + + queue.emplace(src, 0); + seen.insert(src); + + while ( !queue.empty() ) { + auto [pos, steps] = queue.front(); + queue.pop(); + + if ( pos == dest ) { + return steps; + } + + static const pos_type dirs[]{ { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; + const auto [x, y] = pos; + + for ( const auto [dx, dy]: dirs ) { + const pos_type new_pos{ x + dx, y + dy }; + + if ( grid.at(new_pos) == '#' || seen.contains(new_pos) ) { + continue; + } + + seen.insert(new_pos); + queue.emplace(new_pos, steps + 1); + } + } + + return 0; +} + +dists_type +build_dists(const grid_type& grid, const points_type& points) +{ + dists_type dists; + + for ( auto src = points.begin(); src != points.end(); ++src ) { + for ( auto dest = next(src); dest != points.end(); ++dest ) { + const auto dist = bfs(grid, src->second, dest->second); + + dists[{ src->first, dest->first }] = dist; + dists[{ dest->first, src->first }] = dist; + } + } + + return dists; +} + +size_t +shortest_route(const dists_type& dists, + const points_type& points, + bool return_to_start) +{ + vector others; + for ( const auto& [id, _]: points ) { + if ( id != '0' ) { + others.push_back(id); + } + } + + size_t best = numeric_limits::max(); + + do { + size_t dist = 0; + char current = '0'; + + for ( char next: others ) { + dist += dists.at({ current, next }); + current = next; + } + + if ( return_to_start ) { + dist += dists.at({ current, '0' }); + } + + best = min(best, dist); + } while ( next_permutation(others.begin(), others.end()) ); + + return best; +} + +void +part1(const grid_type& grid, const points_type& points) +{ + auto dists = build_dists(grid, points); + auto route = shortest_route(dists, points, false); + cout << "Part1: " << route << '\n'; +} + +void +part2(const grid_type& grid, const points_type& points) +{ + auto dists = build_dists(grid, points); + auto route = shortest_route(dists, points, true); + cout << "Part2: " << route << '\n'; +} + +} // namespace + +int +main() +{ + auto [grid, points] = read_file("data/day24.txt"); + part1(grid, points); + part2(grid, points); +} diff --git a/2016/src/day25.cpp b/2016/src/day25.cpp new file mode 100644 index 0000000..ba3ad04 --- /dev/null +++ b/2016/src/day25.cpp @@ -0,0 +1,210 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +enum class OpCode : uint8_t { + CPY, + INC, + DEC, + JNZ, + OUT, +}; + +using memory_type = map; + +struct Argument { + explicit Argument(string value) + : value{ std::move(value) } + { + } + + [[nodiscard]] + int eval(const memory_type& memory) const + { + const auto chr = value.at(0); + + if ( chr >= 'a' && chr <= 'z' ) { + return memory.at(chr); + } + else { + return stoi(value); + } + } + + [[nodiscard]] + char reg() const + { + if ( !is_reg() ) { + throw runtime_error("invalid register access! "s + value); + } + + return value.at(0); + } + + [[nodiscard]] + bool is_reg() const + { + const auto chr = value.at(0); + + return chr >= 'a' && chr <= 'z'; + } + + string value; +}; + +struct Instruction { + Instruction(OpCode opCode, const Argument& x) + : opCode{ opCode } + , x{ x } + { + } + + Instruction(OpCode opCode, const Argument& x, const Argument& y) + : opCode{ opCode } + , x{ x } + , y{ y } + { + } + + OpCode opCode; + optional x; + optional y; +}; + +vector +split_words(const string& line, char sep = ' ') +{ + vector words; + stringstream strm{ line }; + + for ( string word; getline(strm, word, sep); ) { + words.emplace_back(word); + } + + return words; +} + +vector +read_file(const filesystem::path& filename) +{ + ifstream input{ filename }; + + vector instructions; + + for ( string line; getline(input, line); ) { + const auto words = split_words(line); + + if ( words.at(0) == "cpy" ) { + instructions.emplace_back(OpCode::CPY, Argument(words.at(1)), Argument(words.at(2))); + } + else if ( words.at(0) == "inc" ) { + instructions.emplace_back(OpCode::INC, Argument(words.at(1))); + } + else if ( words.at(0) == "dec" ) { + instructions.emplace_back(OpCode::DEC, Argument(words.at(1))); + } + else if ( words.at(0) == "jnz" ) { + instructions.emplace_back(OpCode::JNZ, Argument(words.at(1)), Argument(words.at(2))); + } + else if ( words.at(0) == "out" ) { + instructions.emplace_back(OpCode::OUT, Argument(words.at(1))); + } + else { + cerr << "unknown opcode..." << '\n'; + } + } + + return instructions; +} + +#define JIT + +string +execute(memory_type& memory, vector instructions) +{ + string result; + + for ( size_t ip = 0; ip < instructions.size(); ) { + const auto& instruction = instructions.at(ip); + + // cout << "#" << ip << " - " << memory['a'] << ", " << memory['b'] << ", " << memory['c'] << ", " << memory['d'] << ": " << (int) instruction.opCode << '\n'; + + switch ( instruction.opCode ) { + using enum OpCode; + case CPY: + memory[instruction.y->reg()] = instruction.x->eval(memory); + ++ip; + break; + case INC: + memory[instruction.x->reg()]++; + ++ip; + break; + case DEC: + memory[instruction.x->reg()]--; + ++ip; + break; + case JNZ: + if ( instruction.x->eval(memory) != 0 ) { + ip += static_cast(instruction.y->eval(memory)); + } + else { + ++ip; + } + break; + case OUT: + result += to_string(instruction.x->eval(memory)); + if ( result.size() >= 20 ) { + ip = instructions.size(); + } + else { + ++ip; + } + } + } + + return result; +} + +void +part1(const vector& instructions) +{ + for ( int seed = 0;; ++seed ) { + map memory; + + memory['a'] = seed; + memory['b'] = 0; + memory['c'] = 0; + memory['d'] = 0; + + auto result = execute(memory, instructions); + + if ( result == "01010101010101010101" ) { + cout << "Part1: " << seed << '\n'; + return; + } + } +} + +} // namespace + +int +main() +{ + const auto instructions = read_file("data/day25.txt"); + try { + part1(instructions); + } + catch ( exception& e ) { + cerr << e.what() << '\n'; + } +} -- cgit v1.3