You up for solving another Python coding challenge together?
Yes? Great, let's check this one out.
This is the first 5 kyu difficulty challenge I have received since I reset my account. My account is currently ranked 7 kyu, so this is a significant difficulty jump. Let's analyze the challenge first.
It looks like we are going to be fed a string and we need to parse it for valid parentheses syntax. Our function should accept a string that contains any number of characters, digits, and symbols along with a set amount of open and close parentheses. We need to determine if there is the correct amount of open and close parentheses and if they are valid order.
I've always hated parsing text in any programming language, but this looks a lot harder than it really is. Let's figure out our main problems we need to solve.
- Identify parentheses in input
- Determine if parentheses is in valid position
- Determine if we have correct amount of open and close parentheses
- Return boolean result
If you have been following along with my series, you will notice I always break down our challenge into problems we need to solve. One of the most important skills of a programmer is to take bigger problems and turn them into a group of smaller problems. Whenever you feel you are stuck solving a problem, you likely didn't break it down small enough.
We can see in the constraints we will receive more than just parentheses and we can ignore other types of brackets.
Can you guess the first thing we need to? If you said iterate our input string, you are correct. Let's start by creating a for loop.
def valid_parentheses(string):
for character in string:
pass
By now you should be used to this pattern. We want to take each character of the input string and analyze it one at a time. A for loop is perfect for this, we could also use a list comprehension. A list compression is more pythonic, but let's leave that for a potential refactor.
There is nothing to test with this solution as we know it will fail so let's figure out what we need to do next.
There are a few ways to solve this problem, they all vary dramatically in complexity. I'm thinking we will keep track of whenever a parentheses is opened, and update whenever we receive a closing parentheses. The easiest way to do this is to create a variable to keep track of the opened parentheses and subtract from it when we hit a close parentheses. Let's give that a try.
def valid_parentheses(string):
counter = 0
for character in string:
pass
Notice we put the counter outside of the for loop, this is very important as we want it to persist between iterations of the for loop.
Let's try looking at each character and updating the counter appropriately.
def valid_parentheses(string):
counter = 0
for character in string:
if character == '(':
counter += 1
Here we will increment the counter whenever we reach a '(', but we also need to look for a closing parentheses.
def valid_parentheses(string):
counter = 0
for character in string:
if character == '(':
counter += 1
if character == ')':
counter -= 1
There is nothing to test as we are not providing a return value. Any guess what we want to return? We can't return counter as that doesn't represent if the string if valid or not. In what conditions would a string be valid?
If counter = 0 after the for loop has iterated all characters would represent a correct amount of parentheses, so let's do that.
def valid_parentheses(string):
counter = 0
for character in string:
if character == '(':
counter += 1
if character == ')':
counter -= 1
return counter == 0
I am simply returning an expression that will evaluate to True if we have a valid string. Let's run the tests and see how we did.
Ugh, that doesn't look good. We apparently missed something.
Any idea what it is?
Our code correctly tests that every open parentheses has a matching closing parentheses, but we overlooked one issue. What if we receive a closing parentheses before an open parentheses? This wouldn't be a valid string, but our code has no way to test for this. Any idea how we can?
If we receive a closing parentheses before an open, our counter will be a negative number. Just think about it, if we start at 0 and receive a '(' we would subtract 1 from our counter. Let's at a check for this.
def valid_parentheses(string):
counter = 0
for character in string:
if character == '(':
counter += 1
if character == ')':
counter -= 1
if counter < 0:
return False
return counter == 0
After running the tests, we have all green.
We have a potentially valid solution, let's run the full test suite and submit the solution if it passes.
BOOM!
We are in business, we can attempt to refactor this solution into a list comprehension but I wouldn't as we have a lot of code in the for loop and it isn't easily made concise by a list comprehension.
Looking at the solutions, one condensed things onto one line more efficiently and another is very similar to our solution.
Both are good solutions but one thing you should avoid doing is using non-descriptive variable names. The more your variable names explain what you are doing and read like English, the less you need to comment and the easier it is to read and understand. The first solution also has a very janky return statement.
If you like this series, let me know in the comments.
I'm going to start maintaining a thread for all the posts in this series. You can see them all below starting with the introduction.