• 0 Posts
  • 31 Comments
Joined 11 months ago
cake
Cake day: December 5th, 2023

help-circle

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


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




  • 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
    


  • 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
    


  • 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 &amp;&amp; p.x &lt; a(0).size &amp;&amp; p.y >= 0 &amp;&amp; p.y &lt; 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 &lt;- a.indices yield Seq((Pos(-1, y), Right), (Pos(a(y).size, y), Left)))
            ++ (for x &lt;- 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)))