Day 14 Part 1 - That looks a lot like a grid

Ok, I've reached the part of Advent of Code where I'm picking and choosing my puzzles based on whether I can grok the problem straight away or not, which normally bites me for part 2, but lets try this anyway.

This one has robots that move in a striaght line according to a start point and a velocity. We can draw a grid of the robots and see where they all move to from turn to turn and the examples do indeed have a nice grid laid out, like this:

1.12.......
...........
...........
......11.11
1.1........
.........1.
.......1...

However, looking at the problem description, with robots moving in a straight line, and wrapping the world as if it's a donut (so from top to bottom and right to left, actually a toroidal plane), this is actually a very simple maths transformation.

We want to do that for hundreds of robots and varying velocities and find out which quadrant they all end up in.

In the first example we have a robot who starts a (2,4) and has a velocity of (2,-3). (note that in a moment of mass confusion, for the examples, they have y going down, so 0,0 is the top left corner)

He starts looking like this:

...........
...........
...........
...........
..1........
...........
...........

and after one move is here:

...........
....1......
...........
...........
...........
...........
...........

But if we look at that as coordinates, he starts at (2,4) and after 1 move is at (4,1) and after a second move is at (6,5). What we're actually saying is that the end coordinate of any given robot is simply start + velocity * magnitude with the coordinates then produced modulo the height and width of the toroid.

So I'm going to create a new Toroidal Coordinate that takes not just a coordinate, but references a limit, and when added or multiplied, will use the modulo. We can then just add the robots velocities times the number of seconds to the original coordinates and count the robots in the quadrants.

Here's our coordinate and our vector class (you can see my writeup for Day 4 to see why it's a vector).

#[derive(Debug, Copy, Clone, PartialEq, Hash, Eq)]
pub struct ToroidalCoordinate {
    pub x: i32,
    pub y: i32,
    pub width: i32,
    pub height: i32,
}

#[derive(Debug, Copy, Clone, PartialEq, Hash, Eq)]
pub struct Vector {
    pub dx: i32,
    pub dy: i32,
}

Everything else is standard, but let's look at the Add function

/* We want to add a Vector to Coordinate to result in a new Coordinate, which is std::ops:Add to enable us to use the + symbol in the compiler */
impl std::ops::Add<Vector> for ToroidalCoordinate {
    type Output = Self;
    fn add(self, other: Vector) -> Self {
        Self {
            x: (self.x + other.dx).rem_euclid(self.width),
            y: (self.y + other.dy).rem_euclid(self.height),
            width: self.width,
            height: self.height,
        }
    }
}

The rem_euclid is a bit funky, and that's because like many languages, rust has a remainder operator, rather than a modulo operator. The remainder operator works out what the remainder is if you divide a by b, so if you do 7's into 4, you have 1 4, and a remainder of 3. This acts like working out the modulo for positive numbers, but negative numbers are slightly more complicated. The way one works out the modulo of a negative number is supposed to work more like clock arithmatic, so for example, -1's into 4. How many 4's go into -1, none, and what's left is a -1. But in modulus arithmatic, we actually expect the answer to be 3, because any number lower than 0 should wrap round to the modulo and keep going. This is true if there are bigger numbers, so 4's into -5, is 1 4, and then remainder of -1. So our remainder will give the wrong number unless we use a specific function for euclidian remainders (which was a new term to me, but is another term for modulo operations apparently).

Moving a paranoid android

Anyway, this works in our tests, so let's create some robots, parse the input lines, and try moving them in the test environment.

let re =
    Regex::new(r"p=(\d+),(\d+) v=(-?\d+),(-?\d+)").expect("Regex compilation shouldn't fail!");
re.captures_iter(input)
    .map(|c| c.extract())
    .map(|(_, [x, y, dx, dy])| Robot {
        position: ToroidalCoordinate {
            x: x.parse::<i32>().unwrap(),
            y: y.parse::<i32>().unwrap(),
            width: unsafe { WORLD_WIDTH },
            height: unsafe { WORLD_HEIGHT },
        },
        velocity: Vector {
            dx: dx.parse::<i32>().unwrap(),
            dy: dy.parse::<i32>().unwrap(),
        },
    })
    .collect()

