Day 10: Syntax Scoring
Challenge
You ask the submarine to determine the best route out of the deepsea cave, but it only replies:
Syntax error in navigation subsystem on line: all of them
All of them?! The damage is worse than you thought. You bring up a copy of the navigation subsystem (your puzzle input).
The navigation subsystem syntax is made of several lines containing chunks. There are one or more chunks on each line, and chunks contain zero or more other chunks. Adjacent chunks are not separated by any delimiter; if one chunk stops, the next chunk (if any) can immediately start. Every chunk must open and close with one of four legal pairs of matching characters:

If a chunk opens with
(
, it must close with)
. 
If a chunk opens with
[
, it must close with]
. 
If a chunk opens with
{
, it must close with}
. 
If a chunk opens with
<
, it must close with>
.
So,
()
is a legal chunk that contains no other chunks, as is []
. More complex but valid chunks include ([])
, {()()()}
, <([{}])>
, [<>({}){}[([])<>]]
, and even (((((((((())))))))))
.
Some lines are incomplete, but others are corrupted. Find and discard the corrupted lines first.
A corrupted line is one where a chunk closes with the wrong character  that is, where the characters it opens and closes with do not form one of the four legal pairs listed above.
Examples of corrupted chunks include
(]
, {()()()>
, (((()))}
, and <([]){()}[{}])
. Such a chunk can appear anywhere within a line, and its presence causes the whole line to be considered corrupted.
For example, consider the following navigation subsystem:
[({(<(())[]>[[{[]{<()<>>
[(()[<>])]({[<{<<[]>>(
{([(<{}[<>[]}>{[]{[(<()>
(((({<>}<{<{<>}{[]{[]{}
[[<[([]))<([[{}[[()]]]
[{[{({}]{}}([{[{{{}}([]
{<[[]]>}<{[{[{[]{()[[[]
[<(<(<(<{}))><([]([]()
<{([([[(<>()){}]>(<<{{
<{([{{}}[<[[[<>{}]]]>[]]
Some of the lines aren't corrupted, just incomplete; you can ignore these lines for now. The remaining five lines are corrupted:

{([(<{}[<>[]}>{[]{[(<()>
 Expected]
, but found}
instead. 
[[<[([]))<([[{}[[()]]]
 Expected]
, but found)
instead. 
[{[{({}]{}}([{[{{{}}([]
 Expected)
, but found]
instead. 
[<(<(<(<{}))><([]([]()
 Expected>
, but found)
instead. 
<{([([[(<>()){}]>(<<{{
 Expected]
, but found>
instead.
Stop at the first incorrect closing character on each corrupted line.
Did you know that syntax checkers actually have contests to see who can get the high score for syntax errors in a file? It's true! To calculate the syntax error score for a line, take the first illegal character on the line and look it up in the following table:

)
:3
points. 
]
:57
points. 
}
:1197
points. 
>
:25137
points.
In the above example, an illegal
)
was found twice (2*3 =
6
points), an illegal ]
was found once (57
points), an illegal }
was found once (1197
points), and an illegal >
was found once (25137
points). So, the total syntax error score for this file is 6+57+1197+25137 =
26397
points!
Find the first illegal character in each corrupted line of the navigation subsystem. What is the total syntax error score for those errors?
🔗 Part Two
Now, discard the corrupted lines. The remaining lines are incomplete.
Incomplete lines don't have any incorrect characters  instead, they're missing some closing characters at the end of the line. To repair the navigation subsystem, you just need to figure out the sequence of closing characters that complete all open chunks in the line.
You can only use closing characters (
)
, ]
, }
, or >
), and you must add them in the correct order so that only legal pairs are formed and all chunks end up closed.
In the example above, there are five incomplete lines:

[({(<(())[]>[[{[]{<()<>>
 Complete by adding}}]])})]
. 
[(()[<>])]({[<{<<[]>>(
 Complete by adding)}>]})
. 
(((({<>}<{<{<>}{[]{[]{}
 Complete by adding}}>}>))))
. 
{<[[]]>}<{[{[{[]{()[[[]
 Complete by adding]]}}]}]}>
. 
<{([{{}}[<[[[<>{}]]]>[]]
 Complete by adding])}>
.
Did you know that autocomplete tools also have contests? It's true! The score is determined by considering the completion string characterbycharacter. 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 in the following table:

)
:1
point. 
]
:2
points. 
}
:3
points. 
>
:4
points.
So, the last completion string above 
])}>
 would be scored as follows:

Start with a total score of
0
. 
Multiply the total score by 5 to get
0
, then add the value of]
(2) to get a new total score of2
. 
Multiply the total score by 5 to get
10
, then add the value of)
(1) to get a new total score of11
. 
Multiply the total score by 5 to get
55
, then add the value of}
(3) to get a new total score of58
. 
Multiply the total score by 5 to get
290
, then add the value of>
(4) to get a new total score of294
.
The five lines' completion strings have total scores as follows:

}}]])})]
288957
total points. 
)}>]})
5566
total points. 
}}>}>))))
1480781
total points. 
]]}}]}]}>
995444
total points. 
])}>
294
total points.
Autocomplete tools are an odd bunch: the winner is found by sorting all of the scores and then taking the middle score. (There will always be an odd number of scores to consider.) In this example, the middle score is
288957
because there are the same number of scores smaller and larger than it.
Find the completion string for each incomplete line, score the completion strings, and sort the scores. What is the middle score?
🔗 Part A
First we need a way to associate open tags with their closing tags (i.e.
(
with )
), and the point values for closing tags.
import { strings } from "./util"
const pairs: { [key: string]: string } = {
")": "(",
"]": "[",
"}": "{",
">": "<",
}
const closes = new Set(Object.keys(pairs))
const opens = new Set(Object.values(pairs))
const pointValues: {
[key: string]: number
} = {
")": 3,
"]": 57,
"}": 1197,
">": 25137,
}
Our algorithm is thus as follows:
We need to maintain a stack which holds the open tags. If we get an open tag, we push it to the stack. When we get a closing tag, however, we must do the following:

If it matches the current open tag (the top of the stack), pop the stack because we have "closed" the chunk successfully.

If it does not match, then our end tag is invalid. Figure out what it's worth.
Then we can log the result.
let score = 0
strings().forEach(line => {
const stack = []
for (let i = 0; i < line.length; i++) {
if (opens.has(line[i])) {
stack.push(line[i])
} else if (closes.has(line[i])) {
if (
stack[stack.length  1] ===
pairs[line[i]]
) {
stack.pop()
} else {
score += pointValues[line[i]]  0
break
}
}
}
})
console.log(score)
🔗 Part B
Part B is very similar, except we don't compute the score for a corrupted line. Instead, we throw it out. (We've also renamed
pairs
to closesToOpens
, more on that soon).
let allScores: number[] = []
strings().forEach(line => {
const stack = []
for (let i = 0; i < line.length; i++) {
if (opens.has(line[i])) {
stack.push(line[i])
} else if (closes.has(line[i])) {
if (
stack[stack.length  1] ===
closesToOpens[line[i]]
) {
stack.pop()
} else {
// Corrupted line, ignore
return
}
}
}
// ...
})
If we reach the end of the line, we start computing the score. For each open tag in the tag, we'll need the corresponding closing tag and its value. For this we need two more objects, so our top of the file looks like this:
import { strings } from "./util"
const opensToCloses: {
[key: string]: string
} = {
"(": ")",
"[": "]",
"{": "}",
"<": ">",
}
const closesToOpens: {
[key: string]: string
} = {
")": "(",
"]": "[",
"}": "{",
">": "<",
}
const opens = new Set(
Object.keys(opensToCloses)
)
const closes = new Set(
Object.values(opensToCloses)
)
const pointValues: {
[key: string]: number
} = {
")": 1,
"]": 2,
"}": 3,
">": 4,
}
const allScores = []
Back in the for loop, we iterate through the stack and on each iteration:

Multiply the score by
5

Add the value of the corresponding end tag
Finally, add
score
to the allScores
array.
strings().forEach(line => {
// ...
let score = 0
stack.reverse().forEach(open => {
score *= 5
score += pointValues[opensToCloses[open]]
})
allScores.push(score)
})
Autocomplete tools are an odd bunch: the winner is found by sorting all of the scores and then taking the middle score. (There will always be an odd number of scores to consider.) In this example, the middle score is
288957
because there are the same number of scores smaller and larger than it.
We'll sort, then take the center.
const sorted = allScores.sort(
(a, b) => b  a
)
console.log(sorted[(sorted.length  1) / 2])