Posts by __blackjack__

#!/usr/bin/env python3
import sys

from attr import attrib, attrs
from more_itertools import chunked, split_at
from parse import parse

EXAMPLE_LINES = """\
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
""".splitlines()


@attrs(frozen=True)
class Range:
    """
    >>> Range(2)
    Range(start=2, end=2)
    >>> r = Range(23, 42)
    >>> r
    Range(start=23, end=42)
    >>> len(r)
    20

    The end points are included (unlike the built-in `range()`):

    >>> 3 in r
    False
    >>> 23 in r
    True
    >>> 42 in r
    True
    >>> 43 in r
    False
    """

    start = attrib()
    end = attrib()

    @end.default
    def _end_factory(self):
        return self.start

    def __len__(self):
        return self.end - self.start + 1

    def __contains__(self, number):
        return self.start <= number <= self.end

    @classmethod
    def from_start_and_length(cls, start, length):
        """
        >>> Range.from_start_and_length(79, 14)
        Range(start=79, end=92)
        """
        return cls(start, start + length - 1)


@attrs(frozen=True)
class RangeMap:
    """
    >>> map_ = RangeMap.from_starts_and_length(3, 7, 11)
    >>> map_
    RangeMap(source=Range(start=3, end=13), destination=Range(start=7, end=17))

    Check if an input number can be mapped by this `RangeMap`:

    >>> 0 in map_, 3 in map_, 13 in map_, 14 in map_
    (False, True, True, False)

    Numbers outside the source range are mapped to `None`:

    >>> map_[0], map_[3], map_[13], map_[14]
    (None, 7, 17, None)
    """

    source = attrib()
    destination = attrib()

    def __attrs_post_init__(self):
        if len(self.source) != len(self.destination):
            raise ValueError(
                f"{self.source!r} and {self.destination!r}"
                f" must have the same length"
                f" ({len(self.source)} != {len(self.destination)})"
            )

    def __contains__(self, number):
        return number in self.source

    def __getitem__(self, number):
        if number in self:
            return number - self.source.start + self.destination.start

        return None

    def map(self, range_):
        """
        Map a given `Range` to a tuple of mapped ranges and remaining unmapped
        parts of the given `Range`.

        >>> map_ = RangeMap.from_starts_and_length(5, 105, 11)
        >>> map_
        RangeMap(source=Range(start=5, end=15), destination=Range(start=105, end=115))

        Mapping a range that is outside of this `RangeMap` returns no mapped
        ranges and the original range:

        >>> map_.map(Range(0, 4))
        ([], [Range(start=0, end=4)])

        Mapping ranges that are complete within this `RangeMap` leave no
        remaining ranges:

        >>> map_.map(Range(7, 13))
        ([Range(start=107, end=113)], [])
        >>> map_.map(Range(5, 15))
        ([Range(start=105, end=115)], [])

        Mapping a range that overlaps the start *or* beginning return the mapped
        overlapping part and the unmapped remaining part:

        >>> map_.map(Range(3, 7))
        ([Range(start=105, end=107)], [Range(start=3, end=4)])
        >>> map_.map(Range(10, 20))
        ([Range(start=110, end=115)], [Range(start=16, end=20)])

        Finally mapping a range that encloses the `RangeMap` returns the mapped
        middle part, and the remaining unmapped parts bevor and after:

        >>> map_.map(Range(0, 20))
        ([Range(start=105, end=115)], [Range(start=0, end=4), Range(start=16, end=20)])
        """
        start = self[range_.start]
        end = self[range_.end]
        if start is None and end is None:
            if (
                range_.start < self.source.start
                and range_.end > self.source.end
            ):
                return (
                    [self.destination],
                    [
                        Range(range_.start, self.source.start - 1),
                        Range(self.source.end + 1, range_.end),
                    ],
                )
            else:
                return ([], [range_])
        elif start is None:
            return (
                [Range(self.destination.start, end)],
                [Range(range_.start, self.source.start - 1)],
            )
        elif end is None:
            return (
                [Range(start, self.destination.end)],
                [Range(self.source.end + 1, range_.end)],
            )
        else:
            return ([Range(start, end)], [])

    @classmethod
    def from_starts_and_length(cls, source_start, destination_start, length):
        return cls(
            Range.from_start_and_length(source_start, length),
            Range.from_start_and_length(destination_start, length),
        )

    @classmethod
    def parse(cls, text):
        """
        >>> RangeMap.parse("10 20 7")
        RangeMap(source=Range(start=20, end=26), destination=Range(start=10, end=16))
        """
        destination_start, source_start, length = map(int, text.split())
        return cls.from_starts_and_length(
            source_start, destination_start, length
        )


