Week 11: A2 Continued

Ok, looking back at fixing regex_match: as a review, the problem I was having was that my code did not account for valid string matches that were less than one character long for bar and dot trees.

This meant my code was fundamentally wrong, since I used range(0, len(string)), which would not execute at all where len(string) == 0.

The mistake was easily remedied by initializing the variables I was using outside of my range loop, so I would have some values to work with regardless of the length of the string:

        s1 = ''

        s2 = ''

        for i in range(0, len(s)):

            if regex_match(r.children[0], s1) and \

               regex_match(r.children[1], s2):

                return True

            s1 = s[0:i]

            s2 = s[i:]

Which made the code work out, thankfully. Come to think of it, this bugged me at first when I approached this function, but I forgot to account for it: this makes me realize another important aspect of coding, which is very similar to story writing: it cannot be 'edge of your seat' work, it must be planned before hand, and whenever you think of potential test cases, issues, or ways to throw off your protagonist, write them down!

Ok: the last issue with the code was this:

AssertionError: None is not true : Rejects valid match: (DotTree(Leaf('e'), Leaf('e')), '')

Which reminded me that the same problem I was trying to address previously had still not been solved.
With a little bit of thinking and a lot of redundancy, I came up with a working solution:

        s1 = ''

        s2 = ''

        if regex_match(r.children[0], s1) and \

               regex_match(r.children[1], s2):

                return True

        for i in range(0, len(s)):

            if regex_match(r.children[0], s1) and \

               regex_match(r.children[1], s2):

                return True

            s1 = s[0:i]

            s2 = s[i:]

Week 10: Looking over A2

Since I'm writing this a few weeks late, I realize there may be errors here, but I decided to work out all the kinks in my A2 code, just for kicks (alliteration!).

I'll start with the first error:

 AssertionError: False is not true : Rejects valid regex: ((0|1)*|2)*

For my A2 code, I used several helper functions, and turns out that some were quite useless:

I made a function called num_parentheses, and used it in balanced_parentheses:

def balanced_parentheses(s: str) -> bool:

    if num_parentheses(s) == 2:

        return s[0] == '(' and s[-1] == ')' 

    if len(s) == 1:

        return s == '0' or s =='1' or s =='2' or s == 'e'

    i = []

    for char in s:

        if char == '(':

            i.append('(')

        if char == ')':

            if len(i) == 0:

                return False

            else:

                i.pop()

    return len(i) == 0

Look familiar? This is very similar to Dan's code for stacks and balanced parentheses, minus the stack ADT.

The problem here was very straightforward:

  if num_parentheses(s) == 2:

        return s[0] == '(' and s[-1] == ')' 

This code would lead to an error for any regex which did not have ')' as the last character, such as ((0|1)*|2)*. Upon taking it out, the code worked for this case, as well as the next failure (grumble).

Another failure in my code was:

AssertionError: None is not true : Rejects valid match: (DotTree(Leaf('e'), Leaf('2')), '2')

In order to figure out the mistake in my code, I scrutinized the section handling DotTrees:

if r.symbol == '.':

        for i in range(0, len(s)):

            s1 = s[0:i+1]

            s2 = s[i+1:]

            if regex_match(r.children[0], s1) and \

               regex_match(r.children[1], s2):

                return True

Looking at the length of the string s, I realized that my code did not account for the special case where s is one character long! All I needed to add was this:

if len(s) == 1:

            return regex_match(r.children[0], '') and \

                   regex_match(r.children[1], s) or\

                   regex_match(r.children[1], '') and \

                   regex_match(r.children[0], s)

And the code worked.

For the next failure:

AssertionError: None is not true : Rejects valid match: (DotTree(StarTree(Leaf('1')), StarTree(Leaf('2'))), '2222')

This time, the problem with my code was that I assumed no matter what, the string would be at least 1 character long in order to match, especially with the Bar and Dot operators. I'll leave this for next week's post, so I have some information left to cover.