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)

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 @hades@lemm.ee 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

deleted by creator

C++, kind of

Ok so this is a little weird. My code for task1 is attached to this comment, but I actually solved task2 by hand. After checking that bruteforce indeed takes longer than a second, I plotted the graph just to see what was going on, and you can immediately tell that the result is the least common multiple of four numbers, which can easily be obtained by running task1 with a debugger, and maybe read directly from the graph as well. I also pre-broke my include statements, so hopefully the XSS protection isn't completely removing them again.

My graph: https://files.catbox.moe/1u4daw.png

blue is the broadcaster/button, yellows are flipflops, purples are nand gates and green is the output gate.

Also I abandoned scala again, because there is so much state modification going on.

#include fstream>
#include memory>
#include algorithm>
#include optional>
#include stdexcept>
#include set>
#include vector>
#include map>
#include deque>
#include unordered_map>

#include fmt/format.h>
#include fmt/ranges.h>
#include flux.hpp>
#include scn/all.h>
#include scn/scan/list.h>

enum Pulse { Low=0, High };

struct Module {
    std::string name;
    Module(std::string _name) : name(std::move(_name)) {}
    virtual std::optional handle(Module const& from, Pulse type) = 0;
    virtual ~Module() = default;
};

struct FlipFlop : public Module {
    using Module::Module;
    bool on = false;
    std::optional handle([[maybe_unused]] Module const& from, Pulse type) override {
        if(type == Low) {
            on = !on;
            return on ? High : Low;
        }
        return {};
    }
    virtual ~FlipFlop() = default;
};

struct Nand : public Module {
    using Module::Module;
    std::unordered_map last;
    std::optional handle(Module const& from, Pulse type) override {
        last[from.name] = type;

        for(auto& [k, v] : last) {
            if (v == Low) {
                return High;
            }
        }
        return Low;
    }
    virtual ~Nand() = default;
};

struct Broadcaster : public Module {
    using Module::Module;
    std::optional handle([[maybe_unused]] Module const& from, Pulse type) override {
        return type;
    }
    virtual ~Broadcaster() = default;
};

struct Sink : public Module {
    using Module::Module;
    std::optional handle([[maybe_unused]] Module const& from, Pulse type) override {
        return {};
    }
    virtual ~Sink() = default;
};

struct Button : public Module {
    using Module::Module;
    std::optional handle([[maybe_unused]] Module const& from, Pulse type) override {
        throw std::runtime_error{"Button should never recv signal"};
    }
    virtual ~Button() = default;
};

void run(Module* button, std::map> connections, long& lows, long& highs) {
    std::deque> pending;
    pending.push_back({button, Low});

    while(!pending.empty()) {
        auto [m, p] = pending.front();
        pending.pop_front();

        for(auto& m2 : connections.at(m->name)) {
            ++(p == Low ? lows : highs);
            fmt::println("{} -{}-> {}", m->name, p == Low ? "low":"high", m2->name);
            if(auto p2 = m2->handle(*m, p)) {
                pending.push_back({m2, *p2});
            }
        }
    }
}

struct Setup {
    std::vector> modules;
    std::map by_name;
    std::map> connections;
};

Setup parse(std::string path) {
    std::ifstream in(path);
    Setup res;
    auto lines = flux::getlines(in).to>();

    std::map> pre_connections;

    for(const auto& line : lines) {
        std::string name;
        if(auto r = scn::scan(line, "{} -> ", name)) {
            if(name == "broadcaster") {
                res.modules.push_back(std::make_unique(name));
            } 
            else if(name.starts_with('%')) {
                name = name.substr(1);
                res.modules.push_back(std::make_unique(name));
            }
            else if(name.starts_with('&')) {
                name = name.substr(1);
                res.modules.push_back(std::make_unique(name));
            }

            res.by_name[name] = res.modules.back().get();

            std::vector cons;
            if(auto r2 = scn::scan_list_ex(r.range(), cons, scn::list_separator(','))) {
                for(auto& c : cons) if(c.ends_with(',')) c.pop_back();
                fmt::println("name={}, rest={}", name, cons);
                pre_connections[name] = cons;
            } else {
                throw std::runtime_error{r.error().msg()};
            }
        } else {
            throw std::runtime_error{r.error().msg()};
        }
    }

    res.modules.push_back(std::make_unique("sink"));

    for(auto& [k, v] : pre_connections) {
        res.connections[k] = flux::from(std::move(v)).map([&](std::string s) { 
                try {
                    return res.by_name.at(s); 
                } catch(std::out_of_range const& e) {
                    fmt::print("out of range at {}\n", s);
                    return res.modules.back().get();
                }}).to>();
    }

    res.modules.push_back(std::make_unique("button"));
    res.connections["button"] = {res.by_name.at("broadcaster")};
    res.connections["sink"] = {};

    for(auto& [m, cs] : res.connections) {
        for(auto& m2 : cs) {
            if(auto nand = dynamic_cast(m2)) {
                nand->last[m] = Low;
            }
        }
    }

    return res;
}

