23d5p2.py

'''
	A 'range' in this context is a 2-tuple
	(a, b) that represents the set of integers
	in the (mathematical) range (a, b].
	
	a must always be less than b.
'''

def range_contains(ra, sub):
	'Checks if range `sub` is wholly contained by `ra`'
	return sub[0] >= ra[0] and sub[1] <= ra[1]

def range_overlaps(ra, rb):
	if ra[0] > rb[0]: ra,rb = rb,ra
	return (ra[0] <= rb[0] < ra[1]) or (ra[0] < rb[1] <= ra[1])

def range_intersection(ra, rb):
	assert range_overlaps(ra,rb)
	
	if range_contains(ra, rb):
		return rb
	if range_contains(rb, ra):
		return ra
	
	left = ra if ra[0] < rb[0] else rb
	right = rb if left == ra else ra
	
	return right[0],left[1]

def range_extract(ra, rb):
	'Removes rb from ra, returning a left and/or right range, or empty tuple'
	assert range_contains(ra,rb)
	res = []
	if ra[0] != rb[0]:
		res.append((ra[0], rb[0]))
	if rb[1] != ra[1]:
		res.append((rb[1],ra[1]))
	return tuple(res)

def test():
	assert range_contains( (0,100), (10, 20) ) == True
	assert range_contains( (0,100), (90, 100) ) == True
	assert range_contains( (0,100), (95, 101) ) == False
	assert range_contains( (0,100), (-10, 100) ) == False
	assert range_contains( (0,100), (0,100) ) == True
	assert range_contains( (0,float('Inf')), (5,15) ) == True
	
	assert range_overlaps( (20,30), (0,10) ) == False
	assert range_overlaps( (20,30), (10,20) ) == False
	assert range_overlaps( (20,30), (10,21) ) == True
	
	assert range_overlaps( (20,30), (20,30) ) == True
	
	assert range_overlaps( (20,30), (29,40) ) == True
	
	assert range_overlaps( (20,30), (30,40) ) == False
	assert range_overlaps( (20,30), (35,45) ) == False
	
	assert range_overlaps( (35,45), (30,50) ) == True
	assert range_overlaps( (35,45), (45,50) ) == False
	
	assert range_intersection( (30,50), (40,60) ) == (40,50)
	assert range_intersection( (35,45), (30,50) ) == (35,45)
	assert range_intersection( (30,50), (35,45) ) == (35,45)
	assert range_intersection( (5,10), (5,10) ) == (5,10)
	
	assert range_extract( (40,60), (45,50) ) == ( (40,45), (50,60) )
	

test()

def transform(input_ranges, transitions):
	# isolate inputs that do not overlap any transition
	out = [ra for ra in input_ranges if not any( range_overlaps(ra, rb) for rb, _ in transitions )]
	input_ranges = [ra for ra in input_ranges if ra not in out]
	
	sub = []
	last_hash = []
	
	# strategy: subdivide input_ranges until:
	# all(ra contains rb or rb contains ra)
	while 1:
		for ra in input_ranges:
			if ra in sub: continue
			
			# inputs that do not overlap any transition
			if not any( range_overlaps(ra, rb) for rb, _ in transitions ):
				sub.append(ra)
				continue
			
			for rb, shift in transitions:
				# if the input is wholly contained by ONE transition range
				if range_contains(rb, ra) and ra not in sub:
					sub.append( ra )
					continue
				
				# if the input overlaps the transition range
				if range_overlaps(ra, rb):
					# extract the range that overlaps
					overlap = range_intersection(ra, rb)
					# determine the parts of ra that do not overlap rb
					# i.e. union(ra rb) - intersection(ra rb)
					leftovers = range_extract(ra, overlap)
					sub.append(overlap)
					sub.extend(leftovers)
					break
		input_ranges = list(set(sub))
		sub.clear()
		
		new_hash = hash(tuple(input_ranges))
		if new_hash in last_hash: break
		last_hash.append(new_hash)

	# we've done this subdiving step to break the input
	# into ranges that either fit perfectly in ONE transition
	# range, or NO transition range.
	# i.e. (ra contains rb   or   rb contains ra) == True

	# subdiving complete
	# start shifting ranges according to the transition's shift
	for ra in input_ranges:
		# ranges that don't overlap move on without any shifting
		if not any(range_overlaps(ra,rb) for rb,_ in transitions):
			out.append( ra )
			
		else:
			# ranges that do overlap can have the shift applied
			for rb, shift in transitions:
				if range_contains(ra,rb) or range_contains(rb, ra):
					out.append( (ra[0]+shift, ra[1]+shift) )

	# sorted for debugging convenience. unnecessary.
	return sorted(out, key=lambda x:x[0])
			

import re
with open('input.txt','r') as f:
	data = f.read().strip().split('\n\n')

seeds = list(map(int, re.findall(r'\d+', data[0]))) # convert to int
seeds = list(zip(seeds[::2],seeds[1::2])) # pair them up
seeds = [(a,a+b) for a,b in seeds] # convert from (start, count) to (start, end)

# load each map as [ ((start, end), shift), ... ]
transition_ranges = []
for rangedata in data[1:]:
	rs = []
	for line in rangedata.split('\n')[1:]:
		dest, src, amount = [int(i) for i in re.findall(r'\d+', line)]
		rs.append( ((src, src+amount), dest-src) )
	transition_ranges.append(rs)

# feedback input to transform function for all maps
for tra in transition_ranges:
	seeds = transform(seeds, tra)

print(min(a for a,b in seeds))