Day 14 – Parabolic Reflector Dish

The Advent of Code has been running for a few days by now, but I’m still writing and posting my thoughts, findings, and code from last year’s contest.

Day 14 follows the mirrors from the previous day. As always, read the problem description for a better, more detailed, explanation.

You find a parabolic reflector dish which is deformed by the presence of lots of rocks. The dish can tilt in four directions, and when it does, some of the rocks will roll in the direction of the tilt. They only roll to the edge of the dish, however, and won’t roll past any other rocks that are in the way. Some rocks are stationary and won’t move at all — they just block the movement of the rolling rocks (No relation).

When the platform tilts north, the rolling rocks move as far as they can go. Each rock adds to the load on the north side of the platform, which is equal to the distance that rock is from the southern edge.

So for part one, you tilt the platform so all the rocks move to the north, and calculate the load on the north side for all the moving rocks.

Approach

My approach here was fairly straight forward — find all the rocks that can move, and move them. The best way to do this is to start one row below the north edge (since nothing will move past that). Working left to right, check each space. If that space is a movable rock, check if it can move north. If so, move it and replace it with an empty space. Rinse and repeat, then calculate the load.

Part 1

Start by reading the input file, and converting it to a Vec<Vec<char>> called platform. Then, to make things easy, you can make helper functions to do the actual work.

Start with one which will handle moving the rocks when the platform tilts north:

fn tilt_north(mut platform: Vec<Vec<char>>) -> Vec<Vec<char>>{

    for y in 1..platform.len(){
        for x in 0..platform[y].len(){
            // If it's a round rock, and there is an open space above it
            let mut y1 = y;
            while y1 >= 1 && platform[y1][x] == 'O' && platform[y1-1][x] == '.'{
                platform[y1][x] = '.';
                platform[y1-1][x] = 'O';
                y1 -= 1;
            }
        }
    }

    platform
}

In keeping with the Rust way of handling data, tilt_north() takes ownership of platform, and returns the modified Vec<Vec<char>>. You could also use &mut platform if you wanted to modify the reference, but I thought it was better to take ownership and give back the changed Vec.

Since you’re moving everything to the north, you start one row below that with the for y in 1..platform.len() loop. You have to process every column though, so next you start the for x in 0..platform[y].len() loop.

The mut y1 tracks the current vertical position of movable rocks, starting with the current y position. If this position is, indeed, a movable rock, then check whether the space to the north of it (at platform[y1-1][x]) is open. If so, move the rock there, replace it with an open space, and change y1 to track the new position of the movable rock. Rinse and repeat for every row, then return the new platform.

Once the platform has been tilted and all the rocks moved, you need to figure out the load on the north support. Again, a helper function makes this easier:

fn calc_load(platform: &Vec<Vec<char>>) -> usize {
    let mut load = 0;

    let bottom = platform.len();
    // Now calculate the load
    for y in 0..platform.len(){
        for x in 0..platform[y].len(){
            if platform[y][x] == 'O'{
                load += bottom - y;
            }
        }
    }
    load
}

You start with a zero load, and since the load of any rock is the distance from the south edge, you use the length of the Vec<> as that edge. Then, you simply loop over the whole platform, adding the load of each rock to load, and return it when you’re done.

With these helpers, the part 1 code looks like this:

fn part1(lines: &Vec<String>) -> usize{

    // Convert to a matrix of chars
    let mut platform = convert_to_char_array(&lines);

    // Move all the rocks to the north
    platform = tilt_north(platform);

    // Return the load
    calc_load(&platform)
}

Which gives the right answer for both sample and real data.

Part 2

The complication for part 2 requires you to do a similar action as part 1, but tilting the platform in all four directions in order (which I call a "spin") several times, then calculating the load on the north supports.

By "several times", we mean 1,000,000,000 (that’s billion with a B). Yeah — it’s a lot.

The first part is relatively easy — since you’ve got code for tilting to the north, modifying that to handle tilting the other three directions is just a matter of changing some numbers and some loop variables. Here’s an example:

fn tilt_east(mut platform: Vec<Vec<char>>) -> Vec<Vec<char>>{

    for x in (0..platform[0].len()-1).rev(){
        for y in 0..platform.len(){
            // If it's a round rock, and there is an open space to the right
            let mut x1 = x;
            while x1 < platform[0].len()-1 && platform[y][x1] == 'O' && platform[y][x1+1] == '.'{
                platform[y][x1] = '.';
                platform[y][x1+1] = 'O';
                x1 += 1;
            }
        }
    }

    platform
}

Because you’re tilting to the right (aka east), the outer loop tracks columns from the left index of 0 to one short of the right, which is platform[0].len()-1. You use .rev() to get those numbers in reverse order. Otherwise, the code should be a straightforward port.

The code to calculate the load is the same, so no changes are needed there.

