leetcode month, day 2: Fenceposted by “valid parens”

Today’s challenge is Valid parens. And it reminded me of several of the things that I don’t particularly like in Go.

Problem statement boils down to “here’s a string of brackets: parens, square brackets, braces. Tell us if they match properly (true) or don’t (false)”. Algorthmically this is dead simple:

Start with an empty stack.
for each character in the string:
  if it's an open bracket, push it.
  if its a close bracket:
    if the stack is empty, return false.
    if the top of the stack isn't the matching open, return false.
    pop the stack.

When we're done, return true if the stack is empty, false otherwise.

In Perl or Python, I’d have a stack pointer, and move it up and down an array as I pushed and popped characters by altering the stack pointer and assigning to the appropriate point in the array. If the stack pointer went below 0, I’ve gotten too many close parens, and I return false.

This approach doesn’t work well at all with Go, because Go arrays and slices Do Not Work Like That.

To push onto an existing array, we need to use a := append(a, new). Just assigning to an index outside of the slice’s current boundaries will panic.

We could still use the stack pointer to move backward, but then we’d have to have more complex code to decide if we need to append or just move the pointer. (Side note: doing it that way would probably use less memory — the working version of my solution used more memory than 90% of the other solutions). Instead, we just use the slice notation to pop the stack instead, with a := a[:len(a)-1].

My original iterations with a real stack pointer failed miserably because I wasn’t properly tracking the length of the array, and was perpetually getting the stack pointer position wrong, causing the code to panic. It was only after completely discarding the stack pointer that I got it to finally work.

Items of note:

• I remembered I’d need to use range() to iterate over the string, but forgot that I would have to string() the characters I was getting so they were strings instead of runes. I wasted a good chunk of time trying to mess with runes before I realized that I needed string() instead. Runes are considerably more second-class citizens.
• Still running afoul of using make() properly. Finally figured out the syntax to create an empty string array, but it took some Googling to get it.
• I decided to make the code less complex by creating a pairs map that mapped left brackets to right ones. This meant I could check pairs[left] == right for whether I’d matched the left and right brackets. It also meant that if we ever added more bracket pairs in the future, it’d be be easier to implement them.
• I got fenceposted by a[len(a)-1] accessing the last element, and a[:len([a)-1] dropping the last element. I naively expected that since a[len(a)-1] accessed the last element, I’d want a[:len(a)-2] to drop that last element, but that takes one too many, running me into another fencepost. Yes, it’s good that it’s symmetric, and now I’ll remember, but I definitely had to look it up to figure out both of them.
• Forgot the check for “did we close all the opens”. I probably would not have missed it if I was making my own test cases, but it wasn’t in the tests. Note to self: watch out for poor initial test cases. There is an opportunity to add more, I think?

So how’d I do overall? We saw I was in the bottom 10% in memory usage, boo, but runtime? “Beats 100.00% of users with Go”.

I’ll definitely take that as a win, but it’s definitely obvious I need to keep practicing and getting these idioms back under my belt.

func isValid(s string) bool {
    // We'll run through the string, doing the following:
    // - if we see an open bracket, we stack it.
    // - if we see a close bracket, we pop the stack. If the
    //   brackets match, we continue, otherwise we fail.
    // - when we run out of brackets, the stack must be empty or we fail.

    stack := make([]string,0)

    pairs := map[string]string{
        "(": ")", 
        "[": "]", 
        "{": "}",
    }

    for i := range s {
        char := string(s[i])
       _, ok := pairs[char]
       if ok {
           // left, push it
           stack = append(stack, char)
       } else {
           // right, stack empty?
           if (len(stack) == 0) {
               fmt.Println("pop of empty stack")
               return false
           }
           // Not empty. match?
           if (pairs[stack[len(stack)-1]] != char) {
               fmt.Println ("mismatch")
               // mismatched bracket, fail
               return false
           }
           // Match. Pop stack.
           stack = stack[:len(stack)-1]
       }
    }
    // Check for "did we close all the open brackets".
    return len(stack) == 0
}

That’s one for today, and I need to clean the house, so I’ll call it a day.