Let's solve Advent of Code 2024 Day 24 by fixing a faulty Ripple Carry Adder!

AOC 2024, Day 24: Ripple Carry Adder


Advent of Code Day 24 was the toughest day of the year for me. I had absolutely no idea how to even begin approaching Day 24, lets figure it out!


The below is a guest post by the amazing Shraddha Agrawal.


Part 1

The first half of the input signifies the starting value of some wires. This serves as the input for the entire system. The second half lists all of the gates and the wires connected to them. Each line signifies 2 input wires to a gate and the output wire. eg: x00 AND y00 -> z00 signifies x00 and y00 connected to gate AND which outputs the result onto wire z00.

We need to process all the connections listed in the second half of the input and find the value present in all gates starting with z. The output of all z wires signify bits of a number, where z00 is the least significant bit. The answer for part 1 is this number is base 10 formed out of converting the base 2 representation of the number signified by all the z gates.

Solution

First, I processed the input into maps, one for values of input wires, called inputMap and the other for connections present in the second half of the input, called evalMap.

evalMap has wires as the key and a slice of its connections as its value, where eachentry holds the other input wire, gate and the output wire. For each connection present in the input, I added two entries in the evalMap, by flipping the two wires that feed into a gate so that all connections for a given wire are present in the value slice of the map.

Implementing it:

func createInputMap(input []string) (map[string]int, map[string][][]string) {
	inputMap := make(map[string]int)
	evalMap := make(map[string][][]string)

	isInitialState := true
	for _, line := range input {
		if len(line) == 0 {
			isInitialState = false
		}

		if isInitialState {
			inputMap[line[:3]] = aoc.FetchNumFromStringIgnoringNonNumeric(line[3:])
		}

		if !isInitialState && len(line) > 3 {
			vals := strings.Split(line, " ")
			evalMap[vals[0]] = append(evalMap[vals[0]], []string{vals[2], vals[1], vals[4]})
			evalMap[vals[2]] = append(evalMap[vals[2]], []string{vals[0], vals[1], vals[4]})
		}
	}
	return inputMap, evalMap
}

Lets write a function to process the gates and store the calculated value for the output gate in the inputMap:

func evalGate(a, gate, b, output string, inputMap map[string]int) {
	switch gate {
	case "AND":
		inputMap[output] = inputMap[a] & inputMap[b]
	case "OR":
		inputMap[output] = inputMap[a] | inputMap[b]
	case "XOR":
		inputMap[output] = inputMap[a] ^ inputMap[b]
	}
}

Now, to process it I used a BFS approach. A few things:

  1. The next slice should be prefilled with all the wires that we have the inital value for.
  2. For each iteration, we take the first element from the next slice and check if this wire is present in the inputMap. If not, we add it back to the end of the next slice and move on.
  3. If the wire is present in the inputMap, we evaluate all its combinations in the evalMap. If the output wire has not yet been visited, we add it to the next slice to process later.
  4. To avoid getting stuck in a loop, we use a visited map to store all wires we have processed so dar.

Implementing this:

func evaluateWires(inputMap map[string]int, evalInst map[string][][]string) {
	next := []string{}
	visited := make(map[string]struct{})
	for key, _ := range inputMap {
		next = append(next, key)
	}

	for len(next) != 0 {
		current := next[0]
		next = next[1:]

		if _, ok := visited[current]; ok {
			continue
		}

		if _, ok := evalInst[current]; !ok {
			continue
		}

		if _, ok := inputMap[current]; !ok {
			next = append(next, current)
			continue
		}

		found := false
		for _, combination := range evalInst[current] {
			if _, ok := inputMap[combination[0]]; !ok {
				continue
			}
			found = true
			evalGate(current, combination[1], combination[0], combination[2], inputMap)
			if _, ok := visited[combination[2]]; !ok {
				next = append(next, combination[2])
			}
		}

		if !found {
			next = append(next, current)
			continue
		}

		visited[current] = struct{}{}
	}
}

We have processed all wires, now we need to get the binary representation of the number in wires starting with z. We can do this by iterating over the inputMap and finding values of all z wires.

func getDecimal10FromGatesStartingWith(inputMap map[string]int, char string) int64 {
	resultZ, result := []string{}, []string{}
	for key, _ := range inputMap {
		if string(key[0]) == char {
			resultZ = append(resultZ, key)
		}
	}

	sort.Strings(resultZ)
	for i := len(resultZ) - 1; i >= 0; i-- {
		result = append(result, fmt.Sprintf("%d", inputMap[resultZ[i]]))
	}
	intValue, _ := strconv.ParseInt(strings.Join(result, ""), 2, 64)
	return intValue
}

And that’s it! Calling the above function with the z character will give us the answer for part 1.

Part 2

The system is actually trying to add two numbers. The two numbers are the base 10 numbers formed by all x and y wires respectively. The output number formed by the bits of z wires should be the sum of the numbers formed by x and y wires.

