When doing functional programming, you can't really do loops (because of referential transparency, you can't update iterators or indices). However, recursion still works.
Agreed, i get annoyed when I can't actually solve the problem. I would be ok if the inputs are trivial special cases, as long as feasible (but harder) generalized solutions still existed.
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
Scala3
Learning about scala-graph yesterday seems to have paid off already. This explicitly constructs the entire graph of allowed moves, and then uses a naive dijkstra run. This works, and I don't have to write a lot of code, but it is fairly inefficient.
import day10._
import day10.Dir._
import day11.Grid
// standing on cell p, having entered from d
case class Node(p: Pos, d: Dir)
def connect(p: Pos, d: Dir, g: Grid[Int], dists: Range) =
val from = Seq(-1, 1).map(i => Dir.from(d.n + i)).map(Node(p, _))
val ends = List.iterate(p, dists.last + 1)(walk(_, d)).filter(g.inBounds)
val costs = ends.drop(1).scanLeft(0)(_ + g(_))
from.flatMap(f => ends.zip(costs).drop(dists.start).map((dest, c) => WDiEdge(f, Node(dest, d), c)))
def parseGrid(a: List[List[Char]], dists: Range) =
val g = Grid(a.map(_.map(_.getNumericValue)))
Graph() ++ g.indices.flatMap(p => Dir.all.flatMap(d => connect(p, d, g, dists)))
def compute(a: List[String], dists: Range): Long =
val g = parseGrid(a.map(_.toList), dists)
val source = Node(Pos(-1, -1), Right)
val sink = Node(Pos(-2, -2), Right)
val start = Seq(Down, Right).map(d => Node(Pos(0, 0), d)).map(WDiEdge(source, _, 0))
val end = Seq(Down, Right).map(d => Node(Pos(a(0).size - 1, a.size - 1), d)).map(WDiEdge(_, sink, 0))
val g2 = g ++ start ++ end
g2.get(source).shortestPathTo(g2.get(sink)).map(_.weight).getOrElse(-1.0).toLong
def task1(a: List[String]): Long = compute(a, 1 to 3)
def task2(a: List[String]): Long = compute(a, 4 to 10)
Scala3
def diffs(a: Seq[Long]): List[Long] =
a.drop(1).zip(a).map(_ - _).toList
def predictNext(a: Seq[Long], combine: (Seq[Long], Long) => Long): Long =
if a.forall(_ == 0) then 0 else combine(a, predictNext(diffs(a), combine))
def predictAllNexts(a: List[String], combine: (Seq[Long], Long) => Long): Long =
a.map(l => predictNext(l.split(raw"\s+").map(_.toLong), combine)).sum
def task1(a: List[String]): Long = predictAllNexts(a, _.last + _)
def task2(a: List[String]): Long = predictAllNexts(a, _.head - _)
I can prove the opposite for you. The assumption that Gobbel2000 describes is wrong in general. For example, take
L
A -> B, X
B -> C, X
C -> Z, X
Z -> C, X
X -> X, X
the first Z is reached after 3 steps, but then every cycle only takes 2 steps.
The matches are still at consistent intervals, but you can easily find a counterexample for that as well:
L
A -> 1Z, X
1Z -> 2Z, X
2Z -> A, X
X -> X, X
now the intervals will be 2, 1, 2, 1, ...
However, it is easy to prove that there will be a loop of finite length, and that the intervals will behave somewhat nicely:
Identify a "position" by a node you are at, and your current index in the LRL instruction sequence. If you ever repeat a position P, you will repeat the exact path away from the position you took the last time, and the last time you later reached P, so you will keep reaching P again and again. There are finitely many positions, so you can't keep not repeating any forever, you will run out.
Walking in circles along this loop you eventually find yourself in, the intervals between Zs you see will definitely be a repeating sequence (as you will keep seeing not just same-length intervals, but in fact the exact same paths between Zs).
So in total, you will see some finite list of prefix-intervals, and then a repeating cycle of loop-intervals. I have no idea if this can be exploited to compute the answer efficiently, but see my solution-comment for something that only assumes that only one Z will be encountered each cycle.
Scala3
this is still not 100% general, as it assumes there is only one Z-node along the path for each start. But it doesn't assume anything else, I think. If you brute force combinations of entries of the zs-arrays, this assumption can be trivially removed, but if multiple paths see lots of Z-nodes, then the runtime will grow exponentially. I don't know if it's possible to do this any faster.
def parse(a: List[String]): (List[Char], Map[String, Map[Char, String]]) =
def parseNodes(n: List[String]) =
n.flatMap{case s"$from = ($l, $r)" => Some(from -> Map('L'->l, 'R'->r)); case _ => None}.toMap
a match{case instr::""::nodes => ( instr.toList, parseNodes(nodes) ); case _ => (List(), Map())}
def task1(a: List[String]): Long =
val (instr, nodes) = parse(a)
def go(i: Stream[Char], pos: String, n: Long): Long =
if pos != "ZZZ" then go(i.tail, nodes(pos)(i.head), n+1) else n
go(instr.cycle, "AAA", 0)
// ok so i originally thought this was going to be difficult, so
// we parse a lot of info we won't use
case class PathInfo(zs: List[Long], loopFrom: Long, loopTo: Long):
def stride: Long = loopTo - loopFrom
type Cycle = Long
def getInfo(instr: List[Char], isEnd: String => Boolean, map: Map[String, Map[Char, String]], start: String): PathInfo =
def go(i: Cycle, pos: String, is: List[Char], seen: Map[(Long, String), Cycle], acc: List[Long]): PathInfo =
val current: (Long, String) = (is.size % instr.size, pos)
val nis = if is.isEmpty then instr else is
val nacc = if isEnd(pos) then i::acc else acc
seen.get(current) match
case Some(l) => PathInfo(acc, l, i)
case _ => go(i + 1, map(pos)(nis.head), nis.tail, seen + (current -> i), nacc)
go(0, start, instr, Map(), List())
// turns out we don't need to check all the different positions
// in each cycle where we are on a Z position, as a) every start
// walks into unique cycles with b) exactly one Z position,
// and c) the length of the cycle is equivalent to the steps to first
// encounter a Z (so a->b->c->Z->c->Z->... is already more complicated,
// as the cycle length is 2 but the first encounter is after 3 steps)
// anyway let's do some math
// this is stolen code
def gcd(a: Long, b: Long): Long =
if(b ==0) a else gcd(b, a%b)
def primePowers(x: Long): Map[Long, Long] =
// for each prime p for which p^k divides x: p->p^k
def go(r: Long, t: Long, acc: Map[Long, Long]): Map[Long, Long] =
if r == 1 then acc else
if r % t == 0 then
go(r/t, t, acc + (t -> acc.getOrElse(t, 1L)*t))
else
go(r, t+1, acc)
go(x, 2, Map())
// this algorithm is stolen, but I scalafied the impl
def vanillaCRT(congruences: Map[Long, Long]): Long =
val N = congruences.keys.product
val x = congruences.map((n, y) => y*(N/n)*((N/n) % n)).sum
if x <= 0 then x + N else x
def generalizedHardcoreCRTThatCouldHaveBeenAnLCMBecauseTheInputIsVeryConvenientlyTrivialButWeWantToDoThisRight(ys: List[Long], xs: List[Long]): Option[Long] =
// finds the smallest k s.t. k === y_i (mod x_i) for each i
// even when stuff is not nice
// pre-check if everything is sufficiently coprime
// https://math.stackexchange.com/questions/1644677/what-to-do-if-the-modulus-is-not-coprime-in-the-chinese-remainder-theorem
val vars = for
((y1, n1), i1) <- ys.zip(xs).zipWithIndex
((y2, n2), i2) <- ys.zip(xs).zipWithIndex
if i2 > i1
yield
val g = gcd(n1, n2)
y1 % g == y2 % g
if !vars.forall(a => a) then
None
else
// we need to split k === y (mod mn) into k === y (mod m) and k === y (mod n) for m, n coprime
val congruences = for
(x, y) <- xs.zip(ys)
(p, pl) <- primePowers(x)
yield
p -> (y % pl -> pl)
// now we eliminate redundant congruences
// since our input is trivial, this is essentially
// the step in which we solve the task by
// accidentaly computing an lcm
val r = congruences.groupMap(_._1)(_._2).mapValues(l => l.map(_._2).max -> l.head._1).values.toMap
// ok now we meet the preconditions
// for doing this
Some(vanillaCRT(r))
def task2(a: List[String]): Long =
val (instr, nodes) = parse(a)
val infos = nodes.keySet.filter(_.endsWith("A")).map(s => getInfo(instr, _.endsWith("Z"), nodes, s))
generalizedHardcoreCRTThatCouldHaveBeenAnLCMBecauseTheInputIsVeryConvenientlyTrivialButWeWantToDoThisRight(
infos.map(_.zs.head).toList, infos.map(_.stride).toList
).getOrElse(0)
@main def main: Unit =
val data = readlines("/home/tim/test/aoc23/aoc23/inputs/day8/task1.txt")
for f <- List(
task1,
task2,
).map(_ andThen println)
do f(data)
Scala3
val tiers = List(List(1, 1, 1, 1, 1), List(1, 1, 1, 2), List(1, 2, 2), List(1, 1, 3), List(2, 3), List(1, 4), List(5))
val cards = List('2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A')
def cardValue(base: Long, a: List[Char], cards: List[Char]): Long =
a.foldLeft(base)(cards.size * _ + cards.indexOf(_))
def hand(a: List[Char]): List[Int] =
a.groupMapReduce(s => s)(_ => 1)(_ + _).values.toList.sorted
def power(a: List[Char]): Long =
cardValue(tiers.indexOf(hand(a)), a, cards)
def power3(a: List[Char]): Long =
val x = hand(a.filter(_ != 'J'))
val t = tiers.lastIndexWhere(x.zipAll(_, 0, 0).forall(_ <= _))
cardValue(t, a, 'J'::cards)
def win(a: List[String], pow: List[Char] => Long) =
a.flatMap{case s"$hand $bid" => Some((pow(hand.toList), bid.toLong)); case _ => None}
.sorted.map(_._2).zipWithIndex.map(_ * _.+(1)).sum
def task1(a: List[String]): Long = win(a, power)
def task2(a: List[String]): Long = win(a, power3)
Scala3
// math.floor(i) == i if i.isWhole, but we want i-1
def hardFloor(d: Double): Long = (math.floor(math.nextAfter(d, Double.NegativeInfinity))).toLong
def hardCeil(d: Double): Long = (math.ceil(math.nextAfter(d, Double.PositiveInfinity))).toLong
def wins(t: Long, d: Long): Long =
val det = math.sqrt(t*t/4.0 - d)
val high = hardFloor(t/2.0 + det)
val low = hardCeil(t/2.0 - det)
(low to high).size
def task1(a: List[String]): Long =
def readLongs(s: String) = s.split(raw"\s+").drop(1).map(_.toLong)
a match
case List(s"Time: $time", s"Distance: $dist") => readLongs(time).zip(readLongs(dist)).map(wins).product
case _ => 0L
def task2(a: List[String]): Long =
def readLong(s: String) = s.replaceAll(raw"\s+", "").toLong
a match
case List(s"Time: $time", s"Distance: $dist") => wins(readLong(time), readLong(dist))
case _ => 0L
Scala3
kind of convoluted, but purely functional
import scala.collection.immutable.NumericRange.Exclusive
import math.max
import math.min
extension [A] (l: List[A])
def chunk(pred: A => Boolean): List[List[A]] =
def go(l: List[A], partial_acc: List[A], acc: List[List[A]]): List[List[A]] =
l match
case (h :: t) if pred(h) => go(t, List(), partial_acc.reverse :: acc)
case (h :: t) => go(t, h :: partial_acc, acc)
case _ => partial_acc.reverse :: acc
go(l, List(), List()).reverse
type R = Exclusive[Long]
def intersectTranslate(r: R, c: R, t: Long): R =
(t + max(r.start, c.start) - c.start) until (t + min(r.end, c.end) - c.start)
case class MappingEntry(from: R, to: Long)
case class Mapping(entries: List[MappingEntry], produces: String):
def resolveRange(in: R): List[R] =
entries.map(e => intersectTranslate(in, e.from, e.to)).filter(!_.isEmpty)
def completeEntries(a: List[MappingEntry]): List[MappingEntry] =
a ++ ((0L until 0L) +: a.map(_.from).sorted :+ (Long.MaxValue until Long.MaxValue)).sliding(2).flatMap{ case List(a, b) => Some(MappingEntry(a.end until b.start, a.end)); case _ => None}.toList
def parse(a: List[String], init: List[Long] => List[R]): (List[R], Map[String, Mapping]) =
def parseEntry(s: String): MappingEntry =
s match
case s"$end $start $range" => MappingEntry(start.toLong until start.toLong + range.toLong, end.toLong)
a.chunk(_ == "") match
case List(s"seeds: $seeds") :: maps =>
init(seeds.split(raw"\s+").map(_.toLong).toList) -> (maps.flatMap{ case s"$from-to-$to map:" :: entries => Some(from -> Mapping(completeEntries(entries.map(parseEntry)), to)); case _ => None }).toMap
case _ => (List(), Map()).ensuring(false)
def singletons(a: List[Long]): List[R] = a.map(s => s until s + 1)
def paired(a: List[Long]): List[R] = a.grouped(2).flatMap{ case List(x, y) => Some(x until x+y); case _ => None }.toList
def chase(d: (List[R], Map[String, Mapping]), initial: String, target: String) =
val (init, m) = d
def go(a: List[R], s: String): List[R] =
if trace(s) == target then a else
val x = m(s)
go(a.flatMap(x.resolveRange), x.produces)
go(trace(init), initial)
def task1(a: List[String]): Long =
chase(parse(a, singletons), "seed", "location").min.start
def task2(a: List[String]): Long =
chase(parse(a, paired), "seed", "location").min.start
Scala3
all done!