2023: Day 9 - Mirage Maintenance

Published

December 9, 2023

Setup and notes

Puzzle input: series of values about the oasis ecosystem. Each line corresponds to the history of a single value.

For example:

0 3 6 9 12 15
1 3 6 10 15 21
10 13 16 21 30 45

Must create environmental report with prediction of the next value in each series.

To do this, start by making a new sequence from the difference at each step of your history. If that sequence is not all zeroes, repeat this process, using the sequence you just generated as the input sequence. Once all of the values in your latest sequence are zeroes, you can extrapolate what the next value of the original history should be.

Example:

0   3   6   9  12  15
  3   3   3   3   3
    0   0   0   0

To extrapolate, start by adding a new zero to the end of your list of zeroes; because the zeroes represent differences between the two values above them, this also means there is now a placeholder in every sequence above it:

0   3   6   9  12  15   B
  3   3   3   3   3   A
    0   0   0   0   0

In this example, the next value in sequence (B) is 18.

Note that for each series it may be necessary to obtain a different number of sequences until reaching the all-zero differences.

1   3   6  10  15  21
  2   3   4   5   6
    1   1   1   1
      0   0   0

Analyze your OASIS report and extrapolate the next value for each history. What is the sum of these extrapolated values?

Part 1

I think it’s a good idea to load this data as a list of vectors (each row in the input would be a vector).

library(tidyverse)
library(here)

input <- here("2023/day/9/input")  %>%
  read_lines() %>%
  str_split(" ") %>%
  map(as.numeric) %>%
  map(list)

input[1:5]

[[1]]
[[1]][[1]]
 [1]      3     10     23     46     99    234    563   1310   2904   6131
[11]  12351  23745  43470  75464 123501 189097 268370 349700 418439 484617
[21] 669380


[[2]]
[[2]][[1]]
 [1]     16     41     77    119    171    265    488   1017   2162   4417
[11]   8519  15515  26837  44385  70618 108653 162372 236537 336913 470399
[21] 645167


[[3]]
[[3]][[1]]
 [1]      20      45      91     182     351     648    1157    2027    3543
[10]    6296   11556   22009   43088   85209  167316  322244  604526 1101399
[19] 1947905 3347136 5596837


[[4]]
[[4]][[1]]
 [1]      24      50      87     141     223     341     487     621     653
[10]     420    -352   -2121   -5670  -12365  -24598  -46505  -85074 -151786
[19] -264963 -453031 -758943


[[5]]
[[5]][[1]]
 [1]       13       31       76      172      351      645     1075     1649
 [9]     2399     3508     5604    10347    21558    47460   105396   232221
[17]   507493  1104469  2398816  5191706 11149877

Now, for each item of the list, I should iteratively add diffs until all of the elements of the last diff are zero.

Let’s do it for a base case:

example_case <- input[[1]]

last_vector <- example_case[[1]]

output <- example_case

while (any(last_vector) != 0) {
  last_vector <- diff(last_vector)
  output <- append(output, list(last_vector))
}

output

[[1]]
 [1]      3     10     23     46     99    234    563   1310   2904   6131
[11]  12351  23745  43470  75464 123501 189097 268370 349700 418439 484617
[21] 669380

[[2]]
 [1]      7     13     23     53    135    329    747   1594   3227   6220
[11]  11394  19725  31994  48037  65596  79273  81330  68739  66178 184763

[[3]]
 [1]      6     10     30     82    194    418    847   1633   2993   5174
[11]   8331  12269  16043  17559  13677   2057 -12591  -2561 118585

[[4]]
 [1]      4     20     52    112    224    429    786   1360   2181   3157
[11]   3938   3774   1516  -3882 -11620 -14648  10030 121146

[[5]]
 [1]     16     32     60    112    205    357    574    821    976    781
[11]   -164  -2258  -5398  -7738  -3028  24678 111116

[[6]]
 [1]    16    28    52    93   152   217   247   155  -195  -945 -2094 -3140
[13] -2340  4710 27706 86438

[[7]]
 [1]    12    24    41    59    65    30   -92  -350  -750 -1149 -1046   800
[13]  7050 22996 58732