int main(int argc, char* argv[]) {
    auto setup = parse(argc > 1 ? argv[1] : "../task1.txt");
    long lows{}, highs{};
    for(int i = 0; i < 1000; ++i)
        run(setup.modules.back().get(), setup.connections, lows, highs);

    fmt::println("task1: low={} high={} p={}", lows, highs, lows*highs);
}

My graph: https://files.catbox.moe/1u4daw.png

blue is the broadcaster/button, yellows are flipflops, purples are nand gates and green is the output gate.

Scala3

case class Part(x: Range, m: Range, a: Range, s: Range):
    def rating: Int = x.start + m.start + a.start + s.start
    def combinations: Long = x.size.toLong * m.size.toLong * a.size.toLong * s.size.toLong

type ActionFunc = Part => (Option[(Part, String)], Option[Part])

case class Workflow(ops: List[ActionFunc]):
    def process(p: Part): List[(Part, String)] =
        @tailrec def go(p: Part, ops: List[ActionFunc], acc: List[(Part, String)]): List[(Part, String)] =
            ops match
                case o :: t => o(p) match
                    case (Some(branch), Some(fwd)) => go(fwd, t, branch::acc)
                    case (None, Some(fwd)) => go(fwd, t, acc)
                    case (Some(branch), None) => branch::acc
                    case (None, None) => acc
                case _ => acc
        go(p, ops, List())

def run(parts: List[Part], workflows: Map[String, Workflow]) =
    @tailrec def go(parts: List[(Part, String)], accepted: List[Part]): List[Part] =
        parts match
            case (p, wf) :: t => 
                val res = workflows(wf).process(p)
                val (acc, rest) = res.partition((_, w) => w == "A")
                val (rej, todo) = rest.partition((_, w) => w == "R")
                go(todo ++ t, acc.map(_._1) ++ accepted)
            case _ => accepted
    go(parts.map(_ -> "in"), List())

def parseWorkflows(a: List[String]): Map[String, Workflow] =
    def generateActionGt(n: Int, s: String, accessor: Part => Range, setter: (Part, Range) => Part): ActionFunc = p => 
        val r = accessor(p)
        (Option.when(r.end > n + 1)((setter(p, math.max(r.start, n + 1) until r.end), s)), Option.unless(r.start > n)(setter(p, r.start until math.min(r.end, n + 1))))
    def generateAction(n: Int, s: String, accessor: Part => Range, setter: (Part, Range) => Part): ActionFunc = p => 
        val r = accessor(p)
        (Option.when(r.start < n)((setter(p, r.start until math.min(r.end, n)), s)), Option.unless(r.end <= n)(setter(p, math.max(r.start, n) until r.end)))
    
    val accessors = Map("x"->((p:Part) => p.x), "m"->((p:Part) => p.m), "a"->((p:Part) => p.a), "s"->((p:Part) => p.s))
    val setters = Map("x"->((p:Part, v:Range) => p.copy(x=v)), "m"->((p:Part, v:Range) => p.copy(m=v)), "a"->((p:Part, v:Range) => p.copy(a=v)), "s"->((p:Part, v:Range) => p.copy(s=v)))

    def parseAction(a: String): ActionFunc =
        a match
            case s"$v<$n:$s" => generateAction(n.toInt, s, accessors(v), setters(v))
            case s"$v>$n:$s" => generateActionGt(n.toInt, s, accessors(v), setters(v))
            case s => p => (Some((p, s)), None)

    a.map(_ match{ case s"$name{$items}" => name -> Workflow(items.split(",").map(parseAction).toList) }).toMap

def parsePart(a: String): Option[Part] =
    a match
        case s"{x=$x,m=$m,a=$a,s=$s}" => Some(Part(x.toInt until 1+x.toInt, m.toInt until 1+m.toInt, a.toInt until 1+a.toInt, s.toInt until 1+s.toInt))
        case _ => None

