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)