@attrs(frozen=True)
class Map:
    """
    >>> map_ = Map("seed",
    ...            "soil",
    ...            [RangeMap.from_starts_and_length(98, 50, 2),
    ...             RangeMap.from_starts_and_length(50, 52, 48)])
    >>> ranges = list(map(Range, [79, 14, 55, 13]))
    >>> [[range_.start for range_ in map_[source_range]]
    ...  for source_range in ranges]
    [[81], [14], [57], [13]]

    >>> map_[Range(79)]
    [Range(start=81, end=81)]
    >>> map_[Range.from_start_and_length(79, 14)]
    [Range(start=81, end=94)]
    """

    #
    # The two names are not really needed but make debugging easier and adding a
    # rountrip back to source at least possible.
    #
    source_name = attrib()
    destination_name = attrib()
    range_maps = attrib()

    def __getitem__(self, range_):
        result = []
        sources = [range_]
        for range_map in self.range_maps:
            next_sources = []
            for source_range in sources:
                mapped_ranges, remaining_ranges = range_map.map(source_range)
                result.extend(mapped_ranges)
                next_sources.extend(remaining_ranges)
            sources = next_sources
            if not sources:
                break

        result.extend(sources)
        return result

    @classmethod
    def parse_lines(cls, lines):
        lines = iter(lines)
        source_name, destination_name = parse("{}-to-{} map:", next(lines))
        return cls(
            source_name, destination_name, list(map(RangeMap.parse, lines))
        )


@attrs(frozen=True)
class Almanach:
    seed_ranges = attrib()
    maps = attrib()

    def get_revised(self):
        """
        >>> almanach = Almanach.parse_lines(EXAMPLE_LINES).get_revised()
        >>> almanach.seed_ranges
        [Range(start=79, end=92), Range(start=55, end=67)]
        >>> almanach.get_min_location()
        46
        """
        if not all(len(range_) == 1 for range_ in self.seed_ranges):
            raise ValueError("can't be revised")

        return Almanach(
            [
                Range.from_start_and_length(start.start, end.start)
                for start, end in chunked(self.seed_ranges, 2, strict=True)
            ],
            self.maps,
        )

    def get_location_ranges(self, seed_range):
        """
        >>> almanach = Almanach.parse_lines(EXAMPLE_LINES)

        >>> almanach.get_location_ranges(Range(79))
        [Range(start=82, end=82)]

        >>> almanach.get_location_ranges(Range(79, 92))
        [Range(start=60, end=60), Range(start=46, end=55), Range(start=82, end=84)]
        """
        ranges = [seed_range]
        for map_ in self.maps:
            next_ranges = []
            for range_ in ranges:
                next_ranges.extend(map_[range_])
            ranges = next_ranges

        return ranges

    def iter_location_ranges(self):
        """
        >>> almanach = Almanach.parse_lines(EXAMPLE_LINES)

        >>> ranges = list(almanach.iter_location_ranges())
        >>> all(len(range_) == 1 for range_ in ranges)
        True
        >>> [range_.start for range_ in ranges]
        [82, 43, 86, 35]

        >>> from attr import astuple
        >>> list(map(astuple, almanach.get_revised().iter_location_ranges()))
        [(60, 60), (46, 55), (82, 84), (86, 89), (94, 96), (56, 59), (97, 98)]
        """
        for ranges in map(self.get_location_ranges, self.seed_ranges):
            yield from ranges

    def get_min_location(self):
        """
        >>> almanach = Almanach.parse_lines(EXAMPLE_LINES)
        >>> almanach.get_min_location()
        35
        >>> almanach.get_revised().get_min_location()
        46
        """
        return min(self.iter_location_ranges()).start

    @classmethod
    def parse_lines(cls, lines):
        lines = (line.rstrip() for line in lines)
        line_blocks = split_at(lines, lambda line: line == "")
        seed_ranges = [
            Range(int(text))
            for text in parse("seeds: {}", next(line_blocks)[0])[0].split()
        ]
        return cls(seed_ranges, list(map(Map.parse_lines, line_blocks)))


