Advent of Code 2021 - Day 10

Every weekday, I participate to a “Clash of Code” challenge on Codingame

Recently, I had some difficulties with a puzzle that was about syntax analysis, and I could not validate all test cases. I reviewed other contestants codes, and I learnt how to solve this kind of puzzle.

Today puzzle in Advent of Code was similar to this Clash of Code problem. That is why I immediately knew which algorithm to use.

Problem description

The objective of the problem is to analyze lines of code, and to classify them in 3 types : correct, incomplete, or corrupted.

Each line of code (example below) is composed of “chunks” that can contain zero or more other chunks, and every chunk must open and close with one of four possible pairs of characters : ( and ), [ and ], { and }, < and >.

[({(<(())[]>[[{[]{<()<>>
[(()[<>])]({[<{<<[]>>(
{([(<{}[<>[]}>{[]{[(<()>
(((({<>}<{<{<>}{[]{[]{}
[[<[([]))<([[{}[[()]]]
[{[{({}]{}}([{[{{{}}([]
{<[[]]>}<{[{[{[]{()[[[]
[<(<(<(<{}))><([]([]()
<{([([[(<>()){}]>(<<{{
<{([{{}}[<[[[<>{}]]]>[]]

If a chunk is closed with a wrong character, the line is corrupted. If a line ends whereas chunks are not closed, it is incomplete. Otherwise, it is correct.

Syntax check

First, let’s define an enum, containing the 3 possible outcomes of our syntax checker. Note that last two variants have an integer parameter. This will be explained later.

pub enum SyntaxCheck {
    Correct,
    Corrupted(u64),
    Incomplete(u64),
}

Then, let’s write the syntax check function.

The algorithm uses a stack. The input line is read from the left to the right, and, for each character : * if the character is a opening character (i.e in ([{<), it is pushed to the stack. * otherwise, if it is a closing character (i.e in )]}>), we check if the top of the stack corresponds to our character (for example, if the current character is a ), we check if the character on the stack is a (). If it is the case, the top of the stack is popped. Otherwise, this means that the line is corrupted, and the analysis is stopped.

When the last character of the line is read, if the stack is empty, then the line is correct. Otherwise, it is incomplete.

pub fn check_syntax(line: &String) -> SyntaxCheck {
    let mut stack = Vec::new();

    let opening_chars = HashMap::from([
        (')', '('), (']', '['), ('}', '{'), ('>', '<')
    ]);

    for ch in line.chars().collect::<Vec<char>>() {
        match ch {
            '(' | '[' | '{' | '<' => { stack.push(ch); }
            ')' | ']' | '}' | '>' => {
                if opening_chars.get(&ch).unwrap() == stack.last().unwrap() {
                    stack.pop();
                }
                else {
                    return SyntaxCheck::Corrupted(*corruption_scores.get(&ch).unwrap());
                }
            },
            _ => panic!("Character not supported")
        }
    }
    
    if stack.len() == 0 {
        SyntaxCheck::Correct
    }
    else {
        SyntaxCheck::Incomplete(completion_score(&stack))
    }
}

Part 1

For the part 1, only corrupted lines are considered.

A corrupted line gets a “corruption score” (the parameter of the SyntaxCheck::Corrupted variant), function of the first wrong character of the line.

let corruption_scores = HashMap::from([
    (')', 3), (']', 57), ('}', 1197), ('>', 25137)
]);

In the main function, corruption scores are summed.

pub fn solve_part1(input: &Vec<String>) -> u64 {
    let mut score = 0;

    for line in input {
        match check_syntax(line) {
            SyntaxCheck::Correct | SyntaxCheck::Incomplete(_) => {},
            SyntaxCheck::Corrupted(v) => score += v
        }
    }

    score
}

Part 2

For the part 2, only incomplete lines are considered. When the line has been entirely read, the stack (a simple Vec in Rust) is reversed, and this produces the missing characters sequence. Then, a “completion score” (the parameter of the SyntaxCheck::Incomplete variant) is computed.

pub fn completion_score(stack: &Vec<char>) -> u64 {
    let mut score = 0;
    let completion_scores = HashMap::from([
        ('(', 1), ('[', 2), ('{', 3), ('<', 4)
    ]);

    for ch in stack.iter().cloned().rev().collect::<Vec<char>>() {
        score = score * 5 + completion_scores.get(&ch).unwrap()
    }

    score
}