Perfectly Spherical Houses in a Vacuum

AoC 2015 with Rust - Day 3

Jul 17 23 • 9 min read

Source of the final solution

Part 1

Santa is delivering gifts in a two-dimensional grid of houses. He gets instructions over the radio by arrow characters (>, <, v, ^) and moves according to these. He delivers a gift in each move, but sometimes he gets wrong instructions and revisits some of the locations he has already visited.

For the first part, I want to solve how many houses get at least 1 present. Starting location will also count as one present delivered.

For example,

  • > delivers presents to 2 houses: one at the starting location, and one to the east.
  • ^>v< delivers presents to 4 houses in a square, including twice to the house at his starting/ending location.

If there is a data type that can hold non-duplicate items in Rust, like some sort of set, I can use it. I can iterate over the instructions, call a move() function that takes the direction character and either returns the next coordinate which can then be added to hash set. These coordinates can maybe be some sort of struct. I will also copy file reading stuff from the previous challenge.

struct Coordinate {
    x: i32,
    y: i32,
}

fn main() {
    let starting_coordinates = Coordinate { x: 0, y: 0 };

    let new_coord = move_santa('v', starting_coordinates);

    println!("{:?} {:?}", new_coord.x, new_coord.y)
}

fn move_santa(direction: char, current_coordinate: Coordinate) -> Coordinate {
    match direction {
        '^' => Coordinate {
            x: current_coordinate.x,
            y: current_coordinate.y + 1,
        },
        '>' => Coordinate {
            x: current_coordinate.x + 1,
            y: current_coordinate.y,
        },
        'v' => Coordinate {
            x: current_coordinate.x,
            y: current_coordinate.y - 1,
        },
        '<' => Coordinate {
            x: current_coordinate.x - 1,
            y: current_coordinate.y,
        },
        _ => unreachable!(),
    }
}

This succesfully moved the character one line down, giving us 0 -1 for x y. I can move on to hash sets:

let starting_coordinates = Coordinate { x: 0, y: 0 };

let mut visited_coordinates: HashSet<Coordinate> = HashSet::from([starting_coordinates]);
let mut current_coordinates = starting_coordinates;

for direction in directions {
    current_coordinates = move_santa(direction, current_coordinates);
    visited_coordinates.insert(current_coordinates);
}

But insert() function of hash set gives me the error the method `insert` exists for struct `HashSet<Coordinate>`, but its trait bounds were not satisfied. Naturally, it needs some way to compare Coordinates so Rust can decide which ones are duplicates.

#[derive(Eq, Clone, Copy)]
struct Coordinate {
    x: i32,
    y: i32,
}

impl PartialEq for Coordinate {
    fn eq(&self, other: &Coordinate) -> bool {
        self.x == other.x && self.y == other.y
    }
}

impl std::hash::Hash for Coordinate {
    fn hash<H>(&self, state: &mut H)
    where
        H: std::hash::Hasher,
    {
        state.write_i32(self.x);
        state.finish();
    }
}

I had to “extend” the functionality of Coordinate by adding hash and PartialEq functions and add three traits, Eq, Clone, and Copy to make it work.

With everything put together, first part of the puzzle is now solved.

use std::{collections::HashSet, fs};

#[derive(Eq, Clone, Copy)]
struct Coordinate {
    x: i32,
    y: i32,
}

impl PartialEq for Coordinate {
    fn eq(&self, other: &Coordinate) -> bool {
        self.x == other.x && self.y == other.y
    }
}

impl std::hash::Hash for Coordinate {
    fn hash<H>(&self, state: &mut H)
    where
        H: std::hash::Hasher,
    {
        state.write_i32(self.x);
        state.finish();
    }
}

fn main() {
    let filename = "data.txt";

    let contents = fs::read_to_string(filename).expect("Something went wrong");
    let directions = contents.chars();

    let starting_coordinates = Coordinate { x: 0, y: 0 };

    let mut visited_coordinates: HashSet<Coordinate> = HashSet::from([starting_coordinates]);
    let mut current_coordinates = starting_coordinates;

    for direction in directions {
        current_coordinates = move_santa(direction, current_coordinates);
        visited_coordinates.insert(current_coordinates);
    }

    println!("{:?}", visited_coordinates.into_iter().count())
}

fn move_santa(direction: char, current_coordinate: Coordinate) -> Coordinate {
    match direction {
        '^' => Coordinate {
            x: current_coordinate.x,
            y: current_coordinate.y + 1,
        },
        '>' => Coordinate {
            x: current_coordinate.x + 1,
            y: current_coordinate.y,
        },
        'v' => Coordinate {
            x: current_coordinate.x,
            y: current_coordinate.y - 1,
        },
        '<' => Coordinate {
            x: current_coordinate.x - 1,
            y: current_coordinate.y,
        },
        _ => unreachable!(),
    }
}

Part 2

Santa has a robot assistant now and they follow directions in turns. How many houses do they visit?

This should be easier to implement into our current code. I just need to track one more character and move them in turns. A simple modulo operator should be enough for checking turns.

use std::{collections::HashSet, fs};

#[derive(Eq, Clone, Copy)]
struct Coordinate {
    x: i32,
    y: i32,
}

impl PartialEq for Coordinate {
    fn eq(&self, other: &Coordinate) -> bool {
        self.x == other.x && self.y == other.y
    }
}

impl std::hash::Hash for Coordinate {
    fn hash<H>(&self, state: &mut H)
    where
        H: std::hash::Hasher,
    {
        state.write_i32(self.x);
        state.finish();
    }
}

fn main() {
    let filename = "data.txt";

    let contents = fs::read_to_string(filename).expect("Something went wrong");
    let directions = contents.chars();

    let starting_coordinates = Coordinate { x: 0, y: 0 };

    let mut visited_coordinates: HashSet<Coordinate> = HashSet::from([starting_coordinates]);
    let mut santa_coordinate = starting_coordinates;
    let mut robot_coordinate = starting_coordinates;

    for (idx, direction) in directions.enumerate() {
        if idx % 2 == 0 {
            santa_coordinate = move_character(direction, santa_coordinate);
            visited_coordinates.insert(santa_coordinate);
        } else {
            robot_coordinate = move_character(direction, robot_coordinate);
            visited_coordinates.insert(robot_coordinate);
        }
    }

    println!("{:?}", visited_coordinates.into_iter().count())
}

fn move_character(direction: char, current_coordinate: Coordinate) -> Coordinate {
    match direction {
        '^' => Coordinate {
            x: current_coordinate.x,
            y: current_coordinate.y + 1,
        },
        '>' => Coordinate {
            x: current_coordinate.x + 1,
            y: current_coordinate.y,
        },
        'v' => Coordinate {
            x: current_coordinate.x,
            y: current_coordinate.y - 1,
        },
        '<' => Coordinate {
            x: current_coordinate.x - 1,
            y: current_coordinate.y,
        },
        _ => unreachable!(),
    }
}

This works as expected and the second part of the puzzle is now solved, but I am leaving this behind puzzle a bit unsatisfied because I feel like I partly cheated my way through it, because I can’t say I completely get how traits are working here. I kind of get it, but I also don’t… I should try and write a post about it.

#advent-of-code #advent-of-code-2015 #rust