Scala3

all done!

def parseLine(a: String): List[UnDiEdge[String]] = a match
    case s"$n: $r" => r.split(" ").map(_ ~ n).toList
    case _ => List()

def removeShortestPath(g: Graph[String, UnDiEdge[String]], ns: List[String]) =
    g.removedAll(g.get(ns(0)).shortestPathTo(g.get(ns(1))).map(_.edges.map(_.outer)).getOrElse(List()))

def removeTriple(g: Graph[String, UnDiEdge[String]], ns: List[String]) =
    List.fill(3)(ns).foldLeft(g)(removeShortestPath)

def division(g: Graph[String, UnDiEdge[String]]): Option[Long] =
    val t = g.componentTraverser()
    Option.when(t.size == 2)(t.map(_.nodes.size).product)

def task1(a: List[String]): Long = 
    val g = Graph() ++ a.flatMap(parseLine)
    g.nodes.toList.combinations(2).map(a => removeTriple(g, a.map(_.outer))).flatMap(division).take(1).toList.head

When doing functional programming, you can't really do loops (because of referential transparency, you can't update iterators or indices). However, recursion still works.

Agreed, i get annoyed when I can't actually solve the problem. I would be ok if the inputs are trivial special cases, as long as feasible (but harder) generalized solutions still existed.

Scala3

Learning about scala-graph yesterday seems to have paid off already. This explicitly constructs the entire graph of allowed moves, and then uses a naive dijkstra run. This works, and I don't have to write a lot of code, but it is fairly inefficient.

import day10._
import day10.Dir._
import day11.Grid

// standing on cell p, having entered from d
case class Node(p: Pos, d: Dir)

def connect(p: Pos, d: Dir, g: Grid[Int], dists: Range) = 
    val from = Seq(-1, 1).map(i => Dir.from(d.n + i)).map(Node(p, _))
    val ends = List.iterate(p, dists.last + 1)(walk(_, d)).filter(g.inBounds)
    val costs = ends.drop(1).scanLeft(0)(_ + g(_))
    from.flatMap(f => ends.zip(costs).drop(dists.start).map((dest, c) => WDiEdge(f, Node(dest, d), c)))

def parseGrid(a: List[List[Char]], dists: Range) =
    val g = Grid(a.map(_.map(_.getNumericValue)))
    Graph() ++ g.indices.flatMap(p => Dir.all.flatMap(d => connect(p, d, g, dists)))

def compute(a: List[String], dists: Range): Long =
    val g = parseGrid(a.map(_.toList), dists)
    val source = Node(Pos(-1, -1), Right)
    val sink = Node(Pos(-2, -2), Right)
    val start = Seq(Down, Right).map(d => Node(Pos(0, 0), d)).map(WDiEdge(source, _, 0))
    val end = Seq(Down, Right).map(d => Node(Pos(a(0).size - 1, a.size - 1), d)).map(WDiEdge(_, sink, 0))
    val g2 = g ++ start ++ end
    g2.get(source).shortestPathTo(g2.get(sink)).map(_.weight).getOrElse(-1.0).toLong

def task1(a: List[String]): Long = compute(a, 1 to 3)
def task2(a: List[String]): Long = compute(a, 4 to 10)

Scala3

def hash(s: String): Long = s.foldLeft(0)((h, c) => (h + c)*17 % 256)

extension [A] (a: List[A])
    def mapAtIndex(idx: Long, f: A => A): List[A] =
        a.zipWithIndex.map((e, i) => if i == idx then f(e) else e)

def runProcedure(steps: List[String]): Long =
    @tailrec def go(boxes: List[List[(String, Int)]], steps: List[String]): List[List[(String, Int)]] =
        steps match
            case s"$label-" :: t =>
                go(boxes.mapAtIndex(hash(label), _.filter(_._1 != label)), t)
            case s"$label=$f" :: t =>
                go(boxes.mapAtIndex(hash(label), b => 
                    val slot = b.map(_._1).indexOf(label)
                    if slot != -1 then b.mapAtIndex(slot, (l, _) => (l, f.toInt)) else (label, f.toInt) :: b
                ), t)
            case _ => boxes
    
    go(List.fill(256)(List()), steps).zipWithIndex.map((b, i) =>
        b.zipWithIndex.map((lens, ilens) => (1 + i) * (b.size - ilens) * lens._2).sum
    ).sum