The sticker is the 1,000,000,000 spin cycles. If this contest has taught me anything over the years, it’s that when the problem mentions 1,000,000,000 (or more) of anything, simply iterating over your initial solution will take too much time.

Don’t believe me? Here’s a fact you can calculate on your own:

One million seconds is roughly 11.6 days.
One billion seconds is roughly 31.7 years.

Even if you can do 1,000 iterations every second, your code will still take 11.6 days to finish. The lesson here is: if you have to do one billion iterations of anything, you need to find a better solution than just for x in 0..1000000000.

Repeating Patterns

In this case, you can make the observation (or assumption) that, after a certain number of spins, the rocks wind up in a configuration they’ve been in before. Once they’re in that configuration, they will return to it after a certain number of spins have passed, and never get out of it.

In other words, the spins will create a larger cycle of rock configurations, which will repeat themselves ad infinitum. You just need some way to detect if the rocks have entered that cycle.

To find a rock cycle, you track every state the rocks get into after every spin. The easiest way to do that is to store the rock positions after every spin, along with the number of spins it took to get there. You can turn the Vec<Vec<char>> of the platform into a String, then store that data in a HashMap:

// Save states
let mut states: HashMap<String, usize> = HashMap::new();

...

// Convert the platform to a string
let pstr = make_str(&platform);

// Is the state in our hashset
if !states.contains_key(&pstr){
    states.insert(pstr, count);
}

Why turn the platform into an immutable str? Because an immutable string is hashable, which means we can store it in the HashMap.

So how do you find a cycle in something like this? Well, in this case, if the state of the platform is ever repeated, it will go through the same sequence for every spin. So, if pstr is found as a key in states, you know that spin is the start of a new rock cycle.

Of course, to make this work properly, you need to also track the platform load for each spin — a simple Vec<usize> will do the trick there.

Now we need some math, and an example will help figure out what we need to do.

Math Incoming

Let’s say we’re only tracking 200 spins, and after 5 unrelated numbers, the loads then cycle every seven spins. What is the load after the 200th spin?

So the numbers start like this (with zero-based indexes):

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	…
10	11	12	13	14	1	2	3	4	5	6	7	1	2	3	4	5	6	7	1	…

The pattern from cycle 5 through 11 repeats forever, and we want to know what the 200th number in this sequence will be?

To solve this, we need to know the following:

How many iterations will we do? In this case, it’s 200.
Where is the start of initial cycle? In this case, it’s at cycle 5.
Where is the start of the current cycle? In this case, you see it at cycle 12.

We know our cycle is $12-5 = 7$ spins long, and we can quickly figure out that $200 / 7 = 28$ complete spins will have been done. That leaves $200\mod\ 7 = 4$ spins, so we should look at the fourth item in this list.

But that’s not quite right — the cycle doesn’t start until the 6th item, which means we have fewer than 200 total spins available — we only have 195 spins, since the first five aren’t part of it. In this case, that’s $200 – 5$, or the index of the start of the cycle. So we figure $195\mod\ 7 = 6$. But we don’t need the sixth item, but the sixth item from start, which is at index 11, or the number 7.

So, lets piece this together with some variables, so we can generalize

start = 5 is where the cycle starts
current = 12 is where the current repeat was found
total = 200 is how many spins we’re going to take.

With this, we can figure out:

The number of items to check: count = total - start
The length of the cycle: cycle_len = current - start
The item in the cycle we want: item_num = count % cycle_len
The item in the list we want: item_index = item_num + start

Let’s do that with what we have above, but only 20 cycles. The answer we want is 2:

start = 5
current = 12
total = 20
count = total - start         # 15
cycle_len = current - start   # 7
item_num = count % cycle_len  # 15%7 = 1
item_index = item_num + start # 1 + 5 = 6, item[6] = 2

In our problem, total = 1000000000, current is the current iteration we are on, and start is the index of the previous occurrence of this platform pattern, giving us the following code:

// Save the load  
loads.push(calc_load(&platform));

// Is the state in our hashset
if !states.contains_key(&pstr){
    states.insert(pstr, current);
} else {
    let start = states.get(&pstr).unwrap();
    return loads[(1000000000-start)%(current-start)+start];
}

You don’t need to do too many iterations to find the repeat — in my case, it happened within 300 iterations, so I tailored my loop accordingly.

Summary

I originally thought I needed to do some fancy cycle counting for this one — that’s why, when you look at my code, you’ll see an unused function check_cycle(loads: &Vec<usize>). I wrote it, but it didn’t work and I left it there as a warning for future generations.

This problem represents one common way to solve problems with massive numbers — look for patterns, and do math, not iterations. Other problems in the past used things like modular arithmetic to handle huge numbers. One thing is certain — there will always be new problems and techniques to learn to solve them!

Cogito Coders

I think (like a coder), therefore I am (a coder).

Day 14 – Parabolic Reflector Dish