Robert Mion

Posted on Feb 7, 2022

Syntax Scoring

#adventofcode #programming #algorithms #computerscience

Advent of Code 2021 Day 10

Try the simulator!

Solve for X where

X = a score derived from corrupted or incomplete navigation lines

The tallied score of all corrupted lines
The middle score among all tallied incomplete lines

Input is

A multi-line string

It represents

Subsystem navigation lines
Each consisting of the character pairs: () [] {} <>

New Game Plus

I solved both parts of this challenge the day it was released
Returning to it again offered a new challenge: solving it with more eloquent, more performant algorithms
New Game Plus is a common bonus mode in video games where, once a player beats the game, they can replay it using the weapons and skill points accrued throughout the last play through...in order to fight the same enemies - yet more difficult to account for their increased skills - this time around

Critiquing my original algorithms

Three objects used to map character pairs and their weights
Four sub-routines used in each part:

Recursive check if a line is corrupt: checks smaller subsets of the string, slicing from the beginning
Recursive check if a line is incomplete: checks smaller subsets of the string, slicing from the beginning
Build the string of closing characters for each line
Calculate the score of missing closing characters for incomplete lines

Two main sub-routines, one for each part:

Part 1
  Split the input into lines
  For each line
    Replace the contents of the line with whether it is corrupt or not
  For each line
    Throw away non-corrupt lines, keep corrupt lines
    Return the smaller list of lines
  For each line
    Replace the contents of the line with the associated score of the first invalid character
  For each line
    Add the score to an accumulating value, starting from 0
  Return the accumulated score

Part 2
  Split the input into lines
  For each line
    Keep lines that are not corrupt
    Return the smaller list of lines
  For each line
    Replace the contents of the line with its score based on the provided formula in the challenge instructions, using the stored objects as reference
  For each line
    Sort in order by score
  Return the middle score

Looking back on my code, a lot of it felt duplicative and unnecessary.

Thankfully, this was proof that I've absorbed knowledge and skills from the code I studied as part of this series.

Round 2: less code, fewer loops, highly rewarding

From a code golf perspective:

74 lines, 3 supplemental objects, 4 helper functions - 2 of which were recursive, and too many looping array methods to count
34 lines, 1 supplemental multi-dimensional array, 0 helper function, 2 loops for part 1 and 5 loops for part 2, no recursion

Let's dive in!

Setup:
  Split the puzzle input into an array of strings
  Store an array with three arrays of length 4:
    1. Opening characters
    2. Closing characters
    3. Points for each closing character in a corrupt line

The refactored algorithm for Part 1

For each line, starting with a score of 0
  Set score to 0
  Create an array to hold a varying list of closing characters
  For each character in the line
    If it is in the list of opening characters
      Insert its corresponding closing character at the beginning of the array
    Else if it is the same as the first item in the array
      Remove the first item in the array
    Else if the array is not empty and this character is not the same as the first item in the array
      Update score to the number in the third array whose index matches the index of the second array which this character must be in, since it must be a closing character
      Break out of this loop
  Add the score to the accumulating sum of scores

The refactored algorithm for Part 2

Set scores to an array resulting from the following operation:
  For each line
    Create an array to hold a varying list of closing characters
    Create a flag identifying a line as corrupt - assume not corrupt initially
    For each character in the line
      If it is in the list of opening characters
        Insert its corresponding closing character at the beginning of the array
      Else if it is the same as the first item in the array
        Remove the first item in the array
      Else if the array is not empty and this character is not the same as the first item in the array
        Update the corrupt flag to mark this line as corrupt
        Break out of this loop
  If the line is corrupt
    Update the line to the number 0
  Else
    Update the line to the number resulting from the following operation
      For each character that was added to the array of closing characters, starting with a total of 0
        Multiply the total by 5
        Add to it one number higher than the character's index in the array of closing characters

For each line's score
  Throw away scores of 0 (which is a False-y number), keep other scores
  Return the smaller list of scores

Sort the new, smaller list of scores

Return the middle score

See my JavaScript code here

Want to interact with these algorithms?

I built a web app where you can enter valid corrupt or incomplete strings, and walk one step at a time to ultimately reveal the score for that string

Basking in a moment of pride and satisfaction

This was the first puzzle that enabled me to demonstrate the reason for embarking on this series:

Improve my critical-thinking abilities
Increase my programming skills such that:
I can more easily solve the puzzles by writing code that, had I found it instead of written it, I would consider it eloquent

I hope the remaining 9 2-part challenges for 2021 offer the same reward since - spoiler alert - I also solved all but 3 parts of them the day the puzzle was released.

DEV Community