21
🎄 - 2023 DAY 8 SOLUTIONS -🎄
(programming.dev)
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)