Advent of Code 2023 Day 3

Day 3: Gear Ratios

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

You reach a gondola lift, but it’s broken (what a surprise). So you offer to help fix it.

The engine is missing a part.

Today’s input file is the engine schematic, a visual representation of the engine.

An example input looks like this:

input.txt

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

Part 1

In the schematic, periods are empty spaces.

Any number adjacent (even diagonally) to a symbol is a part number.

The question asks what the sum is of all part numbers in the engine schematic.

In the example, only 2 numbers are not part numbers: 114 (top right) and 58 (middle right).

First, the engine schematic is built from the input as a 2D list where each point is a character (a point, a digit, or a symbol).

We iterate through the schematic, checking every digit.

While we do so, we keep track of a few temporary variables:

The current number so far (a number can have multiple digits)
If the current number is adjacent to a symbol

For every digit we encounter, those temporary variables get updated:

We concatenate the digit to the end of the current number.
We check if any point adjacent to the digit is a symbol

If the next horizontal point is not a digit (it’s either the end of a line, a symbol, or an empty space), the current number is complete.

At that point, we check if the current number is adjacent to a symbol. If it is, we increment our final sum. Finally, we reset the temporary variables before we start building up the next number.

In pseudocode:

let engine = // a 2D grid where each point is a character (a point, a digit, or a symbol)
let mut sum = 0;
let mut current_num = 0;
let mut has_adjacent_symbol = false;

for point in engine {
    // check if current point is a digit
    if !point.is_digit() {
        continue;
    }

    // concatenate digit to current number
    current_num = current_num * 10 + point.value;

    for neighbour in point.neighbours() {
        if neighbour.is_symbol() {
            has_adjacent_symbol = true;
        }
    }

    // check if current_num is complete
    if next_point.is_out_of_bounds() || next_point.is_symbol() || next_point.is_empty_space() {
        // check if current_num is adjacent to a symbol
        if has_adjacent_symbol {
            sum = sum + current_num;
        }
        // reset temporary variables
        current_num = 0;
        has_adjacent_symbol = false;
    }
}

sum

Code

day_03.rs

