Day 8: Haunted Wasteland

So the ultimate solution here is pretty simple, since it's just taking all the loop lengths and getting their LCM.

However, there are so many edge cases that are possible here that you couldn't logically arrive at a quick solution from the problem description and must analyze the input to see what's going on.

For example, from what I can tell the following input is entirely valid:

L

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

You can check to see that in this case you never escape!

There are more complex cases than that, though:

L

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

where the solution requires the Chinese Remainder Theorem to solve programmatically.

And there are cases even worse than that...

To make matters worse, they used the same LCM idea in 2019 and had the problem worded in such a way that you could arrive at the LCM solution logically and prove that it worked, rather than guessing at it from the specific input you're given. They got it right already! Was this really the best way to bring out this idea again?

I get that sometimes hacking the input is its own type of cleverness, but this was a significant break from the convention of the other problems and there was no indication this would the right way to go.

Implementation notes:

Aside from the almost comedically bad string parsing (even after cleaning up),
there are a couple of dumb implementation details that I love,
like converting a string to an int by just sticking the whole thing in a map or by dynamically resizing the array whenever we need extra elements.
After parsing all the strings, it's relatively easy to get the answer out.

If anyone has a better way to parse strings (that doesn't involve a library) I would be happy to hear it.
Somehow I suspect this might not exist, because C++ tends to be the sort of language that makes you do that yourself.

#include <bits/stdc++.h>
using namespace std;
map<string,int> string_to_node;
int get_node(const string& s) {
	if(string_to_node.count(s)) {
		return string_to_node[s];
	} else {
		int ans = string_to_node.size();
		string_to_node[s] = ans;
		return ans;
	}
}
int main() {
	string path_choices;
	getline(cin,path_choices);
	string input_line;
	getline(cin,input_line);

	vector<array<int,2>> left_right_paths;
	getline(cin,input_line);

	while(input_line.size() > 0) {

		// Ah yes, bespoke string parsing in C++
		stringstream ss(input_line);
		string start,left_string,right_string,_;
		ss >> start;
		ss >> _;
		ss >> left_string;
		ss >> right_string;
		// Take out the first character '(' and the last character ',' from the left
		// Take out the last character ')' from the right
		left_string = left_string.substr(1,left_string.size()-2);
		right_string = right_string.substr(0,right_string.size()-1);

		int node = get_node(start);
		int left_node = get_node(left_string);
		int right_node = get_node(right_string);

		left_right_paths.resize(string_to_node.size());
		left_right_paths[node][0] = left_node;
		left_right_paths[node][1] = right_node;
		getline(cin,input_line);
	}

	int node = get_node("AAA");
	int end_node = get_node("ZZZ");

	int len = 0;
	while(node != end_node) {
		int path = path_choices[len%path_choices.size()] == 'L'?0:1;
		node = left_right_paths[node][path];
		len++;
	}
	cout << len << '\n';
}

#include <bits/stdc++.h>
using namespace std;
map<string,int> string_to_node;
long long gcd(long long a, long long b) {
	if(a == 0) {return b;}
	if(b == 0) {return a;}
	return gcd(b,a%b);
}
long long lcm(long long a, long long b) {
	return b/gcd(a,b)*a;
}

int get_node(const string& s) {
	if(string_to_node.count(s)) {
		return string_to_node[s];
	} else {
		int ans = string_to_node.size();
		string_to_node[s] = ans;
		return ans;
	}
}
int main() {
	string path_choices;
	getline(cin,path_choices);
	string input_line;
	getline(cin,input_line);

	vector<array<int,2>> left_right_paths;
	getline(cin,input_line);

	while(input_line.size() > 0) {
		stringstream ss(input_line);
		string start,left_string,right_string,_;
		ss >> start;
		ss >> _;
		ss >> left_string;
		ss >> right_string;
		left_string = left_string.substr(1,left_string.size()-2);
		right_string = right_string.substr(0,right_string.size()-1);

		int node = get_node(start);
		int left_node = get_node(left_string);
		int right_node = get_node(right_string);

		left_right_paths.resize(string_to_node.size());
		left_right_paths[node][0] = left_node;
		left_right_paths[node][1] = right_node;
		getline(cin,input_line);
	}

	set<int> z_suffix;
	vector<int> a_suffix;
	for(const auto& it: string_to_node) {
		if(it.first.back() == 'Z') {
			z_suffix.insert(it.second);
		}
		if(it.first.back() == 'A') {
			a_suffix.push_back(it.second);
		}
	}

	long long total = 1;
	for(const auto& node: a_suffix) {
		int len = 0;
		int current_node = node;
		while(!z_suffix.count(current_node)) {
			int path = path_choices[len%path_choices.size()] == 'L'?0:1;
			current_node = left_right_paths[current_node][path];
			len++;
		}
		total = lcm(total,len);
	}
	cout << total << '\n';
}

import json
import re
from copy import copy, deepcopy


class Solver:
    start = 'AAA'
    end = 'ZZZ'

    def __init__(self):
        with open('info.json', 'r', encoding='utf-8') as f:
            self.data = json.load(f)
        self.directions = self.data["line1"] * 20000
        self.resulting_options = [self.parse_line(line) for line in self.data["lookup"].split('\n')]
        self.lookup = {item['start']: item for item in self.resulting_options}

    @staticmethod
    def parse_line(line):
        start = line.split(' = ')[0]
        results = line.split(' = ')[1].replace('(', '').replace(')', '')
        return {
            'start': start,
            'L': results.split(', ')[0],
            'R': results.split(', ')[1],
        }

    def run(self):
        total = 0
        cur = self.start
        for char in self.directions:
            total += 1
            cur = self.lookup[cur][char]
            if cur == self.end:
                break

        return total


if __name__ == '__main__':
    print(Solver().run())

import json
import math
import re
import numpy as np


class Solver:
    start = 'AAA'
    end = 'ZZZ'

    def __init__(self):
        with open('info.json', 'r', encoding='utf-8') as f:
            self.data = json.load(f)
        self.directions = self.data["line1"] * 2000000
        self.resulting_options = [self.parse_line(line) for line in self.data["lookup"].split('\n')]
        self.lookup = {item['start']: item for item in self.resulting_options}

    @staticmethod
    def parse_line(line):
        start = line.split(' = ')[0]
        results = line.split(' = ')[1].replace('(', '').replace(')', '')
        return {
            'start': start,
            'L': results.split(', ')[0],
            'R': results.split(', ')[1],
        }

    def run(self):
        total = 0
        cur = [loc for loc in self.lookup.keys() if loc.endswith('A')]
        prime_factors = [None] * len(cur)
        for char in self.directions:
            total += 1
            for i, loc in enumerate(cur):
                new_square = self.lookup[loc][char]
                cur[i] = new_square
                if new_square.endswith('Z') and prime_factors[i] is None:
                    prime_factors[i] = total
            print(prime_factors)
            if all(x is not None for x in prime_factors):
                break
        print(prime_factors)

        return np.lcm.reduce(prime_factors)


if __name__ == '__main__':
    print(Solver().run())

Python's itertools.cycle is really useful here.

#!/usr/bin/env pypy3

import itertools
import sys

seq = tuple(int(c == 'R') for c in sys.stdin.readline().strip())
sys.stdin.readline()
moves = {}
for line in sys.stdin:
    k, v = map(str.strip, line.split('='))
    moves[k] = tuple(side.strip('()') for side in v.split(', '))

position = 'AAA'
steps = 0
for move in itertools.cycle(seq):
    if position == 'ZZZ':
        break
    position = moves[position][move]
    steps += 1

print(steps)

#!/usr/bin/env pypy3

import itertools
import math
import sys

def nsteps(seq, moves, positions):
    for p in positions:
        steps = 0
        for move in itertools.cycle(seq):
            if p[-1] == 'Z':
                break
            p = moves[p][move]
            steps += 1
        yield steps

seq = [int(c == 'R') for c in sys.stdin.readline().strip()]
sys.stdin.readline()
moves = {}
for line in sys.stdin:
    k, v = map(str.strip, line.split('='))
    moves[k] = tuple(side.strip('()') for side in v.split(', '))

positions = (p for p in moves if p[-1] == 'A')
steps = nsteps(seq, moves, positions)
print(math.lcm(*steps))

# Advent of Code 2023
# Day 8: Haunted Wasteland

import math

graph = {}

with open("inputs/day_8.txt") as file:
    for i, line in enumerate(file):
        if i == 0:
            instructions = line.rstrip("\n")
        elif i > 1:
            graph[line[:3]] = (line[7:10], line[12:15])

def next_location(graph, location):
    return graph[location]["LR".index(instructions[steps % len(instructions)])]

steps = 0
location = "AAA"

while location != "ZZZ":
    location = next_location(graph, location)
    steps += 1

print(f"Part 1: {steps}")

locations = [location for location in graph if location[-1] == "A"]
steps_per_location = []

for i in range(len(locations)):
    steps = 0
    z_count = 0

    while z_count < 2:
        locations[i] = next_location(graph, locations[i])
        steps += 1

        if locations[i][-1] == "Z":
            if z_count == 0:
                steps = 0

            z_count += 1

    steps_per_location.append(steps)

print(f"Part 2: {math.lcm(*steps_per_location)}")

instruction = gets.chomp
gets

nodes = {}

while l = gets do
	parsed = l.match(/^([A-Z]+) = \(([A-Z]+), ([A-Z]+)\)/)
	nodes[parsed[1]] = {
		"L" => parsed[2],
		"R" => parsed[3],
	}
end

current = "AAA"
step = 0

while current != "ZZZ" do
	cmd = instruction[step % instruction.length]
	current = nodes[current][cmd]
	step += 1
end

puts step

instruction = gets.chomp
gets

$nodes = {}

while l = gets do
	parsed = l.match(/^([0-9A-Z]+) = \(([0-9A-Z]+), ([0-9A-Z]+)\)/)
	$nodes[parsed[1]] = {
		"L" => parsed[2],
		"R" => parsed[3],
	}
end

current = $nodes.keys.filter { |k| k.end_with?("A") }

current_z_every = current.map { |v| 
	step = 0
	cur = v
	while !cur.end_with?("Z") do
		cmd = instruction[step % instruction.length]
		cur = $nodes[cur][cmd]
		step += 1
	end
	step
}

puts current_z_every.reduce(1, :lcm)

First part was very straight-forward: read the input in and simulate the navigation. Taking advantage of itertools.cycle made cycling through the instructions very easy :]

