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 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

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)))