#
# Part 2 solution is as follows:
#
# First we know how to get from "left" (seed) to "right" (location) for
# any number following the part1 rules.  We rewrite this to ensure that
# it works efficiently even if the ranges are *extremely* large - today's
# gods frown on iterating through the problem space!
#
# Part two, we must look backwards - we look for discontinuities in the
# "location" numberline (where inputs from different humidities come to
# nearly the same location) and follow those discontinuities backwards -
# either because they are the projection of a discontinuity to the right,
# or because they're the right-hand end of a mapping from their "left"
# neighbouring layer.
#
# Eventually we discover get all the seed numbers that are near the start
# of a subsequent discontinuity which follows through to the final layer
# ("location"), i.e. all the seeds which could trace through to either side
# of a discontinuity in the final output which could affect the result.
#
# Search through these (checking both sides of the 'minimum' edge of each
# discontinuity) to get the result without brute forcing a problem space
# that could take all lunchtime or even more!
#
import re
import json
re1 = re.compile("seeds: (.*)")
re2 = re.compile("(\\w+)-to-(\\w+) map:")
re3 = re.compile("([0-9 ]+)")
res = re.compile("\\s+")

seed_list = []
map_connections = {} # src name -> dest name
rev_connections = {} # dest name -> src name
map_values = {} # (src_name,dst_name) -> [(src_start, dst_start, length), ...]
map_boundaries = {} # (src_name,dst_name) -> [list of places where a change could occur (lower side only)]

#
# Advent of parsing, naturally...
#
src = None
dst = None
for line in open("input.txt"):
    m1 = re1.match(line)
    m2 = re2.match(line)
    m3 = re3.match(line)
    if m1 is not None:
        seed_list = [int(x) for x in res.split(m1.group(1))]
    elif m2 is not None:
        src = m2.group(1)
        dst = m2.group(2)
        map_connections[src] = dst
        rev_connections[dst] = src
        map_values[(src,dst)] = []
    elif m3 is not None:
        (dest_start, source_start, length) = [int(x) for x in res.split(m3.group(1))]
        map_values[(src,dst)].append((source_start, dest_start, length)) # opposite way around

#
# Follow a number from left to right [seed to location]:
#
def lookup(src_type, src_num, looking_for_type, depth):
    next_type = map_connections[src_type]
    next_num = src_num # default if no ranges found
    for mapping in map_values[(src_type, next_type)]:
        (source_start, dest_start, length) = mapping
        if source_start <= src_num < source_start + length:
            next_num = dest_start + (src_num - source_start)
    if next_type == looking_for_type:
        return next_num
    else:
        return lookup(next_type, next_num, looking_for_type, depth + 1)

#
# This is called recursively by boundary_map_right
#
# Recursively follow boundaries from right to left, given
# that the right hand side has already been added to
# map_boundaries
#
def boundary_map_middle(dst_type, looking_for_type, depth):
    src_type = rev_connections[dst_type]
    map_boundaries[src_type] = []

    # 1: ones based on inherant boundaries in this layer
    for mapping in map_values[(src_type, dst_type)]:
        (source_start, dest_start, length) = mapping
        map_boundaries[src_type].append(source_start)
        map_boundaries[src_type].append(source_start - 1)

    # 2: ones based on lines from the next-right layer
    for dst_boundary in map_boundaries[dst_type]:
        src_boundary = dst_boundary
        for mapping in map_values[(src_type, dst_type)]:
            (source_start, dest_start, length) = mapping
            if dest_start <= dst_boundary < dest_start + length:
                src_boundary = source_start + (dst_boundary - dest_start)
        map_boundaries[src_type].append(src_boundary)
        map_boundaries[src_type].append(src_boundary - 1)

    # and recurse to explore the next-left layer
    if src_type != looking_for_type:
        boundary_map_middle(src_type, looking_for_type, depth + 1)

# Start the recursive search on the right hand side, by looking
# at boundary conditions where mapped ranges end, and following
# them to the source, including mapping of "straight" connections
# where a non-mapped region might end up having an interesting
# connection.
#
# This calls boundary_map_middle, which becomes recursive after
# this first layer.
#
def boundary_map_right(dst_type):
    src_type = rev_connections[dst_type]
    map_boundaries[src_type] = [0]
    for mapping in map_values[(src_type, dst_type)]:
        (source_start, dest_start, length) = mapping
        map_boundaries[src_type].append(source_start)
        map_boundaries[src_type].append(dest_start -1)
        map_boundaries[src_type].append(dest_start + length + 1)
    boundary_map_middle(src_type, "seed", 0)

# Utility to split list into a list of ranges
def array_to_pairs(array):
    result = []
    iterator = iter(array)
    for a in iterator:
        b = next(iterator)
        result.append((a,a+b))
    return result

# Utility to check if number is within a list of ranges
def number_in_ranges(ranges, number):
    yes = False
    for r in ranges:
        (a,b) = r
        if a <= number < b:
            yes = True
    return yes

# The main program!
part1 = False
if part1:
    # Part 1: search list of seeds
    locations = []
    for seed in seed_list:
        location = lookup("seed", seed, "location", 0)
        locations.append(location)
    print("Part 1 minimum location is %d" % min(locations))

else:
    # Start the recursive backwards propogation of interesting
    # boundary points - this takes things which could affect the
    # rightmost layer of the structure and follows them backwards
    # (leftwards) to find boundaries in the previous layer which
    # could cause discontinuities in the mapping of large ranges
    # of numbers from left to right
    #
    boundary_map_right("location")

    locations = []
    seed_pairs = array_to_pairs(seed_list)

    # Do the search using map_boundaries["seed"], which is the result of looking
    # backwards through the network for points in which conditions change which
    # could lead to a discontinuity through the network:
    for potential_seed in map_boundaries["seed"]:

        # Is this seed actually within any of the ranges from the
        # first line of the challenge?
        if number_in_ranges(seed_pairs, potential_seed):

            # consider one number as a possible solution
            location = lookup("seed", potential_seed, "location", 0)
            locations.append(location)

    # Now we've searched enough very specific seeds at the edge of
    # boundary conditions to be overconfident at having enough
    # coverage to ask it for the final answer...!?
    print("Part 2 (for real) minimum location is %d" % min(locations))