Network = dict[str, dict[str, str]]

def read_instructions(stream=sys.stdin) -> Iterator[str]:
    return itertools.cycle(stream.readline().strip())

def read_network(stream=sys.stdin) -> Network:
    network = defaultdict(dict)

    for line in map(str.strip, stream):
        if not line:
            continue

        source, target_l, target_r = re.findall('[A-Z]{3}', line)
        network[source] = {
            'L': target_l,
            'R': target_r,
        }

    return network

def navigate(instructions: Iterator[str], network: Network) -> int:
    count  = 0
    source = 'AAA'
    target = 'ZZZ'

    while source != target:
        source = network[source][next(instructions)]
        count += 1

    return count

def main(stream=sys.stdin) -> None:
    instructions = read_instructions(stream)
    network      = read_network(stream)
    print(navigate(instructions, network))

The second part was also straight-forward: locate the ghosts, and then navigate from each ghost until you hit an element that ends with a 'Z'. The trick to avoid brute-forcing is to realize that the ghosts will cycle (ie. repeat the same paths) if they all don't land on an element that ends with a 'Z' at the same time. To solve the problem, you just ened to calculate the steps for each ghost to reach an endpoint and then compute the lowest common multiple of those counts. Fortunately, Python has math.lcm, so not much code was needed!

