|
29
|
1 --- Day 20: Pulse Propagation ---
|
|
|
2
|
|
|
3 Modules communicate using pulses. Each pulse is either a high pulse or a low pulse. When a module sends a pulse, it sends that type of pulse to each module in its list of destination modules.
|
|
|
4
|
|
|
5 There are several different types of modules:
|
|
|
6
|
|
|
7 Flip-flop modules (prefix %) are either on or off; they are initially off. If a flip-flop module receives a high pulse, it is ignored and nothing happens. However, if a flip-flop module receives a low pulse, it flips between on and off. If it was off, it turns on and sends a high pulse. If it was on, it turns off and sends a low pulse.
|
|
|
8
|
|
|
9 Conjunction modules (prefix &) remember the type of the most recent pulse received from each of their connected input modules; they initially default to remembering a low pulse for each input. When a pulse is received, the conjunction module first updates its memory for that input. Then, if it remembers high pulses for all inputs, it sends a low pulse; otherwise, it sends a high pulse.
|
|
|
10
|
|
|
11 There is a single broadcast module (named broadcaster). When it receives a pulse, it sends the same pulse to all of its destination modules.
|
|
|
12
|
|
|
13 There is a module with a single button on it called the button module. When you push the button, a single low pulse is sent directly to the broadcaster module.
|
|
|
14
|
|
|
15 After pushing the button, you must wait until all pulses have been delivered and fully handled before pushing it again. Never push the button if modules are still processing pulses.
|
|
|
16
|
|
|
17 Pulses are always processed in the order they are sent. So, if a pulse is sent to modules a, b, and c, and then module a processes its pulse and sends more pulses, the pulses sent to modules b and c would have to be handled first.
|
|
|
18
|
|
|
19 The module configuration (your puzzle input) lists each module. The name of the module is preceded by a symbol identifying its type, if any. The name is then followed by an arrow and a list of its destination modules. For example:
|
|
|
20
|
|
|
21 broadcaster -> a, b, c
|
|
|
22 %a -> b
|
|
|
23 %b -> c
|
|
|
24 %c -> inv
|
|
|
25 &inv -> a
|
|
|
26
|
|
|
27 In this module configuration, the broadcaster has three destination modules named a, b, and c. Each of these modules is a flip-flop module (as indicated by the % prefix). a outputs to b which outputs to c which outputs to another module named inv. inv is a conjunction module (as indicated by the & prefix) which, because it has only one input, acts like an inverter (it sends the opposite of the pulse type it receives); it outputs to a.
|
|
|
28
|
|
|
29 By pushing the button once, the following pulses are sent:
|
|
|
30
|
|
|
31 button -low-> broadcaster
|
|
|
32 broadcaster -low-> a
|
|
|
33 broadcaster -low-> b
|
|
|
34 broadcaster -low-> c
|
|
|
35 a -high-> b
|
|
|
36 b -high-> c
|
|
|
37 c -high-> inv
|
|
|
38 inv -low-> a
|
|
|
39 a -low-> b
|
|
|
40 b -low-> c
|
|
|
41 c -low-> inv
|
|
|
42 inv -high-> a
|
|
|
43
|
|
|
44 After this sequence, the flip-flop modules all end up off, so pushing the button again repeats the same sequence.
|
|
|
45
|
|
|
46 Here's a more interesting example:
|
|
|
47
|
|
|
48 broadcaster -> a
|
|
|
49 %a -> inv, con
|
|
|
50 &inv -> b
|
|
|
51 %b -> con
|
|
|
52 &con -> output
|
|
|
53
|
|
|
54 This module configuration includes the broadcaster, two flip-flops (named a and b), a single-input conjunction module (inv), a multi-input conjunction module (con), and an untyped module named output (for testing purposes). The multi-input conjunction module con watches the two flip-flop modules and, if they're both on, sends a low pulse to the output module.
|
|
|
55
|
|
|
56 Here's what happens if you push the button once:
|
|
|
57
|
|
|
58 button -low-> broadcaster
|
|
|
59 broadcaster -low-> a
|
|
|
60 a -high-> inv
|
|
|
61 a -high-> con
|
|
|
62 inv -low-> b
|
|
|
63 con -high-> output
|
|
|
64 b -high-> con
|
|
|
65 con -low-> output
|
|
|
66
|
|
|
67 Both flip-flops turn on and a low pulse is sent to output! However, now that both flip-flops are on and con remembers a high pulse from each of its two inputs, pushing the button a second time does something different:
|
|
|
68
|
|
|
69 button -low-> broadcaster
|
|
|
70 broadcaster -low-> a
|
|
|
71 a -low-> inv
|
|
|
72 a -low-> con
|
|
|
73 inv -high-> b
|
|
|
74 con -high-> output
|
|
|
75
|
|
|
76 Flip-flop a turns off! Now, con remembers a low pulse from module a, and so it sends only a high pulse to output.
|
|
|
77
|
|
|
78 Push the button a third time:
|
|
|
79
|
|
|
80 button -low-> broadcaster
|
|
|
81 broadcaster -low-> a
|
|
|
82 a -high-> inv
|
|
|
83 a -high-> con
|
|
|
84 inv -low-> b
|
|
|
85 con -low-> output
|
|
|
86 b -low-> con
|
|
|
87 con -high-> output
|
|
|
88
|
|
|
89 This time, flip-flop a turns on, then flip-flop b turns off. However, before b can turn off, the pulse sent to con is handled first, so it briefly remembers all high pulses for its inputs and sends a low pulse to output. After that, flip-flop b turns off, which causes con to update its state and send a high pulse to output.
|
|
|
90
|
|
|
91 Finally, with a on and b off, push the button a fourth time:
|
|
|
92
|
|
|
93 button -low-> broadcaster
|
|
|
94 broadcaster -low-> a
|
|
|
95 a -low-> inv
|
|
|
96 a -low-> con
|
|
|
97 inv -high-> b
|
|
|
98 con -high-> output
|
|
|
99
|
|
|
100 This completes the cycle: a turns off, causing con to remember only low pulses and restoring all modules to their original states.
|
|
|
101
|
|
|
102 The answer is the number of low pulses multiplied by the number of high pulses when the button is pressed 1000 times.
|
|
|
103
|
|
|
104 In the first example, the same thing happens every time the button is pushed: 8 low pulses and 4 high pulses are sent. So, after pushing the button 1000 times, 8000 low pulses and 4000 high pulses are sent. Multiplying these together gives 32000000.
|
|
|
105
|
|
|
106 In the second example, after pushing the button 1000 times, 4250 low pulses and 2750 high pulses are sent. Multiplying these together gives 11687500. |