def main():
    almanach = Almanach.parse_lines(sys.stdin)
    print(almanach.get_min_location())
    print(almanach.get_revised().get_min_location())


if __name__ == "__main__":
    main()

#!/usr/bin/env python3
import sys
from itertools import groupby

from attr import attrib, attrs

EXAMPLE_LINES = """\
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
""".splitlines()


@attrs(frozen=True)
class Item:
    value = attrib()
    coordinate = attrib()

    def __len__(self):
        return len(self.value)

    def __int__(self):
        return int(self.value)

    @property
    def x(self):
        return self.coordinate[0]

    @property
    def y(self):
        return self.coordinate[1]

    @property
    def coordinates(self):
        return ((self.x + i, self.y) for i in range(len(self)))

    @property
    def surrounding_coordinates(self):
        yield from (
            (self.x + d_x, self.y + d_y)
            for d_y in [-1, 1]
            for d_x in range(-1, len(self) + 1)
        )
        yield (self.x - 1, self.y)
        yield (self.x + len(self), self.y)

    def is_empty(self):
        return self.value == "."

    def is_number(self):
        return self.value.isdigit()

    def is_symbol(self):
        return not (self.is_empty() or self.is_number())

    def extended(self, items):
        return Item(
            self.value + "".join(item.value for item in items), self.coordinate
        )


@attrs(frozen=True)
class Schematic:
    items = attrib()
    coordinate_to_number = attrib()
    coordinate_to_symbol = attrib()

    def has_adjacent_symbol(self, item):
        return any(
            map(self.coordinate_to_symbol.get, item.surrounding_coordinates)
        )

    def get_adjacent_numbers(self, item):
        return set(
            map(self.coordinate_to_number.get, item.surrounding_coordinates)
        ) - {None}

    @classmethod
    def from_items(cls, items):
        items = list(items)
        coordinate_to_number = {}
        coordinate_to_symbol = {}
        for item in items:
            for coordinate in item.coordinates:
                if item.is_number():
                    coordinate_to_number[coordinate] = item
                elif item.is_symbol():
                    coordinate_to_symbol[coordinate] = item
                else:
                    assert item.is_empty(), repr(Item)

        return cls(items, coordinate_to_number, coordinate_to_symbol)


def parse_items(lines):
    return (
        Item(character, (x, y))
        for y, line in enumerate(lines)
        for x, character in enumerate(line.rstrip())
    )


def group_and_filter_items(items):
    for (_, is_number), group in groupby(
        items, lambda item: (item.y, item.is_number())
    ):
        if is_number:
            yield next(group, None).extended(group)
        else:
            yield from (item for item in group if not item.is_empty())


def parse_lines(lines):
    return Schematic.from_items(group_and_filter_items(parse_items(lines)))


def sum_part_numbers(schematic):
    """
    >>> sum_part_numbers(parse_lines(EXAMPLE_LINES))
    4361
    """
    return sum(
        int(item)
        for item in schematic.items
        if item.is_number() and schematic.has_adjacent_symbol(item)
    )


def sum_gear_ratios(schematic):
    """
    >>> sum_gear_ratios(parse_lines(EXAMPLE_LINES))
    467835
    """
    candidates = (
        list(schematic.get_adjacent_numbers(item))
        for item in schematic.items
        if item.value == "*"
    )
    return sum(
        int(candidate[0]) * int(candidate[1])
        for candidate in candidates
        if len(candidate) == 2
    )


def main():
    schematic = parse_lines(sys.stdin)
    print(sum_part_numbers(schematic))
    print(sum_gear_ratios(schematic))


if __name__ == "__main__":
    main()