def navigate(instructions: Iterator[str], network: Network, element: str) -> int:
    count = 0

    while not element.endswith('Z'):
        element = network[element][next(instructions)]
        count += 1

    return count

def locate_ghosts(network: Network) -> list[str]:
    return [element for element in network if element.endswith('A')]

def main(stream=sys.stdin) -> None:
    instructions = read_instructions(stream)
    network      = read_network(stream)
    ghosts       = locate_ghosts(network)
    counts       = [navigate(cycle(instructions), network, ghost) for ghost in ghosts]
    print(math.lcm(*counts))

main.go

I should not have wasted time on the naïve solution (doing the walk of the graph with all of the starts simultaneously, instead of doing them one by one and finding the LCM). I should know by now to look for the shortcut first.

module Main (main) where
import Prelude hiding (lookup)
import Data.Map (Map, fromList, lookup, keys)

main :: IO ()
main = do
    input <- readFile "./input.txt"
    putStrLn $ "Part 1: " ++ show (uncurry solve1 $ parseInput input)
    putStrLn $ "Part 2: " ++ show (uncurry solve2 $ parseInput input)

parseInput :: String -> (String, Map String (String, String))
parseInput input = (steps, mapping) where
    steps = head $ lines input
    mappingStrs = drop 2 $ lines input
    mapping = fromList $ map parseLine mappingStrs

