Tag: #CodingPuzzle

This is part of a series of coding puzzles inspired by the #CodingPuzzle tag/puzzles originally curated and shared by Ali Spittel. This is my approach to solving those puzzles in Swift. If you have any comments or answers you want to share, post them below! I’d love to read them.

---

Puzzle #2

Given strings of brackets, determine whether each sequence of brackets is balanced.

When would you come across a situation like this? Well, if you ever write a source editor, you might come across something like this. As most programming languages use brackets to denote context, functions, and other divisions, we’ve probably all come across a situation where we forgot to close something off.

For the sake of this exercise, let’s define what brackets mean. In this case, it’ll be three sets of characters: ( ) , [ ] , and { } . The first character we’ll call the “open bracket” and the latter the “close bracket”.

So, what makes a balanced sequence?

1. A matched pair of brackets.
2. Any nested brackets must also be matched pairs.

An example of some balanced sequences include: () , [(){}] , {([()])}

An example of some imbalanced sequences include: (() , [([)]] , {([)]}

If any of those become unpaired, then the entire sequence is considered imbalanced. If you’ve ever created a class in Swift and forgot to close a brace when defining functions, you’ll know what that is.

By the above definitions, we can thus determine that in a balanced sequence:

1. It has an even number of brackets
2. An open bracket will never meet a close bracket of a different type
3. A closed bracket will never appear before its corresponding open bracket

That said, here’s how I approached the problem.

First, I defined what each of the brackets were.

let brackets: [Character: Character] = [
    "[":"]",
    "(":")",
    "{":"}"
]
var openBrackets: [Character] { return Array(brackets.keys) as! [Character] }
var closeBrackets: [Character] { return Array(brackets.values) as! [Character] }

Using a dictionary, I’ll be able to easily look up the close bracket for a given open bracket.

Next, let’s look at my function to solve this.

func isBalanced(_ string: String) -> Bool {
    if string.count % 2 != 0 { return false }
    var stack: [Character] = []
    for character in string {
        if closeBrackets.contains(character) {
            if stack.isEmpty {
                return false
            } else {
                let indexOfLastCharacter = stack.endIndex - 1
                let lastCharacterOnStack = stack[indexOfLastCharacter]
                if character == brackets[lastCharacterOnStack] {
                    stack.removeLast()
                } else {
                    return false
                }
            }
        }
        if openBrackets.contains(character) {
            stack.append(character)
        }
    }
    
    return stack.isEmpty
}

First, if the string has an odd number of characters, we automatically fail it. This is in line with point number 1 above.

I then declare a variable to temporarily hold brackets. This stack will be used in the following loop.

Next, we go through each character of the string. Our first check is whether the character is a close bracket or not. If it is, and our stack is empty, it means we’re encountering a close bracket before its open bracket counterpart. We thus return false. If the stack isn’t empty, we check if the last character on the stack is an open counterpart of this close bracket. If it is, we remove the open bracket from the stack. Otherwise, we return false.

If it’s not a close bracket, we’re likely looking at an open bracket. Those automatically get added to the stack.

This loop functions for all characters in the string. Afterwards, our return is whether or not the stack is empty. If it’s not empty, it meant we had more open brackets than closed brackets, and while the earlier catches may not have produced a return, it technically is an unbalanced bracket set.

Here are a few sample calls to this function and their outputs.

isBalanced("()") // True
isBalanced("[]") // True
isBalanced("][") // False
isBalanced("[][") // False
isBalanced("()()") // True
isBalanced("[(){}]") // True
isBalanced("{{[()()][]}}") // True
isBalanced("[]()({)}") // False
isBalanced("(((") // False

I had initially hoped to tackle this with recursion, but I found the above solution to be easier to follow and much easier to manage.

Did you have a different solution? Is there something I could improve with my Swift code? I’d love to hear from you!

I’ve been following Ali Spittel‘s #CodingPuzzle challenges. While I’ve read most of them, I haven’t actually done them.  But each of them would be a fun little exercise. So, I figured I’d go back and tackle each of them in Swift.

Before I start, a note: There are always multiple ways to tackle coding challenges. This is just my approach to it. If there are better/more optimal ways of doing it, please comment and share your solutions! I’d love to see them. This is as much a way for me to share what I’ve done as it is for me to learn from how others see problems and want to solve them.

That said, here is the first puzzle:

Puzzle #1 – Simple Pig Latin

“Move the first letter of each word to the end of it, then add “ay” to the end of the word. Leave punctuation marks untouched.”

If this was just taking a sentence without punctuation, this would be a lot easier. You could split the array, modify the words, and rebuild the sentence. But keeping punctuation untouched adds a bit of a challenge.

Being me, I also wanted to make sure that this would handle if someone inadvertently misses a space after some punctuation. (No, this likely doesn’t handle apostrophes properly, so contractions will probably not be correct; but I’m no native Pig Latin speaker to know.) So I may have put a little too much thought into this.

First, I wanted to make a function that modifies a word into its proper Pig Latin form.

/// Takes a word and makes it Pig Latinized
func pigLatin(word: String) -> String {
    var newWord = word
    let startIndex = newWord.startIndex
    let firstCharacter = newWord[startIndex]
    newWord.append(firstCharacter)
    newWord.append("ay")
    newWord.remove(at: startIndex)
    return newWord
}

With this function, I can now pass in parts of a sentence as needed. With that done, now I just need to get the words to pass in.

I could have split the array based on space, but that wouldn’t necessarily preserve punctuation. So I instead opted to go through the string character-by-character and parsing words that are found.

func simplePigLatin(_ text: String) -> String {
    let characterSet = CharacterSet.whitespacesAndNewlines.union(.punctuationCharacters)
    var piggyText = ""
    var temporaryWord = ""
    for (index, character) in text.enumerated() {
        let scalar = character.unicodeScalars.first!
        if characterSet.contains(scalar) || index == text.count - 1 {
            if temporaryWord.count > 0 {
                let pigLatinWord = pigLatin(word: temporaryWord)
                piggyText.append(pigLatinWord)
                temporaryWord = ""
            }
            
            // Append any punctuation or white space
            if characterSet.contains(scalar) {
                piggyText.append(character)
            }
        } else {
            // Append letter to temporary word
            temporaryWord.append(character)
        }
    }
    
    return piggyText
}

I go through each character and, if it’s a letter, I add it to a temporary word. If I hit a non-letter (punctuation or whitespace) or the end of the string, I take that temporary word, modify it for authentic Pig Latin, and append it to the return string.

With all of that, here are some sample outputs:

let word = simplePigLatin("I wish I could speak in Pig Latin; I really do!")
print(word) // Iay ishway Iay ouldcay peaksay niay igPay atinLay; Iay eallyray oday!

let contractions = simplePigLatin("I've got day-to-day issues.")
print(contractions) // Iay'evay otgay ayday-otay-ayday ssuesiay.

let badSpacing = simplePigLatin("I forgot,this is not where commas,go")
print(badSpacing) // Iay orgotfay,histay siay otnay hereway ommascay,ogay

So that’s how you can do Pig Latin in Swift. No, it’s not perfect. There are other cases that aren’t dealt with, such as how to handle words starting with vowels or ‘qu’. But I’m no linguist.