Tag 6 liess sich ja einfach „brute forcen“. Teil 1 problemlos und bei Teil 2 rechnet mein nicht mehr so aktueller Büro-Rechner ein paar Sekunden. Aber das wird sicher nicht auf dem VIC-20 funktionieren, also muss ich da wohl noch mal ein bisschen Nachdenken was man da machen kann.
Folgendes kleines BASIC-Programm druckt was aus (auf Epson kompatiblen 9-Nadel-Druckern (IBM-Proprinter sollte auch gehen)), was beim Nachdenken helfen kann:
Code: Alles auswählen
#!/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)
2023
@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 before 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()
Zum Grossteil einfach die Werte aus der Beispielbeschreibung überprüft. Kann man entweder mit dem `doctest`-Modul aus der Standardbibliothek überprüfen, oder aber ``pytest`` mit der entsprechenden Option aufrufen: Ersteres ist im Erfolgsfall sehr unspektakulär — es gibt einfach nix aus. Bei ``pytest`` gibt es mehr Ausgaben:
Im Terminal ist die ``pytest``-Ausgabe auch schön bunt, damit man in diesem Fall schön viele grüne PASSED sieht, und im Fehlerfall die roten FAILED schnell findet.
(Die naive Lösung ließ sich zum Glück trotzdem leicht umstricken auf eine, die auch mit den tatsächlichen Daten klar kommt)
