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.

Rust Solution

Memories of Day 8. It took me too long to realize I forgot to remove the 1000 iteration limit for part two.

Python

Also on Github

import collections
import math
import re

from .solver import Solver


class Day20(Solver):
  modules: dict[str, tuple[str, list[str]]]
  conjunction_inputs: dict[str, set[str]]

  def __init__(self):
    super().__init__(20)

  def presolve(self, input: str):
    self.modules = {}
    self.conjunction_inputs = collections.defaultdict(set)
    for line in input.splitlines():
      m = re.fullmatch(r'(\W?)(\w+) -> (.*)', line)
      assert m
      kind, name, destinations = m.groups()
      self.modules[name] = (kind, destinations.split(', '))
    for source, (_, destinations) in self.modules.items():
      for destination, (kind, _) in ((d, self.modules[d]) for d in destinations if d in self.modules):
        if kind == '&':
          self.conjunction_inputs[destination].add(source)

  def _press_button(self, flip_flops_on: set[str],
                    conjunction_high_pulses: dict[str, set[str]]) -> tuple[list[str], list[str]]:
    low_pulses: list[str] = []
    high_pulses: list[str] = []
    pulse: list[tuple[str, str, int]] = [('', 'broadcaster', 0)]
    while pulse:
      origin, source, value = pulse.pop(0)
      if value == 0:
        low_pulses.append(source)
      else:
        high_pulses.append(source)
      if source not in self.modules:
        continue
      kind, destinations = self.modules[source]
      if source == 'broadcaster':
        for d in destinations:
          pulse.append((source, d, value))
      elif kind == '%' and value == 0:
        if source in flip_flops_on:
          flip_flops_on.remove(source)
          for d in destinations:
            pulse.append((source, d, 0))
        else:
          flip_flops_on.add(source)
          for d in destinations:
            pulse.append((source, d, 1))
      elif kind == '&':
        if value:
          conjunction_high_pulses[source].add(origin)
        elif origin in conjunction_high_pulses[source]:
          conjunction_high_pulses[source].remove(origin)
        if conjunction_high_pulses[source] == self.conjunction_inputs[source]:
          for d in destinations:
            pulse.append((source, d, 0))
        else:
          for d in destinations:
            pulse.append((source, d, 1))
    return low_pulses, high_pulses


  def solve_first_star(self) -> int:
    flip_flops_on = set()
    conjunction_high_pulses = collections.defaultdict(set)
    low_pulse_count = 0
    high_pulse_count = 0
    for _ in range(1000):
      low, high = self._press_button(flip_flops_on, conjunction_high_pulses)
      low_pulse_count += len(low)
      high_pulse_count += len(high)
    return low_pulse_count* high_pulse_count

  def solve_second_star(self) -> int:
    flip_flops_on = set()
    conjunction_high_pulses = collections.defaultdict(set)
    button_count = 0
    rx_upstream = [module for module, (_, destinations) in self.modules.items() if 'rx' in destinations]
    if len(rx_upstream) != 1:
      rx_upstream = []
    else:
      rx_upstream = [module for module, (_, destinations) in self.modules.items() if rx_upstream[0] in destinations]
    rx_upstream_periods = [None] * len(rx_upstream)
    low_pulses = []
    while 'rx' not in low_pulses and (not rx_upstream or not all(rx_upstream_periods)):
      button_count += 1
      low_pulses, _ = self._press_button(flip_flops_on, conjunction_high_pulses)
      for module, periods in zip(rx_upstream, rx_upstream_periods, strict=True):
        if periods is not None:
          continue
        if module in low_pulses:
          rx_upstream_periods[rx_upstream.index(module)] = button_count
    if 'rx' in low_pulses:
      return button_count
    return math.lcm(*rx_upstream_periods)

Nim

Another least common multiple problem. I kinda don’t like these, as it’s not practical to solve them purely with code that operates on arbitrary inputs.

• Day 20, part 1
• Day 20, part 2 partial solution
• Day 20, part 2 answer