parseLine :: String -> (String, (String, String))
parseLine line = (a, (b, c)) where
    a = take 3 line
    b = take 3 $ drop 7 line
    c = take 3 $ drop 12 line

nextNode :: Map String (String, String) -> String -> Char -> String
nextNode mapping curr direction = case lookup curr mapping of
    Nothing -> error "key not found"
    Just (l, r) -> case direction of
        'L' -> l
        'R' -> r
        _   -> error "invalid step"

solve :: Map String (String, String) -> String -> (String -> Bool) -> [Char] -> Int
solve mapping steps endCond start = solveRec (cycle steps) start 0 where
    solveRec steps curr n
        | endCond curr = n
        | otherwise = solveRec (tail steps) (nextNode mapping curr (head steps)) (n+1)

solve1 :: String -> Map String (String, String) -> Int
solve1 steps mapping = solve mapping steps (=="ZZZ") "AAA"

solve2 :: String -> Map String (String, String) -> Int
solve2 steps mapping = foldr lcm 1 cycleLengths where
    aStarts = filter ((=='A') . (!!2)) $ keys mapping
    cycleLengths = map (solve mapping steps ((=='Z') . (!!2))) aStarts

Well, that was fun. I tried to brute-force Part 2 at first, with puzzles being brute-forceable being a theme of the year so far, but nope.

I hate it when Part 2 asks you to do something in parallel, like the "release steam from vents together with an Elephant"-puzzle in one of the last years, because depending on how you structured part 1, that can be really difficult to rework. Thankfully that wasn't really the case for me here.

(nom-Parser omitted for brevity)

pub struct PuzzleInput {
    pub instructions: &'static str,
    pub nodes: BTreeMap<&'static str, (&'static str, &'static str)>,
}

impl PuzzleInput {
    pub fn instructions(&self) -> impl Iterator<Item = char> {
        self.instructions.chars().cycle()
    }

    pub fn path_to_end(&self, start: &'static str) -> impl Iterator<Item = &str> {
        let mut current = start;
        let mut instrs = self.instructions();

        std::iter::once(current).chain(std::iter::from_fn(move || {
            if current == "ZZZ" {
                return None;
            }

            let (left, right) = self.nodes.get(current).unwrap();
            let go_left = instrs.next().unwrap() == 'L';
            current = if go_left { left } else { right };
            Some(current)
        }))
    }
}

pub fn part1(input: &'static str) -> usize {
    let parsed = parser::parse(input).expect("Failed to parse input").1;
    parsed.path_to_end("AAA").count() - 1
}

The algorithm is simple once you figured it out: find all cycles, compute the indices on which a given path arrives at a Z-node, and then find the least common multiple between all paths, because that is the first step at which all paths will land on a Z-node.

pub fn part2(input: &'static str) -> usize {
    let parsed = parser::parse(input).expect("Failed to parse input").1;

    find_paths(parsed)
}

