Advent of Code 2015 Day 3

Day 3: Perfectly Spherical Houses in a Vacuum

https://adventofcode.com/2015/day/3

Santa is delivering presents to an infinite two-dimensional grid of houses.

Today’s input is a list of move instructions for Santa.

Moves are always a single step:

^ North
v South
> East
< West

An example input looks like this:

input.txt

^^<<v<<v><v^^<><>^^<

After every move, Santa delivers a present to the house at that coordinate.

Part 1

By following these instructions, Santa ends up visiting some houses multiple times.

The question asks how many houses receive at least one present.

Helpers

A data structure to keep track of a coordinate in that 2D space.

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

About that derive bit on top: Those are some automatically derived traits I use to be able to use Coord in a few different ways. They enable several behaviours of our Coord struct. Like Eq to be able to tell if two Coords are equal.

Option 1: A set of coordinates

Santa starts at a random coordinate. I picked 0,0 but the starting location doesn’t matter.

After every move, the new coordinate is added to a set of visited houses. Because it’s a set, it won’t store duplicates and only count a specific coordinate once.

At the end, the length of that set is the answer to part 1.

pub fn part_1(input: &str) -> usize {
    let mut santa = Coord { x: 0, y: 0 };
    let mut visited: HashSet<Coord> = HashSet::new();
    // visit starting point
    visited.insert(santa);

    for c in input.chars() {
        // move to a house
        match c {
            '>' => santa.x += 1,
            '<' => santa.x -= 1,
            '^' => santa.y -= 1,
            'v' => santa.y += 1,
            _ => panic!("invalid input"),
        }
        // visit a house
        visited.insert(santa);
    }

    visited.len()
}

Option 2: Turning the list of moves into a list of coordinates

This solution turns the iterator of moves into an iterator of coordinates. Only the unique coordinates in that iterator are kept. The amount of items in that iterator is the answer to part 1.

use itertools::Itertools;

pub fn part_1(input: &str) -> usize {
    input
        .chars()
        // turn into iterator of coordinates santa is at
        .scan(Coord { x: 0, y: 0 }, |santa, c| {
            match c {
                '>' => santa.x += 1,
                '<' => santa.x -= 1,
                '^' => santa.y -= 1,
                'v' => santa.y += 1,
                _ => panic!("invalid input"),
            }
            Some(*santa)
        })
        // filter out duplicates
        .unique()
        .count()
}

Main code for part 1

day_03.rs

use itertools::Itertools;

pub fn part_1(input: &str) -> usize {
    input
        .chars()
        // turn into iterator of coordinates santa is at
        .scan(Coord { x: 0, y: 0 }, |santa, c| {
            match c {
                '>' => santa.x += 1,
                '<' => santa.x -= 1,
                '^' => santa.y -= 1,
                'v' => santa.y += 1,
                _ => panic!("invalid input"),
            }
            Some(*santa)
        })
        // filter out duplicates
        .unique()
        .count()
}

Part 2

The next year, Santa creates a robot that can deliver presents too, “Robo-Santa”.

They both start at the same coordinate.

They take turns moving based on the instructions.

The list of instructions is still the same one.

The question asks how many houses receive at least one present.

Option 1: A set of coordinates

Similar to part 1, but keep track of 2 coordinates. To check which santa moves, check if the index of the move is divisible by 2.

pub fn part_2(input: &str) -> usize {
    let mut santa = Coord { x: 0, y: 0 };
    let mut robo_santa = Coord { x: 0, y: 0 };
    let mut visited: HashSet<Coord> = HashSet::new();
    visited.insert(santa);
    visited.insert(robo_santa);

    for (idx, c) in input.chars().enumerate() {
        let mover = if idx % 2 == 0 { &mut santa } else { &mut robo_santa };
        match c {
            '>' => mover.x += 1,
            '<' => mover.x -= 1,
            '^' => mover.y -= 1,
            'v' => mover.y += 1,
            _ => panic!("invalid input"),
        }
        visited.insert(*mover);
    }

    visited.len()
}

Option 2: Turning the list of moves into a list of coordinates

Identical logic changes to convert from part 1 to part 2 as in Option 1:

pub fn part_2(input: &str) -> usize {
    input
        .chars()
        .enumerate()
        // turn into iterator of coordinates (robo-)santa is at
        .scan(
            (Coord { x: 0, y: 0 }, Coord { x: 0, y: 0 }),
            |(santa, robo_santa), (idx, c)| {
                let mover = if idx % 2 == 0 { santa } else { robo_santa };
                match c {
                    '>' => mover.x += 1,
                    '<' => mover.x -= 1,
                    '^' => mover.y -= 1,
                    'v' => mover.y += 1,
                    _ => panic!("invalid input"),
                }
                Some(*mover)
            },
        )
        // filter out duplicates
        .unique()
        .count()
}

Main code for part 2

day_03.rs

use itertools::Itertools;

pub fn part_2(input: &str) -> usize {
    input
        .chars()
        .enumerate()
        // turn into iterator of coordinates (robo-)santa is at
        .scan(
            (Coord { x: 0, y: 0 }, Coord { x: 0, y: 0 }),
            |(santa, robo_santa), (idx, c)| {
                let mover = if idx % 2 == 0 { santa } else { robo_santa };
                match c {
                    '>' => mover.x += 1,
                    '<' => mover.x -= 1,
                    '^' => mover.y -= 1,
                    'v' => mover.y += 1,
                    _ => panic!("invalid input"),
                }
                Some(*mover)
            },
        )
        // filter out duplicates
        .unique()
        .count()
}

Final code

day_03.rs

1use itertools::Itertools;
2
3#[derive(Clone, Copy, PartialEq, Eq, Hash)]
4struct Coord {
5    x: i32,
6    y: i32,
7}
8
9pub fn part_1(input: &str) -> usize {
10    input
11        .chars()
12        // turn into iterator of coordinates santa is at
13        .scan(Coord { x: 0, y: 0 }, |santa, c| {
14            match c {
15                '>' => santa.x += 1,
16                '<' => santa.x -= 1,
17                '^' => santa.y -= 1,
18                'v' => santa.y += 1,
19                _ => panic!("invalid input"),
20            }
21            Some(*santa)
22        })
23        // filter out duplicates
24        .unique()
25        .count()
26}
27
28pub fn part_2(input: &str) -> usize {
29    input
30        .chars()
31        .enumerate()
32        // turn into iterator of coordinates (robo-)santa is at
33        .scan(
34            (Coord { x: 0, y: 0 }, Coord { x: 0, y: 0 }),
35            |(santa, robo_santa), (idx, c)| {
36                let mover = if idx % 2 == 0 { santa } else { robo_santa };
37                match c {
38                    '>' => mover.x += 1,
39                    '<' => mover.x -= 1,
40                    '^' => mover.y -= 1,
41                    'v' => mover.y += 1,
42                    _ => panic!("invalid input"),
43                }
44                Some(*mover)
45            },
46        )
47        // filter out duplicates
48        .unique()
49        .count()
50}