Rust

As others have shown, part 2 can be pretty simple if you allow one assumption: The distance from a start point to the nearest end point is always the same as cycling from that nearest end point back to itself. Under that assumption you can just take the lowest common multiple of these distances. And honestly, who can claim to understand ghost navigation and what you can and can’t assume? Empirical evidence suggests that this is how ghosts travel.

Scala3

this is still not 100% general, as it assumes there is only one Z-node along the path for each start. But it doesn’t assume anything else, I think. If you brute force combinations of entries of the zs-arrays, this assumption can be trivially removed, but if multiple paths see lots of Z-nodes, then the runtime will grow exponentially. I don’t know if it’s possible to do this any faster.

def parse(a: List[String]): (List[Char], Map[String, Map[Char, String]]) =
    def parseNodes(n: List[String]) =
        n.flatMap{case s"$from = ($l, $r)" => Some(from -> Map('L'->l, 'R'->r)); case _ => None}.toMap
    a match{case instr::""::nodes => ( instr.toList, parseNodes(nodes) ); case _ => (List(), Map())}

def task1(a: List[String]): Long =
    val (instr, nodes) = parse(a)
    def go(i: Stream[Char], pos: String, n: Long): Long =
        if pos != "ZZZ" then go(i.tail, nodes(pos)(i.head), n+1) else n
    go(instr.cycle, "AAA", 0)

// ok so i originally thought this was going to be difficult, so
// we parse a lot of info we won't use
case class PathInfo(zs: List[Long], loopFrom: Long, loopTo: Long):
    def stride: Long = loopTo - loopFrom

type Cycle = Long

def getInfo(instr: List[Char], isEnd: String => Boolean, map: Map[String, Map[Char, String]], start: String): PathInfo =
    def go(i: Cycle, pos: String, is: List[Char], seen: Map[(Long, String), Cycle], acc: List[Long]): PathInfo =
        val current: (Long, String) = (is.size % instr.size, pos)
        val nis = if is.isEmpty then instr else is
        val nacc = if isEnd(pos) then i::acc else acc
        seen.get(current) match
            case Some(l) => PathInfo(acc, l, i)
            case _ => go(i + 1, map(pos)(nis.head), nis.tail, seen + (current -> i), nacc)
    go(0, start, instr, Map(), List())

// turns out we don't need to check all the different positions
// in each cycle where we are on a Z position, as a) every start
// walks into unique cycles with b) exactly one Z position,
// and c) the length of the cycle is equivalent to the steps to first
// encounter a Z (so a->b->c->Z->c->Z->... is already more complicated, 
// as the cycle length is 2 but the first encounter is after 3 steps)

// anyway let's do some math

// this is stolen code
def gcd(a: Long, b: Long): Long =
    if(b ==0) a else gcd(b, a%b)

def primePowers(x: Long): Map[Long, Long] =
    // for each prime p for which p^k divides x: p->p^k
    def go(r: Long, t: Long, acc: Map[Long, Long]): Map[Long, Long] =
        if r == 1 then acc else
            if r % t == 0 then
                go(r/t, t, acc + (t -> acc.getOrElse(t, 1L)*t))
            else
                go(r, t+1, acc)
    go(x, 2, Map())

// this algorithm is stolen, but I scalafied the impl
def vanillaCRT(congruences: Map[Long, Long]): Long = 
    val N = congruences.keys.product
    val x = congruences.map((n, y) => y*(N/n)*((N/n) % n)).sum
    if x <= 0 then x + N else x

def generalizedHardcoreCRTThatCouldHaveBeenAnLCMBecauseTheInputIsVeryConvenientlyTrivialButWeWantToDoThisRight(ys: List[Long], xs: List[Long]): Option[Long] =
    // finds the smallest k s.t. k === y_i  (mod x_i) for each i
    // even when stuff is not nice

    // pre-check if everything is sufficiently coprime
    // https://math.stackexchange.com/questions/1644677/what-to-do-if-the-modulus-is-not-coprime-in-the-chinese-remainder-theorem
    val vars = for
        ((y1, n1), i1) <- ys.zip(xs).zipWithIndex
        ((y2, n2), i2) <- ys.zip(xs).zipWithIndex
        if i2 > i1
    yield 
        val g = gcd(n1, n2)
        y1 % g == y2 % g
    
    if !vars.forall(a => a) then
        None
    else
        // we need to split k === y (mod mn) into k === y (mod m) and k === y (mod n) for m, n coprime
        val congruences = for
            (x, y) <- xs.zip(ys)
            (p, pl) <- primePowers(x)
        yield
            p -> (y % pl -> pl)
        
        // now we eliminate redundant congruences
        // since our input is trivial, this is essentially
        // the step in which we solve the task by 
        // accidentaly computing an lcm
        val r = congruences.groupMap(_._1)(_._2).mapValues(l => l.map(_._2).max -> l.head._1).values.toMap
        
        // ok now we meet the preconditions
        // for doing this
        Some(vanillaCRT(r))

