create account

Code Wars Python Challenge: Valid Parentheses by themarkymark

View this thread on: hive.blogpeakd.comecency.com
· @themarkymark ·
$21.35
Code Wars Python Challenge: Valid Parentheses
https://i.imgur.com/6GGhnvn.png

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.

![image.png](https://files.peakd.com/file/peakd-hive/themarkymark/Iq0swGgY-image.png)

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.

https://i.imgur.com/L1EU5CS.png

We have a potentially valid solution, let's run the full test suite and submit the solution if it passes.

https://i.imgur.com/OJQTuue.png

**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.

https://i.imgur.com/ynDl9xF.png

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.

# Code Wars Python Challenge Series

* [How to become a better programmer with Code Wars](https://peakd.com/programming/@themarkymark/how-to-become-a-better-programmer-using-code-wars)
* [Vowel Count](https://peakd.com/codewithmarky/@themarkymark/code-wars-python-challenge-vowel-count)
* [Array.diff](https://peakd.com/codewithmarky/@themarkymark/code-wars-python-challenge-walk-through-array-diff)
* [RGB to Hex](https://peakd.com/codewithmarky/@themarkymark/code-wars-python-challenge-walk-through-rgb-to-hex)
* [Square Every Digit](https://peakd.com/programming/@themarkymark/code-war-python-challenge-square-every-digit)

👍  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , and 338 others
👎  , , , , ,
properties (23)
authorthemarkymark
permlinkcode-wars-python-challenge-valid-parentheses
categorycodewithmarky
json_metadata{"app":"peakd/2020.09.4","format":"markdown","tags":["codewithmarky","programming","development","codewars","tutorial","palnet","neoxian"],"users":["themarkymark"],"links":["/programming/@themarkymark/how-to-become-a-better-programmer-using-code-wars","/codewithmarky/@themarkymark/code-wars-python-challenge-vowel-count","/codewithmarky/@themarkymark/code-wars-python-challenge-walk-through-array-diff","/codewithmarky/@themarkymark/code-wars-python-challenge-walk-through-rgb-to-hex","/programming/@themarkymark/code-war-python-challenge-square-every-digit"],"image":["https://i.imgur.com/6GGhnvn.png","https://files.peakd.com/file/peakd-hive/themarkymark/Iq0swGgY-image.png","https://i.imgur.com/L1EU5CS.png","https://i.imgur.com/OJQTuue.png","https://i.imgur.com/ynDl9xF.png"]}
created2020-09-17 03:18:03
last_update2020-09-17 03:18:03
depth0
children5
last_payout2020-09-24 03:18:03
cashout_time1969-12-31 23:59:59
total_payout_value12.982 HBD
curator_payout_value8.363 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length6,732
author_reputation1,774,088,473,727,210
root_title"Code Wars Python Challenge: Valid Parentheses"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id99,668,906
net_rshares87,251,944,588,151
author_curate_reward""
vote details (408)
@clove71 ·
I need to learn how to code, it is so interesting to me, I love it! I have been pushing my 13-year-old to learn basic code as well, lol!
properties (22)
authorclove71
permlinkqgt500
categorycodewithmarky
json_metadata{"app":"hiveblog/0.1"}
created2020-09-17 14:45:39
last_update2020-09-17 14:45:39
depth1
children2
last_payout2020-09-24 14:45:39
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length136
author_reputation679,470,738,132,560
root_title"Code Wars Python Challenge: Valid Parentheses"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id99,676,924
net_rshares0
@themarkymark ·
Check out Code Combat. 
👍  
👎  
properties (23)
authorthemarkymark
permlinkre-clove71-qgtk5f
categorycodewithmarky
json_metadata{"tags":["codewithmarky"],"app":"peakd/2020.09.4"}
created2020-09-17 20:12:51
last_update2020-09-17 20:12:51
depth2
children1
last_payout2020-09-24 20:12:51
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length23
author_reputation1,774,088,473,727,210
root_title"Code Wars Python Challenge: Valid Parentheses"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id99,682,803
net_rshares-453,232,939,383
author_curate_reward""
vote details (2)
@clove71 ·
Thank you, this looks so awesome!
properties (22)
authorclove71
permlinkqgyp2i
categorycodewithmarky
json_metadata{"app":"hiveblog/0.1"}
created2020-09-20 14:47:06
last_update2020-09-20 14:47:06
depth3
children0
last_payout2020-09-27 14:47:06
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length33
author_reputation679,470,738,132,560
root_title"Code Wars Python Challenge: Valid Parentheses"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id99,727,291
net_rshares0
@nathen007 ·
Going to try and solve this QBasic! Looking forward to the next one.
properties (22)
authornathen007
permlinkqgtavu
categorycodewithmarky
json_metadata{"app":"hiveblog/0.1"}
created2020-09-17 16:52:45
last_update2020-09-17 16:52:45
depth1
children0
last_payout2020-09-24 16:52:45
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length68
author_reputation259,697,568,226,684
root_title"Code Wars Python Challenge: Valid Parentheses"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id99,679,767
net_rshares0
@poshbot ·
https://twitter.com/MarkyHive/status/1306433227473784834
properties (22)
authorposhbot
permlinkre-code-wars-python-challenge-valid-parentheses-20200917t032215z
categorycodewithmarky
json_metadata"{"app": "beem/0.24.8"}"
created2020-09-17 03:22:15
last_update2020-09-17 03:22:15
depth1
children0
last_payout2020-09-24 03:22:15
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length56
author_reputation5,554,335,374,496
root_title"Code Wars Python Challenge: Valid Parentheses"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id99,668,936
net_rshares0