If you make the recurrent case a little more complicated, you can sidestep the weird base cases, but I like reducing the endpoints down to things like this that are easily implementable, even if they sound a little weird at first.

T counts the number of ways to place the blocks with lengths specified in b in the remaining a.size - ai slots. If there are no more slots left, there are two cases: Either there are also no more blocks left, then everything is fine, and the current situation is 1 way to place the blocks in the slots. Otherwise, there are still blocks left, and no more space to place them in. This means the current sitution is incorrect, so we contribute 0 ways to place the blocks. This is what the if bi >= b.size then 1L else 0L{.scala} does.

The start at size + 1 is necessary, as we need to compute every table entry before it may get looked up. When placing the last block, we may check the entry (ai + b(bi) + 1, bi + 1), where ai + b(bi) may already equal a.size (in the case where the block ends exactly at the end of a). The + 1 in the entry is necessary, as we need to skip a slot after every block: If we looked at (ai + b(bi), bi + 1), we could start at a.size, but then, for e.g. b = [2, 3], we would consider ...#####. a valid placement.

Let me know if there are still things unclear :)

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

Scala3, Sympy

case class Particle(x: Long, y: Long, z: Long, dx: Long, dy: Long, dz: Long)

def parseParticle(a: String): Option[Particle] = a match
    case s"$x, $y, $z @ $dx, $dy, $dz" => Some(Particle(x.toLong, y.toLong, z.toLong, dx.trim.toLong, dy.trim.toLong, dz.trim.toLong))
    case _ => None

def intersect(min: Double, max: Double)(p: Particle, q: Particle): Boolean =
    val n = p.dx * q.y - p.y * p.dx - q.x * p.dy + p.x * p.dy
    val d = p.dy * q.dx - p.dx * q.dy

    if(d == 0) then false else 
        val k = n.toDouble/d
        val k2 = (q.y + k * q.dy - p.y)/p.dy
        val ix = q.x + k * q.dx
        val iy = q.y + k * q.dy
        k2 >= 0 && k >= 0 && min <= ix && ix <= max && min <= iy && iy <= max

def task1(a: List[String]): Long = 
    val particles = a.flatMap(parseParticle)
    particles.combinations(2).count(l => intersect(2e14, 4e14)(l(0), l(1)))

import re as re2
from sympy import *

p, v, times, eqs = symbols('x y z'), symbols('dx dy dz'), [], []

def parse_eq(i: int, s: str):
    parts = [int(p) for p in re2.split(r'[,\s@]+', s) if p.strip() != '']
    time = Symbol(f't{i}')
    times.append(time)
    for rp, rv, hp, hv in zip(p, v, parts[:3], parts[3:]):
        eqs.append(Eq(rp + time * rv, hp + time * hv))

# need 3 equations for result, everything after that just slows things down
neq = 3
with open('task1.txt', 'r') as fobj:
    for i, s in zip(range(neq), fobj.readlines()):
        parse_eq(i, s)

for sol in solve(eqs, list(p) + list(v) + times):
    x, y, z, *_ = sol
    print(x + y + z)

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.

Scala3

val allowed: Map[Char, List[Dir]] = Map('>'->List(Right), '<'->List(Left), '^'->List(Up), 'v'->List(Down), '.'->Dir.all)

def toGraph(g: Grid[Char], start: Pos, goal: Pos) =
    def nb(p: Pos) = allowed(g(p)).map(walk(p, _)).filter(g.inBounds).filter(g(_) != '#')

    @tailrec def go(q: List[Pos], seen: Set[Pos], acc: List[WDiEdge[Pos]]): List[WDiEdge[Pos]] =
        q match
            case h :: t =>
                @tailrec def findNext(prev: Pos, n: Pos, d: Int): Option[(Pos, Int)] =
                    val fwd = nb(n).filter(_ != prev)
                    if fwd.size == 1 then findNext(n, fwd.head, d + 1) else Option.when(fwd.size > 1 || n == goal)((n, d))

                val next = nb(h).flatMap(findNext(h, _, 1))
                go(next.map(_._1).filter(!seen.contains(_)) ++ t, seen ++ next.map(_._1), next.map((n, d) => WDiEdge(h, n, d)) ++ acc)
            case _ => acc
    
    Graph() ++ go(List(start), Set(start), List()) 

