2
\$\begingroup\$

The task involves determining the lowest location number corresponding to a given set of seeds by following numerical mappings for soil, fertilizer, water, light, temperature, humidity, and location.

The almanac (your puzzle input) lists all of the seeds that need to be planted. It also lists what type of soil to use with each kind of seed, what type of fertilizer to use with each kind of soil, what type of water to use with each kind of fertilizer, and so on. Every type of seed, soil, fertilizer and so on is identified with a number, but numbers are reused by each category - that is, soil 123 and fertilizer 123 aren't necessarily related to each other.

For example:

seeds: 79 14 55 13

seed-to-soil map:
50 98 2
52 50 48

soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15

fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4

water-to-light map:
88 18 7
18 25 70

light-to-temperature map:
45 77 23
81 45 19
68 64 13

temperature-to-humidity map:
0 69 1
1 0 69

humidity-to-location map:
60 56 37
56 93 4

The almanac starts by listing which seeds need to be planted: seeds 79, 14, 55, and 13.

The rest of the almanac contains a list of maps which describe how to convert numbers from a source category into numbers in a destination category. That is, the section that starts with seed-to-soil map: describes how to convert a seed number (the source) to a soil number (the destination).

The maps describe entire ranges of numbers that can be converted. Each line within a map contains three numbers: the destination range start, the source range start, and the range length.

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 second line means that the source range starts at 50 and contains 48 values: 50, 51, ..., 96, 97. This corresponds to a destination range starting at 52 and also containing 48 values: 52, 53, ..., 98, 99. So, seed number 53 corresponds to soil number 55.

Any source numbers that aren't mapped correspond to the same destination number. So, seed number 10 corresponds to soil number 10.

So, the entire list of seed numbers and their corresponding soil numbers looks like this:

seed  soil
0     0
1     1
...   ...
48    48
49    49
50    52
51    53
...   ...
96    98
97    99
98    50
99    51

With this map, you can look up the soil number required for each initial seed number:

Seed number 79 corresponds to soil number 81. Seed number 14 corresponds to soil number 14. Seed number 55 corresponds to soil number 57. Seed number 13 corresponds to soil number 13.

The goal is to convert each seed number through these categories until determining its corresponding location number, ultimately identifying the closest location that needs a seed.

In this example, the corresponding types are:

Seed 79, soil 81, fertilizer 81, water 81, light 74, temperature 78, humidity 78, location 82.
Seed 14, soil 14, fertilizer 53, water 49, light 42, temperature 42, humidity 43, location 43.
Seed 55, soil 57, fertilizer 57, water 53, light 46, temperature 82, humidity 82, location 86.
Seed 13, soil 13, fertilizer 52, water 41, light 34, temperature 34, humidity 35, location 35.

So, the lowest location number in this example is 35.

My initial approach - although very inefficient - successfully handled the sample input presented here, but crashed for the larger file provided at the website (EHWPOISON 133 Memory page has hardware error, I was out of resources). But it could still use a review.

#!/usr/bin/env python3

from functools import reduce
from pathlib import Path
from typing import Iterable

import typer


def map_ranges(lines: Iterable[str]) -> dict[int, int]:
    range_map = {}

    for line in lines:
        # We are at the end of the map if there's an empty line.
        if not line.strip():
            break

        dest_range_start, src_range_start, range_len = map(int, line.split())

        for i in range(range_len):
            range_map[src_range_start + i] = dest_range_start + i

    return range_map


def parse_seeds(line: str) -> int:
    # seeds: X Y Z ...
    return {int(i) for i in line.split() if i[0].isdigit()}


def parse_locations(seeds: set[int], maps: dict[str, dict[int, int]]) -> int:
    return {
        reduce(lambda curr, map_: maps[map_].get(curr, curr), maps, seed)
        for seed in seeds
    }


def parse_maps(lines: Iterable[str]) -> dict[str, dict[int, int]]:
    return {
        line.strip(): map_ranges(lines)
        for line in lines
        if any(
            line.startswith(x)
            for x in [
                "seed",
                "soil",
                "fertilizer",
                "water",
                "light",
                "temperature",
                "humidity",
            ]
        )
    }


def lowest_location(lines: Iterable[str]) -> int:
    return min(parse_locations(parse_seeds(lines.readline()), parse_maps(lines)))


def main(almanac_file: Path) -> None:
    with open(almanac_file) as f:
        print(lowest_location(f))


if __name__ == "__main__":
    typer.run(main)

After opting for another algorithm, this new approach didn't hog system resources and works well for both small and large datasets.

#!/usr/bin/env python3

from pathlib import Path
from typing import Iterable

import typer