#[derive(Debug, PartialEq, PartialOrd, Eq, Ord, Clone)]
pub struct GraphNode {
    node: &'static str,
    index: usize,
}

fn find_paths(input: PuzzleInput) -> usize {
    fn single_loop(input: &PuzzleInput, from: &'static str) -> (usize, Vec<GraphNode>) {
        let instr_len = input.instructions.len();

        let mut current = from;
        let mut instrs = input.instructions();
        let mut index = 0;

        let mut result = VecDeque::new();
        let mut seen = BTreeSet::new();

        let mut node = GraphNode {
            node: current,
            index,
        };

        loop {
            result.push_back(node.clone());

            if !seen.insert(node.clone()) {
                cycle_start = node;
                break;
            }

            let go_left = instrs.next().unwrap() == 'L';

            if go_left {
                let (left, _) = input.nodes.get(current).unwrap();
                current = left;
            } else {
                let (_, right) = input.nodes.get(current).unwrap();
                current = right;
            }

            index = (index + 1) % instr_len;

            node = GraphNode {
                node: current,
                index,
            };
        }

        let mut cycle_starts_at = 0;
        while result.front() != Some(&cycle_start) {
            result.pop_front();
            cycle_starts_at += 1;
        }

        result.pop_back();

        (cycle_starts_at, result.into())
    }

    fn cycle_times(cycle: &Vec<GraphNode>, cycle_starts_at: usize) -> Vec<usize> {
        let mut result = Vec::new();

        for (i, node) in cycle.iter().enumerate() {
            if node.node.ends_with('Z') {
                result.push(cycle_starts_at + i);
            }
        }

        result
    }

    fn gcd(a: usize, b: usize) -> usize {
        let mut a = a;
        let mut b = b;

        while b != 0 {
            let t = b;
            b = a % b;
            a = t;
        }

        a
    }

    fn lcm(a: usize, b: usize) -> usize {
        a * b / gcd(a, b)
    }

    let loop_lengths = input
        .nodes
        .keys()
        // Find all starting nodes
        .filter(|node| node.ends_with('A'))
        // Determine how the path loops
        .map(|node| single_loop(&input, node))
        // Calculate the time indices where a path is at a Z-node
        .map(|(cycle_starts_at, cycle)| cycle_times(&cycle, cycle_starts_at))
        .collect::<Vec<_>>();

    // There must be a more elegant way to compute the least-common multiple
    // of a Vector of indeterminate length...
    (loop_lengths.into_iter().fold(BTreeSet::new(), |acc, x| {
        let mut result = BTreeSet::new();

        if acc.is_empty() {
            for x in x.iter() {
                result.insert(*x);
            }
            return result;
        }

        for a in acc.iter() {
            for b in x.iter() {
                result.insert(lcm(*a, *b));
            }
        }

        result
    }))
    .into_iter()
    // Lowest common multiple
    .min()
    .unwrap()
}

import { getInput } from "./input";
import * as utils from "./utils";

const gcd = (a: number, b: number): number => {
  return !b ? a : gcd(b, a % b);
};

const lcm = (a: number, b: number): number => {
  return (a * b) / gcd(a, b);
};

const alcm = (nums: number[]): number => {
  nums.sort((a, b) => a - b);
  while (nums.length > 1) {
    const x = lcm(nums[0], nums[1]);
    nums.splice(0, 2, x);
  }
  return nums[0];
};

(async () => {
  const input = getInput();
  const lines = input.split("\n").filter((l) => !!l);

  const dirs = lines[0].split("");
  const nodes: Map<string, [string, string]> = new Map();
  const regex = /(\w+) = \((\w+), (\w+)\)/;

  for (let i = 1; i < lines.length; i++) {
    const args = lines[i].match(regex)!;
    nodes.set(args[1], [args[2], args[3]]);
  }

  const keys = [...nodes.keys()].filter((x) => x.endsWith("A"));
  console.log(`Going through ${keys.length} paths`);
  const steps = keys.map((key, i) => {
    let count = 0;
    let currNode = key;
    while (currNode != "ZZZ") {
      const lr = nodes.get(currNode)!;
      const dir = dirs[count % dirs.length] === "L" ? 0 : 1;
      currNode = lr[dir];
      count++;
      if (currNode.endsWith("Z")) {
        break;
      }
    }
    console.log(`Finished ${i + 1}`);
    return count;
  });

  console.log(alcm(steps));
})();

