HN Explorer

Ask HN: Extra puzzle for day 10 of Advent of Code

2 points by fjfaase ↗ HN
What is the minimum number of brackets to add to fix every line of the input? (I think it is 81 for the example input.)

And what is an efficient algorithm for find this number?

3 comments

[ 4.4 ms ] story [ 17.6 ms ] thread
jstx1
Isn't that number fixed for each line? You just need to close every open bracket (in the correct order obviously). Or do you mean something else?
fjfaase
What about [(((])))? If you fix this in a 'linear' manner you get [((()))]()()(). But a shorter way to fix it is: []((([]))).
jstx1
Oh I got it, you're talking about the corrupted lines from part 1, I was thinking about the incomplete ones from part 2.