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
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.
Top comments (0)