So we grab the numbers from each line, we map them into groups of x,y,dx and dy. I've realised that the test and the real run use a different standard height and width, and the rust aoc create I use doesn't have an easy way to inject variables, so I've set up a mutable static variable, which is multi-thread unsafe, but lets me define the width and height to 103 and 101 in the production run, but to 11 and 7 in the test runs. I've then taken the original test case for 100 runs and I've used map to convert robots to tuples for the test to show where they'll be after 100 iterations:

let robots = input_generator(input);
#[rustfmt::skip]
assert_eq_unordered!(
    robots
        .iter()
        .map(|r|r.position_at(100))
        .map(|robot|(robot.position.x, robot.position.y))
        .collect(), 
    vec![
        (6,0), (6,0), (9,0),
        (0,2),
        (1,3),(2,3),
        (5,4),
        (3,5),(4,5),(4,5),
        (1,6),(6,6),
]);

Finally, we need to count robots in each given quadrant, with the peculiar attribute that any robots on the middle line are simply not counted (which is I suspect to prevent us from simply counting all the robots). I think there should be a smart way of doing this, but the simplest I can think of is to have a partitionX and partitionY value, and then go through all the robots, if we return 1 for anything less than partitionX and less than partitionY; return 2 for anything greater than partitionX but still less than partitionY; return 3 for anything less than partionX and greater than partition Y; and finally return 4 for anything greater than partitionX and PartitionY - We'll get a 1,2,3 or 4, along with a default of 0 for anthing on the line.

pub fn count_quadrants(
    robots: &Vec<Robot>,
    partition_x: i32,
    partition_y: i32,
) -> HashMap<i32, usize> {
    robots
        .iter()
        .map(|r| {
            if r.position.x < partition_x && r.position.y < partition_y {
                1
            } else if r.position.x > partition_y && r.position.y < partition_y {
                2
            } else if r.position.x < partition_x && r.position.y > partition_y {
                3
            } else if r.position.x > partition_x && r.position.y > partition_y {
                4
            } else {
                0
            }
        })
        .counts()
}

Counts here is an adapter from the itertools crate that turns a list of values into essentially a counter, a map of values to count of values.

Debugging and tidying up

This didn't work, and you might have spotted the error above (left in on purpose). But looking at my solution I couldn't work out what was going wrong. I decided that I must be adding up my numbers wrong, and the 0 in that map above made me uncomfrotable.

Rust, and most functional languages, has a concept for computation on things that may or may not have a valid number, an Option. An option is a special type that can either be Some value, or can be None. You can think of it a bit like a list or vector that either contains a value, or doesn't contain anything. This means we can return Some or None values, and that will look like Some(1), Some(2), None, Some(1), or if you prefer something like [[1], [2], [1]]. We can then flatten a list of Options, which folds the None values away silently. This resulted in the below code

.map(|r| {
    if r.position.x < partition_x && r.position.y < partition_y {
        Some(1)
    } else if r.position.x > partition_y && r.position.y < partition_y {
        Some(2)
    } else if r.position.x < partition_x && r.position.y > partition_y {
        Some(3)
    } else if r.position.x > partition_x && r.position.y > partition_y {
        Some(4)
    } else {
        None
    }
})
.collect::<Vec<Option<u8>>>()

and much nicer code that consumes it to work out the sum

count_quadrants(
    &input.iter().map(|r| r.position_at(100)).collect(),
    WORLD_WIDTH / 2,
    WORLD_HEIGHT / 2,
)
.iter()
.flatten()
.counts()
.values()
.product()

This takes the list of Options, flattens them back down to just numbers, counts the numbers, takes only the counts, and multiplies them all together.

This worked, but while rewriting this, I spotted the error...

if r.position.x < partition_x && r.position.y < partition_y {
    Some(1)
} else if r.position.x > partition_y && r.position.y < partition_y {

We shouldn't ever be comparing the x position to the y partition! Rewriting that to compare to partition_x gives us the correct answer.

I note that the test data didn't catch this, and due to the puzzle, it was very difficult to generate test data. With the height of 7 and width of 11, there was only 2 lines difference, and that didn't seem to catch out any test input.

Part 2