[[8]]
 [1]    12    17    18     6   -35  -122  -258  -400  -399   103  1846  6250
[13] 15946 35736

[[9]]
 [1]     5     1   -12   -41   -87  -136  -142     1   502  1743  4404  9696
[13] 19790

[[10]]
 [1]    -4   -13   -29   -46   -49    -6   143   501  1241  2661  5292 10094

[[11]]
 [1]   -9  -16  -17   -3   43  149  358  740 1420 2631 4802

[[12]]
 [1]   -7   -1   14   46  106  209  382  680 1211 2171

[[13]]
[1]   6  15  32  60 103 173 298 531 960

[[14]]
[1]   9  17  28  43  70 125 233 429

[[15]]
[1]   8  11  15  27  55 108 196

[[16]]
[1]  3  4 12 28 53 88

[[17]]
[1]  1  8 16 25 35

[[18]]
[1]  7  8  9 10

[[19]]
[1] 1 1 1

[[20]]
[1] 0 0

Now let’s turn this into a function and apply it to the original list through purrr:map

obtain_diffs <- function(history) {
  last_vector <- history[[1]]

  output <- history

  while (any(last_vector != 0)) {
    last_vector <- diff(last_vector)
    output <- append(output, list(last_vector))
  }

  output
}

obtain_diffs(input[[1]])

[[1]]
 [1]      3     10     23     46     99    234    563   1310   2904   6131
[11]  12351  23745  43470  75464 123501 189097 268370 349700 418439 484617
[21] 669380

[[2]]
 [1]      7     13     23     53    135    329    747   1594   3227   6220
[11]  11394  19725  31994  48037  65596  79273  81330  68739  66178 184763

[[3]]
 [1]      6     10     30     82    194    418    847   1633   2993   5174
[11]   8331  12269  16043  17559  13677   2057 -12591  -2561 118585

[[4]]
 [1]      4     20     52    112    224    429    786   1360   2181   3157
[11]   3938   3774   1516  -3882 -11620 -14648  10030 121146

[[5]]
 [1]     16     32     60    112    205    357    574    821    976    781
[11]   -164  -2258  -5398  -7738  -3028  24678 111116

[[6]]
 [1]    16    28    52    93   152   217   247   155  -195  -945 -2094 -3140
[13] -2340  4710 27706 86438

[[7]]
 [1]    12    24    41    59    65    30   -92  -350  -750 -1149 -1046   800
[13]  7050 22996 58732

[[8]]
 [1]    12    17    18     6   -35  -122  -258  -400  -399   103  1846  6250
[13] 15946 35736

[[9]]
 [1]     5     1   -12   -41   -87  -136  -142     1   502  1743  4404  9696
[13] 19790

[[10]]
 [1]    -4   -13   -29   -46   -49    -6   143   501  1241  2661  5292 10094

[[11]]
 [1]   -9  -16  -17   -3   43  149  358  740 1420 2631 4802

[[12]]
 [1]   -7   -1   14   46  106  209  382  680 1211 2171

[[13]]
[1]   6  15  32  60 103 173 298 531 960

[[14]]
[1]   9  17  28  43  70 125 233 429

[[15]]
[1]   8  11  15  27  55 108 196

[[16]]
[1]  3  4 12 28 53 88

[[17]]
[1]  1  8 16 25 35

[[18]]
[1]  7  8  9 10

[[19]]
[1] 1 1 1

[[20]]
[1] 0 0

series_with_diffs <- map(input, obtain_diffs)
series_with_diffs[[1]]

[[1]]
 [1]      3     10     23     46     99    234    563   1310   2904   6131
[11]  12351  23745  43470  75464 123501 189097 268370 349700 418439 484617
[21] 669380

[[2]]
 [1]      7     13     23     53    135    329    747   1594   3227   6220
[11]  11394  19725  31994  48037  65596  79273  81330  68739  66178 184763

[[3]]
 [1]      6     10     30     82    194    418    847   1633   2993   5174
[11]   8331  12269  16043  17559  13677   2057 -12591  -2561 118585

[[4]]
 [1]      4     20     52    112    224    429    786   1360   2181   3157