def task1(a: List[String]): Long = a.head.split(",").map(hash).sum
def task2(a: List[String]): Long = runProcedure(a.head.split(",").toList)

Scala3

type Grid = List[List[Char]]

def tiltUp(a: Grid): Grid = 
    @tailrec def go(c: List[Char], acc: List[Char]): List[Char] =
        def shifted(c: List[Char]) = 
            val (h, t) = c.splitAt(c.count(_ == 'O'))
            h.map(_ => 'O') ++ t.map(_ => '.') ++ acc
        val d = c.indexOf('#')
        if d == -1 then shifted(c) else go(c.slice(d + 1, c.size), '#'::shifted(c.slice(0, d)))
        
    a.map(go(_, List()).reverse)

def weight(a: Grid): Long = a.map(d => d.zipWithIndex.filter((c, _) => c == 'O').map(1 + _._2).sum).sum
def rotateNeg90(a: Grid): Grid = a.reverse.transpose
def runCycle = Seq.fill(4)(tiltUp andThen rotateNeg90).reduceLeft(_ andThen _)

def stateAt(target: Long, a: Grid): Grid =
    @tailrec def go(cycle: Int, state: Grid, seen: Map[Grid, Int]): Grid =
        seen.get(state) match
            case Some(i) => if (target - cycle) % (cycle - i) == 0 then state else go(cycle + 1, runCycle(state), seen)
            case None => go(cycle + 1, runCycle(state), seen + (state -> cycle))
    
    go(0, a, Map())

def toColMajorGrid(a: List[String]): Grid = rotateNeg90(a.map(_.toList))

def task1(a: List[String]): Long = weight(tiltUp(toColMajorGrid(a)))
def task2(a: List[String]): Long = weight(stateAt(1_000_000_000, toColMajorGrid(a)))

Scala3

// i is like
//  # # # # #
//   1 2 3 4
def smudgesAround(i: Int, s: List[List[Char]]): Long =
    val toEdge = math.min(i, s.size - i)
    (0 until toEdge).map(e => s(i - e - 1).lazyZip(s(i + e)).count(_ != _)).sum

def symmetries(g: List[List[Char]], smudges: Int) =
    val rows = (1 until g.size).filter(smudgesAround(_, g) == smudges)
    val g2 = g.transpose
    val cols = (1 until g2.size).filter(smudgesAround(_, g2) == smudges)
    100*rows.sum + cols.sum

def task1(a: List[String]): Long = a.chunk(_ == "").map(g => symmetries(g.map(_.toList), 0)).sum
def task2(a: List[String]): Long = a.chunk(_ == "").map(g => symmetries(g.map(_.toList), 1)).sum

Scala3

def diffs(a: Seq[Long]): List[Long] =
    a.drop(1).zip(a).map(_ - _).toList

def predictNext(a: Seq[Long], combine: (Seq[Long], Long) => Long): Long =
    if a.forall(_ == 0) then 0 else combine(a, predictNext(diffs(a), combine))

def predictAllNexts(a: List[String], combine: (Seq[Long], Long) => Long): Long = 
    a.map(l => predictNext(l.split(raw"\s+").map(_.toLong), combine)).sum

def task1(a: List[String]): Long = predictAllNexts(a, _.last + _)
def task2(a: List[String]): Long = predictAllNexts(a, _.head - _)

I can prove the opposite for you. The assumption that Gobbel2000 describes is wrong in general. For example, take

L

A -> B, X
B -> C, X
C -> Z, X
Z -> C, X
X -> X, X

the first Z is reached after 3 steps, but then every cycle only takes 2 steps.

The matches are still at consistent intervals, but you can easily find a counterexample for that as well:

L

A -> 1Z, X
1Z -> 2Z, X
2Z -> A, X
X -> X, X

now the intervals will be 2, 1, 2, 1, ...

However, it is easy to prove that there will be a loop of finite length, and that the intervals will behave somewhat nicely:

Identify a "position" by a node you are at, and your current index in the LRL instruction sequence. If you ever repeat a position P, you will repeat the exact path away from the position you took the last time, and the last time you later reached P, so you will keep reaching P again and again. There are finitely many positions, so you can't keep not repeating any forever, you will run out.

Walking in circles along this loop you eventually find yourself in, the intervals between Zs you see will definitely be a repeating sequence (as you will keep seeing not just same-length intervals, but in fact the exact same paths between Zs).

