`<- as.double(readLines(here::here("2020", "day", "9", "input"))) input `

# 2020: Day 9

## Setup

## Part 1

We have to find the first number in the list which is *not* the sum of a pair of different numbers in the preceding 25 numbers.

There’s a nice trick for finding the pair of numbers in a vector that sum to a target that was doing the rounds on twitter in response to the Day 1 challenge: `intersect(input, 2020 - input)`

. For this challenge, we expand on that idea, writing it as a `check_sum`

function. Where there’s more than one pair, it won’t say which pair together, and if the number that’s half the target appears in the addends, it will only appear once in the output. However, for this challenge, we only need to know when there are *no* pairs that sum to the target, which will be the case when the length of the output of `check_sum`

is 0.

```
<- function(target, addends) {
check_sum intersect(addends, target-addends)
}
```

Then, it’s simply a case of iterating over windows of length 25, checking whether the following number is the sum of a distinct pair in that window, and returning the first one that isn’t.

```
<- function(vec, win = 25) {
find_invalid_num
for (i in (win+1):length(vec)) {
<- check_sum(vec[i], vec[(i-win):(i-1)])
check
if (length(check) == 0) return(vec[i])
}
}
find_invalid_num(input)
```

`[1] 507622668`

## Part 2

Find a contiguous set in the list that sums to the invalid number from Part 1, and add together the largest and smallest number in that range.

First, we note that after a certain point, all numbers in the input are larger than the target, so we don’t need to consider those. We reduce our input vector accordingly.

```
<- find_invalid_num(input)
target
<- input[1:(max(which(input <= target)))] input_reduced
```

To find the contiguous set in the list that sums to the target, we make use of `accumulate()`

from the `purrr`

package. Let the input list be \(x = (x_1, x_2,..., x_n)\). Then `accumulate(x, sum)`

returns \(a = (x_1, x_1 + x_2,..., \sum_{j=1}^n x_j)\). We check whether any element of this vector is equal to the target. If so we index into the input vector appropriately, sum the min and max in the range and we’re done. If not, we consider the sums of all windows starting with the second element of the input list, and so on.

```
<- function(input, target) {
contiguous_sum
<- length(input)
len
for (i in 1:len) {
<- purrr::accumulate(input[i:len], sum)
a <- a == target
b
if (sum(b) == 1) {
<- which(b)
output_length
<- input[i:(i + output_length - 1)]
contiguous_set
return(sum(range(contiguous_set)))
}
}
}
contiguous_sum(input_reduced, target)
```

`[1] 76688505`

I appreciate that there’s some redundant calculation in this method. The vectors of accumulated sums can contain numbers larger than the target (if writing our own loop, we could break as soon as the accumulated sum got too big). Also, in retrospect, we could have only run `accumulate`

once, then in the second iteration of the loop, subtracted `input[1]`

from the result, in the third iteration subtracted `input[2]`

from that result, etc. However, the function as written is concise and easy to understand, and gets our answer in around a second, so that will do!

## Session info

## Toggle

```
─ Session info ───────────────────────────────────────────────────────────────
setting value
version R version 4.3.1 (2023-06-16)
os macOS Sonoma 14.0
system aarch64, darwin20
ui X11
language (EN)
collate en_US.UTF-8
ctype en_US.UTF-8
tz Europe/London
date 2023-11-06
pandoc 3.1.1 @ /Applications/RStudio.app/Contents/Resources/app/quarto/bin/tools/ (via rmarkdown)
quarto 1.4.466 @ /usr/local/bin/quarto
─ Packages ───────────────────────────────────────────────────────────────────
package * version date (UTC) lib source
sessioninfo * 1.2.2 2021-12-06 [1] CRAN (R 4.3.0)
[1] /Users/ellakaye/Library/R/arm64/4.3/library
[2] /Library/Frameworks/R.framework/Versions/4.3-arm64/Resources/library
──────────────────────────────────────────────────────────────────────────────
```