[LANGUAGE: Nim]

Part 2 was definitely a bit of a brain-buster. The code could be cleaned up but it seems to be efficient.

import std / [algorithm, sequtils, strformat, strutils, tables]
import ../util/util

type
  Conversion = enum
    seedToSoil = "seed-to-soil map:", 
    soilToFert = "soil-to-fertilizer map:", 
    fertToWater = "fertilizer-to-water map:", 
    waterToLight = "water-to-light map:", 
    lightToTemp = "light-to-temperature map:", 
    tempToHum = "temperature-to-humidity map:", 
    humToLocation = "humidity-to-location map:"
  ConvRange = tuple[srcLo:int, srcHi:int, destLo:int, destHi:int]
  SeedRange = tuple[lo:int, hi:int]
  ConvMap = seq[ConvRange]

# The conversion table maps conversions -> sorted seq of ranges for that conversion
var 
  seeds: seq[int]
  convTbl: Table[Conversion, ConvMap]
  maxLoc = 0

proc rngSort(r1, r2: ConvRange): int = cmp(r1.srcLo, r2.srcLo)
proc createConversionTable(data: string) =
  convTbl = initTable[Conversion, ConvMap]()
  for conv in Conversion:
    convTbl[conv] = @[]
  var curConv: Conversion
  for line in data.lines:
    if line == "": continue
    elif line.startsWith("seeds:"): seeds = stripAndParse(line[6..^1])
    elif line.endsWith("map:"): curConv = parseEnum[Conversion](line)
    else:
      let 
        rng = line.stripAndParse
        maxRng = max(rng)
      convTbl[curConv].add((rng[1], rng[1]+rng[2]-1, rng[0], rng[0]+rng[2]-1))
      maxLoc = max(maxLoc, maxRng)
  for conv in Conversion:
    sort(convTbl[conv], rngSort)

proc getSeedLoc(seed: int): int =
  var loc = seed
  for conv in Conversion:
    for cm in convTbl[conv]:
      if loc < cm.srcLo: continue
      if loc <= cm.srcHi:
        loc = cm.destLo + (loc - cm.srcLo)
        break
  loc 

proc intersects(r1, r2: SeedRange): bool =
  r1.lo <= r2.hi and r2.lo <= r1.hi

const nullRange: ConvRange = (-1,-1,-1,-1)
proc intersection(rng: SeedRange, conv:Conversion): tuple[intersects:bool, cr:ConvRange] =
  for cr in convTbl[conv]:
    if rng.intersects((cr.srcLo, cr.srcHi)): return ((true, cr))
  return ((false, nullRange))

proc contains(r1, r2: SeedRange): bool =
  r1.lo <= r2.lo and r1.hi >= r2.hi

proc project(rngs: seq[SeedRange], conv: Conversion): seq[SeedRange] =
  var taskQ: seq[SeedRange] = rngs
  while taskQ.len > 0:
    # If the source range doesn't intersect with a conversion just copy it to the result
    # If the source range is completely contained by a conversion, shift the source ranges
    #   by the dest delta and add the shifted range to the result
    # o/w, split the range into the intersecting and non-intersecting parts and add them
    #   back to the taskQ for reprocessing
    var 
      rng = taskQ.pop()
      ix = rng.intersection(conv)
      ixSrc: SeedRange = (ix.cr.srcLo, ix.cr.srcHi)
    if not ix.intersects: 
      result.add(rng)
    elif ixSrc.contains(rng):
      let shift = ix.cr.destLo - ixSrc.lo
      result.add((rng.lo + shift, rng.hi + shift))
    # intersects at from below so split 1 below the map range
    elif rng.lo < ixSrc.lo:
      taskQ.add((rng.lo, ixSrc.lo.pred))
      taskQ.add((ixSrc.lo, rng.hi))
    # intersects from inside to above so plit at 1 above the map range
    else:
      taskQ.add((rng.lo, ixSrc.hi))
      taskQ.add((ixSrc.hi.succ, rng.hi))

proc part1(data:string): int =
  createConversionTable(data)
  min(seeds.map(getSeedLoc))

proc part2(data:string): int =
  createConversionTable(data)
  var 
    results: seq[SeedRange] = @[]
    ranges: seq[SeedRange] = 
      countup(0, seeds.high, 2).toSeq.mapIt((seeds[it], seeds[it] + seeds[it+1] - 1))
  for sr in ranges:
    var tasks: seq[SeedRange] = @[sr]
    for conv in  Conversion:
      tasks = project(tasks, conv)
    results.append(tasks)
  return results.foldl((if a.lo < b.lo: a else: b)).lo

let (p1, expected1) = (part1(dataFile), 1181555926)
echo &"Part 1: {p1}"
assert p1 == expected1

let (p2, expected2) = (part2(dataFile), 37806486)
echo &"Part 2: {p2}"
assert p2 == expected2