object Day08 {
    fun parse(input: String): Pair<String, Map<String, Pair<String, String>>> {
        val (path0, graph0) = input.split("\n\n")
        val path = path0.trim()
        val graph = mutableMapOf<String, Pair<String, String>>()
        for (line in graph0.lines()) {
            val (node, left, right) = alnumsOf(line).toList()
            graph[node] = Pair(left, right)
        }
        return Pair(path, graph)
    }

    fun cycleOf(path: String) = iterator {
        var i = 0
        while (true) {
            yield(path[i])
            i = (i + 1) % path.length
        }
    }

    fun stepsOf(node: String, path: String, graph: Map<String, Pair<String, String>>): Int {
        val cycle = cycleOf(path)
        var numSteps = 0
        var location = node
        while (!location.endsWith('Z')) {
            location = when (cycle.next()) {
                'L' -> graph[location]!!.first
                'R' -> graph[location]!!.second
                else -> error(Unit)
            }
            numSteps++
        }
        return numSteps
    }

    fun part1(input: String): Int {
        val (path, graph) = parse(input)
        return stepsOf("AAA", path, graph)
    }

    fun part2(input: String): Long {
        val (path, graph) = parse(input)
        val starts = graph.keys.filter { it.endsWith('A') }
        val steps = starts.map { stepsOf(it, path, graph).toLong() }
        return steps.reduce { x, y -> lcm(x, y) }
    }
}

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::HashMap;

extern crate num;
use num::integer;

extern crate regex;
use regex::Regex;

#[derive(Debug)]
struct Node {
    name: String,
    left: String,
    right: String,
}
impl From<&String> for Node {
    fn from(s: &String) -> Node {
        let (name,left,right) = node_values(&s);
        Self {
            name:  name,
            left:  left,
            right: right,
        }
    }
}

fn node_values(s: &String) -> (String,String,String) {
    let re = Regex::new(r"^(\w+) = \((\w+), (\w+)\)$").unwrap();
    let matches = re.captures(s).unwrap();
    (matches[1].to_string(),
     matches[2].to_string(),
     matches[3].to_string())
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
            Err(err) => panic!("Unknown error reading input: {}", err),
            Ok(result) => result,
    };

    let directions: Vec<_> = input[0].chars().collect();

    let nodes: HashMap<String, Node> = input[2..]
        .iter()
        .map(|l| {
            let (n,l,r) = node_values(&l);
            (n.clone(), Node { name: n, left: l, right: r })
        })
        .collect();

    // Part 1
    let mut steps = 0;
    let mut current = "AAA";
    loop {
        let dir = directions[steps % directions.len()];
        steps += 1;
        let next = match dir {
            'L' => &nodes.get(current).unwrap().left,
            'R' => &nodes.get(current).unwrap().right,
            _ => panic!("Unknown direction: {dir}"),
        };
        current = &next;
        if current == "ZZZ" { break }
    }
    println!("Part 1: {steps}"); // 19951

    // Part 2
    let mut steps = 0;
    let mut ghosts = nodes.keys().filter(|k| k.ends_with("A")).collect::<Vec<_>>();
    let mut z_steps = vec![0; ghosts.len()];
    loop {
        let dir = directions[steps % directions.len()];
        steps += 1;
        let next_ghosts: Vec<_> = ghosts
            .clone()
            .iter()
            .enumerate()
            .map(|(i,g)| {
                let next = match dir {
                    'L' => &nodes.get(*g).unwrap().left,
                    'R' => &nodes.get(*g).unwrap().right,
                    _ => panic!("Unknown direction: {dir}"),
                };
                if next.ends_with("Z") { z_steps[i] = steps }
                next
            })
            .collect();
        ghosts = next_ghosts.clone();

        if ghosts.iter().all(|g| g.ends_with("Z")) { break } // Normal exit
        if z_steps.iter().all(|z| z != &0usize) { break }    // Optimized exit
    }
    println!("Part 2: {}",lcm(&z_steps)); // 16342438708751

    Ok(())
}

