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.

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

Rust Solution

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

deleted by creator

Haskell

Very cute. There’s one like this every year…

I suppose I could write some code to replicate what I did by hand, but I guess that would be missing the point? (And I don’t want to think about this problem any more)

{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE TupleSections #-}

import Control.Monad
import Control.Monad.State.Strict
import Data.List
import Data.List.Split
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map

data Module = Broadcast | FlipFlop | Conjoin

type Connection = (Module, [String])

readConnection :: String -> (String, Connection)
readConnection s =
  let [a, b] = splitOn " -> " s
      outs = splitOn ", " b
      (name, m) = case a of
        "broadcaster" -> (a, Broadcast)
        ('%' : n) -> (n, FlipFlop)
        ('&' : n) -> (n, Conjoin)
   in (name, (m, outs))

type Signal = (String, String, Bool)

buildNetwork :: [(String, Connection)] -> ([Signal] -> State (Map (String, String) Bool) [Signal], Map (String, String) Bool)
buildNetwork input = (go, initState)
  where
    network = Map.fromList input
    initState = Map.fromList $ do
      (src, (_, outs)) <- input
      out <- outs
      case network Map.!? out of
        Just (Conjoin, _) -> return ((out, src), False)
        _ -> mempty
    go :: [Signal] -> State (Map (String, String) Bool) [Signal]
    go [] = return []
    go sigs = (sigs ++) <$> (mapM dispatch sigs >>= go . concat)
    dispatch :: Signal -> State (Map (String, String) Bool) [Signal]
    dispatch (src, dest, v) =
      case network Map.!? dest of
        Just (Broadcast, outs) -> return $ map (dest,,v) outs
        Just (FlipFlop, outs)
          | v -> return []
          | otherwise -> do
              newState <- gets (maybe True not . (Map.!? (dest, dest)))
              modify (Map.insert (dest, dest) newState)
              return $ map (dest,,newState) outs
        Just (Conjoin, outs) -> do
          modify (Map.insert (dest, src) v)
          mem <- gets (Map.filterWithKey (\(n, _) _ -> n == dest))
          return $ map (dest,,not $ and mem) outs
        _ -> return []

part1 :: [(String, Connection)] -> Int
part1 input =
  let (go, initState) = buildNetwork input
      sigs = concat $ evalState (replicateM 1000 $ go [("button", "broadcaster", False)]) initState
      (hi, lo) = partition (\(_, _, v) -> v) sigs
   in length lo * length hi

part2 _ =
  foldl1'
    lcm
    -- by inspection
    [ 0b111101011001,
      0b111111010011,
      0b111010110111,
      0b111011101111
    ]

main = do
  input <- map readConnection . lines <$> readFile "input20"
  print $ part1 input
  print $ part2 input