def map_seeds(seeds: list[int], lines: Iterable[str]) -> list[int]:
    new = seeds.copy()

    for line in lines:
        # We are at the end of the map if there's an empty line.
        if not line.strip():
            break

        dest, src, range_ = map(int, line.split())

        for idx, seed in enumerate(seeds):
            if seed >= src and seed <= (src + range_ - 1):
                new[idx] += dest - src
    return new


def parse_maps(seeds: list[int], lines: Iterable[str]) -> list[int]:
    for line in lines:
        if any(
            line.startswith(x)
            for x in [
                "seed",
                "soil",
                "fertilizer",
                "water",
                "light",
                "temperature",
                "humidity",
            ]
        ):
            seeds = map_seeds(seeds, lines)
    return seeds


def parse_seeds(line: str) -> list[int]:
    # seeds: X Y Z ...
    return [int(i) for i in line.split() if i[0].isdigit()]


def lowest_location(lines: Iterable[str]) -> int:
    return min(parse_maps(parse_seeds(lines.readline()), lines))


def main(almanac_file: Path) -> None:
    with open(almanac_file) as f:
        print(lowest_location(f))


if __name__ == "__main__":
    typer.run(main)


Review Request:

What'd be a better algorithm?

How can parse_maps() be simplified? What are some other simplications?

General coding comments, style, etc.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Algorithmically your code looks fine and there is nothing that has to be changed. There are a few changes I would suggest that could slightly improve performance or be more Pythonic. There are additional suggestions that might not result in faster execution but might make the code marginally clearer (and this is just my opinion; others may differ).

You have a loop in function map_seeds that computes two values that are loop invariant and should ideally be calculated once before entering the loop. map_seeds is called repeatedly.

Only on the first invocation is my_seeds being passed list of seed values; on subsequent calls it is being a passed a list of locations. So calling this function map_seeds, which is passed an argument named seeds, is not really accurate. In general, this function is being passed a list of values that are to be mapped to new values. So a better name for this function is map_values, which is passed an argument named input_values.

I have also changed the name of variables to match more closely the problem description names for these quantities.

Finally, I have modified your check to see whether a value falls within a range of values to be more Pythonic:

...

def map_values(input_values: list[int], lines: Iterable[str]) -> list[int]:
    new_values = input_values.copy()

    for line in lines:
        # We are at the end of the map if there's an empty line.
        if not line.strip():
            break

        # Modified variable names to match problem description names:
        destination_range_start, source_range_start, range_length = map(int, line.split())

        # Calculate these values once:
        source_range_end = source_range_start + range_length - 1
        adjustment = destination_range_start - source_range_start

        for idx, value in enumerate(input_values):
            # A more Pythonic range check:
            if source_range_start <= value <= source_range_end:
                new_values[idx] += adjustment
    return new_values


def parse_maps(seeds: list[int], lines: Iterable[str]) -> list[int]:
    input_values = seeds
    for line in lines:
        if any(
            line.startswith(x)
            for x in [
                "seed",
                "soil",
                "fertilizer",
                "water",
                "light",
                "temperature",
                "humidity",
            ]
        ):
            input_values = map_values(input_values, lines)
    return input_values

...

Further Simplification

If we assume that the input is correct, then we know we have a seeds specification followed by one or more maps separated by an empty line. We don't really care what the names of these maps are. Therefore functions parse_maps and map_values can be combined into a single function, map_seeds, which is appropriately named now because it is only invoked once with a list of seeds to be mapped to locations. Note that I have rewritten parse_seeds and lowest_location to now consistently use the expression next(lines) to fetch the next line. Note that in your code you have specified lines to be of type Iterable[str] but you then proceed to call method lines.readline() but readline is not a method of an iterable type (by using next(lines) instead, we can have lines be, for example, a list of strings).

...

def map_seeds(seeds: list[int], lines: Iterable[str]) -> list[int]:
    input_values = seeds
    try:
        while True:
            next(lines) # Get next map if any
            # Any more lines in the current map?
            new_values = input_values.copy()
            while (line := next(lines).strip()):  # Empty line?
                # Modified variable names to match problem description names:
                destination_range_start, source_range_start, range_length = map(int, line.split())

                # Calculate these values once:
                source_range_end = source_range_start + range_length - 1
                adjustment = destination_range_start - source_range_start

                for idx, value in enumerate(input_values):
                    # A more Pythonic range check:
                    if source_range_start <= value <= source_range_end:
                        new_values[idx] += adjustment
            input_values = new_values
    except StopIteration:
        # No more lines in the input
        return new_values

def parse_seeds(lines: Iterable[str]) -> list[int]:
    line = next(lines)
    next(lines) # Read in following blank line
    return list(map(int, line.split(': ')[1].split()))

def lowest_location(lines: Iterable[str]) -> int:
    return min(map_seeds(parse_seeds(lines), lines))
...
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.