1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
Conversion = Data.define(:source, :dest) do
  def [](k)
    return nil unless source.cover?(k)

    dest.begin + k - source.begin
  end
end

Mapping = Data.define(:conversions) do
  def [](source)
    conversions.filter_map { _1[source] }.first || source
  end
end

chunks = ARGF.read.split("\n\n")
seeds = chunks.shift.scan(/\d+/).map(&:to_i)
mappings = chunks.map {|chunk|
  Mapping.new(
    chunk
      .strip.split("\n")[1..-1]
      .map { _1.scan(/\d+/).map(&:to_i) }
      .map { Conversion.new((_2..._2+_3), (_1..._1+_3)) }
      # .sort_by { _1.source.begin }
  )
}

# part one
p seeds
  .map {|seed|
    mappings.inject(seed) {|cur, mapping| mapping[cur] }
  }
  .min

# part two

# clamps range a to range b
def clamp(a, b)
  case
  when a.cover?(b.begin) && a.cover?(b.end)
    b
  when b.cover?(a.begin) && b.cover?(a.end)
    a
  when a.cover?(b.begin)
    (b.begin...a.end)
  when b.cover?(a.begin)
    (a.begin...b.end)
  else
    nil
  end
end

seeds = seeds
  .each_slice(2)
  .map {|start, length| (start...start+length) }
  .sort_by(&:begin)
dests = mappings.inject(seeds) {|cur, mapping|
  sources = cur
    .flat_map {|range|
      sources = mapping.conversions.map(&:source).sort_by(&:begin)
      sources.concat(sources.each_cons(2).map { (_1.end..._2.begin) })
      sources << (0...(sources.map(&:begin).min))
      sources << (sources.map(&:end).max..)
      sources.filter_map {|source|
        clamp(source, range)
      }
    }
    .reject { _1.size == 0 }
  sources.map { (mapping[_1.begin]..mapping[_1.end-1]) }
}
p dests.map(&:begin).min

### prior explorations for part two

# p seeds
#   .each_slice(2)
#   .map {|start, length|
#     (start...start+length).map {|seed|
#       mappings.inject(seed) {|cur, mapping| mapping[cur] }
#     }
#     .min
#   }
#   .min

reversed = mappings
  .map {|mapping|
    Mapping.new(
      mapping.conversions.map {|c|
        Conversion.new((c.dest.begin...c.dest.begin+c.source.size), c.source)
      }
    )
  }
  .reverse
# p (0..).find {|i|
#     source = reversed.inject(i) {|cur, mapping| mapping[cur] }
#     seeds.any? { _1.cover?(source) }
#   }

lowest = seeds
  .flat_map(&:minmax)
  .filter_map {|seed|
    mappings.inject(seed) {|cur, mapping| mapping[cur] }
  }
  .min
p (0..lowest).bsearch {|loc|
    source = reversed.inject(loc) {|cur, mapping| mapping[cur] }
    seeds.any? { _1.cover?(source) }
  }