Day 9 — Mirage Maintenance

Day 9 sees you out of the desert sandstorm and in an oasis.

While you wait for your next move, you decide to check out the delicate ecosystem the oasis provides. Using your handy dandy sensor instrument, you take some readings of key values and how they are changing over time.

There values are given as lists of numbers — each list is on a separate line, and each number is separated by a space:

1 2 3 4 5
2 4 6 8
1 2 3 5 8 13 21 34

To make your report complete, you need to predict the next value in each sequence. You can do so calculating the difference between each pair of numbers, and making a new list from those differences. If these aren’t all 0, then do the same thing with that list. Continue doing that until they are all 0.

Then, to predict the next value, add a new 0 to the end of the final list. Then, add a new value to the end of the list above, which is last current number in that list to the number you just added to the previous list. Keep going until you get to the original list.

An example is in order — let’s say you have the following:

0 4 8 12 16 20

First, generate lists of differences until they are all 0:

0   4   8   12  16  20
  4   4   4    4    4
    0   0    0    0

Now, add a new zero to end of the final list:

0   4   8   12  16  20
  4   4   4    4    4
    0   0    0    0    0

Next, add a new number to the list above by adding the last current number in that list to the number you just added to the previous list.

0   4   8   12  16  20  24
  4   4   4    4    4    4
    0   0    0    0    0

When you are done doing this for all the lists you are given, add all the predicted next values together for your final answer.

Approach

While the sample input only has positive numbers, my real input has negative numbers, as well as numbers in the billions, so i64 was the order of the day to make sure I had room for everything.

I also stored each list in a Vec<i64>, because I didn’t know how many numbers were in each list, and I thought I needed to add a new number to the end of each list as well. It turns out I didn’t, and you’ll see why later.

I also didn’t know how many new lists I needed to create to get to one with all zeroes, so after reading in each line with:

let history: Vec<_> = line
    .split_whitespace()
    .into_iter()
    .map(|i| i.parse::<i64>())
    .collect::<Result<Vec<i64>, std::num::ParseIntError>>().unwrap();

I pushed it on a new Vec<Vec<i64>> called sequences, which I used to track all the new lists I created for each individual list in my input.

After reading each line, I started my search for a list with all zeroes (with a quick helper function all_zeros()):

// Which list in the sequence are we currently working on
let mut count = 0;

// Start running the sequences until the last one is all zeros
while !all_zeros(&sequences[count]){
    let mut next: Vec<i64> = vec![];
    for x in 1..sequences[count].len(){
        next.push(sequences[count][x] - sequences[count][x-1]);
    }
    sequences.push(next);
    count += 1;
}

If the current list isn’t all zeros, I create a new list called next to hold the differences between each of the numbers in the previous list. When done, I push that list onto sequences and increment my count to keep track of which is the current list.

Once I have all these lists built, I can start figuring out the next values in each:

// Use this to track the last number in each sequence
let mut last = 0;

// Now we can work bacwards
for y in (0..count).rev(){
    let l = sequences[y].len();
    last = sequences[y][l-1] + last;
}
sum += last;

Rather than tack on a new value to each list, I opted to keep track of the last number in the current sequence, starting with 0. Working backwards, I get the last list in sequences and add it’s last value to last. I keep moving up until I run out of lists to process — at this point, last is the predicted value of the initial list I needed to find. I add that final value to sum, and were done.

Part 2

Of course, predicting the future is easy — ask any 16th century French astrologer. Predicting the past is where the real money is at.

For part 2, instead of adding a new value to the end of each list, you add it to the beginning, starting with your zero list. Again, add up all the new first values and report them for a final answer.

Part 2 Approach

Had I actually appended a new number to the end of each list in part 1, then this would have been a costlier challenge. It’s likely I would have followed that same logic to try to insert a new number onto the front of each Vec<i64>, which is a time-consuming operation (see why below).

As it stands, my technique of simply keeping a running value of last in part 1 worked well for part 2. After generating sequences in the exact same way, I used the cunningly named first to track the first numbers for each list, sutracting it from the first value in each list because we are working backwards:

// Use this to track the first number in each sequence
let mut first = 0;

// Now we can work bacwards
for y in (0..count).rev(){
    first = sequences[y][0] - first;
}
sum += first;

This was so easy, I almost felt I was cheating.

But why would it have been more costly to add a new value to the front of an array? To answer that, it helps to know a little about how Vec<> values are stored in memory.

Vec Layout

Most of this section is an oversimplification of what actually happens, but it will suffice to explain why inserting data at the front of a Vec is costlier than appending it at the end.

In Rust, Vecs have three parts:

1. A pointer (or reference for you Java folks) to the memory block containing the data for the Vec.
2. A capacity indicator showing how big the memory block is.
3. A length of how many elements are in the memory block.

When you define a Vec using vec![], it allocates enough memory to hold what you want to hold, i.e. whatever is in the [] part. We aren’t giving any data there in our case, so Rust doesn’t know how much memory to set aside initially. In this case, no memory is allocated until we store the first item. When that happens (when we execute next.push()), Rust allocates enough memory for that first item, and continues to expand the memory block when more items are added.

Expanding a memory block is called growing, and it basically means finding a (possibly) new memory block big enough to hold the current data in the Vec, as well as the new data you want to add. The contents of the old memory block are copied to the location of the new memory block (if necessary), and you now have a larger capacity Vec.

Note that the Vec grows whether you are appending data to the end of the Vec, or trying to insert data at the front of it. So why is appending to the end less costly that inserting at the beginning?

Push v. Insert

Let’s say Rust has just grown a memory block, and needs to move a Vec with 10 items to the new block with room for 11 items. The extra space for the 11th item in the new block will be at the end of the block, after the 10 items were copied over. This is because the copy operation starts at the beginning of the old block, and copies the data to the beginning of the new block.

Finding the address of this new empty space at the end of the new block is a reasonably fast and easy calculation. Take the address of the start of the new block, and add the result of multiplying the length of the existing Vec data and the size of the data being stored. In this case, expanding a Vec containing 10 i64 values means the empty space is 80 bytes (each i64 value is 64 bits or 8 bytes long) from the start of the block.

On the other hand, inserting data at the beginning of the Vec requires the data already in the block to move forward to make room for it at the start of the block. In C, this is done by the memmove() function — in Rust, it’s called ptr::copy(). In either case, it’s a relatively expensive operation, as ptr::copy needs to check for overlapping memory ranges and which way items are being copied, among other things. In our Vec<i64>, each item needs to move 8 bytes to the right to make room, which takes some time to ensure we don’t lose any data.

As mentioned above, this is a very simplified version of what really happens. For the full exhaustive description, check out the Rustnomicon. It covers all sorts of implementation specifics for Rust, including concurrency, type coercions, ownership, and much more.

Summary

As always, my code can be found here — comments and PR’s are always welcome!

Sometimes the choices made at the beginning of a challenge make the later complications easier. This was one of those times — by choosing to not append new data to the end of my part 1 lists, I didn’t get caught trying to insert new items at the front of my part 2 lists.