82 lines
2.2 KiB
D
82 lines
2.2 KiB
D
|
import std.stdio;
|
||
|
|
import std.algorithm;
|
||
|
|
import std.string;
|
||
|
|
import std.array;
|
||
|
|
import std.math;
|
||
|
|
|
||
|
|
struct Node {
|
||
|
|
string name, left, right;
|
||
|
|
}
|
||
|
|
|
||
|
|
struct Puzzle {
|
||
|
|
string instructions;
|
||
|
|
Node[string] nodes;
|
||
|
|
}
|
||
|
|
|
||
|
|
Puzzle parsePuzzle(string filename) {
|
||
|
|
Puzzle p;
|
||
|
|
string[] lines = File(filename).byLineCopy.array;
|
||
|
|
p.instructions = lines[0].strip;
|
||
|
|
foreach (string line; lines[2..$]) {
|
||
|
|
string[] nameAndBranches = line.split("=");
|
||
|
|
string name = nameAndBranches[0].strip;
|
||
|
|
string[] branches = nameAndBranches[1].strip[1..$-1].split(",").map!strip.array;
|
||
|
|
p.nodes[name] = Node(name, branches[0], branches[1]);
|
||
|
|
}
|
||
|
|
return p;
|
||
|
|
}
|
||
|
|
|
||
|
|
void part1() {
|
||
|
|
Puzzle p = parsePuzzle("input.txt");
|
||
|
|
Node currentNode = p.nodes["AAA"];
|
||
|
|
size_t instructionIdx = 0;
|
||
|
|
ulong steps = 0;
|
||
|
|
while (currentNode.name != "ZZZ") {
|
||
|
|
char instruction = p.instructions[instructionIdx++];
|
||
|
|
if (instructionIdx >= p.instructions.length) instructionIdx = 0;
|
||
|
|
if (instruction == 'L') {
|
||
|
|
currentNode = p.nodes[currentNode.left];
|
||
|
|
} else if (instruction == 'R') {
|
||
|
|
currentNode = p.nodes[currentNode.right];
|
||
|
|
}
|
||
|
|
steps++;
|
||
|
|
}
|
||
|
|
writeln(steps);
|
||
|
|
}
|
||
|
|
|
||
|
|
void part2() {
|
||
|
|
ulong gcd(ulong a, ulong b) {
|
||
|
|
if (a < b) swap(a, b);
|
||
|
|
while (b != 0) {
|
||
|
|
a = a % b;
|
||
|
|
swap(a, b);
|
||
|
|
}
|
||
|
|
return a;
|
||
|
|
}
|
||
|
|
|
||
|
|
ulong lcm(ulong a, ulong b) {
|
||
|
|
return a / gcd(a, b) * b;
|
||
|
|
}
|
||
|
|
Puzzle p = parsePuzzle("input.txt");
|
||
|
|
Node[] startNodes = p.nodes.values.filter!(n => n.name[$-1] == 'A').array;
|
||
|
|
ulong lcmSteps = 1;
|
||
|
|
foreach (size_t i, Node startNode; startNodes) {
|
||
|
|
Node currentNode = startNode;
|
||
|
|
ulong cycleLength = 0;
|
||
|
|
size_t instructionIdx = 0;
|
||
|
|
while (currentNode.name[$-1] != 'Z') {
|
||
|
|
char instruction = p.instructions[instructionIdx++];
|
||
|
|
if (instructionIdx >= p.instructions.length) instructionIdx = 0;
|
||
|
|
currentNode = instruction == 'L' ? p.nodes[currentNode.left] : p.nodes[currentNode.right];
|
||
|
|
cycleLength++;
|
||
|
|
}
|
||
|
|
lcmSteps = lcm(lcmSteps, cycleLength);
|
||
|
|
}
|
||
|
|
writeln(lcmSteps);
|
||
|
|
}
|
||
|
|
|
||
|
|
void main() {
|
||
|
|
part1();
|
||
|
|
part2();
|
||
|
|
}
|