#!/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()
Display More