def parseGraph(a: List[String]) =
    val (start, goal) = (Pos(1, 0), Pos(a(0).size - 2, a.size - 1))
    (toGraph(Grid(a.map(_.toList)), start, goal), start, goal)

def task1(a: List[String]): Long = 
    val (g, start, goal) = parseGraph(a)
    val topo = g.topologicalSort.fold(failure => List(), order => order.toList.reverse)
    topo.tail.foldLeft(Map(topo.head -> 0.0))((m, n) => m + (n -> n.outgoing.map(e => e.weight + m(e.targets.head)).max))(g.get(start)).toLong

def task2(a: List[String]): Long = 
    val (g, start, goal) = parseGraph(a)

    // this problem is np hard (reduction from hamilton path)
    // on general graphs, and I can't see any special case
    // in the input.
    // => throw bruteforce at it
    def go(n: g.NodeT, seen: Set[g.NodeT], w: Double): Double =
        val m1 = n.outgoing.filter(e => !seen.contains(e.targets.head)).map(e => go(e.targets.head, seen + e.targets.head, w + e.weight)).maxOption
        val m2 = n.incoming.filter(e => !seen.contains(e.sources.head)).map(e => go(e.sources.head, seen + e.sources.head, w + e.weight)).maxOption
        List(m1, m2).flatMap(a => a).maxOption.getOrElse(if n.outer == goal then w else -1)
    
    val init = g.get(start)
    go(init, Set(init), 0).toLong

Scala3

Not much to say about this, very straightforward implementation that was still fast enough

case class Pos3(x: Int, y: Int, z: Int)
case class Brick(blocks: List[Pos3]):
    def dropBy(z: Int) = Brick(blocks.map(b => b.copy(z = b.z - z)))
    def isSupportedBy(other: Brick) = ???

def parseBrick(a: String): Brick = a match
    case s"$x1,$y1,$z1~$x2,$y2,$z2" => Brick((for x <- x1.toInt to x2.toInt; y <- y1.toInt to y2.toInt; z <- z1.toInt to z2.toInt yield Pos3(x, y, z)).toList)

def dropOn(bricks: List[Brick], brick: Brick): (List[Brick], List[Brick]) =
    val occupied = bricks.flatMap(d => d.blocks.map(_ -> d)).toMap

    @tailrec def go(d: Int): (Int, List[Brick]) =
        val dropped = brick.dropBy(d).blocks.toSet
        if dropped.intersect(occupied.keySet).isEmpty && !dropped.exists(_.z <= 0) then
            go(d + 1)
        else
            (d - 1, occupied.filter((p, b) => dropped.contains(p)).map(_._2).toSet.toList)
    
    val (d, supp) = go(0)
    (brick.dropBy(d) :: bricks, supp)

def buildSupportGraph(bricks: List[Brick]): Graph[Brick, DiEdge[Brick]] =
    val (bs, edges) = bricks.foldLeft((List[Brick](), List[DiEdge[Brick]]()))((l, b) => 
        val (bs, supp) = dropOn(l._1, b)
        (bs, supp.map(_ ~> bs.head) ++ l._2)
    )
    Graph() ++ (bs, edges)

def parseSupportGraph(a: List[String]): Graph[Brick, DiEdge[Brick]] =
    buildSupportGraph(a.map(parseBrick).sortBy(_.blocks.map(_.z).min))

def wouldDrop(g: Graph[Brick, DiEdge[Brick]], b: g.NodeT): Long =
    @tailrec def go(shaking: List[g.NodeT], falling: Set[g.NodeT]): List[g.NodeT] = 
        shaking match
            case h :: t => 
                if h.diPredecessors.forall(falling.contains(_)) then
                    go(h.diSuccessors.toList ++ t, falling + h)
                else
                    go(t, falling)
            case _ => falling.toList
    
    go(b.diSuccessors.toList, Set(b)).size

def task1(a: List[String]): Long = parseSupportGraph(a).nodes.filter(n => n.diSuccessors.forall(_.inDegree > 1)).size
def task2(a: List[String]): Long = 
    val graph = parseSupportGraph(a)
    graph.nodes.toList.map(wouldDrop(graph, _) - 1).sum

