Advent of Code 2023, Day 5

❄️ Back to Advent of Code 2023 solutions homepage ❄️

# Imports
from aoc23.utils import read_input
import numpy as np
import time

input_5 = read_input(5)

Part 1

The first part of the Day 5 puzzle gives a collection of seeds, along with a series of maps. These map from the seed numbers to the soil numbers, the soil numbers to the fertiliser numbers, and so on, mapping finally to the location numbers. These maps are specified by three numbers $(s, l, r)$ - the source number, location number, and a range. This excerpt gives description of how these numbers are to be converted into a complete map:

Consider again the example seed-to-soil map:

50 98 2

52 50 48

The first line has a destination range start of 50, a source range start of 98, and a range length of 2. This line means that the source range starts at 98 and contains two values: 98 and 99. The destination range is the same length, but it starts at 50, so its two values are 50 and 51. With this information, you know that seed number 98 corresponds to soil number 50 and that seed number 99 corresponds to soil number 51.

The first job is to convert the input into a more useful format. Let’s create seeds (a list of the seed numbers) and maps (a dict where the keys are the map names, and the values are lists of three numbers determining the mapping):

def process_input_5(input_5: list[str]):
    # Extract seeds from the first line of the file
    seeds = input_5[0].split(':')[1].split()
    seeds = [int(seed) for seed in seeds]
    
    maps = {}
    value = []
    
    for line in input_5[2:]:
        if line == '':
            # Line between maps
            maps[key] = value
            value = []
            
        elif ':' in line:
            # Start of new map
            key = line.split()[0]
            
        else:
            # Map values
            value.append([int(x) for x in line.split()])
    
    # No empty string after last map value, so update maps
    maps[key] = value
    
    return seeds, maps

seeds, maps = process_input_5(input_5)

We could create the dictionary for the entire range of seed values, by constructing each of the intermediate maps in their entirety. But this sounds like too much work - after all, we only care about the seeds in the provided list seeds. So instead, given a seed number $n$, we just need to follow it from map to map until we get to a final location. This isn’t too tricky - given a seed number, loop over each of the ranges in the seed-to-soil map, checking if it is in the range $[s, s+r)$; if so, compute the corresponding destination number as $d+s-n$.

def seed_location(seed_idx: int, maps: dict[str, list[list[int]]]) -> int:

    for key in maps:
        map_ranges = maps[key]
        
        for destination, source, n in map_ranges:
            if source <= seed_idx < source + n:
                seed_idx = destination + seed_idx - source
                break
    
    return seed_idx

For example, the location of the first seed is given by:

seed_location(seeds[0], maps)

860904829

And the minimum location across all the seeds is

min([seed_location(seed, maps) for seed in seeds])

579439039

So the part 1 answer is: 579439039.

Part 2

It turns out that seed isn’t a list of seed numbers, but a list of $(seed, range)$ pairs - so all the seeds between $seed$ and $seed + range$ are valid seeds. This information can be used to reshape the seeds list into an array called seed_pairs:

seed_pairs = np.reshape(seeds, (int(len(seeds)/2), 2))

seed_pairs[0]

array([1514493331,  295250933], dtype=int64)

From this, we can see that we now have a huge number of valid seeds now - more than 1 billion:

seed_pairs[:, 1].sum()

1638141121

It is clearly not feasible to check all the valid seeds to find the minimum location value. Instead, note that the way in which the maps are defined makes it easy to create an inverse mapping - all we need to do is invert the source and destination numbers in each of the maps: \(\text{map}[(s, f, n)] \rightarrow \text{map}[(f, s, n)]\)

By doing this inversion, and by reversing the order in which the maps are processed (from location to seed, instead of seed to location), the reverse map can be constructed explicitly:

reversed_keys = list(maps.keys())[::-1]
reversed_maps = {key: [[v[1], v[0], v[2]] for v in maps[key]] for key in reversed_keys}

Just to check this:

assert seed_location(seed_location(111111111, reversed_maps), maps) == 111111111
assert seed_location(seed_location(3141592, reversed_maps), maps) == 3141592
assert seed_location(seed_location(271828182, reversed_maps), maps) == 271828182

This provides a way of computing seeds from locations. And so, to find the minimum valid location, we can work up from 0 until we find a location where the corresponding seed is in our original list. The following helper function checks if a given seed is valid (i.e. belongs to one of the ranges defined by seed_pairs):

def is_valid_seed(candidate: int, seed_pairs: np.ndarray) -> bool:
    for lower, n in seed_pairs:
        if lower <= candidate < lower + n:
            return True
    return False

And the search begins…

start_time = time.time()

for i in range(10_000_000):
    candidate = seed_location(i, reversed_maps)
    if is_valid_seed(candidate, seed_pairs):
        print(f'Found one! location = {i}, candidate = {candidate}')
        break
        
end_time = time.time()
print(f'{(end_time - start_time) // 60} minutes, {(end_time - start_time) % 60} seconds')

Found one! location = 7873084, candidate = 665347394
8.0 minutes, 13.60687804222107 seconds

In just over 8 minutes, we found a solution - let’s double check that it makes sense:

assert seed_location(665347394, maps) == 7873084
assert seed_location(7873084, reversed_maps) == 665347394
assert is_valid_seed(665347394, seed_pairs)

And so the answer to part 2 is 7,873,084, with original seed 665,347,394.

❄️ Back to Advent of Code 2023 solutions homepage ❄️