Day 8

It seems like you're meant to use the left/right instructions to navigate the network.

After examining the maps for a bit, two nodes stick out: AAA and ZZZ. You feel like AAA is where you are now, and you have to follow the left/right instructions until you reach ZZZ.

This format defines each node of the network individually. For example:

RL

AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)

Starting with AAA, you need to look up the next element based on the next left/right instruction in your input. In this example, start with AAA and go right (R) by choosing the right element of AAA, CCC. Then, L means to choose the left element of CCC, ZZZ. By following the left/right instructions, you reach ZZZ in 2 steps.

Of course, you might not find ZZZ right away. If you run out of left/right instructions, repeat the whole sequence of instructions as necessary: RL really means RLRLRLRLRLRLRLRL... and so on. For example, here is a situation that takes 6 steps to reach ZZZ:

LLR

AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)

Starting at AAA, follow the left/right instructions. How many steps are required to reach ZZZ?

Problem solving

Using the first example, traversing will take 2 steps: AAA -> CCC -> ZZZ The second example, traversing will take 6 steps:

AAA -> (L)BBB -> (L)AAA -> (R)BBB -> (L)AAA -> (L)BBB -> (R)ZZZZ

Simple solution: traverse through each node and count the steps

Part 2

Simultaneously start on every node that ends with A. How many steps does it take before you're only on nodes that end with Z?

LR

11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)

Part 2 states that we must simultaneously start on nodes ending with 'A' as well as simultaneously end with 'Z'

For example we must start on 11A and 22A

Following 1 traversal, or 1 step is 11A -> 11B, 22A -> 22B

Eventually, in 6 steps, we both end up with 11Z and 22Z respectively.

The simple solution of traversing each node will not work or will take too long.

Lets look at each individual traversal:

LR
11A |L 11B |R 11Z |L 11B |R 11Z |L 11B |R 11Z
22A |L 22B |R 22C |L 22Z |R 22B |L 22C |R 22Z

Lets take 11A: It reaches 11Z in 2 steps, 11B and 11Z 
          22A: It reaches 22Z in 3 steps, 22B and 22C then 22Z

In order for them to meet on the same node:

Node 11A must repeat 3 times
Node 22A must repeat 2 times
Lowest common multiple of 2 and 3 is 6 (the answer)

Algorithm:

For each Node ending with 'A': NodeA,
Traverse through the tree until we encounter a Node ending with 'Z': NodeZ
Count the steps it takes from NodeA to NodeZ

Calculate the Lowest Common Multiple of all steps of N NodeA, i.e (NodeA0, NodeA1, ... NodeAN):

LCM(steps0, steps1, stepsN)

Day 8 Part 2 Answer

In our input we encountered 6 Nodes: ['KTA', 'PLA', 'LJA', 'AAA', 'JXA', 'NFA']

For each one we calculated the steps:

String	Steps to 'Z'
KTA	14893
PLA	19951
LJA	22199
AAA	16579
JXA	17141
NFA	12083

Simply calculate the Least Common Multiple:

LCM(14893, 19951, 22199, 16579, 17141, 12083) = 12927600769609