Advent of Code Day 1: Historian Hysteria – A Deep Dive into My Solution

Day One

Advent of Code is a thrilling time of the year for coding enthusiasts, blending festive puzzles with challenging algorithms. Day 1 of 2024, titled “Historian Hysteria,” tasked us with reconciling two lists of location IDs and analysing their relationships. Here’s a detailed walkthrough of the challenge and my Go solution.

Understanding the Problem

The puzzle had two parts:

  1. Part One:
    Given two lists of integers, calculate the total “distance” between them. The smallest number in the first list is paired with the smallest in the second list, and so on, with the distance defined as the absolute difference. The goal was to sum all these distances.
  2. Part Two:
    Instead of calculating distances, determine how many times each number from the first list appears in the second list. Multiply the number by its occurrence count and sum these values for a “similarity score.”

Solution Overview

My Go solution processes the lists efficiently by leveraging sorting and hash maps. Here’s a breakdown of the approach:

Step 1: Input Handling

The input is read from a file containing pairs of integers. I used bufio.Scanner for efficient line-by-line parsing:

func readInputFile(fileName string) ([]string, error) {
    file, err := os.Open(fileName)
    if err != nil {
        return nil, err
    }
    defer file.Close()

    var lines []string
    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        lines = append(lines, scanner.Text())
    }
    return lines, scanner.Err()
}

This function loads the input into memory as a slice of strings.

Step 2: Parsing the Input

Each line contains two integers. I parsed these into two separate slices:

for i, v := range inputLines {
    _, err := fmt.Sscanf(v, "%d %d", &listOne[i], &listTwo[i])
    if err != nil {
        return
    }
}

Step 3: Part One – Calculate Distance

To minimize distances between pairs:

  1. Sort both lists.
  2. Pair the numbers by index and compute the absolute differences.
  3. Sum up all differences.
func CalculateMinDifferenceSum(listOne, listTwo []int) float64 {
    if !sort.IntsAreSorted(listOne) {
        sort.Ints(listOne)
    }
    if !sort.IntsAreSorted(listTwo) {
        sort.Ints(listTwo)
    }

    var results float64
    for i := 0; i < len(listOne); i++ {
        results += math.Abs(float64(listOne[i] - listTwo[i]))
    }
    return results
}

Sorting ensures minimal pairwise differences, and the use of math.Abs simplifies distance calculation.

Step 4: Part Two – Calculate Similarity Score

To calculate the similarity score:

  1. Build a frequency map for the second list.
  2. For each number in the first list, look up its count in the second list and compute the contribution to the score.
func CalculateSumWithOccurrences(listOne, listTwo []int) int {
    listTwoMap := make(map[int]int)
    for _, v := range listTwo {
        listTwoMap[v]++
    }

    var results int
    for _, v := range listOne {
        results += listTwoMap[v] * v
    }
    return results
}

This approach ensures efficiency by using a map for O(1) lookups.

Efficiency Analysis

  1. Time Complexity:
  • Sorting both lists: (O(n \log n))
  • Calculating distances or building the map and summing scores: (O(n))
    Total: (O(n \log n)).
  1. Space Complexity:
  • Two input lists and a frequency map: (O(n)).

Results

After running the solution on the provided input:

  • Part One Result: 1646452
  • Part Two Result: 23609874

These results are printed to the console:

fmt.Println("Part One Result:", CalculateMinDifferenceSum(listOne, listTwo))
fmt.Println("Part Two Result:", CalculateSumWithOccurrences(listOne, listTwo))

Key Learnings

  1. Sorting for Minimal Differences: Sorting both lists ensured that pairwise differences were minimized.
  2. Using Maps for Quick Lookups: A frequency map allowed for efficient calculation of the similarity score in Part Two.
  3. Modular Design: Each task (e.g., input parsing, sorting, distance calculation) was broken into functions for clarity and reusability.

Conclusion

Day 1 of Advent of Code 2024 was a fantastic challenge that tested problem decomposition and algorithm optimization. By leveraging Go’s efficient libraries and data structures, we arrived at an elegant and performant solution. Advent of Code continues to be a delightful way to hone problem-solving skills while celebrating the holiday spirit!

Leave a comment