Problem description

We are given a list of integer ranges (with the format start-end, where start and end are included in the range), and a list of -(integer) ingredient identifiers. Ranges can overlap.

3-5
10-14
16-20
12-18

1
5
8
11
17

Part 1

In part 1, we have to count how many numbers from the ingredients list are included in the integer ranges. In our example, 3 numbers (5, 11 and 17) are included in the ranges.

First, I defined an immutable class for Ranges.

case class Range(start: Long, end: Long)

I parsed the input data with some pattern matching

private def parseIngredients(input: List[String]): (ArrayBuffer[Range], ArrayBuffer[Long]) =
  var ranges: ArrayBuffer[Range] = ArrayBuffer()
  var ingredients: ArrayBuffer[Long] = ArrayBuffer()

  for line <- input do
    line match
      case s"$start-$end" => ranges += (Range(start.toLong, end.toLong))
      case "" =>
      case s"$id" => ingredients += id.toLong

  (ranges, ingredients)

Then, for performance reasons, I sorted the ranges by start number. And for each ingredient, I checked whether the identifier is contained in a range. The search stopped either when a compatible range was found, or when the ingredient ID is inferior to the start of a range. In both cases, it is useless to check the remaining ranges.

def solvePart1(input: List[String]): Int =
  var (ranges, ingredients) = parseIngredients(input)
  ranges = ranges.sortBy(x => x.start)
  var fresh = 0

  for ingredient <- ingredients do
    var i = 0
    var done = false
    while i < ranges.length && !done do
      if ranges(i).start <= ingredient && ranges(i).end >= ingredient then
        done = true
        fresh += 1
      if ingredient < ranges(i).start then
        done = true
      i += 1

  fresh

Part 2

Now, the task is to count the total number of integers contained in at least one range.

This part is more difficult, and cannot be solved by brute-force.

My idea was to transform the unsorted and overlapping list of ranges given in the input data, into a sorted list of disjoint ranges. First, the ranges were sorted by start. Then, I took the first two ranges, (s1, e1) and (s2, e2), and I checked if I could merge them. If this is the case (i.e if s2 <= e1 + 1) the ranges become a unique range (s1, max(e1, e2)) and I repeat the procedure with this merged range and the third range. Otherwise, I try to merge the second and the third range. This procedure is repeated until the end of the list is reached.

When the remaining ranges are disjoint, the number of included integers is simply : ∑ i=1 ne i−s i+1\sum_{i=1}^{n}e_i - s_i + 1

where s is_i and e ie_i are the start and the end of the i-th range.

def solvePart2(input: List[String]): Long =
  var (ranges, ingredients) = parseIngredients(input)
  ranges = ranges.sortBy(x => x.start)

  var i = 0
  while i < ranges.length do
    if i+1 < ranges.length && ranges(i+1).start <= ranges(i).end + 1 then
      val merged = Range(ranges(i).start, ranges(i).end.max(ranges(i+1).end))
      ranges = ranges.slice(0, i) ++ ArrayBuffer(merged) ++ ranges.slice(i+2, ranges.length)
    else
      i += 1

  ranges.map(x => x.end - x.start + 1).sum