Advent of code 2021: Day 10

This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.

In this article I'll be solving: Advent of code 2021: Day #10.

Part 1

The navigation subsystem of my submarine is failing and there seems to be syntax errors on all lines of my input file. Each opening bracket of any kind [({< should have a matching closing bracket ])}>. The first part is to find the corrupted lines, which are lines with false ‘closing’ brackets.

The first method I wrote is an input parser:

fn parse(input: &Vec<&str>) -> Vec<(Vec<char>, Vec<char>)> {
    let map = HashMap::from([
        ('}', '{'),
        (')', '('),
        ('>', '<'),
        (']', '['),
    ]);

    let mut result = vec![];

    for line in input {
        let mut opens = vec![];
        let mut closes = vec![];

        for ch in line.chars() {
            match ch {
                '[' | '(' | '{' | '<' => opens.push(ch),
                ']' | ')' | '}' | '>' => {
                    let opener = map.get(&ch).unwrap();
                    if opens.last().unwrap() == opener {
                        opens.pop();
                    } else {
                        closes.push(ch)
                    }
                },
                _ => panic!("Invalid syntax")
            }

        }

        result.push((opens, closes));
    }

    result
}

Nothing too fancy, it reads each line, then each char of each line and make two lists: one for all the opening characters and one for all the closing characters. There’s a catch to the closing characters, each closing character checks the last value that was pushed in the opening characters list and drops it if is found. If it isn’t found, we push the character to the closing characters list.

To determine the amount of points for the first mismatching bracket:

fn parse_navigation_subsystem(input: &Vec<&str>) -> u64 {
    let points = HashMap::from([
        (')', 3),
        (']', 57),
        ('}', 1197),
        ('>', 25137)
    ]);

    let mut subtotal = 0;
    let parsed = parse(input);

    for (_, closes) in parsed {
        if closes.len() > 0 {
            subtotal += points.get(&closes[0]).unwrap();
        }
    }

    subtotal
}

Part 2

Because my initial parse()-method acts the way it does, part 2 is actually quite simple. I have to only check the amount of remaining opening brackets and do some basic calculation:

fn autocomplete_subsystem(input: &Vec<&str>) -> u64 {
    let mut scores = vec![];
    let points = HashMap::from([
        ('(', 1),
        ('[', 2),
        ('{', 3),
        ('<', 4)
    ]);

    let parsed = parse(input);

    for (opens, closes) in parsed {
        if !closes.is_empty() {
            continue;
        }

        let mut autocomplete_total = 0;

        for open in opens.iter().rev() {
            autocomplete_total *= 5;
            autocomplete_total += points.get(open).unwrap();
        }

        scores.push(autocomplete_total)
    }

    scores.sort();
    scores[(scores.len() / 2)]
}

Voilà, solved! ⭐️⭐️

The full solution is available on GitHub.

1716151413121110987654321