def task1(a: List[String]): Long = 
    val in = a.chunk(_ == "")
    val wfs = parseWorkflows(in(0))
    val parts = in(1).flatMap(parsePart)
    run(parts, wfs).map(_.rating).sum

def task2(a: List[String]): Long =
    val wfs = parseWorkflows(a.chunk(_ == "").head)
    val parts = List(Part(1 until 4001, 1 until 4001, 1 until 4001, 1 until 4001))
    run(parts, wfs).map(_.combinations).sum

looks like some broken XSS protection is killing the includes, can't really fix that

C++

No scala today

#include 
#include 
#include <map>
#include 

#include 
#include 
#include 
#include 
#include 
#include 
#include 

struct HorizontalEdge { boost::icl::discrete_interval x; long y; };

long area(std::vector he) {
    if(he.empty())
        return 0;

    boost::icl::interval_set intervals;
    std::ranges::sort(he, std::less{}, &amp;HorizontalEdge::y);
    long area{};
    long y = he.front().y;

    for(auto const&amp; e : he) {
        area += intervals.size() * (e.y - std::exchange(y, e.y));
        if(intervals.find(e.x) != intervals.end())
            intervals.erase(e.x);
        else 
            intervals.add(e.x);
    }

    return area;
}

struct Instruction {
    long l;
    int d;
    std::string color;
};

enum Dir { R=0, U=1, L=2, D=3 };
std::unordered_map char_to_dir = {{'R', R}, {'U', U}, {'L', L}, {'D', D}};

auto transcode(std::vector const&amp; is) {
    return flux::from(std::move(is)).map([](Instruction in) {
        long v = std::stoul(in.color.substr(0, 5), nullptr, 16);
        return Instruction{.l = v, .d = (4 - (in.color.at(5) - '0')) % 4, .color=""};
    }).to>();
}

std::vector read(std::string path) {
    std::ifstream in(std::move(path));
    return flux::getlines(in).map([](std::string const&amp; s) {
        Instruction i;
        char dir;
        if(auto r = scn::scan(s, "{} {} (#{:6})", dir, i.l, i.color)) {
            i.d = char_to_dir[dir];
            return i;
        } else {
            throw std::runtime_error{r.error().msg()};
        }
    }).to>();
}

auto turns(std::vector is) {
    if(is.empty()) throw std::runtime_error{"Too few elements"};
    is.push_back(is.front());
    return flux::from(std::move(is)).pairwise_map([](auto const&amp; lhs, auto const&amp; rhs) { return (rhs.d - lhs.d + 4) % 4 == 1; });
}

std::vector toEdges(std::vector is, bool left) {
    std::vector res;
    long x{}, y{};

    auto t = turns(is).to>();

    // some magic required to turn the ### path into its outer edge
    // (which is the actual object we want to compute the area for)
    for(size_t j = 0; j &lt; is.size(); ++j) {
        auto const&amp; i = is.at(j);
        bool s1 = t.at((j + t.size() - 1) % t.size()) == left;
        bool s2 = t.at(j) == left;
        long sign = (i.d == U || i.d == L) ? -1 : 1;
        long old_x = x;
        if(i.d == R || i.d == L) {
            x += i.l * sign;
            auto [l, r] = old_x &lt; x ? std::tuple{old_x + !s1, x + s2} : std::tuple{x + !s2, old_x + s1};
            res.push_back(HorizontalEdge{.x = {l, r, boost::icl::interval_bounds::right_open()}, .y = y});
        } else {
            y += (i.l + s1 + s2 - 1) * sign;
        }
    }

    return res;
}

long solve(std::vector is) {
    auto tn = turns(is).sum() - ssize(is);
    return area(toEdges(std::move(is), tn > 0));
}