def task2(a: List[String]): Long =
    val (instr, nodes) = parse(a)
    val infos = nodes.keySet.filter(_.endsWith("A")).map(s => getInfo(instr, _.endsWith("Z"), nodes, s))
    generalizedHardcoreCRTThatCouldHaveBeenAnLCMBecauseTheInputIsVeryConvenientlyTrivialButWeWantToDoThisRight(
        infos.map(_.zs.head).toList, infos.map(_.stride).toList
    ).getOrElse(0)

@main def main: Unit =
  val data = readlines("/home/tim/test/aoc23/aoc23/inputs/day8/task1.txt")
  for f <- List(
      task1,
      task2,
    ).map(_ andThen println)
  do f(data)

Nim

I like how if you have an error in your calculations, you end up wandering the haunted desert for eternity. Very flavorful.

My solution for part 2 is pretty much the same as for part 1, just modified to work on a sequence of nodes instead of a single node. However, it doesn’t find an answer in the time that I was willing to wait for it. I thought about trying to optimize it to run faster, but figured that if it was taking this long on Nim, then interpreted languages would have no chance, so that couldn’t be the right approach.

I suspected that maybe the ghosts arrived at the Z locations at predictable intervals. I added some code to output the step count each time each ghost reached a Z (see commented code), and my suspicion was correct. Just needed to calculate the least common multiple of the 6 cycle lengths.

• Day 8, part 1
• Day 8, part 2 partial solution
• Day 8, part 2 actual answer

APL

I’m using this year’s AoC to learn (Dyalog) APL, so this is most likely a pretty terrible solutions. I would’ve liked to use ⍣ instead of of my imitation of a while loop with a recursive function, but I couldn’t figure out how to get to the number of iterations ⍣ performed to arrive at the destination. If someone here knows how to do that (or has other suggestions for improvement) I’m open for suggestions.

⎕IO ← 0       ⍝ use 0-based indexes
I←⌷⍨∘⊃⍨⍤0 99  ⍝ "sane" indexing
⎕PP←17        ⍝ print integers with up to 17 significant digits without use of scientific notation

input←⊃⎕NGET'inputs/day8.txt'1
instructions←⊃input
p←↑{0 2 4 I{6⍴⎕CSV⍠'Widths'(3 4 3 2 3 1)⊢⍵'S'1}⍵}¨ 2↓input
nodes←,1↑[1]p
L←(⍳⍴nodes) ∘.{nodes[⍺]≡⍵ 1 ⌷p} ⍳⍴nodes
R←(⍳⍴nodes) ∘.{nodes[⍺]≡⍵ 2 ⌷p} ⍳⍴nodes
S←(⊃(+.×)/{'R'≡⍵:R ⋄ ⍵≡'L':L}¨⌽instructions)
⎕←(≢instructions) × {⍺←0 ⋄ ⍵[⍸'ZZZ'∘≡¨nodes]: ⍺ ⋄ ⍺+1 ∇ S+.×⍵}'AAA'∘≡¨nodes                             ⍝ part 1
⎕←∧/(≢instructions) × {⍺←0 ⋄ 0≡+/⍵[⍸~('Z'∘=⊢/)¨nodes]: ⍺ ⋄ ⍺+1 ∇ S+.×⍵}¨{(⍳≢nodes)=⍵}¨⍸('A'∘=⊢/)¨nodes  ⍝ part 2

Dart

Part 1 was easy enough. For Part 2 I took a guess that the cycles were all well behaved and I could get away with just calculating the LCM, and it paid off.

