Module day24

Crossed Wires

Part one is a straightforward simulation of the gates. Part two asks us to fix a broken ripple carry adder.

The structure of the adder is:

• Half adder for bits x00 and y00. Outputs sum to z00 and carry to z01.
• Full adder for bits x01..x44 and y01..y44. Outputs carry to next bit in the chain “rippling” up to final bit.
• z45 is the carry output from x44 and y44.

Implemented in logic gates this looks like:

   Half Adder     Full Adder
   ┌───┐ ┌───┐    ┌───┐ ┌───┐
   |x00| |y00|    |x01| |y01|
   └───┘ └───┘    └───┘ └───┘
    | | ┌─┘ |      | | ┌─┘ |
    | └───┐ |      | └───┐ |
    | ┌-┘ | |      | ┌-┘ | |
   ┌───┐ ┌───┐    ┌───┐ ┌───┐
   |XOR| |AND|    |XOR| |AND|
   └───┘ └───┘    └───┘ └───┘
     |     |    ┌───┴┐     |
     |     └──┬────┐ |     |
     |   Carry| | ┌───┐    |
     |    out | | |AND|    |
     |        | | └───┘    |
     |        | |   └────┐ |
     |        | └────┐   | |
     |        └────┐ |   | |
     |            ┌───┐ ┌───┐
     |            |XOR| |OR |                                  Carry
     |            └───┘ └───┘                                   out
     |              |     |                                      |
   ┌───┐          ┌───┐   |                                    ┌───┐
   |z00|          |z01| Carry    ...repeat for z01 to z44...   |z45|
   └───┘          └───┘  out                                   └───┘

Then we can deduce some rules for the output of each gate type:

1. XOR If inputs are x and y then output must be another XOR gate (except for inputs x00 and y00) otherwise output must be z.
2. AND Output must be an OR gate (except for inputs x00 and y00).
3. OR Output must be both AND and XOR gate, except for final carry which must output to z45.

We only need to find swapped outputs (not fix them) so the result is the labels of gates that breaks the rules in alphabetical order.

Functions

parse

part1

part2

Type Aliases

Input 🔒