Created
January 1, 2024 11:32
-
-
Save M0r13n/fe30d82277bc8a1bd3402dfa126f13eb to your computer and use it in GitHub Desktop.
Python solution for Advent of Code 2023 (AOC) day 5 part 2 based on iterative transformation of ranges
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import itertools | |
def row2int(row: str) -> list[int]: | |
return list(map(int, row.strip().split(' '))) | |
def rows2list(fd): | |
l = [] | |
for row in fd: | |
if not row.strip(): | |
break | |
l.append(row2int(row)) | |
return l | |
def do_overlap(x_start, x_len, y_start, y_len): | |
return x_start <= y_len and y_start <= x_len | |
def bubble_wise(l): | |
for i in range(0, len(l) - 1, 2): | |
yield l[i], l[i+1] | |
def abs_range(pair): | |
return pair[0], sum(pair) | |
def iter_map(map): | |
for x, y, z in map: | |
yield x, y, z, y+z | |
def remember_left_overlap(start, end, source_range_start, remaining_seeds): | |
left_i, left_j = min(start, source_range_start), min(end, source_range_start) | |
if left_i < left_j: | |
print(f'Hangover (left): [{left_i}, {left_j}]') | |
remaining_seeds.append((left_i, left_j - 1)) | |
def remember_right_overlap(end, source_range_end, remaining_seeds): | |
right_i, right_j = max(end, source_range_end), max(end, source_range_end) | |
if right_i < right_j: | |
print(f'Hangover (right): [{right_i}, {right_j}]') | |
remaining_seeds.append((right_i, right_j - 1)) | |
def transform_intersection(start, end, source_range_start, source_range_end, destination_range_start): | |
overlap_i, overlap_j = max(start, source_range_start), min(end, source_range_end) | |
if overlap_i < overlap_j: | |
offset = destination_range_start - source_range_start | |
new_i, new_j = overlap_i + offset, overlap_j+offset | |
print(f'Overlap: [{overlap_i}, {overlap_j}] ~~> [{new_i}, {new_j}]') | |
return new_i, new_j | |
def find_locations(seed_ranges, maps): | |
# General Idea | |
# ------------ | |
# Iterate over every seed-range "from top to bottom". | |
# Check for every map (seed-to-soil, soil-to-fertilizer, ...) if we have to | |
# convert numbers from a source category into numbers in a destination category. | |
# There are only two cases (for every map): | |
# 1. There is a line to describes how to convert a source num to a destination num | |
# 2. Source numbers aren't mapped | |
# | |
# In the first case, the source range needs to be converted into a | |
# destination range based in the destination-range-start. | |
# | |
# In the second case, nothing needs to be converted, because the same source | |
# maps to the same destination (e.g. seed 10 maps to soil 10). | |
# | |
# This basically means, that is is enough to perform four checks for every line | |
# in every map ("from top to bottom"): | |
# 1. Get the range of source numbers that are smaller then the source-range-start ("overlap to the left") | |
# 2. Get the range of source numbers that are greater then the source-range-end ("overlap to the right") | |
# 3. Get the range of source numbers that are mapped and transform them based on the destination-range-start | |
# 4. Leave the source range as it is, if there is no mapping | |
for pair in bubble_wise(seed_ranges): | |
remaining_seeds = [abs_range(pair)] | |
temp = [] | |
for mp in maps: | |
while len(remaining_seeds) > 0: | |
(start, end), found_any = remaining_seeds.pop(), False | |
print('---') | |
for sd, ss, _, se in iter_map(mp): | |
if do_overlap(start, end, ss, se): | |
found_any = True | |
# Does the seed range overlap on the left? | |
# [1,2,3,4,5] | |
# [4,5,6,7,8] | |
# [1,2,3] <-- this remains | |
remember_left_overlap(start, end, ss, remaining_seeds) | |
# Does the seed range overlap on the right? | |
# [4,5,6,7,8] | |
# [1,2,3,4,5] | |
# [6,7,8] <-- this remains | |
remember_right_overlap(end, se, remaining_seeds) | |
# Interection of both ranges ("a perfect overlap") | |
# [1,2,3,4,5] | |
# [4,5,6,7,8] | |
# [4,5] <-- this overlaps | |
new_i, new_j = transform_intersection(start, end, ss, se, sd) | |
temp.append((new_i, new_j)) | |
else: | |
# [1,2,3,4,5] | |
# [6,7,8,9,10] | |
print(f'No Overlap: [{start}, {end}] vs. [{ss}, {se}]') | |
continue | |
if not found_any: | |
temp.append((start, end)) | |
remaining_seeds, temp = temp, [] | |
yield remaining_seeds | |
def parse_almanac(path: str): | |
with open(path) as fd: | |
for i, line in enumerate(fd): | |
if i == 0: | |
seeds = row2int(line.removeprefix('seeds:')) | |
elif line.startswith('seed-to-soil'): | |
seed_to_soil = rows2list(fd) | |
elif line.startswith('soil-to-fertilizer'): | |
soil_to_fertilizer = rows2list(fd) | |
elif line.startswith('fertilizer-to-water'): | |
fertilizer_to_water = rows2list(fd) | |
elif line.startswith('water-to-light'): | |
water_to_light = rows2list(fd) | |
elif line.startswith('light-to-temperature'): | |
light_to_temperature = rows2list(fd) | |
elif line.startswith('temperature-to-humidity'): | |
temperature_to_humidity = rows2list(fd) | |
elif line.startswith('humidity-to-location'): | |
humidity_to_location = rows2list(fd) | |
else: | |
pass | |
return seeds, [ | |
seed_to_soil, | |
soil_to_fertilizer, | |
fertilizer_to_water, | |
water_to_light, | |
light_to_temperature, | |
temperature_to_humidity, | |
humidity_to_location | |
] | |
if __name__ == '__main__': | |
seed_ranges, maps = parse_almanac('./map.txt') | |
# seed_ranges, maps = parse_almanac('./map.txt.orig') | |
locations = itertools.chain.from_iterable(find_locations(seed_ranges, maps)) | |
locations_sorted = sorted(locations, key=lambda x: x[0]) | |
smallest_loc = locations_sorted[0][0] | |
print('28580589 and got', smallest_loc, ) | |
assert 28580589 == smallest_loc, "WRONG!!!! :(" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment