Advent of Code 2023 - Day 5If You Give A Seed A Fertilizer

| Problem statement | Source code | Tags: MathematicsPuzzle

Part 1

Let me reformulate the problem. There is a list of functions, each piecewise linear of the form

We need to map a list of numbers through these functions. To map a single number, we just need to check which piece applies to it, and add the corresponding $d_i$ to it. It's not a bad idea to use binary search, but since $n$ is small, a linear search suffices.

map_seed <- function(seed, map) {
  applicable <- map[map$from_start <= seed & map$from_end > seed, ]
  if (nrow(applicable) == 0) {
    # Identity mapping if there are no applicable pieces
    return(seed)
  }
  seed + applicable$diff[1]
}

(My input is parsed to a list of dataframes, each one containing columns from_start, from_end, and diff, which are $s_i$, $e_i$, and $d_i$ respectively.)

Part 2

Now we need to map ranges of numbers. Because the ranges are big, it's infeasible to map each number individually. However, there's a key observation: most points' relative order do not change. For example, if $p$ and $p+1$ are both in the target range and are mapped by the same function piece for every function, then their relative order never changes, and $p+1$ is always larger than $p$. When can $p+1$ become a candidate for the minimum mapped value? Only when $p$ and $p+1$ are mapped by different pieces of some function—in other words, when $p$ is the ending point of one piece and $p+1$ is the starting point of another piece.

So, consider one mapping step:

We can map each range one by one. First, we find all pieces that overlap with the input range. The first and last piece may not be fully covered by the range; they are clipped to the input range. For example, in the diagram above, the blue range is mapped by a single piece that's greater than the range, so the piece is clipped. We iterate through these pieces in order. It is guaranteed that the pieces are fully covered by the input range (although might not be vice versa). Therefore we can just apply the mapping to the endpoints of each piece to get its output range. If there's a gap between this piece and the previous one (including at the beginning and end of the input range—we can pretend there's a piece that ends immediately before the input range, and another that starts immediately after), the gap is filled by an identity mapping.

map_range <- function(range, map) {
  # All pieces that overlap with the range
  applicable <- map[!(map$from_end <= range[1] | map$from_start >= range[2]), ]
  n <- nrow(applicable)
  if (n == 0) {
    # Identity mapping if there are no applicable pieces
    return(list(range))
  }
  # Clip the first and last pieces to the range
  applicable[1, "from_start"] <- max(applicable[1, "from_start"], range[1])
  applicable[n, "from_end"] <- min(applicable[n, "from_end"], range[2])
  ranges <- list()
  last_end <- range[1]
  for (i in seq_len(n)) {
    piece <- applicable[i, ]
    if (piece$from_start > last_end) {
      # Identity mapping if there's no corresponding piece
      ranges <- push(ranges, c(last_end, piece$from_start))
    }
    ranges <- push(ranges, c(piece$from_start, piece$from_end) + piece$diff)
    last_end <- piece$from_end
  }
  if (last_end < range[2]) {
    ranges <- push(ranges, c(last_end, range[2]))
  }
  ranges
}