fn lcm(numbers: &Vec<usize>) -> usize {
    numbers.iter().fold(1, |acc, &x| num::integer::lcm(acc,x))
}


fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

package day08

import (
    "fmt"
    "strings"

    "github.com/dlclark/regexp2"
    "github.com/rs/zerolog/log"
    "github.com/spf13/cobra"

    "spit-evil-olive.tips/aoc2023/common"
)

var nodeRegex = regexp2.MustCompile(`(?<location>\w+) = \((?<left>\w+), (?<right>\w+)\)`, regexp2.None)

type Node struct {
    location string
    left     string
    right    string
}

type Map map[string]Node

func parseInput(path string) (string, Map, error) {
    var directions string
    var m Map = make(Map)

    parts, err := common.ReadFileParts(path, "\n\n")
    if err != nil {
        return directions, m, err
    }
    directions = parts[0]

    for _, line := range strings.Split(parts[1], "\n") {
        match, err := nodeRegex.FindStringMatch(line)
        if err != nil {
            return directions, m, err
        }

        if match == nil {
            return directions, nil, fmt.Errorf("failed to parse %v", line)
        }

        location := match.GroupByName("location").String()
        node := Node{
            location,
            match.GroupByName("left").String(),
            match.GroupByName("right").String(),
        }
        m[location] = node
    }

    return directions, m, nil
}

func (m Map) Walk(start string, target string, directions string) int {
    steps := 0

    current := start
    for {
        if current == target {
            return steps
        }

        direction := directions[steps%len(directions)]

        var next string
        switch direction {
        case 'L':
            next = m[current].left
        case 'R':
            next = m[current].right
        }

        steps++
        current = next
    }
}

var CommandA = &cobra.Command{
    Use:  "08a",
    Args: cobra.ExactArgs(1),
    RunE: func(cmd *cobra.Command, args []string) error {
        directions, m, err := parseInput(args[0])
        if err != nil {
            return err
        }

        steps := m.Walk("AAA", "ZZZ", directions)
        log.Info().Msgf("steps: %v", steps)

        return nil
    },
}

func (m Map) walkGhosts(directions string) int {
    var ghosts []string
    for location, _ := range m {
        if location[2] == 'A' {
            ghosts = append(ghosts, location)
        }
    }

    var lengths []int
    for _, start := range ghosts {
        length := m.PathLength(start, directions)
        lengths = append(lengths, length)
    }

    total := common.LCM(lengths)

    return total
}

func (m Map) PathLength(start string, directions string) int {
    steps := 0

    current := start
    for {
        if current[2] == 'Z' {
            return steps
        }

        direction := directions[steps%len(directions)]

        var next string
        switch direction {
        case 'L':
            next = m[current].left
        case 'R':
            next = m[current].right
        }

        steps++
        current = next
    }
}

var CommandB = &cobra.Command{
    Use:  "08b",
    Args: cobra.ExactArgs(1),
    RunE: func(cmd *cobra.Command, args []string) error {
        directions, m, err := parseInput(args[0])
        if err != nil {
            return err
        }

        steps := m.walkGhosts(directions)
        log.Info().Msgf("steps: %v", steps)

        return nil
    },
}

package common

func GCD(x, y int) int {
    for y != 0 {
        t := y
        y = x % y
        x = t
    }
    return x
}

func LCM(n []int) int {
    var lcm int

    x, y := n[0], n[1]
    lcm = x * y / GCD(x, y)

    for i := 2; i < len(n); i++ {
        lcm = lcm * n[i] / GCD(lcm, n[i])
    }

    return lcm
}

