Created
December 6, 2023 23:04
-
-
Save saucecode/f3f5426bc683f95926317e339ec3d8b4 to your computer and use it in GitHub Desktop.
This file contains hidden or 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
| ''' | |
| 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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Sample input.txt