(List, Map) parse(List lines) => (
      lines.first.split(''),
      {
        for (var l in lines.skip(2).map((e) => e.split(RegExp(r'[^A-Z0-9]'))))
          l[0]: [l[4], l[6]]
      }
    );
int movesTo(pos, steps, rules) {
  var stepNo = -1;
  while (!pos.endsWith('Z')) {
    pos = rules[pos]![steps[(stepNo += 1) % steps.length] == 'L' ? 0 : 1];
  }
  return stepNo + 1;
}

part1(List lines) {
  var (steps, rules) = parse(lines);
  return movesTo('AAA', steps, rules);
}

// All cycles are independent of state of `steps`, and have
// first instance == cycle length which makes this verrry simple.
part2(List lines) {
  var (steps, rules) = parse(lines);
  return [
    for (var start in rules.keys.where((e) => e.endsWith('A')))
      movesTo(start, steps, rules)
  ].reduce((s, t) => s.lcm(t));
}
}

Crystal

!crystal_lang@lemmy.ml

part 1 was made way simpler after I made it a function for part 2
also I accidentally saw someone elses code, so I can’t take full credit for figuring out how to do part 2

Input = File.read("input.txt").lines

Dirs = Input[0].chars.map {|c| c == 'L' ? 0 : 1}
Nodes = Hash(String, Tuple(String, String)).new
Input[2..].each {|line| Nodes[line[..2]] = {line[7..9], line[12..14]} }

# part 1
puts num_steps("AAA", &.== "ZZZ")

# part 2
currents = Nodes.keys.select(&.ends_with? 'A')
steps = currents.map {|cur| num_steps(cur, &.ends_with? 'Z')}
puts steps.reduce(1_i64) {|a, b| a.lcm b}

def num_steps(start)
	steps = 0
	Dirs.cycle do |dir|
		steps += 1
		start = Nodes[start][dir]
		break if yield start
	end
	steps
end

Python

import itertools
import math
import re

from .solver import Solver

class Day08(Solver):

  def __init__(self):
    super().__init__(8)
    self.instructions: str = ''
    self.nodes: dict[str, tuple[str, str]] = {}

  def presolve(self, input: str):
    lines = input.rstrip().split('\n')
    self.instructions = lines[0]
    for line in lines[2:]:
      g = re.fullmatch(r'(\w+) = \((\w+), (\w+)\)', line)
      assert g, f"line {line} doesn't match expected format"
      target, left, right = g.groups()
      self.nodes[target] = (left, right)

  def solve_first_star(self) -> int:
    instructions = itertools.cycle(self.instructions)
    cur = 'AAA'
    counter = 0
    while cur != 'ZZZ':
      instruction = next(instructions)
      if instruction == 'L':
        cur = self.nodes[cur][0]
      elif instruction == 'R':
        cur = self.nodes[cur][1]
      else:
        raise RuntimeError(f'Unexpected instruction: {instruction}')
      counter += 1
    return counter

  def solve_second_star(self) -> int:
    start_nodes: list[str] = [node for node in self.nodes if node.endswith('A')]
    end_nodes: set[str] = set(node for node in self.nodes if node.endswith('Z'))
    loop_offsets: dict[str, int] = {}
    loop_sizes: dict[str, int] = {}
    destination_offset_in_loops: dict[str, list[int]] = {}
    for node in start_nodes:
      cur = node
      path: list[tuple[int, str]] = [(0, cur)]
      for instruction_offset, instruction in itertools.cycle(enumerate(self.instructions)):
        next_node = self.nodes[cur][0] if instruction == 'L' else self.nodes[cur][1]
        next_state = ((instruction_offset + 1) % len(self.instructions), next_node)
        if next_state in path:
          loop_offsets[node] = path.index(next_state)
          loop_sizes[node] = len(path) - loop_offsets[node]
          destination_offset_in_loops[node] = [i for i, [_, n] in enumerate(path) if n in end_nodes]
          break
        path.append(next_state)
        cur = next_node
    return math.lcm(*loop_sizes.values())

My C solutions: https://git.sr.ht/~aidenisik/aoc23/tree/master/item/day8

Yes, it’d be faster to read the file into memory and use that, but I decided to throw efficiency out the window.

Removed by mod

Language: Python

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))

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))

GitHub Repo

C#

Day 8

