Day 1: Historian Hysteria

The first task, together with the introduction to this year’s quest, is described on the Advent of Code 2024 website. This year, our mission is to assist the Elves in locating the Chief Historian

Last year, I used ChatGPT to generate custom illustrations to visualize the task descriptions, which added a fun, creative touch. However, this year presented a greater challenge: it was tricky to produce an image that aligned with my vision using tools like ChatGPT/DALL-E or Gemini/Imagen 3. After some experimentation, I discovered that by selectively erasing parts of the image, I could guide the model to create something closer to what I had in mind.

Part 1: Sum of differences

The task is to calculate the sum of the absolute differences between two lists of numbers, each sorted in ascending order. Here’s the step-by-step breakdown:

1. We are given two lists of numbers separated by a space on each line.
   
2. First, sort both lists in ascending order.
   
3. Pair corresponding elements from the sorted lists.
   
4. Calculate the absolute difference for each pair.
   
5. Sum all these differences to get the answer.

For example, given input:

3   4
4   3
2   5
1   3
3   9
3   3

We need to sort the lists first:

Left:  [1, 2, 3, 3, 3, 4]
Right: [3, 3, 3, 4, 5, 9]

Then, pair the corresponding elements and compute the differences:

|1 - 3| = 2
|2 - 3| = 1
|3 - 3| = 0
|3 - 4| = 1
|3 - 5| = 2
|4 - 9| = 5

And finally, add up the differences:

2 + 1 + 0 + 1 + 2 + 5 = 11

The final answer for this example is 11.

Save example input to a variable

To help test the execution, I will save example input to a variable.

example_input = """
3   4
4   3
2   5
1   3
3   9
3   3
"""

The first part, and the first task all together are the warmup tasks – relatively easy and quick! To solve it, I will:

• Read the inputs into two sorted lists
• Calculate and sum the differences

Let’s start by reading the inputs.

import os

def read_input(input_source):
    """Read input from a file path or a string of lines."""
    if os.path.isfile(input_source):
        with open(input_source, "r") as f:
            lines = f.readlines()
    else:
        lines = input_source.strip().split("\n")

    left, right = zip(
        *(map(int, line.split()) for line in lines if line.strip())
    )

    return left, right


read_input(example_input)

((3, 4, 2, 1, 3, 3), (4, 3, 5, 3, 9, 3))

Helper function to verify the answer

I will create a helper function to verify the answer and print nice message.

def verify_answer(f, expected_answer, example_input=example_input):
    """Verify the answer"""
    result = f(example_input)
    if result == expected_answer:
        print(f"✔️ That's right! The answer is {expected_answer}.")
    else:
        print(f"❌ Expected {expected_answer}, but got {result}.")

And then, I will calculate the sum of differences.

def part_one(input_source):
    """Get the answer to the first part, i.e. the sum of the absolute
    differences between two sorted lists."""
    left, right = read_input(input_source)
    return sum(abs(l - r) for l, r in zip(sorted(left), sorted(right)))

verify_answer(part_one, 11)

✔️ That's right! The answer is 11.

%time
part_one("../inputs/day_01.txt")

CPU times: user 1 μs, sys: 0 ns, total: 1 μs
Wall time: 4.05 μs

2430334

That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.

Part 2: Weighted sum of common elements

In this part, we calculate a weighted sum based on the frequency of each number from the left list in the right list. Here’s the step-by-step process:

1. Count how many times each number from the left list appears in the right list.
   
2. Multiply each number from the left list by its count in the right list.
   
3. Sum up all these products to get the answer.

Here’s an example – given input:

3   4
4   3
2   5
1   3
3   9
3   3

First, we need to count how many times each number in the left list appears in the right list:

• 3 appears 3 times in the right list.
  
• 4 appears 1 time in the right list.
  
• 2 and 1 do not appear in the right list.

Then, for each number in the left list, multiply it by its count from the right list:

• For 3: 3 * 3 = 9
  
• For 4: 4 * 1 = 4
  
• For 2: 2 * 0 = 0
  
• For 1: 1 * 0 = 0
  
• Repeat this for each occurrence of 3 in the left list.

And finally, add all the products together:

9 + 4 + 0 + 0 + 9 + 9 = 31

The total weighted sum is 31.

In the answer, I will re-use reading the inputs from part one and I will use the Counter class from the collections module to count the occurrences of each number from the left list in the right list. Then, I will calculate the weighted sum.

from collections import Counter

def part_two(input_source):
    """
    Get the answer to the second part, i.e., the sum of the product of
    the number and the number of times it appears in the right list.
    """
    left, right = read_input(input_source)

    # Count occurrences in both lists
    left_counts = Counter(left)
    right_counts = Counter(right)

    # 
    total = sum(
        left_counts[key] * right_counts[key] * key
        for key in left_counts
        if key in right_counts
    )

    return total


verify_answer(part_two, 31)

✔️ That's right! The answer is 31.

Replacing collections.Counter with a custom function

If I would want to limit the use of any libraries, I would write a function that counts the occurrences of each element in the list.

def count_occurrences(input_list: list) -> dict:
    """Counts occurrences of each element in the list."""
    counts = {}
    for num in input_list:
        counts[num] = counts.get(num, 0) + 1
    return counts

%time
part_two("../inputs/day_01.txt")

CPU times: user 1 μs, sys: 0 ns, total: 1 μs
Wall time: 2.86 μs

28786472

That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.

Bonus Bash solutions

I wanted to see how the same problems can be solved in Bash. The full script is available in the Day01.sh file in the repository. Here’s a brief overview of the Bash solutions:

Part 1

In part 1, I sort both lists, merge them, calculate the absolute differences, and sum them up.

part_one() {
  local input_file=$1
  paste \
    <(tr -s ' ' <"${input_file}" | cut -f1 -d' ' | sort) \
    <(tr -s ' ' <"${input_file}" | cut -f2 -d' ' | sort) |
    awk -v FS=" " 'function abs(x) {
      return ((x < 0.0) ? -x : x)
    } {print abs($1 - $2)}' |
    paste -sd+ - |
    bc
}

I am using paste to merge the two sorted lists, awk to calculate the absolute differences, and bc to sum them up.

Part 2

The second part is a bit more complex, as it requires counting the occurrences of each number in the right list. Here’s the Bash solution for part two:

part_two() {
  local input_file=$1
  join -j 1 \
    <(tr -s ' ' <"${input_file}" | cut -f1 -d' ' | sort | uniq -c |
      tr -s ' ' | awk '{print $2, $1}') \
    <(tr -s ' ' <"${input_file}" | cut -f2 -d' ' | sort | uniq -c |
      tr -s ' ' | awk '{print $2, $1}') |
    awk '{printf $1 "*" $2 "*" $3 "+"} END {print "0"}' |
    bc
}

Here, I use:

• uniq -c which counts the occurrences of each number in both lists,
  
• join which combines the left and right lists by their numbers,
  
• with awk I formats the weighted sum equation as num * left_count * right_count,
  
• and finally, I use bc to evaluate the final equation.

In the script I also added functions to check the answers and print them with cowsay for some extra flavor. Like this:

  _                 
 |_) _. ._ _|_   /| 
 |  (_| |   |_    | 
                    
 _______________________________ 
< Part 1 - example test passed! >
 ------------------------------- 
   \
    \
        .--.
       |o_o |
       |:_/ |
      //   \ \
     (|     | )
    /'\_   _/`\
    \___)=(___/

 ___________________________ 
< Part 1 answer is: 2430334 >
 --------------------------- 
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||