Advent of Code 2021 - Day 10

Friday, Dec 10, 2021| Tags: Advent of Code 2021

Photo by Any Lane from Pexels

I’m participating in the Advent of Code 2021. Here’s my solutions for Day 10 - Syntax Scoring.

Problem 1

For Puzzles for Day 10, we’re trying to resolve damage to the navigation subsystem of our submarine. Each navigation line contains a series of “chunks”, which are pairs of delimiter characters (), {}, [] and <>. They may or may not be nested and appear in formats such as:

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

We find that every line of chunks, however, has been damaged. Some are corrupted (characters out of order) and some are incomplete (proper order but the line ends prematurely). For puzzle 1, we have to identify the corrupted lines. We score each line by which invalid character appears first.

  • ): 3 points.
  • ]: 57 points.
  • }: 1197 points.
  • >: 25137 points.

Solution

All my solutions are written in C#. You can find all my solutions in my Git repo.

At first I started writing out this big long recursive function to strip the first character, then check the next character. If it was a starting character, then call the function again, passing in the next character and remaining string, and so forth.

Then I realized there was a simpler solution. First, I iterate through the string over and over, striping out the matches – i.e. pairs that were right next to each other – [] {} () & <>. When no more pairs remained, I check to see if any ending characters remain – }])>. If there are, then it’s clearly a corrupted line. Otherwise, it’s just an incomplete line.

For the scoring part, I used Regex to find the first ending character, then added to the total score based on which character we found first.

using System.Text.RegularExpressions;

Console.WriteLine("Advent of Code 2021");
Console.WriteLine("Day 10 - Puzzle 1");

//Solution logic goes here

//Load input array
string[] lines = System.IO.File.ReadAllLines("input.txt");
var points = 0;
for(int i = 0; i < lines.Length; i++)
{
    var line = lines[i];

    //first, clean out all possible matches
    var foundMatches = true;
    while(foundMatches)
    {
        foundMatches = false;

        if (line.Contains("<>") || line.Contains("[]") || line.Contains("{}") || line.Contains("()")) foundMatches = true;
        line = line.Replace("<>", "");
        line = line.Replace("[]", "");
        line = line.Replace("{}", "");
        line = line.Replace("()", "");
    }

    if (line.Contains(">") || line.Contains("]") || line.Contains("}") || line.Contains(")"))
    {
        //CORRUPTED
        Match match = Regex.Match(line, @"[\]\}\)\>]", RegexOptions.None);
        if (match.Success)
        {
            var m = match.Groups[0].Value;
            if (m == ")") points += 3;
            if (m == "]") points += 57;
            if (m == "}") points += 1197;
            if (m == ">") points += 25137;            
        }
    }
    //Otherwise it's incomplete. Do nothing for now
}

Console.WriteLine($"Total Points: {points}");

//Stop and wait for enter before exiting
Console.ReadLine();

The answer is: 367059

Puzzle 2

For the second half of the problem, we will discard the corrupted lines and repair the incomplete lines by adding the missing ending characters. For example:

[({(<(())[]>[[{[]{<()<>> - Complete by adding }}]])})]

We can do this by taking the incomplete lines and, for each line, step through the characters in reverse order, adding the appropriate ending character to the very end of the string. We score each line per the directions, and then we find the very middle score from the ordered list of scores for all the incomplete lines.

Solution

We reuse our simplification code from puzzle 1 to find out which lines are corrupted and toss those. For the remaining lines, we just step the characters in reverse order and build the character string that we’ll append to the end. As we build those characters, we calculate up the score for each line. When all lines are processed, we sort our list of scores and then use a LINQ query to find the middle element from the sorted list.

using System.Text;
using System.Text.RegularExpressions;

Console.WriteLine("Advent of Code 2021");
Console.WriteLine("Day 10 - Puzzle 1");

//Solution logic goes here

//Load input array
string[] lines = System.IO.File.ReadAllLines("input.txt");
var points = new List<ulong>();
for (int i = 0; i < lines.Length; i++)
{
    var line = lines[i];
    var fixedline = new StringBuilder();
    fixedline.Append(line);

    //first, clean out all possible matches
    var foundMatches = true;
    while (foundMatches)
    {
        foundMatches = false;

        if (line.Contains("<>") || line.Contains("[]") || line.Contains("{}") || line.Contains("()")) foundMatches = true;
        line = line.Replace("<>", "");
        line = line.Replace("[]", "");
        line = line.Replace("{}", "");
        line = line.Replace("()", "");
    }

    if (line.Contains(">") || line.Contains("]") || line.Contains("}") || line.Contains(")"))
    {
        //CORRUPTED - discard
    }
    else
    {
        ulong linepoints = 0;
        //Otherwise it's incomplete. Fix the line
        for (var j = line.Length - 1; j >= 0; j--)
        {
            switch (line[j])
            {
                case '(':
                    fixedline.Append(")");
                    linepoints = (linepoints * 5) + 1;
                    break;
                case '[':
                    fixedline.Append("]");
                    linepoints = (linepoints * 5) + 2;
                    break;
                case '{':
                    fixedline.Append("}");
                    linepoints = (linepoints * 5) + 3;
                    break;
                case '<':
                    fixedline.Append(">");
                    linepoints = (linepoints * 5) + 4;
                    break;
            }
        }

        points.Add(linepoints);
    }
}

//Find the middle points
var score = points.OrderBy(x => x).Skip((points.Count / 2)).First();

Console.WriteLine($"Total Points: {score}");

//Stop and wait for enter before exiting
Console.ReadLine();

The answer is: 1952146692

INTERESTED ?

I am available for part time consulting work. If you are looking for someone to help with Power Automate, SQL Server, Azure or .NET work, feel free to contact me.

Contact me