pub fn part_1(input: &str) -> u32 {
    let grid = input
        .trim()
        .lines()
        .map(|line| line.trim().chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();

    let mut sum = 0;
    let mut current_num = 0;
    let mut has_adjacent_symbol = false;

    for row_idx in 0..grid.len() {
        for col_idx in 0..grid[row_idx].len() {
            let value = grid[row_idx][col_idx];

            // Not a number, not interested
            if !value.is_ascii_digit() {
                continue;
            }

            // check if any adjacent tile is a symbol
            for row_offset in -1..=1 {
                for col_offset in -1..=1 {
                    // Skip self
                    if row_offset == 0 && col_offset == 0 {
                        continue;
                    }

                    let adjacent_row_idx = row_idx as i32 + row_offset;
                    let adjacent_col_idx = col_idx as i32 + col_offset;

                    // Out of bounds
                    if adjacent_row_idx < 0
                        || adjacent_row_idx >= grid.len() as i32
                        || adjacent_col_idx < 0
                        || adjacent_col_idx >= grid[adjacent_row_idx as usize].len() as i32
                    {
                        continue;
                    }

                    let adjacent_value = grid[adjacent_row_idx as usize][adjacent_col_idx as usize];
                    if !adjacent_value.is_ascii_digit() && adjacent_value != '.' {
                        has_adjacent_symbol = true;
                    }
                }
            }

            // Adjust the number currently being built (concatenate a digit using math)
            current_num *= 10;
            current_num += value.to_digit(10).unwrap();

            // If we reached the end of the line, or the next horizontal coordinate is not a digit, the current number is complete
            // check if the number has an adjacent symbol, and reset the temporary values before starting on a new number
            if col_idx + 1 >= grid[row_idx].len() || !grid[row_idx][col_idx + 1].is_ascii_digit() {
                if has_adjacent_symbol {
                    sum += current_num;
                }

                current_num = 0;
                has_adjacent_symbol = false;
            }
        }
    }

    sum
}

Part 2

The gondola starts working, but it’s going painfully slow! The engineer tells you one of the gears in the engine is wrong.

On your schematic, a gear is marked as a star (*) that is adjacent to exactly two part numbers.

You can calculate the gear ratio of a gear by multiplying the numbers of the two adjacent parts.

The question asks to find the sum of all gear ratios.

The code is very similar to part 1. The variable we keep track of throughout the loop changes (sum in part1), and one temporary variable.

The variable we keep track of throughout the loop is a map of all stars, with positions as keys, and a list of adjacent part numbers as value.

We iterate through the schematic, checking every digit.

While we do so, we keep track of a few temporary variables:

The current number so far (a number can have multiple digits)
A set of all star positions that are adjacent to the current number

For every digit we encounter, those temporary variables get updated:

We concatenate the digit to the end of the current number.
We add any adjacent star positions to the adjacent stars set.

If the next horizontal point is not a digit (it’s either the end of a line, a symbol, or an empty space), the current number is complete.

At that point, we add all stars in the set to the map we keep track of throughout the loop. Finally, we reset the temporary variables before we start building up the next number.

After the loop over the engine schematics ends, we filter the map we kept track of so only the valid gears are left. (stars with exactly 2 adjacent numbers.) We multiply those numbers together, and sum those products.

Code

day_03.rs

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

pub fn part_2(input: &str) -> u32 {
    let engine = input
        .trim()
        .lines()
        .map(|line| line.trim().chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();

    // key: star coordinate, val: list of adjacent numbers
    let mut stars: HashMap<(i32, i32), Vec<u32>> = HashMap::new();
    let mut current_num = 0;
    let mut adjacent_star_positions: HashSet<(i32, i32)> = HashSet::new();

    for row_idx in 0..engine.len() {
        for col_idx in 0..engine[row_idx].len() {
            let value = engine[row_idx][col_idx];

            // Not a number, not interested
            if !value.is_ascii_digit() {
                continue;
            }

            // check if any adjacent tile is a star
            for row_offset in -1..=1 {
                for col_offset in -1..=1 {
                    // Skip self
                    if row_offset == 0 && col_offset == 0 {
                        continue;
                    }

                    let adjacent_row_idx = row_idx as i32 + row_offset;
                    let adjacent_col_idx = col_idx as i32 + col_offset;

                    // Out of bounds
                    if adjacent_row_idx < 0
                        || adjacent_row_idx >= engine.len() as i32
                        || adjacent_col_idx < 0
                        || adjacent_col_idx >= engine[adjacent_row_idx as usize].len() as i32
                    {
                        continue;
                    }

                    if engine[adjacent_row_idx as usize][adjacent_col_idx as usize] == '*' {
                        adjacent_star_positions.insert((adjacent_row_idx, adjacent_col_idx));
                    }
                }
            }

            // Adjust the number currently being built (concatenate a digit using math)
            current_num *= 10;
            current_num += value.to_digit(10).unwrap();

            // If we reached the end of the line, or the next horizontal coordinate is not a digit, the current number is complete
            if col_idx + 1 >= engine[row_idx].len()
                || !engine[row_idx][col_idx + 1].is_ascii_digit()
            {
                // add all stars to the variable keeping track of stars (potential gears)
                for point in &adjacent_star_positions {
                    stars.entry(*point).or_default().push(current_num);
                }

                // reset the temporary values before starting on a new number
                current_num = 0;
                adjacent_star_positions.clear();
            }
        }
    }

    stars
        .values()
        // only stars with exactly 2 adjacent numbers are gears
        .filter(|numbers| numbers.len() == 2)
        .map(|numbers| numbers[0] * numbers[1])
        .sum()
}

Final code

day_03.rs

1use std::collections::{HashMap, HashSet};
2
3pub fn part_1(input: &str) -> u32 {
4    let engine = input
5        .trim()
6        .lines()
7        .map(|line| line.trim().chars().collect::<Vec<_>>())
8        .collect::<Vec<_>>();
9
10    let mut sum = 0;
11    let mut current_num = 0;
12    let mut has_adjacent_symbol = false;
13
14    for row_idx in 0..engine.len() {
15        for col_idx in 0..engine[row_idx].len() {
16            let value = engine[row_idx][col_idx];
17
18            // Not a number, not interested
19            if !value.is_ascii_digit() {
20                continue;
21            }
22
23            // check if any adjacent tile is a symbol
24            for row_offset in -1..=1 {
25                for col_offset in -1..=1 {
26                    // Skip self
27                    if row_offset == 0 && col_offset == 0 {
28                        continue;
29                    }
30
31                    let adjacent_row_idx = row_idx as i32 + row_offset;
32                    let adjacent_col_idx = col_idx as i32 + col_offset;
33
34                    // Out of bounds
35                    if adjacent_row_idx < 0
36                        || adjacent_row_idx >= engine.len() as i32
37                        || adjacent_col_idx < 0
38                        || adjacent_col_idx >= engine[adjacent_row_idx as usize].len() as i32
39                    {
40                        continue;
41                    }
42
43                    let adjacent_value =
44                        engine[adjacent_row_idx as usize][adjacent_col_idx as usize];
45                    if !adjacent_value.is_ascii_digit() && adjacent_value != '.' {
46                        has_adjacent_symbol = true;
47                    }
48                }
49            }
50
51            // Adjust the number currently being built (concatenate a digit using math)
52            current_num *= 10;
53            current_num += value.to_digit(10).unwrap();
54
55            // If we reached the end of the line, or the next horizontal coordinate is not a digit, the current number is complete
56            // check if the number has an adjacent symbol, and reset the temporary values before starting on a new number
57            if col_idx + 1 >= engine[row_idx].len()
58                || !engine[row_idx][col_idx + 1].is_ascii_digit()
59            {
60                if has_adjacent_symbol {
61                    sum += current_num;
62                }
63
64                current_num = 0;
65                has_adjacent_symbol = false;
66            }
67        }
68    }
69
70    sum
71}
72
73pub fn part_2(input: &str) -> u32 {
74    let engine = input
75        .trim()
76        .lines()
77        .map(|line| line.trim().chars().collect::<Vec<_>>())
78        .collect::<Vec<_>>();
79
80    // key: star coordinate, val: list of adjacent numbers
81    let mut stars: HashMap<(i32, i32), Vec<u32>> = HashMap::new();
82    let mut current_num = 0;
83    let mut adjacent_star_positions: HashSet<(i32, i32)> = HashSet::new();
84
85    for row_idx in 0..engine.len() {
86        for col_idx in 0..engine[row_idx].len() {
87            let value = engine[row_idx][col_idx];
88
89            // Not a number, not interested
90            if !value.is_ascii_digit() {
91                continue;
92            }
93
94            // check if any adjacent tile is a star
95            for row_offset in -1..=1 {
96                for col_offset in -1..=1 {
97                    // Skip self
98                    if row_offset == 0 && col_offset == 0 {
99                        continue;
100                    }
101
102                    let adjacent_row_idx = row_idx as i32 + row_offset;
103                    let adjacent_col_idx = col_idx as i32 + col_offset;
104
105                    // Out of bounds
106                    if adjacent_row_idx < 0
107                        || adjacent_row_idx >= engine.len() as i32
108                        || adjacent_col_idx < 0
109                        || adjacent_col_idx >= engine[adjacent_row_idx as usize].len() as i32
110                    {
111                        continue;
112                    }
113
114                    if engine[adjacent_row_idx as usize][adjacent_col_idx as usize] == '*' {
115                        adjacent_star_positions.insert((adjacent_row_idx, adjacent_col_idx));
116                    }
117                }
118            }
119
120            // Adjust the number currently being built (concatenate a digit using math)
121            current_num *= 10;
122            current_num += value.to_digit(10).unwrap();
123
124            // If we reached the end of the line, or the next horizontal coordinate is not a digit, the current number is complete
125            if col_idx + 1 >= engine[row_idx].len()
126                || !engine[row_idx][col_idx + 1].is_ascii_digit()
127            {
128                // add all stars to the variable keeping track of stars (potential gears)
129                for point in &adjacent_star_positions {
130                    stars.entry(*point).or_default().push(current_num);
131                }
132
133                // reset the temporary values before starting on a new number
134                current_num = 0;
135                adjacent_star_positions.clear();
136            }
137        }
138    }
139
140    stars
141        .values()
142        // only stars with exactly 2 adjacent numbers are gears
143        .filter(|numbers| numbers.len() == 2)
144        .map(|numbers| numbers[0] * numbers[1])
145        .sum()
146}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 3

Day 3: Gear Ratios

Part 1

Code

Part 2

Code

Final code