[11]   3938   3774   1516  -3882 -11620 -14648  10030 121146

[[5]]
 [1]     16     32     60    112    205    357    574    821    976    781
[11]   -164  -2258  -5398  -7738  -3028  24678 111116

[[6]]
 [1]    16    28    52    93   152   217   247   155  -195  -945 -2094 -3140
[13] -2340  4710 27706 86438

[[7]]
 [1]    12    24    41    59    65    30   -92  -350  -750 -1149 -1046   800
[13]  7050 22996 58732

[[8]]
 [1]    12    17    18     6   -35  -122  -258  -400  -399   103  1846  6250
[13] 15946 35736

[[9]]
 [1]     5     1   -12   -41   -87  -136  -142     1   502  1743  4404  9696
[13] 19790

[[10]]
 [1]    -4   -13   -29   -46   -49    -6   143   501  1241  2661  5292 10094

[[11]]
 [1]   -9  -16  -17   -3   43  149  358  740 1420 2631 4802

[[12]]
 [1]   -7   -1   14   46  106  209  382  680 1211 2171

[[13]]
[1]   6  15  32  60 103 173 298 531 960

[[14]]
[1]   9  17  28  43  70 125 233 429

[[15]]
[1]   8  11  15  27  55 108 196

[[16]]
[1]  3  4 12 28 53 88

[[17]]
[1]  1  8 16 25 35

[[18]]
[1]  7  8  9 10

[[19]]
[1] 1 1 1

[[20]]
[1] 0 0

Cool, now the next step is to make the predictions/imputations using this data. Again, all the series behave independently, so they’re suitable for functional programming (creating functions and then apply them through purrr::map).

example_case <- series_with_diffs[[1]]

current_element <- example_case[[20]]

current_element[length(current_element)]

[1] 0

# I have to "iterate in reverse" from the last element to the first one
current_diff <- 0
for (i in rev(seq_along(example_case))) {
  current_seq <- example_case[[i]]
  last_el_seq <- current_seq[length(current_seq)]
  current_seq <- c(current_seq, last_el_seq+current_diff)
  example_case[[i]] <- current_seq

  current_diff <- current_seq[length(current_seq)] # new element in the sequence
}

The code above solves for a single, example case. Now I’ll wrap it in a function and apply it to each of the sequences in the list:

add_to_history <- function(history_with_diffs) {

  current_element <- history_with_diffs[[length(history_with_diffs)]]

  # I have to "iterate in reverse" from the last element to the first one
  current_diff <- 0
  for (i in rev(seq_along(history_with_diffs))) {
    current_seq <- history_with_diffs[[i]]
    last_el_seq <- current_seq[length(current_seq)]
    current_seq <- c(current_seq, last_el_seq+current_diff)
    history_with_diffs[[i]] <- current_seq

    current_diff <- current_seq[length(current_seq)] # new element in the sequence
  }

  history_with_diffs
}

series_with_diffs2 <- map(series_with_diffs, add_to_history)

Now I have to get the last element of the first sequence (~.[[1]][length(.[[1]])]) in each element of series_with_diffs2 and add all them up.

map_dbl(series_with_diffs2, ~.[[1]][length(.[[1]])]) %>%
  sum()

[1] 2174807968

The solution is correct!

Part 2

Part 2 is just extrapolating backwards instead of forwards. I’m sure that I can do this by just adjusting some parameters in the functions I’ve already created.

add_to_history_backwards <- function(history_with_diffs) {

  current_element <- history_with_diffs[[length(history_with_diffs)]]

  # I have to "iterate in reverse" from the last element to the first one
  current_diff <- 0
  for (i in rev(seq_along(history_with_diffs))) {
    current_seq <- history_with_diffs[[i]]
    first_el_seq <- current_seq[1]
    current_seq <- c(first_el_seq-current_diff, current_seq)
    history_with_diffs[[i]] <- current_seq

    current_diff <- current_seq[1] # new element in the sequence
  }

  history_with_diffs
}

map(series_with_diffs, add_to_history_backwards) %>%
  map_dbl(~.[[1]][1]) %>%
  sum()

[1] 1208

It’s correct too!