Part 1
Interesting problem. When doing some work on basic functions, I came across something a bit weird.
def get_object_destination(
obj: int,
obj_maps: list[list[int]],
):
def is_within_range(r: list[int]):
return r[1] <= obj <= r[0] + r[1]
match = list(filter(is_within_range, obj_maps))
return obj + abs(match[0][1] - match[0][0]) if match else obj
def test_object_is_in_range(self):
seeds, maps = get_game_data_from_input(TEST_DATA)
obj_maps = maps[0]
self.assertEqual(
list(map(lambda seed: get_object_destination(seed, obj_maps),
seeds)),
[81, 14, 57, 13]
) This runs fine, and passes all tests, but I don't like the match[0][1]; instead, Phind suggested changing the match to having the result of a next. In this case, however, the tests fail (only the first get_object_destination gets called?).
def get_object_destination(
obj: int,
obj_maps: list[list[int]],
):
def is_within_range(r: list[int]):
return r[1] <= obj <= r[0] + r[1]
match = next(filter(is_within_range, obj_maps))
return obj + abs(match[1] - match[0]) if match else objTraceback (most recent call last):
File "/Users/alexj/prog/aoc/2023/05/tests.py", line 68, in test_object_is_in_range
self.assertEqual(
AssertionError: Lists differ: [81] != [81, 14, 57, 13]
Second list contains 3 additional elements.
First extra element 1:
14
- [81]
+ [81, 14, 57, 13]So I'm not sure what to make of this, but the exercise is solved anyway. Maybe I'll come back to this later.
Tests
TEST_DATA = """
seeds: 79 14 55 13
seed-to-soil map:
50 98 2
52 50 48
...
"""
class Test202305_01(unittest.TestCase):
def test_transform_input_into_game_data(self):
seeds, maps = get_game_data_from_input(TEST_DATA)
self.assertEqual(
seeds,
[79, 14, 55, 13]
)
self.assertEqual(
maps,
[
[[50, 98, 2], [52, 50, 48]],
[[0, 15, 37], [37, 52, 2], [39, 0, 15]],
[[49, 53, 8], [0, 11, 42], [42, 0, 7], [57, 7, 4]],
[[88, 18, 7], [18, 25, 70]],
[[45, 77, 23], [81, 45, 19], [68, 64, 13]],
[[0, 69, 1], [1, 0, 69]],
[[60, 56, 37], [56, 93, 4]]]
)
# a seed, or a soil, or a fertilizer, etc.
# are OBJECTS; the following function tests
# whether they are in a range and returns destination
def test_first_mapping_of_objects(self):
seeds, maps = get_game_data_from_input(TEST_DATA)
self.assertEqual(
list(map(lambda seed: get_object_destination(seed, maps[0]),
seeds)),
[81, 14, 57, 13]
)
def test_second_mapping_of_objects(self):
_, maps = get_game_data_from_input(TEST_DATA)
self.assertEqual(
list(map(lambda seed: get_object_destination(seed, maps[1]),
[81, 14, 57, 13])),
[81, 53, 57, 52]
)
def test_recursive_mapping_of_objects(self):
seeds, maps = get_game_data_from_input(TEST_DATA)
self.assertEqual(
recursively_map_objects(seeds, maps),
[82, 43, 86, 35]
)
def test_solving_part_one(self):
seeds, maps = get_game_data_from_input(TEST_DATA)
self.assertEqual(
solve_part_one(seeds, maps),
35
)Code
def get_game_data_from_input(data: str):
def get_map_data_from_text_cluster(cluster: str):
return list(map(lambda x: list(map(int, x)),
map(lambda line: line.split(),
cluster.split(':')[1].strip().split("\n"))))
content = data.strip().split("\n\n")
seeds = list(map(int, content[0].split(":")[1].split()))
maps = list(map(lambda cluster: get_map_data_from_text_cluster(cluster),
content[1:]))
return seeds, maps
def get_object_destination(
obj: int,
obj_maps: list[list[int]],
):
def is_within_range(r: list[int]):
return r[1] <= obj <= r[1] + r[2]
match = list(filter(is_within_range, obj_maps))
return match[0][0] + abs(match[0][1] - obj) if match else obj
def recursively_map_objects(
objs: list[int],
all_obj_maps: list[list[list[int]]],
) -> list[int]:
if len(all_obj_maps) == 0:
return objs
return recursively_map_objects(
[get_object_destination(obj, all_obj_maps[0]) for obj in objs],
all_obj_maps[1:],
)
def solve_part_one(
seeds: list[int],
maps: list[list[list[int]]],
) -> int:
return min(recursively_map_objects(seeds, maps))
with open("input", "r") as f:
data = f.read()
seeds, maps = get_game_data_from_input(data)
print(solve_part_one(seeds, maps))Part 2
Part 2 is trickier because of the introduction of ranges. Of course, one could not solve this the regular way (just creating more seeds), as it would get very out of hand in terms of added computation. So all it took was a lot of pen and paper writing. My ranges are open at the right boundary (ie. the range [98, 99], with only two values, is represented by [98, 100[.
I feel I could have done a better job at naming the functions, and I had trouble figuring out a good way of separating the mapped ranges from the unmapped (the ones that had no correspondence in a given set of maps). In the end, that was achieved with a boolean flag - but I suppose there must be a better way to do this.
Tests
class Test202305_02(unittest.TestCase):
def test_transform_input_into_game_data(self):
seeds, maps = get_game_data_from_input(TEST_DATA)
self.assertEqual(
seeds,
[[79, 94], [55, 69]]
)
self.assertEqual(
maps,
[
[[50, 98, 2], [52, 50, 48]],
[[0, 15, 37], [37, 52, 2], [39, 0, 15]],
[[49, 53, 8], [0, 11, 42], [42, 0, 7], [57, 7, 4]],
[[88, 18, 7], [18, 25, 70]],
[[45, 77, 23], [81, 45, 19], [68, 64, 13]],
[[0, 69, 1], [1, 0, 69]],
[[60, 56, 37], [56, 93, 4]]]
)
# 50 98 2 means two numbers, including 98;
# thus, range is [98, 100]
def test_build_range_from_map(self):
seeds, maps = get_game_data_from_input(TEST_DATA)
self.assertEqual(range_from_map(maps[0][0]),
[98, 100])
self.assertEqual(range_from_map(maps[0][1]),
[50, 98])
def test_mapped_range(self):
obj = [52, 61]
obj_map = [52, 50, 48]
self.assertEqual(mapped_range(obj, obj_map),
[54, 63])
obj = [50, 52]
obj_map = [52, 50, 48]
self.assertEqual(mapped_range(obj, obj_map),
[52, 54])
def test_get_range_mapping(self):
obj_map = [52, 50, 48]
# testing total intersection
obj = [51, 54]
self.assertEqual(get_range_mapping(obj, obj_map),
[[53, 56], None, True])
# testing no intersection
obj = [1, 4]
self.assertEqual(get_range_mapping(obj, obj_map),
[[1, 4], [], False])
# testing partial intersections
obj = [40, 55]
self.assertEqual(get_range_mapping(obj, obj_map),
[[52, 57], [40, 50], True])
obj = [55, 102]
self.assertEqual(get_range_mapping(obj, obj_map),
[[57, 100], [98, 102], True])
def test_debug_range_mapping(self):
obj_map = [49, 53, 8]
obj = [57, 71]
self.assertEqual(get_range_mapping(obj, obj_map),
[[53, 57], [61, 71], True])
# a seed, or a soil, or a fertilizer, etc.
# are now RANGES; the following function tests
# whether there's range intersections, returning
# the mapped and unmapped results, accordingly.
def test_mapping_of_objects(self):
seeds, maps = get_game_data_from_input(TEST_DATA)
# both contained
self.assertEqual(
get_mappings_for_objects(seeds, maps[0], []),
[[81, 96], [57, 71]]
)
# both contained and one without intersection
self.assertEqual(
get_mappings_for_objects(seeds + [[1, 2]], maps[0], []),
[[81, 96], [57, 71], [1, 2]]
)
# both contained and one partially intersected
self.assertEqual(
get_mappings_for_objects(seeds + [[1, 55]], maps[0], []),
[[81, 96], [57, 71], [52, 57], [1, 50]]
)
def test_solving_part_two(self):
seeds, maps = get_game_data_from_input(TEST_DATA)
self.assertEqual(
solve_part_two(seeds, maps),
46
)Code
# transforms into a range with open interval at the end;
# [a, b] is represented as [a, b + 1[
def transform_seed_input_into_range(seeds: list[int]) -> list[list[int]]:
return [[seeds[i], seeds[i] + seeds[i + 1] + 1]
for i in range(0, len(seeds), 2)]
def get_game_data_from_input(data: str):
def get_map_data_from_text_cluster(cluster: str):
return list(map(lambda x: list(map(int, x)),
map(lambda line: line.split(),
cluster.split(':')[1].strip().split("\n"))))
content = data.strip().split("\n\n")
seeds = transform_seed_input_into_range(list(map(int, content[0].split(":")[1].split())))
maps = list(map(lambda cluster: get_map_data_from_text_cluster(cluster),
content[1:]))
return seeds, maps
def range_from_map(obj_map: tuple[int, int, int]) -> list[int, int]:
_, beg, span = obj_map
return [beg, beg + span]
def mapped_range(
obj_range: tuple[int, int],
obj_map: tuple[int, int]):
end, start, _ = obj_map
offset = end - start
res = list(map(lambda x: x + offset,
obj_range))
return res
def get_range_mapping(
obj: tuple[int, int],
map_range: tuple[int, int]
) -> list[list[int], list, bool]:
a, b = obj
c, d = range_from_map(map_range)
# no intersection between ranges;
# no mapping; no new_range
if b - 1 < c or a + 1 > d:
return [obj, [], False]
# total intersection between ranges;
# full mapping; no new_range
if a >= c and b <= d:
return [mapped_range(obj, map_range), None, True]
# partial intersections;
return ([mapped_range([c, b], map_range), [a, c], True]
if a < c else
[mapped_range([a, d], map_range), [d, b], True])
# returns the mapped object as soon as possible,
# or the unmapped object if it exhausted all maps.
def try_obj_over_maps(
obj: list,
maps: list,
) -> list:
return next((new_map for m in maps
if ((new_map := get_range_mapping(obj, m))[2] is True)),
[obj, []] + [False])
def get_mappings_for_objects(
obj_ranges: tuple[int, int],
obj_maps: list[tuple[int, int, int]],
mapped: list = [],
):
if obj_ranges == []:
return mapped
else:
mapped_range, new_range, was_mapped = try_obj_over_maps(obj_ranges[0], obj_maps)
return get_mappings_for_objects(
(obj_ranges[1:] + [new_range]
if was_mapped and new_range is not None else obj_ranges[1:]),
obj_maps,
(mapped + [mapped_range]
if mapped_range is not None else mapped))
def recursively_map_objects(
objs: list[int],
all_obj_maps: list[list[list[int]]],
) -> list[int]:
if len(all_obj_maps) == 0:
return objs
return recursively_map_objects(
get_mappings_for_objects(objs, all_obj_maps[0]),
all_obj_maps[1:],
)
def solve_part_two(
seeds: list[int],
maps: list[list[list[int]]],
) -> int:
return min(min(recursively_map_objects(seeds, maps)))