> env BENCHMARK=100 go run main.go 08a day08/08.txt
{"level":"info","time":"2023-12-09T20:30:53.587086939-08:00","message":"mean: 1.582547ms"}
{"level":"info","time":"2023-12-09T20:30:53.587091026-08:00","message":"stddev: 210.491µs"}
> env BENCHMARK=100 go run main.go 08b day08/08.txt
{"level":"info","time":"2023-12-09T20:31:03.433171993-08:00","message":"mean: 2.976401ms"}
{"level":"info","time":"2023-12-09T20:31:03.433174969-08:00","message":"stddev: 255.6µs"}

There have been a handful of puzzles that involve calculating GCD/LCM, and I always forget how, so I figured I'd create a reusable module for those and other slightly-more-than-basic math functions.

defmodule AdventOfCode.Math do
  @moduledoc """
  Common math functions/algorithms.
  """

  @doc """
  Greatest common denominator.
  """
  @spec gcd(Enumerable.t(pos_integer)) :: pos_integer
  def gcd(ns), do: Enum.reduce(ns, &gcd/2)

  defp gcd(d, 0), do: d
  defp gcd(a, b), do: gcd(b, Integer.mod(a, b))

  @doc """
  Least common multiple.
  """
  @spec lcm(Enumerable.t(pos_integer)) :: pos_integer
  def lcm(ns), do: Enum.reduce(ns, &lcm/2)

  defp lcm(a, b), do: div(a * b, gcd(a, b))
end

I've been stubbornly avoiding regexes for parsing inputs this year, because binary pattern matching is neat and weird. As long as the values you're trying to pull out of the string have a constant character length (variable length allowed if it's at the end of the string), binary pattern matching is sufficient.

defmodule AdventOfCode.Solution.Year2023.Day08 do
  alias AdventOfCode.Math

  @type t :: %__MODULE__{
          labels: %{(index :: non_neg_integer) => String.t()},
          step: non_neg_integer,
          zs: MapSet.t(step :: non_neg_integer)
        }
  @enforce_keys [:labels]
  defstruct @enforce_keys ++ [step: 0, zs: MapSet.new()]

  def new(labels) do
    labels
    |> Enum.with_index(fn l, i -> {i, l} end)
    |> Map.new()
    |> then(&%__MODULE__{labels: &1})
  end

  def part1(input) do
    input
    |> parse()
    |> steps_to_z(["AAA"], &(&1 == "ZZZ"))
  end

  def part2(input) do
    input
    |> parse()
    |> steps_to_z(&match?(<<_, _, ?Z>>, &1))
  end

  defp steps_to_z({dirs, map}, done?) do
    steps_to_z({dirs, map}, for(<<_, _, ?A>> = label <- Map.keys(map), do: label), done?)
  end

  defp steps_to_z({dirs, map}, starting_labels, done?) do
    dirs
    |> Stream.cycle()
    |> Enum.reduce_while(new(starting_labels), fn dir, acc ->
      if map_size(acc.labels) == 0 do
        {:halt, acc.zs}
      else
        {:cont, update_acc(acc, map, dir, done?)}
      end
    end)
    |> Math.lcm()
  end

  defp update_acc(acc, map, dir, done?) do
    found_z = Enum.flat_map(acc.labels, fn {i, l} -> if done?.(l), do: [i], else: [] end)

    labels =
      acc.labels
      |> Map.drop(found_z)
      |> Map.new(fn {i, l} -> {i, map[l][dir]} end)

    zs = if match?([_ | _], found_z), do: MapSet.put(acc.zs, acc.step), else: acc.zs

    %{acc | labels: labels, zs: zs, step: acc.step + 1}
  end

  defp parse(input) do
    [dirs, map] = String.split(input, "\n\n")

    dirs = for <<dir::1-bytes <- dirs>>, do: dir |> String.downcase() |> String.to_existing_atom()

    map =
      for <<label::3-bytes, _::4*8, left::3-bytes, _::2*8, right::3-bytes, _::bytes>> <-
            String.split(map, "\n", trim: true),
          into: %{},
          do: {label, %{l: left, r: right}}

    {dirs, map}
  end
end