Jake Pullen
131 lines
4.4 KiB
Python
131 lines
4.4 KiB
Python
with open(r'advent_of_code\2023\05\input.txt', 'r') as file:
|
|
input = file.readlines()
|
|
|
|
with open(r'advent_of_code\2023\05\test_input.txt', 'r') as file:
|
|
test_input = file.readlines()
|
|
|
|
# input = test_input
|
|
|
|
# print(input)
|
|
|
|
lines = [line.strip('\r\n') for line in input]
|
|
|
|
seed_numbers = input[0].split(':')[1].strip().split(' ')
|
|
seeds = [int(num) for num in seed_numbers]
|
|
|
|
maps = {}
|
|
for line in lines[1:]:
|
|
if line.endswith(' map:'):
|
|
k = line.split()[0].split('-')
|
|
k = (k[0], k[2])
|
|
maps[k] = map = []
|
|
elif line:
|
|
# Split the line into parts
|
|
parts = line.split()
|
|
|
|
# Convert each part to an integer
|
|
int_parts = [int(part) for part in parts]
|
|
|
|
# Create a tuple from the list of integer parts
|
|
x = tuple(int_parts)
|
|
|
|
# Calculate the start and end of the range
|
|
range_start = x[1]
|
|
range_end = x[1] + x[2] - 1
|
|
|
|
# Calculate the mapped start of the range
|
|
mapped_start = x[0] - x[1]
|
|
|
|
# Create a tuple representing the range and its mapped start
|
|
range_tuple = ((range_start, range_end), mapped_start)
|
|
|
|
# Append the tuple to the map
|
|
map.append(range_tuple)
|
|
for map in maps.values():
|
|
map.sort()
|
|
|
|
|
|
def map_range(rng, map):
|
|
# Initialize a list with the input range
|
|
ranges = [rng]
|
|
# Initialize an empty list to store the result ranges
|
|
result_range = []
|
|
|
|
# Process each range in the list
|
|
while ranges:
|
|
# Flag to check if a match was found in the map
|
|
matched = False
|
|
# Get the current range
|
|
start, end = rng = ranges.pop()
|
|
|
|
# Check each entry in the map
|
|
for src, delta in map:
|
|
# Case 1: The end of the current range is within the source range
|
|
if start < src[0] <= end <= src[1]:
|
|
matched = True
|
|
# Add the remaining part of the current range to the list
|
|
ranges.append((start, src[0] - 1))
|
|
# Add the mapped range to the result
|
|
result_range.append((src[0] + delta, end + delta))
|
|
|
|
# Case 2: The start of the current range is within the source range
|
|
elif src[0] <= start <= src[1] < end:
|
|
matched = True
|
|
# Add the remaining part of the current range to the list
|
|
ranges.append((src[1] + 1, end))
|
|
# Add the mapped range to the result
|
|
result_range.append((start + delta, src[1] + delta))
|
|
|
|
# Case 3: The current range is entirely within the source range
|
|
elif src[0] <= start <= end <= src[1]:
|
|
matched = True
|
|
# Add the mapped range to the result
|
|
result_range.append((start + delta, end + delta))
|
|
|
|
# Case 4: The current range entirely contains the source range
|
|
elif start < src[0] <= src[1] < end:
|
|
matched = True
|
|
# Add the parts of the current range outside the source range to the list
|
|
ranges.append((start, src[0] - 1))
|
|
ranges.append((src[1] + 1, end))
|
|
# Add the mapped range to the result
|
|
result_range.append((src[0] + delta, src[1] + delta))
|
|
|
|
# If no match was found in the map, add the current range to the result
|
|
if not matched:
|
|
result_range.append(rng)
|
|
|
|
# Sort the result ranges
|
|
result_range.sort()
|
|
|
|
return result_range
|
|
|
|
|
|
ranges = []
|
|
for i in range(0, len(seeds), 2):
|
|
start = seeds[i]
|
|
end = seeds[i] + seeds[i+1] - 1
|
|
ranges.append((start, end))
|
|
k = 'seed'
|
|
# The loop continues until 'k' is equal to 'location'
|
|
while k != 'location':
|
|
# Iterate over each item in the 'maps' dictionary
|
|
for key, map in maps.items():
|
|
# Check if the first element of the key matches 'k'
|
|
if key[0] == k:
|
|
# Initialize an empty list to store the new ranges
|
|
new_range = []
|
|
# Iterate over each range in the current list of ranges
|
|
for item in ranges:
|
|
# Map the current range using the current map
|
|
# and add the resulting ranges to the new list
|
|
new_range.extend(map_range(item, map))
|
|
# Replace the current list of ranges with the new list
|
|
ranges = new_range
|
|
# Update 'k' to the second element of the key
|
|
k = key[1]
|
|
# Break out of the loop over the 'maps' dictionary
|
|
break
|
|
|
|
print(min([result[0] for result in ranges]))
|