First part was simple enough. Second part was easy logically, but after running the brute force solution with a parallel iterator from rayon and maxing out all 12 cores of this CPU, it was still taking forever. I always get tripped up by these ones that need fancy math, because although I was always good at math, I’ve never been good at looking at these problems and figuring out what kind of formula would apply. So I cheated and looked at other people’s comments for their solutions, and saw the least common multiple mentioned. This made sense to me, so I implemented it and got a result almost instantly. I hate having to look at other comments to solve these things, but I never would have came to that conclusion myself.

The code still isn’t the cleanest, and I’d love to tidy up the parsing, but it works and I’m happy.

https://github.com/capitalpb/advent_of_code_2023/blob/main/src/solvers/day08.rs

impl Solver for Day08 {
    fn star_one(&self, input: &str) -> String {
        let (directions, map) = input.split_once("\n\n").unwrap();

        let mut route_map = HashMap::new();

        for line in map.lines() {
            let line = line.replace(" ", "").replace("(", "").replace(")", "");
            let (position, destinations) = line.split_once('=').unwrap();
            let (left, right) = destinations.split_once(',').unwrap();
            route_map.insert(position.to_string(), (left.to_string(), right.to_string()));
        }

        let mut current_position = "AAA".to_string();
        for (step, direction) in directions.chars().cycle().enumerate() {
            current_position = match direction {
                'L' => route_map[¤t_position].0.to_string(),
                'R' => route_map[¤t_position].1.to_string(),
                _ => unreachable!(),
            };

            if current_position == "ZZZ" {
                return (step + 1).to_string();
            }
        }

        unreachable!()
    }

    fn star_two(&self, input: &str) -> String {
        let (directions, map) = input.split_once("\n\n").unwrap();

        let mut route_map = HashMap::new();

        for line in map.lines() {
            let line = line.replace(" ", "").replace("(", "").replace(")", "");
            let (position, destinations) = line.split_once('=').unwrap();
            let (left, right) = destinations.split_once(',').unwrap();
            route_map.insert(position.to_string(), (left.to_string(), right.to_string()));
        }

        let positions = route_map
            .keys()
            .filter(|pos| pos.ends_with('A'))
            .collect::>();

        let steps = positions
            .iter()
            .filter(|pos| pos.ends_with('A'))
            .map(|pos| {
                let mut current_position = pos.to_string();
                for (step, direction) in directions.chars().cycle().enumerate() {
                    current_position = match direction {
                        'L' => route_map[¤t_position].0.to_string(),
                        'R' => route_map[¤t_position].1.to_string(),
                        _ => unreachable!(),
                    };

                    if current_position.ends_with('Z') {
                        return step + 1;
                    }
                }
                unreachable!()
            })
            .collect::>();

        steps
            .into_iter()
            .reduce(|acc, steps| acc.lcm(&steps))
            .unwrap()
            .to_string()
    }
}

[language: Lean4]

I did not make the assumption that the distance from the start to the goal is the same as the cycle length. This made the problem a bit harder, but I’m pretty sure my solution is actually generic. As always, I’ll only post the direct solution. Helper functions (like, in this case, xgcd) are in other files, you can find them together with the full solution on github.

Since my solution contains a ton of comments (that outline my thought process), I’ll again split it in several posts here.

inductive Instruction
  | left
  | right

instance : ToString Instruction where
  toString a := match a with
  | Instruction.left => "Left"
  | Instruction.right => "Right"

abbrev WaypointId := String

structure Waypoint where
  id : WaypointId
  left : WaypointId
  right : WaypointId
  deriving Repr

-- Okay, the need for different representations in both parts has burnt me once too often.
-- This time it's going to be really dumb.

private def parseInstructions (input : String) : Except String $ List Instruction := do
  let mut result := []
  for character in input.toList do
    match character with
    | 'L' => result := Instruction.left :: result
    | 'R' => result := Instruction.right :: result
    | _ => throw s!"Invalid instruction {character}. Only 'L' and 'R' are valid instructions."
  pure result.reverse

private def parseWaypoint (input : String) : Except String Waypoint :=
  if let [id, targets] := input.splitOn " = " |> List.map String.trim then
    if targets.startsWith "(" && targets.endsWith ")" then
      let withoutBraces := targets.drop 1 |> flip String.dropRight 1
      match withoutBraces.splitOn "," |> List.map String.trim with
      | [a,b] => pure {id := id, left := a, right := b : Waypoint}
      | _ => throw s!"Targets need to have 2 entries, separated by ',', but were {targets}"
    else
      throw s!"Targets for waypoint need to be enclosed in (), but were {targets}"
  else
    throw s!"Waypoint could not be split in ID and targets: {input}"

private def parseWaypoints (input : List String) : Except String $ List Waypoint :=
  input.mapM parseWaypoint

open Lean in
private def validateWaypointLinks (waypoints : List Waypoint) : Bool :=
  let validLinks := HashSet.insertMany HashSet.empty $ waypoints.map Waypoint.id
  waypoints.all λw ↦ validLinks.contains w.left && validLinks.contains w.right

def target : WaypointId := "ZZZ"
def start : WaypointId := "AAA"

def parse (input : String) : Except String $ List Instruction × List Waypoint := do
  let lines := input.splitOn "\n" |> List.map String.trim |> List.filter String.notEmpty
  match lines with
  | instructions :: waypoints =>
    let instructions ← parseInstructions instructions
    let waypoints ← parseWaypoints waypoints
    if let none := waypoints.find? λx ↦ x.id == start then
      throw s!"Input must contain the waypoint \"{start}\"."
    if let none := waypoints.find? λx ↦ x.id == target then
      throw s!"Input must contain the waypoint \"{target}\""
    if not $ validateWaypointLinks waypoints then
      throw "Input contained a waypoint that is not properly linked."
    return (instructions, waypoints)
  | [] => throw "Input was empty (or only contained whitespace)."

--------------------------------------------------------------------------------------------------------
-- One of my goals for this Advent of Code is to show that the code terminates whenever that's
-- possible. In this case, it's not directly possible from the riddle input, but it's possible
-- by adding circle detection. So, instead of making the instructions just an infinite list
-- I'll treat the case that we run out of instruction in a special way, such that we detect
-- if we are lost in the desert.

private structure ConnectedWaypoints where
  left : WaypointId
  right : WaypointId

private def ConnectedWaypoints.get : ConnectedWaypoints →  Instruction → WaypointId
| {left, right := _}, Instruction.left => left
| {left := _, right}, Instruction.right => right

-- does a single pass over all instructions. Returns err if no result has been found and another pass is needed.
-- error is optional - if none, then there is an inconsistency in the input and we are stuck.
private def pass (waypoints : Lean.HashMap WaypointId ConnectedWaypoints) (alreadyDoneSteps : Nat) (currentPosition : WaypointId) (instructions : List Instruction) : Except (Option (Nat × WaypointId)) Nat := do
  if currentPosition == "ZZZ" then
    return alreadyDoneSteps
  match instructions with
  | [] => throw $ some (alreadyDoneSteps, currentPosition)
  | a :: as =>
    let currentWaypoint := waypoints.find? currentPosition
    match currentWaypoint with
    | none => throw none -- should not happen
    | some currentWaypoint => pass waypoints (alreadyDoneSteps + 1) (currentWaypoint.get a) as

private def part1_impl (waypoints : Lean.HashMap WaypointId ConnectedWaypoints) (instructions : List Instruction) (possibleStarts : List WaypointId) (alreadyDoneSteps : Nat) (currentPosition : WaypointId) : Option Nat :=
  let remainingStarts := possibleStarts.filter λs ↦ s != currentPosition
  if remainingStarts.length < possibleStarts.length then -- written this way to make termination_by easy
    let passResult := pass waypoints alreadyDoneSteps currentPosition instructions
    match passResult with
    | Except.ok n => some n
    | Except.error none => none -- dead end on map. Should not be possible.
    | Except.error $ some n => part1_impl waypoints instructions remainingStarts n.fst n.snd
  else
    none -- walking in circles
  termination_by part1_impl a b c d e => c.length

open Lean in
def part1 (input : List Instruction × List Waypoint) : Option Nat :=
  let possibleStarts := input.snd.map Waypoint.id
  let waypoints : HashMap WaypointId ConnectedWaypoints := HashMap.ofList $ input.snd.map λw ↦ (w.id, {left := w.left, right := w.right : ConnectedWaypoints})
  let instructions := input.fst
  part1_impl waypoints instructions possibleStarts 0 start