aoc/2023/05/solution.py

#!/usr/bin/python3
import sys
import re

def part1():
    print('part 1')
    split = ''.join(sys.stdin.readlines()).split('\n\n')
    #seeds = [int(n) for n in re.findall(r'\d+', split[0])]
    ranges = [int(n) for n in re.findall(r'\d+', split[0])]
    seeds = []
    for i in range(0, len(ranges), 2):
        for n in range(ranges[i], ranges[i] + ranges[i + 1]):
            seeds.append(n)
    maps = [m.split('\n') for m in split[1:]]
    print(seeds, maps)
    for m in maps:
        source, sink = m[0].rstrip(' map:').split('-to-')
        print(source, sink, seeds)
        for i, seed in enumerate(seeds):
            for line in m[1:]:
                sink_start, source_start, upto = [int(n) for n in line.split(' ')]
                #print(sink_start, source_start, upto)
                if seed >= source_start and seed < source_start + upto:
                    #print(f'src {seed} ({i}) in {source_start} {source_start + upto} maps to {sink_start + seed - source_start}')
                    seeds[i] = sink_start + seed - source_start
    print(seeds)
    print(min(seeds))

def find_overlap(r1, r2):
    start = max(r1[0], r2[0])
    end = min(r1[1], r2[1])
    return (start, end) if start <= end else None

def shift_range(r, delta):
    return (r[0] + delta, r[1] + delta)

def split_range(r, overlap):
    result = set()

    if r[0] < overlap[0]:
        result.add((r[0], overlap[0] - 1))
    if r[1] > overlap[1]:
        result.add((overlap[1] + 1, r[1]))
    
    return result

def part2():
    print('part 2')
    split = ''.join(sys.stdin.readlines()).split('\n\n')
    seeds = [int(n) for n in re.findall(r'\d+', split[0])]
    ranges = set([(seeds[i], seeds[i] + seeds[i + 1] - 1) for i in range(0, len(seeds), 2)])
    maps = [m.split('\n') for m in split[1:]]
    print(ranges)
    for m in maps:
        new_ranges = set()
        for line in m[1:]:
            for r in ranges.copy():
                start_sink, start_source, upto = [int(n) for n in line.split(' ')]
                range_source = (start_source, start_source + upto - 1)
                overlap = find_overlap(r, range_source)
                if overlap:
                    ranges.remove(r)
                    ranges |= split_range(r, overlap)
                    new_ranges.add(shift_range(overlap, start_sink - start_source))
        ranges |= new_ranges
        print(ranges)
    print(min(min(ranges)))

if sys.argv[1] in '1':
    part1()
else:
    part2()