Advent of Code 2024 - Day 24 - Go

   --- 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())
	}

view raw day24.go hosted with ❤ by GitHub

Advent of Code 2024 - Day 19 - Go

  --- Day 19: Linen Layout ---

https://adventofcode.com/2024/day/19

Day 19 - Solution

	package main
	import (
	"bufio"
	"fmt"
	"os"
	"strings"
	)
	func analyzeDesignFormation(availableTowels []string, requested string) (int, bool) {
	n := len(requested)
	combinationCounts := make([]int, n+1) // combinationCounts[i] indicates the number of ways to form requested[:i]
	combinationCounts[0] = 1 // Base case: one way to form an empty string
	// Build the combinationCounts table
	for i := 1; i <= n; i++ {
	for _, towel := range availableTowels {
	towelLen := len(towel)
	if i >= towelLen && requested[i-towelLen:i] == towel {
	combinationCounts[i] += combinationCounts[i-towelLen]
	}
	}
	}
	return combinationCounts[n], combinationCounts[n] > 0 // Return the number of combinations and a boolean indicating if it can be formed
	}
	func main() {
	// Open the input file
	file, err := os.Open("input.txt")
	if err != nil {
	fmt.Printf("Error opening file: %v\n", err)
	return
	}
	defer file.Close()
	// Read the file line by line
	scanner := bufio.NewScanner(file)
	lines := []string{}
	for scanner.Scan() {
	lines = append(lines, scanner.Text())
	}
	if err := scanner.Err(); err != nil {
	fmt.Printf("Error reading file: %v\n", err)
	return
	}
	// Parse the input
	if len(lines) < 2 {
	fmt.Println("Invalid input format: not enough lines")
	return
	}
	// First line: list of available colors
	availableTowels := strings.Split(strings.TrimSpace(lines[0]), ", ")
	// Remaining lines (after the blank line): requested designs
	var requestedTowels []string
	for _, line := range lines[2:] { // Skip the blank line
	line = strings.TrimSpace(line)
	if line != "" {
	requestedTowels = append(requestedTowels, line)
	}
	}
	// Count total number of combinations to form all designs
	totalCombinations := 0
	totalFormable := 0
	for _, towel := range requestedTowels {
	combinations, formable := analyzeDesignFormation(availableTowels, towel)
	totalCombinations += combinations
	if formable {
	totalFormable++
	}
	}
	// Print the total result
	fmt.Printf("Total number of combinations to form all designs: %d\n", totalCombinations)
	fmt.Printf("Total number of designs that can be formed: %d\n", totalFormable)
	}

view raw day19.go hosted with ❤ by GitHub

Advent of Code 2024 - Day 18 - Go

 --- Day 18: RAM Run ---

https://adventofcode.com/2024/day/18

Day 18 - Solution

	package main
	import (
	"fmt"
	"image"
	"os"
	"strings"
	)
	const gridSize = 70
	// Breadth-First Search (BFS)
	func main() {
	// Read and parse input
	obstaclePoints := parseInput("input.txt")
	// Create the grid
	grid := initializeGrid(gridSize)
	// Simulate the process
	for index, obstacle := range obstaclePoints {
	// Mark the obstacle on the grid
	grid[obstacle] = false
	// Check if the target is reachable
	if isTargetReachable(grid, gridSize) {
	if index == 1024 {
	fmt.Printf("Distance to target: %d\n", calculateShortestDistance(grid, gridSize))
	}
	continue
	}
	// Output the obstacle that blocked the target
	fmt.Printf("Blocked by obstacle at: %d,%d\n", obstacle.X, obstacle.Y)
	break
	}
	}
	// parseInput reads the input file and returns a slice of obstacle points
	func parseInput(filename string) []image.Point {
	data, err := os.ReadFile(filename)
	if err != nil {
	panic(fmt.Sprintf("Error reading file: %v", err))
	}
	var obstaclePoints []image.Point
	for _, pointStr := range strings.Fields(string(data)) {
	var x, y int
	fmt.Sscanf(pointStr, "%d,%d", &x, &y)
	obstaclePoints = append(obstaclePoints, image.Point{X: x, Y: y})
	}
	return obstaclePoints
	}
	// initializeGrid creates a grid of the given size, initializing all points as walkable
	func initializeGrid(size int) map[image.Point]bool {
	grid := make(map[image.Point]bool)
	for y := 0; y <= size; y++ {
	for x := 0; x <= size; x++ {
	grid[image.Point{X: x, Y: y}] = true
	}
	}
	return grid
	}
	// isTargetReachable checks if the target (gridSize, gridSize) is reachable
	func isTargetReachable(grid map[image.Point]bool, size int) bool {
	queue := []image.Point{{0, 0}}
	visited := map[image.Point]bool{{0, 0}: true}
	for len(queue) > 0 {
	currentPoint := queue[0]
	queue = queue[1:]
	if currentPoint == (image.Point{X: size, Y: size}) {
	return true
	}
	for _, neighbor := range getNeighbors(currentPoint) {
	if grid[neighbor] && !visited[neighbor] {
	visited[neighbor] = true
	queue = append(queue, neighbor)
	}
	}
	}
	return false
	}
	// calculateShortestDistance calculates the shortest distance to the target (gridSize, gridSize)
	func calculateShortestDistance(grid map[image.Point]bool, size int) int {
	queue := []image.Point{{0, 0}}
	distances := map[image.Point]int{{0, 0}: 0}
	for len(queue) > 0 {
	currentPoint := queue[0]
	queue = queue[1:]
	if currentPoint == (image.Point{X: size, Y: size}) {
	return distances[currentPoint]
	}
	for _, neighbor := range getNeighbors(currentPoint) {
	if grid[neighbor] {
	if _, visited := distances[neighbor]; !visited {
	distances[neighbor] = distances[currentPoint] + 1
	queue = append(queue, neighbor)
	}
	}
	}
	}
	return -1 // Return -1 if the target is unreachable
	}
	// getNeighbors returns the neighboring points of a given point
	func getNeighbors(point image.Point) []image.Point {
	return []image.Point{
	{X: point.X, Y: point.Y - 1}, // Up
	{X: point.X + 1, Y: point.Y}, // Right
	{X: point.X, Y: point.Y + 1}, // Down
	{X: point.X - 1, Y: point.Y}, // Left
	}
	}

view raw main.go hosted with ❤ by GitHub