Advent of Code 2022: Day 15

This challenge requires some mathematical thought to construct an efficient solution. My solution below produces the correct answers, but part 2 is slow. Part 1 became faster when I decided to compute ranges for a row, rather than brute-force the calculation for each point. But I don't have an efficient idea for solving part 2.

One problem to come back to.

Final Program

procedure main(inputs)
  local filename, row_number, max_range, sensors

  if *inputs = 3 then {
    filename := inputs[1]
    row_number := integer(inputs[2])
    max_range := integer(inputs[3])

    sensors := load_data(filename)

    # Part 1 solution
    write("Part 1 solution is: ", part_1(sensors, row_number))
    # Part 2 solution
    write("Part 2 solution is: ", part_2(sensors, max_range))
  } else {
    write("Provide a filename of data, row number and max-range")
  }
end

procedure part_1(sensors, row_number)
  local beacons, invalid_points, range, ranges, sensor

  ranges := get_ranges(sensors, row_number)
  invalid_points := 0
  beacons := set()
  every range := !ranges do {
    invalid_points +:= range[2] - range[1] + 1
    # find every beacon in this row
    every sensor := !sensors do {
      if sensor.beacon_y = row_number then {
        if range[1] <= sensor.beacon_x <= range[2] then 
          insert(beacons, sensor.beacon_x)
      }
    }
  }

  return invalid_points - *beacons
end

procedure part_2(sensors, max_range)
  local ranges, x, y

  every y := 1 to max_range do {
    ranges := get_ranges(sensors, y)

    if *ranges = 1 then { # edge case which never happens
      if ranges[1][1] > 0 then {
        return y
      } else if ranges[1][2] < max_range then {
        return max_range * 4000000 + y
      }
    } else if *ranges = 2 then { # this is only possibility, unless point on edge
      x := min(ranges[1][2], ranges[2][2]) + 1
      return x * 4000000 + y
    } else
      stop("Did not find solution")
    
  }
  stop("Did not find solution")
end

# Return a list of ranges for given row_number
procedure get_ranges(sensors, row_number)
  local c, higher, horizontal_distance, i, lower
  local did_merge, merged_ranges, range, ranges, sensor

  ranges := list()

  every sensor := !sensors do {
    if abs(sensor.y - row_number) < sensor.beacon_distance then {
      horizontal_distance := sensor.beacon_distance - abs(sensor.y - row_number)
      lower := sensor.x - horizontal_distance
      higher := sensor.x + horizontal_distance
      put(ranges, [lower, higher])
    }
  }

  # Merge all possible ranges
  every c := 1 to *ranges do {
    merged_ranges := list()
    every range := !ranges do {
      if *merged_ranges = 0 then 
        put(merged_ranges, range)
      else { # consider each range already in merged_ranges, and try to merge this range with it
        did_merge := 0
        every i := 1 to *merged_ranges do {
          if range[2] >= merged_ranges[i][1] & merged_ranges[i][2] >= range[1] then { # merge
            merged_ranges[i][1] := min(merged_ranges[i][1], range[1])
            merged_ranges[i][2] := max(merged_ranges[i][2], range[2])
            did_merge := 1
            break
          }
        }
        if did_merge = 0 then put(merged_ranges, range)
      }
    }
    ranges := merged_ranges
    if did_merge = 0 then break
  }

  return ranges
end

record sensor(x, y, beacon_x, beacon_y, beacon_distance)

procedure load_data(filename)
  local beacon_x, beacon_y, file, line, sensors, sensor_x, sensor_y

  file := open(filename, "r") | stop("Cannot open ", filename)
  sensors := list()
  
  every line := !file do {
    line ? {
      ="Sensor at x="
      sensor_x := integer(tab(upto(",")))
      =", y="
      sensor_y := integer(tab(upto(":")))
      =": closest beacon is at x="
      beacon_x := integer(tab(upto(",")))
      =", y="
      beacon_y := integer(tab(0))

      put(sensors, sensor(sensor_x, sensor_y, beacon_x, beacon_y,
        manhattan_distance(sensor_x, sensor_y, beacon_x, beacon_y)))
    }
  }

  close(file)

  return sensors
end

procedure manhattan_distance(x1, y1, x2, y2)
  return abs(x1-x2) + abs(y1-y2)
end

procedure min(a, b)
  if a < b then
    return a
  else
    return b
end

procedure max(a, b)
  if a > b then
    return a
  else
    return b
end