98 lines
2.1 KiB
Python
98 lines
2.1 KiB
Python
def read_map(input):
|
|
map = []
|
|
for line in input:
|
|
if not line.strip():
|
|
break
|
|
dst, src, count = nums(line)
|
|
map.append((dst, src, count))
|
|
return map
|
|
|
|
|
|
def overlap(a,b, x,y):
|
|
""" if two ranges a..b and x..y overlap, returns the overlapping range"""
|
|
if b <= x or y <= a:
|
|
return (0,0) # no overlap
|
|
return max(a,x), min(b,y)
|
|
|
|
def lookup(map, m,n):
|
|
r = [] # (start,count)
|
|
used = [] # (start,end)
|
|
for dst, src, count in map:
|
|
a,b = overlap(m,m+n, src,src+count)
|
|
if a != b:
|
|
assert a < b
|
|
used.append((a,b))
|
|
r.append((a-src+dst,b-a))
|
|
# unused values translate to themselves
|
|
used.sort()
|
|
end = m+n
|
|
for a,b in used:
|
|
assert m <= a
|
|
if m < a:
|
|
r.append((m, a-m))
|
|
m = b
|
|
if m < end:
|
|
r.append((m,end-m))
|
|
#r.sort()
|
|
return r
|
|
|
|
def nums(s):
|
|
return [int(x) for x in s.split()]
|
|
|
|
def read_puzzle(input):
|
|
l = next(input)
|
|
name,_, data = l.partition(": ")
|
|
assert name == 'seeds'
|
|
seeds = nums(data)
|
|
|
|
maps = {}
|
|
for l in input:
|
|
if l.strip():
|
|
assert ':' in l
|
|
name = l.split()[0]
|
|
frm, _, to = name.partition('-to-')
|
|
assert frm
|
|
assert to
|
|
map = read_map(input)
|
|
maps[(frm,to)] = map
|
|
|
|
print(seeds)
|
|
print(maps)
|
|
|
|
return seeds,maps
|
|
|
|
def solve(data):
|
|
seeds, maps = data
|
|
|
|
for i in range(0, len(seeds), 2):
|
|
m,n = seeds[i:i+2]
|
|
print(n, lookup(maps[('seed','soil')], m,n))
|
|
|
|
ranges = [(seeds[i],seeds[i+1]) for i in range(0,len(seeds),2)]
|
|
locs = seed2loc(maps, ranges)
|
|
|
|
print(min(locs))
|
|
|
|
|
|
def seed2loc(maps, r):
|
|
for a,b in [
|
|
('seed', 'soil'),
|
|
('soil', 'fertilizer'),
|
|
('fertilizer', 'water'),
|
|
('water', 'light'),
|
|
('light', 'temperature'),
|
|
('temperature', 'humidity'),
|
|
('humidity', 'location'),
|
|
]:
|
|
next = []
|
|
for m,n in r:
|
|
s = lookup(maps[a,b], m,n)
|
|
print(a,b,m,n,":", s)
|
|
next.extend(s)
|
|
r = next
|
|
return r
|
|
|
|
import sys
|
|
p = read_puzzle(sys.stdin)
|
|
solve(p)
|