How to properly implement stack in Direction Array Reduction challenge in Swift

Question

I'm trying to solve a coding challenge in Swift. The task is to build a function that takes in an array of directions ex: ["NORTH", "WEST", "EAST", "NORTH", "EAST", "SOUTH"]. Any opposite directions that are next to each other in the array should be removed. Using the above example, the second and third indexes ("WEST" and "EAST") should be removed. However, the last index "SOUTH" should remain as it not directly next to a "NORTH" value in the array.

I am trying to implement a stack in order to compare the values and can't quite get it to work properly. This is my first time implementing a stack, and I am still getting used to Swift syntax as well.

My code is set up as such:

struct StringStack {
    var array: [String] = []

    func peek() -> String {
        guard let topElement = array.first else { fatalError("The Stack is empty.")}
        return topElement
    }

    mutating func pop() -> String {
        return array.removeFirst()
    }

    mutating func push(_ element: String) {
        array.insert(element, at: 0)
    }
}

func directionsReduce(_ directions: [String]) -> [String] {
    var reducedDirs = StringStack()

    reducedDirs.push(directions[1])
    for direction in directions {
        if((direction == "NORTH" && reducedDirs.peek() == "SOUTH")
            || (direction == "SOUTH" && reducedDirs.peek() == "NORTH")
            || (direction == "EAST" && reducedDirs.peek() == "WEST")
            || (direction == "WEST" && reducedDirs.peek() == "EAST")
        ) {
            reducedDirs.pop()
        } else {
            reducedDirs.push(direction)
        }
    }

    return reducedDirs.array
}

let testDirections1 = ["WEST", "WEST", "NORTH", "SOUTH", "EAST", "WEST"]
print(directionsReduce(testDirections1))

What I have returns an array of ["WEST", "WEST", "WEST"], however, this should be returning ["WEST", "WEST"]. I'm unsure how to initialize the stack in order to workaround this. I would appreciate any fresh eyes that could take a look.I'm also curious if this is best practice for implementing a stack or if there's a better way to go about this challenge. Appreciate any help or advice.

You're very close. Initialize the stack with first element. For the rest of the elements in the list (`directions[1:]`), add the element to the stack if the stack is empty or if the result of peek and the element are not opposite directions. Otherwise, pop off the element at the top of the stack and continue to the next. — snnguyen, Feb 04 '20 at 22:55
@snnguyen This worked, thank you! However, I'm running into another issue with Swift, perhaps you may know what's going on. I'm running two separate function calls to check the algorithm (I added your suggestion to the code). The first function call is the one listed and runs fine. The second function call happens directly underneath the first one with a different array, however it throws the fatalError from the peek() method. Not sure why that's happening as it's the exact same function. Perhaps a scope issue with the struct that I'm overlooking? — msiller455, Feb 04 '20 at 23:45
I'm no swift expert but looking at your code, `peek()` throws a fatalError if `array.first` is null (the stack is empty). You need to add a check to see if the stack is empty, and handle accordingly. — snnguyen, Feb 05 '20 at 00:55

score 1 · Accepted Answer · answered Feb 05 '20 at 16:24

For the rest of the elements in the list (directions[1:]), add the element to the stack if the stack is empty or if the result of peek and the element are not opposite directions. Otherwise, pop off the element at the top of the stack and continue to the next.

A size/length method would be useful for your stack implementation. It would provide a check before peek() to prevent throwing a fatalError

func directionsReduce(_ directions: [String]) -> [String] {
    var reducedDirs = StringStack()

    reducedDirs.push(directions[0])
    for direction in directions[1...] {
        if ((reducedDirs.length() == 0) 
             || (!areOppositeDirections(direction, reducedDirs.peek()))
        {
            reducedDirs.push(direction)
        } else {
            reducedDirs.pop()
        }
    }

    return reducedDirs.array
}

let testDirections1 = ["WEST", "WEST", "NORTH", "SOUTH", "EAST", "WEST"]
print(directionsReduce(testDirections1))

How to properly implement stack in Direction Array Reduction challenge in Swift

1 Answers1