Skip Navigation

πŸ’“ - 2023 DAY 20 SOLUTIONS - πŸ’“

Day 20: Pulse

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

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

  • Python

    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)