Moving on with Day 10 of Advent of Code. This one actually went pretty smooth for me, I solved Part 1 without to much irritation and that solution could easily be extended to solve Part 2 aswell. It was a good day.

Our mission is to validate lines in the submarines navigation subsystem. The input can look like this:

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

Some lines are corrupt, some lines are incomplete. The lines are made up of chunks, and if a chunk opens with for example '(' it must close with ')' and so on. You get the idea, the opening and closing chars of a chunk must match.

For Part 1, we need to find the corrupt lines. Ignore the incomplete lines for now. For each corrupt line, we need to find the first illegal character. Each character corresponds to a number of points. Our task is to find the corrupt lines, find the first illegal character on each line and add the score together for a total score, which is our answer.

Before we look at the code, I'll talk about Part 2 aswell. Since my solution solves both parts in one go, I might as well. In Part 2 we are ignoring the corrupt lines and focusing on the incomplete lines. The incomplete lines can be fixed, by completing them. We have to figure out what characters are missing, and in which order. Again, the characters corresponds to a certain number of points. To get our final answer, we need to calculate our score for each line like this:

Start with a total score of 0. Then, for each character, multiply the total score by 5 and then increase the total score by the point value given for the character.

We add all our scores to a list, and the answer to Part 2 is the score that is in the middle of the list.

Here's how I did it:

var input = File.ReadAllLines("input.txt");

long part1Answer = 0;
var part2Scores = new List<long>();

foreach (var line in input)
{
    var (invalidChars, unclosedChars) = ValidateLine(line);

    if (invalidChars.Length > 0)
    {
        part1Answer += GetInvalidCharScore(invalidChars[0]);
    }
    else if (unclosedChars.Length > 0)
    {
        long score = 0;

        foreach (var c in unclosedChars)
        {
            score *= 5;
            score += GetMissingCharScore(GetMatchingChar(c));
        }

        part2Scores.Add(score);
    }
}

Console.WriteLine($"Part 1: {part1Answer}");
Console.WriteLine($"Part 2: {GetMedian(part2Scores)}");

Looks quite easy, and it is. Of course there are some helper methods that we should take a look at to understand what's going on. ValidateLine() is the most important one, as it actually returns the invalid characters aswell as the "unclosed" characters.

private static (char[] invalidChars, char[] unclosedChars) ValidateLine(string line)
{
    var invalidChars = new List<char>();
    var openingChars = new Stack<char>();

    foreach (var c in line)
    {
        if (c.IsOpeningChar())
        {
            openingChars.Push(c);
        }
        else
        {
            var openingChar = openingChars.Pop();

            if (openingChar != GetMatchingChar(c))
            {
                invalidChars.Add(c);
            }
        }
    }

    return (invalidChars.ToArray(), openingChars.ToArray());
}

We loop through the line, putting each opening char on a stack. If the char isn't an opening char, we pop the last opening char of the stack, check if it matches the current char. If it doesn't, the current char is invalid. At the end of this loop, any chars left on the stack are the "unclosed" chars that needs to be completed.

That was the important parts of the solution. I do have a couple of helpers and extensions to, and we'll take a look at them. There's not much to say about them though, they're quite self explanatory, I think. Fell free to ask questions if I'm wrong though :)

private static char GetMatchingChar(char c)
{
    switch (c)
    {
        case '(':
            return ')';
        case '[':
            return ']';
        case '{':
            return '}';
        case '<':
            return '>';
        case ')':
            return '(';
        case ']':
            return '[';
        case '}':
            return '{';
        case '>':
            return '<';
        default:
            throw new ArgumentException();
    }
}

This'll help us get the matching opening/closing char.

public static bool IsOpeningChar(this char c)
{
    var openingChars = new List<char> { '(', '[', '{', '<' };
    return openingChars.Contains(c);
}

This'll let us know if the passed in char is an opening char.

private static int GetInvalidCharScore(char c)
{
    switch (c)
    {
        case ')':
            return 3;
        case ']':
            return 57;
        case '}':
            return 1197;
        case '>':
            return 25137;
        default:
            throw new ArgumentException();
    }
}

This'll give us the score for each char, for the invalid char score calculations.

private static int GetMissingCharScore(char c)
{
    switch (c)
    {
        case ')':
            return 1;
        case ']':
            return 2;
        case '}':
            return 3;
        case '>':
            return 4;
        default:
            throw new ArgumentException();
    }
}

This'll give us the score for each char, for the missing char score calculations.

private static long GetMedian(IEnumerable<long> scores)
{
    var count = scores.Count();

    scores = scores.OrderBy(x => x);
    var middle = count / 2;

    return scores.ElementAt(middle);
}

This is actually a bit lazy. This implementation of median does not consider lists where there is an even number of items. The question clearly states that there will be an uneven number of items in the scores list, so that's why. If there was an even number of items, we would need to take the two items that are in the middle, and get the average value of those.