--- Day 24: Crossed Wires ---
https://adventofcode.com/2024/day/24
Day 24 - Solution
package main | |
import ( | |
"bufio" | |
"fmt" | |
"os" | |
"regexp" | |
"sort" | |
"strconv" | |
"strings" | |
) | |
type CircuitState map[string]int | |
const ( | |
AND = "AND" | |
OR = "OR" | |
XOR = "XOR" | |
) | |
// parseCircuitInstructions reads the input file and splits it into gate definitions and connection instructions. | |
func parseCircuitInstructions() [][]string { | |
file, err := os.Open("input.txt") | |
if err != nil { | |
panic(err) | |
} | |
defer file.Close() | |
scanner := bufio.NewScanner(file) | |
var sections [][]string | |
currentSection := "" | |
for scanner.Scan() { | |
line := scanner.Text() | |
if line == "" { | |
sections = append(sections, strings.Split(strings.TrimSpace(currentSection), "\n")) | |
currentSection = "" | |
} else { | |
currentSection += line + "\n" | |
} | |
} | |
if currentSection != "" { | |
sections = append(sections, strings.Split(strings.TrimSpace(currentSection), "\n")) | |
} | |
return sections | |
} | |
// initializeCircuitState initializes the circuit state from the gate definitions. | |
func initializeCircuitState(gateDefinitions []string) CircuitState { | |
state := make(CircuitState) | |
for _, gateDefinition := range gateDefinitions { | |
parts := strings.Split(gateDefinition, ": ") | |
value, _ := strconv.Atoi(parts[1]) | |
state[parts[0]] = value | |
} | |
return state | |
} | |
// processGateInstruction processes a single gate instruction and updates the state if possible. | |
func processGateInstruction(instruction string, state CircuitState, gateRegex *regexp.Regexp) bool { | |
match := gateRegex.FindStringSubmatch(instruction) | |
if match != nil { | |
input1, operator, input2, outputGate := match[1], match[2], match[3], match[4] | |
input1Value, input1Exists := state[input1] | |
input2Value, input2Exists := state[input2] | |
// Skip this instruction if either input gate value is not yet computed. | |
if !input1Exists || !input2Exists { | |
return false | |
} | |
// Compute the output gate value based on the operator. | |
switch operator { | |
case AND: | |
state[outputGate] = input1Value & input2Value | |
case OR: | |
state[outputGate] = input1Value | input2Value | |
case XOR: | |
state[outputGate] = input1Value ^ input2Value | |
} | |
return true | |
} | |
return false | |
} | |
// simulateCircuit simulates the circuit and computes the final gate states. | |
func simulateCircuit(sections [][]string) CircuitState { | |
state := initializeCircuitState(sections[0]) | |
gateRegex := regexp.MustCompile(`^(.*) (AND|OR|XOR) (.*) -> (.*)$`) | |
remainingInstructions := make([]string, 0) | |
remainingInstructions = append(remainingInstructions, sections[1]...) | |
for len(remainingInstructions) > 0 { | |
nextRemainingInstructions := make([]string, 0) | |
for _, instruction := range remainingInstructions { | |
if !processGateInstruction(instruction, state, gateRegex) { | |
nextRemainingInstructions = append(nextRemainingInstructions, instruction) | |
} | |
} | |
remainingInstructions = nextRemainingInstructions | |
} | |
return state | |
} | |
// calculateGateValueFromZWires computes a decimal number based on the binary values of gates with IDs starting with "z". | |
func calculateGateValueFromZWires() int { | |
sections := parseCircuitInstructions() | |
finalState := simulateCircuit(sections) | |
// Collect and sort gate IDs starting with "z". | |
var zGateKeys []string | |
for gateID := range finalState { | |
if strings.HasPrefix(gateID, "z") { | |
zGateKeys = append(zGateKeys, gateID) | |
} | |
} | |
sort.Slice(zGateKeys, func(i, j int) bool { | |
return zGateKeys[i] > zGateKeys[j] | |
}) | |
// Concatenate binary values of sorted gates. | |
var binaryBuilder strings.Builder | |
for _, gateKey := range zGateKeys { | |
binaryBuilder.WriteString(strconv.Itoa(finalState[gateKey])) | |
} | |
// Convert the concatenated binary string to a decimal number. | |
binaryString := binaryBuilder.String() | |
result, _ := strconv.ParseInt(binaryString, 2, 64) | |
return int(result) | |
} | |
// findGate searches for a connection matching the given inputs and operator. | |
func findGate(a, b, operator string, instructions []string) string { | |
for _, instruction := range instructions { | |
if strings.HasPrefix(instruction, fmt.Sprintf("%s %s %s", a, operator, b)) || | |
strings.HasPrefix(instruction, fmt.Sprintf("%s %s %s", b, operator, a)) { | |
parts := strings.Split(instruction, " -> ") | |
return parts[len(parts)-1] | |
} | |
} | |
return "" | |
} | |
// analyzeGateConnections processes gate connections to diagnose and repair the malfunctioning circuit. | |
func analyzeGateConnections() string { | |
data := parseCircuitInstructions() | |
instructions := data[1] | |
var swappedConnections []string | |
var previousCarry string | |
// Helper to swap and append gates when a "z" prefix condition is met | |
swapAndTrack := func(a, b string) (string, string) { | |
if strings.HasPrefix(a, "z") { | |
a, b = b, a | |
swappedConnections = append(swappedConnections, a, b) | |
} | |
return a, b | |
} | |
for i := 0; i < 45; i++ { | |
n := fmt.Sprintf("%02d", i) | |
var sumGate, carryGate, andGate, xorGate, nextCarry string | |
// Half adder logic for the circuit | |
sumGate = findGate("x"+n, "y"+n, "XOR", instructions) | |
carryGate = findGate("x"+n, "y"+n, "AND", instructions) | |
if previousCarry != "" { | |
andGate = findGate(previousCarry, sumGate, "AND", instructions) | |
if andGate == "" { | |
// Swap logic if the AND connection is missing | |
sumGate, carryGate = carryGate, sumGate | |
swappedConnections = append(swappedConnections, sumGate, carryGate) | |
andGate = findGate(previousCarry, sumGate, "AND", instructions) | |
} | |
xorGate = findGate(previousCarry, sumGate, "XOR", instructions) | |
// Ensure the gates are in the correct order with respect to "z" prefix | |
sumGate, xorGate = swapAndTrack(sumGate, xorGate) | |
carryGate, xorGate = swapAndTrack(carryGate, xorGate) | |
andGate, xorGate = swapAndTrack(andGate, xorGate) | |
nextCarry = findGate(andGate, carryGate, "OR", instructions) | |
} | |
// Final swap check for next carry gate | |
if strings.HasPrefix(nextCarry, "z") && nextCarry != "z45" { | |
nextCarry, xorGate = swapAndTrack(nextCarry, xorGate) | |
} | |
// Update the carry for the next iteration | |
if previousCarry == "" { | |
previousCarry = carryGate | |
} else { | |
previousCarry = nextCarry | |
} | |
} | |
// Sort and join swapped gates | |
sort.Strings(swappedConnections) | |
return strings.Join(swappedConnections, ",") | |
} | |
func main() { | |
fmt.Println("Part 1: Decimal value from z gates:", calculateGateValueFromZWires()) | |
fmt.Println("Part 2: Analyzed gate connections:", analyzeGateConnections()) | |
} |