So in total, you will see some finite list of prefix-intervals, and then a repeating cycle of loop-intervals. I have no idea if this can be exploited to compute the answer efficiently, but see my solution-comment for something that only assumes that only one Z will be encountered each cycle.

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)

Scala3

val tiers = List(List(1, 1, 1, 1, 1), List(1, 1, 1, 2), List(1, 2, 2), List(1, 1, 3), List(2, 3), List(1, 4), List(5))
val cards = List('2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A')

def cardValue(base: Long, a: List[Char], cards: List[Char]): Long =
    a.foldLeft(base)(cards.size * _ + cards.indexOf(_))

def hand(a: List[Char]): List[Int] =
    a.groupMapReduce(s => s)(_ => 1)(_ + _).values.toList.sorted

def power(a: List[Char]): Long =
  cardValue(tiers.indexOf(hand(a)), a, cards)

def power3(a: List[Char]): Long = 
  val x = hand(a.filter(_ != 'J'))
  val t = tiers.lastIndexWhere(x.zipAll(_, 0, 0).forall(_ <= _))
  cardValue(t, a, 'J'::cards)

def win(a: List[String], pow: List[Char] => Long) =
    a.flatMap{case s"$hand $bid" => Some((pow(hand.toList), bid.toLong)); case _ => None}
        .sorted.map(_._2).zipWithIndex.map(_ * _.+(1)).sum

def task1(a: List[String]): Long = win(a, power)
def task2(a: List[String]): Long = win(a, power3)

Scala3

kind of convoluted, but purely functional

import scala.collection.immutable.NumericRange.Exclusive
import math.max
import math.min

extension [A] (l: List[A])
  def chunk(pred: A => Boolean): List[List[A]] =
    def go(l: List[A], partial_acc: List[A], acc: List[List[A]]): List[List[A]] =
      l match
        case (h :: t) if pred(h) => go(t, List(), partial_acc.reverse :: acc)
        case (h :: t) => go(t, h :: partial_acc, acc)
        case _ => partial_acc.reverse :: acc
    
    go(l, List(), List()).reverse

type R = Exclusive[Long]

def intersectTranslate(r: R, c: R, t: Long): R =
    (t + max(r.start, c.start) - c.start) until (t + min(r.end, c.end) - c.start)

case class MappingEntry(from: R, to: Long)
case class Mapping(entries: List[MappingEntry], produces: String):
    def resolveRange(in: R): List[R] =
        entries.map(e => intersectTranslate(in, e.from, e.to)).filter(!_.isEmpty)

def completeEntries(a: List[MappingEntry]): List[MappingEntry] = 
    a ++ ((0L until 0L) +: a.map(_.from).sorted :+ (Long.MaxValue until Long.MaxValue)).sliding(2).flatMap{ case List(a, b) => Some(MappingEntry(a.end until b.start, a.end)); case _ => None}.toList

def parse(a: List[String], init: List[Long] => List[R]): (List[R], Map[String, Mapping]) =
    def parseEntry(s: String): MappingEntry =
        s match
            case s"$end $start $range" => MappingEntry(start.toLong until start.toLong + range.toLong, end.toLong)

    a.chunk(_ == "") match
        case List(s"seeds: $seeds") :: maps => 
            init(seeds.split(raw"\s+").map(_.toLong).toList) -> (maps.flatMap{ case s"$from-to-$to map:" :: entries => Some(from -> Mapping(completeEntries(entries.map(parseEntry)), to)); case _ => None }).toMap
        case _ => (List(), Map()).ensuring(false)

def singletons(a: List[Long]): List[R] = a.map(s => s until s + 1)
def paired(a: List[Long]): List[R] = a.grouped(2).flatMap{ case List(x, y) => Some(x until x+y); case _ => None }.toList

def chase(d: (List[R], Map[String, Mapping]), initial: String, target: String) =
    val (init, m) = d
    def go(a: List[R], s: String): List[R] =
        if trace(s) == target then a else
            val x = m(s)
            go(a.flatMap(x.resolveRange), x.produces)
    go(trace(init), initial)

def task1(a: List[String]): Long = 
    chase(parse(a, singletons), "seed", "location").min.start

def task2(a: List[String]): Long =
    chase(parse(a, paired), "seed", "location").min.start