shape-warrior-t

shape-warrior-t, 10 months ago

Here's an O(n) solution using a stack instead of repeated search & replace:

closing_to_opening = {')': '(', ']': '[', '}': '{'}
brackets = input()
acc = []
for bracket in brackets:
    if bracket in closing_to_opening:
        if acc and acc[-1] == closing_to_opening[bracket]:
            acc.pop()
        else:
            acc.append(bracket)
    else:
        acc.append(bracket)
print(''.join(acc))

Haven't thoroughly thought the problem through (so I'm not 100% confident in the correctness of the solution), but the general intuition here is that pairs of brackets can only match up if they only have other matching pairs of brackets between them. You can deal with matching pairs of brackets on the fly simply by removing them, so there's actually no need for backtracking.

Golfed, just for fun:

a=[]
[a.pop()if a and a[-1]==dict(zip(')]}','([{')).get(b)else a.append(b)for b in input()]
print(''.join(a))

shape-warrior-t, 1 year ago (edited 1 year ago)

(Attempt 2 at posting something like this, kbin was being weird last time)

Link to a YouTube video going through the main part of the newsletter, with links to other stuff in the description: https://youtu.be/wadIR3wjDfQ

Out-of-context picture

shape-warrior-t, 1 year ago

M O S S

They're certainly a rather interesting character. Both for the audience and, in a different way, presumably for the people in their life (Noelle and Toriel in particular).