int main(int argc, char* argv[]) {
    auto instructions = read(argc > 1 ? argv[1] : "../task1.txt");
    auto start = std::chrono::steady_clock::now();
    fmt::print("task1={}\ntask2={}\n", solve(instructions), solve(transcode(std::move(instructions))));
    fmt::print("took {}\n", std::chrono::steady_clock::now() - start);
}
```</map>

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

This could be much more efficient (and quite a bit shorter), but I wanted to try out the scala-graph library (https://www.scala-graph.org)

import day10._
import day10.Dir._
import scalax.collection.edges.DiEdge
import scalax.collection.immutable.Graph
import scalax.collection.edges.DiEdgeImplicits
import scalax.collection.generic.AnyEdge
import scalax.collection.generic.Edge

case class Node(ps: Set[Pos])

def getNode(p: Pos, d: Dir) = Node(Set(p, walk(p, d)))
def connect(p: Pos, d1: Dir, d2: Dir) = List(getNode(p, d1) ~> getNode(p, d2), getNode(p, d2) ~> getNode(p, d1))

def parseGrid(a: List[List[Char]]) = 
    def parseCell(s: Char, pos: Pos) =
        s match
            case '.' => connect(pos, Left, Right) ++ connect(pos, Up, Down)
            case '/' => connect(pos, Left, Up) ++ connect(pos, Right, Down)
            case '\\' => connect(pos, Left, Down) ++ connect(pos, Right, Up)
            case '-' => connect(pos, Left, Right) ++ List(
                getNode(pos, Up) ~> getNode(pos, Left), getNode(pos, Up) ~> getNode(pos, Right),
                getNode(pos, Down) ~> getNode(pos, Left), getNode(pos, Down) ~> getNode(pos, Right),
            )
            case '|' => connect(pos, Up, Down) ++ List(
                getNode(pos, Left) ~> getNode(pos, Up), getNode(pos, Left) ~> getNode(pos, Down),
                getNode(pos, Right) ~> getNode(pos, Up), getNode(pos, Right) ~> getNode(pos, Down),
            )
            case _ => List().ensuring(false)
        
    val edges = a.zipWithIndex.flatMap((r, y) => r.zipWithIndex.map((v, x) => v -> Pos(x, y))).map(parseCell).reduceLeft((a, b) => a ++ b)
    Graph() ++ edges

def illuminationFrom(p: Pos, d: Dir, g: Graph[Node, DiEdge[Node]], inBounds: Pos => Boolean): Long =
    val es = getNode(p, d.opposite) ~> getNode(p, d)
    val g2 = g + es
    val n = g2.get(getNode(p, d))
    n.outerNodeTraverser.flatMap(_.ps).toSet.filter(inBounds).size

def inBounds(a: List[String])(p: Pos) = p.x >= 0 && p.x < a(0).size && p.y >= 0 && p.y < a.size

def task1(a: List[String]): Long = 
    illuminationFrom(Pos(-1, 0), Right, parseGrid(a.map(_.toList)), inBounds(a))

def task2(a: List[String]): Long = 
    val inits = (for y <- a.indices yield Seq((Pos(-1, y), Right), (Pos(a(y).size, y), Left)))
        ++ (for x <- a(0).indices yield Seq((Pos(x, -1), Down), (Pos(x, a.size), Up)))

    val g = parseGrid(a.map(_.toList))
    inits.flatten.map((p, d) => illuminationFrom(p, d, g, inBounds(a))).max

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

forgot to post this

import Area.*
import Dir.*

enum Dir(num: Int, diff: (Int, Int)):
    val n = num
    val d = diff
    case Up extends Dir(3, (0, -1))
    case Down extends Dir(1, (0, 1))
    case Left extends Dir(2, (-1, 0))
    case Right extends Dir(0, (1, 0))
    def opposite = Dir.from(n + 2)

object Dir:
    def from(n: Int): Dir = Dir.all.filter(_.n == n % 4).ensuring(_.size == 1).head
    def all = List(Up, Down, Left, Right)

enum Area:
    case Inside, Outside, Loop

case class Pos(x: Int, y: Int)
type Landscape = Map[Pos, Pipe]
type Loop = Map[Pos, LoopPiece]

def walk(p: Pos, d: Dir): Pos = Pos(p.x + d.d._1, p.y + d.d._2)

val pipeMap = Map('|' -> List(Up, Down), '-' -> List(Left, Right), 'L' -> List(Up, Right), 'J' -> List(Up, Left), 'F' -> List(Right, Down), '7' -> List(Left, Down))

case class Pipe(neighbors: List[Dir])
case class LoopPiece(from: Dir, to: Dir):
    def left: List[Dir] = ((from.n + 1) until (if to.n < from.n then to.n + 4 else to.n)).map(Dir.from).toList
    def right: List[Dir] = LoopPiece(to, from).left

def parse(a: List[String]): (Pos, Landscape) =
    val pipes = for (r, y) <- a.zipWithIndex; (v, x) <- r.zipWithIndex; p <- pipeMap.get(v) yield Pos(x, y) -> Pipe(p) 
    val start = for (r, y) <- a.zipWithIndex; (v, x) <- r.zipWithIndex if v == 'S' yield Pos(x, y)
    (start.head, pipes.toMap)

def walkLoop(start: Pos, l: Landscape): Loop =
    @tailrec def go(pos: Pos, last_dir: Dir, acc: Loop): Loop =
        if pos == start then acc else
            val dir = l(pos).neighbors.filter(_ != last_dir.opposite).ensuring(_.size == 1).head
            go(walk(pos, dir), dir, acc + (pos -> LoopPiece(last_dir.opposite, dir)))

    Dir.all.filter(d => l.get(walk(start, d)).exists(p => p.neighbors.contains(d.opposite))) match
        case List(start_dir, return_dir) => go(walk(start, start_dir), start_dir, Map(start -> LoopPiece(return_dir, start_dir)))
        case _ => Map()

def task1(a: List[String]): Long =
    walkLoop.tupled(parse(a)).size.ensuring(_ % 2 == 0) / 2

def task2(a: List[String]): Long =
    val loop = walkLoop.tupled(parse(a))

    val ys = a.indices
    val xs = a.head.indices
    val points = (for x <- xs; y <- ys yield Pos(x, y)).toSet
    
    // floodfill
    @tailrec def go(outside: Set[Pos], q: List[Pos]): Set[Pos] =
        if q.isEmpty then outside else
            val nbs = Dir.all.map(walk(q.head, _)).filter(points.contains(_)).filter(!outside.contains(_))
            go(outside ++ nbs, nbs ++ q.tail)

    // start by floodfilling from the known outside: beyond the array bounds
    val boundary = ys.flatMap(y => List(Pos(-1, y), Pos(xs.end, y))) ++ xs.flatMap(x => List(Pos(x, -1), Pos(x, ys.end)))
    val r = go(boundary.toSet ++ loop.keySet, boundary.toList)

    // check on which side of the pipe the outside is, then continue floodfill from there
    val xsl = List[LoopPiece => List[Dir]](_.left, _.right).map(side => loop.flatMap((p, l) => side(l).map(d => walk(p, d))).filter(!loop.contains(_)).toSet).map(a => a -> a.intersect(r).size).ensuring(_.exists(_._2 == 0)).filter(_._2 != 0).head._1
    (points -- go(r ++ xsl, xsl.toList)).size

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 countDyn(a: List[Char], b: List[Int]): Long =
    // Simple dynamic programming approach
    // We fill a table T, where
    //  T[ ai, bi ] -> number of ways to place b[bi..] in a[ai..]
    //  T[ ai, bi ] = 0 if an-ai >= b[bi..].sum + bn-bi
    //  T[ ai, bi ] = 1 if bi == b.size - 1 && ai == a.size - b[bi] - 1
    //  T[ ai, bi ] = 
    //   (place) T [ ai + b[bi], bi + 1]   if ? or # 
    //   (skip)  T [ ai + 1, bi ]          if ? or .
    // 
    def t(ai: Int, bi: Int, tbl: Map[(Int, Int), Long]): Long =
        if ai >= a.size then
            if bi >= b.size then 1L else 0L 
        else
            val place = Option.when(
                bi < b.size && // need to have piece left
                ai + b(bi) <= a.size && // piece needs to fit
                a.slice(ai, ai + b(bi)).forall(_ != '.') && // must be able to put piece there
                (ai + b(bi) == a.size || a(ai + b(bi)) != '#') // piece needs to actually end
            )((ai + b(bi) + 1, bi + 1)).flatMap(tbl.get).getOrElse(0L)
            val skip = Option.when(a(ai) != '#')((ai + 1, bi)).flatMap(tbl.get).getOrElse(0L)
            place + skip

    @tailrec def go(ai: Int, tbl: Map[(Int, Int), Long]): Long =
        if ai == 0 then t(ai, 0, tbl) else go(ai - 1, tbl ++ b.indices.inclusive.map(bi => (ai, bi) -> t(ai, bi, tbl)).toMap)

    go(a.indices.inclusive.last + 1, Map())

def countLinePossibilities(repeat: Int)(a: String): Long =
    a match
        case s"$pattern $counts" => 
            val p2 = List.fill(repeat)(pattern).mkString("?")
            val c2 = List.fill(repeat)(counts).mkString(",")
            countDyn(p2.toList, c2.split(",").map(_.toInt).toList)
        case _ => 0L


def task1(a: List[String]): Long = a.map(countLinePossibilities(1)).sum
def task2(a: List[String]): Long = a.map(countLinePossibilities(5)).sum

(Edit: fixed mangling of &<)