Advent of Code 2023 - Day 3Gear Ratios

| Problem statement | Source code | Tags: Image processing

Part 1

I feel like the coding involved in this problem is more than I'd expect for a day 3 problem.

Since numbers must be laid out horizontally, I can discover all numbers in each row. Each number region is identified by starts[j] and lengths[j], which are the starting index and length of the number.

match_res <- gregexpr("[0-9]+", data[i])
matches <- match_res[[1]]
if (matches[1] == -1) {
  next
}
starts <- as.integer(matches)
values <- regmatches(data[i], match_res)[[1]]
lengths <- nchar(values)

Then, I need to check if the number is next to a symbol, by checking the whole neighborhood around it:

A A A A A
C 0 0 0 D
B B B B B

Because it's so intractable to extract a single character in R, my approach is to slice the substrings I marked A, B, C, and D, concatenate them, and then look for a symbol in this string. Out-of-bounds substr just returns the empty string, so I don't need to worry about that.

for (j in seq_along(starts)) {
  l <- starts[j] - 1
  r <- starts[j] + lengths[j]
  neighbors <- paste0(
    substr(data[i], l, l),
    substr(data[i], r, r),
    if (i > 1) substr(data[i - 1], l, r) else "",
    if (i < length(data)) substr(data[i + 1], l, r) else ""
  )
  if (grepl("[^0-9.]", neighbors)) {
    sum <- sum + as.integer(values[j])
  }
}

Part 2

I find the method of finding numbers and then finding symbols to be simpler, because if I do it the other way, then I need to extract the full range of the number given a starting index that might be in the middle of the number. For part 2 though, I need two numbers next to a single symbol, so searching for symbols anchored by numbers is harder than searching for numbers anchored by symbols.

Nevertheless I think it's doable. All I need is to keep a mapping from symbol location to the numbers that are next to it. Then I can iterate over the symbols and check if they have two numbers next to them. Then R gave me another bummer (one of many these days): not only does it not have tuple hashing (that's okay, JavaScript doesn't have it either, yet), but it doesn't have hashmaps whatsoever?? You can only imagine my disappointment. In the end I just used a list whose keys are serializations of symbol locations, and values are lists of numbers next to that symbol. Inside the loop for each number, not only do I check the existence of symbol neighbors, but I also need their values and locations.

l <- starts[j] - 1
r <- starts[j] + lengths[j]
if (substr(data[i], l, l) == "*") {
  neighbors <-
    add_neighbor(neighbors, key(i, l), as.integer(values[j]))
}
if (substr(data[i], r, r) == "*") {
  neighbors <-
    add_neighbor(neighbors, key(i, r), as.integer(values[j]))
}
rows <- integer(0)
if (i > 1) {
  rows <- c(rows, i - 1)
}
if (i < length(data)) {
  rows <- c(rows, i + 1)
}
for (row in rows) {
  above <- substr(data[row], l, r)
  matches <- gregexpr("\\*", above)[[1]]
  if (matches[1] != -1) {
    for (k in matches) {
      # If l == 0, then we need to add 1 to k to compensate for the
      # leftmost lost character in the above string
      gear_pos <- key(row, l + k - min(l, 1))
      neighbors <-
        add_neighbor(neighbors, gear_pos, as.integer(values[j]))
    }
  }
}

The other tricky part about location calculation is that if the number is at the leftmost edge of the string, then the left neighbor is out of bounds and thus doesn't exist. In this case, I need to add 1 to the index of the symbol neighbor to compensate for the lost character.

A * A A
0 0 0 D
B B B B

k = 2, l = 0 => gear_pos = key(row, 2)

A A * A A
C 0 0 0 D
B B B B B

k = 3, l = 1 => gear_pos = key(row, 3)

This problem wouldn't have been a problem in a 0-based language because then l would just be an offset.

Now I have a list of * locations and the numbers next to them. I just need to sum the products for the pairs of numbers.