If you wonder why the function is a quadratic, I suggest drawing stuff on a piece of paper. Essentially, if there were no obstacles, the furthest reachable cells would form a large diamond, which is tiled by some copies of the diamond in the input and some copies of the corners. As these have constant size, and the large diamond will grow quadratically with steps, you need a quadratic number of copies (by drawing, you can see that if steps = k * width + width/2, then there are floor((2k + 1)^2/2) copies of the center diamond, and ceil((2k + 1)^2/2) copies of each corner around).

What complicates this somewhat is that you don't just have to be able to reach a square in the number of steps, but that the parity has to match: By a chessboard argument, you can see any given square only every second step, as each step you move from a black tile to a white one or vice versa. And the parities flip each time you cross a boundary, as the input width is odd. So actually you have to either just guess the coefficients of a quadratic, as you and @[email protected] did, or do some more working out by hand, which will give you the explicit form, which I did and can't really recommend.

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.

This has a line-second score of of about 100 (including the comments - I don't know what counts as code and what doesn't so I figured I just include everything); translating this 1:1 into c++ (https://pastebin.com/fPhfm7Bs) yields a line-second score of 2.9.

Scala3

task2 is extremely disgusting code, but I was drawing an ugly picture of the situation and just wrote it down. Somehow, this worked first try.

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

extension (p: Pos) def parity = (p.x + p.y) % 2

def connect(p: Pos, d: Dir, g: Grid[Char]) = 
    val to = walk(p, d)
    Option.when(g.inBounds(to) && g.inBounds(p) && g(to) != '#' && g(p) != '#')(DiEdge(p, to))

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

def reachableIn(n: Int, g: Graph[Pos, DiEdge[Pos]], start: g.NodeT) =
    @tailrec def go(q: List[(Int, g.NodeT)], depths: Map[Pos, Int]): Map[Pos, Int] =
        q match
            case (d, n) :: t =>
                if depths.contains(n) then go(t, depths) else
                    val successors = n.outNeighbors.map(d + 1 -> _)
                    go(t ++ successors, depths + (n.outer -> d))
            case _ =>
                depths

    go(List(0 -> start), Map()).filter((_, d) => d <= n).keys.toList

def compute(a: List[String], n: Int): Long =
    val grid = Grid(a.map(_.toList))
    val g = parseGrid(a.map(_.toList))
    val start = g.get(grid.indexWhere(_ == 'S').head)
    reachableIn(n, g, start).filter(_.parity == start.parity).size

def task1(a: List[String]): Long = compute(a, 64)
def task2(a: List[String]): Long = 
    // this only works for inputs where the following assertions holds
    val steps = 26501365
    assert((steps - a.size/2) % a.size == 0)
    assert(steps % 2 == 1 && a.size % 2 == 1)

    val d = steps/a.size
    val k = (2 * d + 1)
    val k1 = k*k/2

    def sq(x: Long) = x * x
    val grid = Grid(a.map(_.toList))
    val g = parseGrid(a.map(_.toList))
    val start = g.get(grid.indexWhere(_ == 'S').head)
    val center = reachableIn(a.size/2, g, start)

    // If you stare at the input enough, one can see that
    // for certain values of steps, the total area is covered
    // by some copies of the center diamond, and some copies
    // of the remaining triangle shapes.
    // 
    // In some repetitions, the parity of the location of S is
    // the same as the parity of the original S.
    // d0 counts the cells reachable in a center diamond where
    // this holds, dn0 counts the cells reachable in a center diamond
    // where the parity is flipped.
    // The triangular shapes are counted by dr and dnr, respectively.
    //
    // The weird naming scheme is taken directly from the weird diagram
    // I drew in order to avoid further confusing myself.
    val d0 = center.count(_.parity != start.parity)
    val dr = g.nodes.count(_.parity != start.parity) - d0
    val dn0 = center.size - d0
    val dnr = dr + d0 - dn0

    // these are the counts of how often each type of area appears
    val r = sq(2 * d + 1) / 2
    val (rplus, rminus) = (r/2, r/2)
    val z = sq(2 * d + 1) / 2 + 1
    val zplus = sq(1 + 2*(d/2))
    val zminus = z - zplus

    // calc result
    zplus * d0 + zminus * dn0 + rplus * dr + rminus * dnr