AoC 2019 D23: Category Six

C++ | Problem statement | Source code | Tags: Intcode

← Previous Back to AoC Index Next →

Part 1

Again, I'm a bit annoyed by the vague wording. How do we deal with races with non-blocking I/O? In what order do we step the programs? The problem doesn't say, so I picked the most conservative approach: step each program one instruction at a time in a round-robin fashion (so they are run at the same "speed"). If a program produces output, we immediately deliver it to the destination program's input queue.

I have to make some modifications to my Program class (which I haven't changed since day 17's addition of string I/O). I added a field called default_input, which is returned when the input queue is empty (previously it threw an error). To keep throwing errors by default, I default it to 0xDEAD, a sentinel value. Now the code for day 23 can set it to -1 when initializing each program.

The main loop looks like this:

while (true) {
    for (int i = 0; i < 50; i++) {
        Program &prog = network[i];
        prog.step();
        if (prog.has_output()) {
            long long dest = prog.pop_output();
            prog.run_until_output();
            long long x = prog.pop_output();
            prog.run_until_output();
            long long y = prog.pop_output();
            if (dest == 255) {
                std::cout << y << std::endl;
                return;
            }
            network[dest].send_input(x);
            network[dest].send_input(y);
        }
    }
}
cpp

Part 2

The problem statement is again vague about what it means by "continuously trying to receive packets". I added a field called starved_cycles, which counts how many times the input instruction was executed while the input queue was empty, and is reset on send_input() (not during the next input instruction, so that a program is immediately considered non-starved when it receives input). If all 50 programs have starved_cycles > 1, we consider the network idle. (For reasons unclear to me, starved_cycles > 1 works but starved_cycles > 0 doesn't; I assume that's the implication of "continuously".) This check happens once after each round-robin cycle.

When the network is idle, and the NAT has a packet stored, I send the stored packet to program 0 (which resets its starved_cycles). I also keep track of the last Y value sent by the NAT, and print it and exit if the same Y value is sent twice in a row.

← Previous Back to AoC Index Next →