But in the current connection of wires, the output is faulty. This is because 4 pairs of wires have been swapped. We need to find these 4 pair of wires, ie total 8 wires. The answer should be these wires sorted in alphabetically separated by commas.

Solution

I really had no idea how to approach this one. I tried to final the expected bits on Z gate but didn’t have any clue how to go about it further. One thing to note is that we don’t actually need to fix the system, but just find the eight faulty wires.

Looking for hints, I realised that the given system is actually a Ripple Carry Adder. Thanks to this post, I landed on these 4 rules to find the eight faulty wires:

  1. If the output of a gate is z, then the operation has to be XOR unless it is the last bit.
  2. If the output of a gate is not z and the inputs are not x, y then it has to be AND / OR gate, but not XOR gate.
  3. If you have a XOR gate with inputs x, y, there must be another XOR gate with the output of this gate as an input. Search through all gates for an XOR-gate with this gate as an input; if it does not exist, your (original) XOR gate is faulty.
  4. Similarly, if you have an AND gate, there must be an OR gate with this gate as an input. If that gate doesn’t exist, the original AND gate is faulty.

Since we used maps for both wires and connections, searching for all the rules above is fairly easy:

// validateRippleCarryAdderRules checks the following rules:
// 1. If the output of a gate is z, then the operation has to be XOR unless it is the last bit.
// 2. If the output of a gate is not z and the inputs are not x, y then it has to be AND / OR, but not XOR.
// 3. If you have a XOR gate with inputs x, y, there must be another XOR gate with this gate as an input.
// Search through all gates for an XOR-gate with this gate as an input; if it does not exist, your (original) XOR gate is faulty.
// 4. Similarly, if you have an AND-gate, there must be an OR-gate with this gate as an input. If that gate doesn't exist, the original AND gate is faulty.
// from: https://www.reddit.com/r/adventofcode/comments/1hla5ql/2024_day_24_part_2_a_guide_on_the_idea_behind_the/
func validateRippleCarryAdderRules(input []string, instMap map[string][][]string) string {
	faulty := []string{}
	for _, line := range input {
		split := strings.Split(line, " ")
		a, gate, b, output := split[0], split[1], split[2], split[4]

		//  If the output of a gate is z, then the operation has to be XOR unless it is the last bit.
		if output[0] == 'z' && gate != "XOR" && output != "z45" {
			faulty = append(faulty, output)
			continue
		}

		// If the output of a gate is not z and the inputs are not x, y then it has to be AND / OR, but not XOR.
		if output[0] != 'z' && a[0] != 'x' && a[0] != 'y' && b[0] != 'x' && b[0] != 'y' && gate == "XOR" {
			faulty = append(faulty, output)
			continue
		}

		// If you have a XOR gate with inputs x, y, there must be another XOR gate with this gate as an input.
		// Search through all gates for an XOR-gate with this gate as an input; if it does not exist, your (original) XOR gate is faulty.
		if gate == "XOR" && ((a[0] == 'x' && b[0] == 'y') || (a[0] == 'y' && b[0] == 'x')) &&
			a != "x00" && b != "x00" && a != "y00" && b != "y00" {
			if _, ok := instMap[output]; !ok {
				faulty = append(faulty, output)
				continue
			}

			isValid := false
			for _, poss := range instMap[output] {
				if poss[1] == "XOR" {
					isValid = true
					break
				}
			}

			if !isValid {
				faulty = append(faulty, output)
				continue
			}
		}

		// if you have an AND-gate, there must be an OR-gate with this gate as an input.
		// If that gate doesn't exist, the original AND gate is faulty.
		if gate == "AND" && ((a[0] == 'x' && b[0] == 'y') || (a[0] == 'y' && b[0] == 'x')) &&
			a != "x00" && b != "x00" && a != "y00" && b != "y00" {
			if _, ok := instMap[output]; !ok {
				faulty = append(faulty, output)
				continue
			}

			isValid := false
			for _, poss := range instMap[output] {
				if poss[1] == "OR" {
					isValid = true
					break
				}
			}

			if !isValid {
				faulty = append(faulty, output)
				continue
			}
		}
	}
	sort.Strings(faulty)
	return strings.Join(faulty, ",")
}

This gives us the answer to part 2! You can find my final code here.

This was a touuuugh day! Forget about part 2, I even got stuck in part 1. Due to some really stupid mistakes I was somehow missing evaluating some of the connections and was getting the wrong answer. After hours of debugging I was finally able to move onto part 2 only to be struck with cluelessness. I’m very grateful for the helpful folks over on Reddit who take the time to write tutorials to explain such tough days. It was fascinating to learn how to debug a faulty Ripple Carry Adder. I find the best days of Advent of Code are the ones I end up learning a tonne from, not just a new algorithm but a few general techniques that can be extended over to my day job.

Quite a lot of folks solved day 2 by visualising the connections and finding the faulty wires manually. How did you solve Day 24? I would love to compare notes and checkout your solution. Reach out to me on TwitterBluesky or on e-mail at contact[at]shraddhaag[dot]dev.