Week Ten - Assignment 2

Week Ten -  Assignment 2

I have spent a relative long period of time on assignment two, especially part two, it was giving me a lot trouble. The first design part was quite easy and straightforward, you can write it in literally one day if you understand the features of the regex expression pretty well. However, I did not my design, I created a class to classify leaf and a class to have one children and one class to have two children. This way works, but I don't think the relationship between different regex expression was characterized well using this approach. On the other hand, the instructor created several inheritance relationship to link the classes. I think this approach is much more clearer than what I did. 

However, part two was the challenge part in this assignment, I did this part twice. When I first did it, I did not look at the hint on piazza. So I break on the regex expression on brackets to produce a nested list. And use the nested list to check validity of the expression. This approach worked, however it only works on valid strings. So an exception can raise if you try to check something like this ")2.(1|1))", since the order of the brackets is incorrect, the method that converts string to list will go out of bound. Moreover the runtime was extremely slow on the function all_regex_permutations when the length of the string get larger. It actually resulted in a OutOfMemoryrError when the length get to greater than 6, I think there are just too many recursions for the computer to handle and eventually caused it use up all the memory. So, I decide to try a different approach for the assignment (it is really hard to give the nested list approach up, because I spent so long to figure it out). The second time, I used the way instructor assignments. I have to say the hint was so useful for the assignments, it kind of give the solution away already. If I were to figure this algorithm out by myself, I think it will take a long time to do so. I think I really need to improve on those type of skills, but that is computer science really about. I used the approach where I look at each individual bar or dot, see whether it split into two valid regex expressions. If all of them doesn't, return false. This approach did not cause any exceptions, and it was much much quicker for the all_regex_permutations methods. Regex_match is little hard to deal with, but in my point of view, if you really understand the algorithm the instructor was talking about in class, it is actually not that band. I think the way to break a string into two parts to check for ‘*‘ is such a smart idea. If I were to do it, I probably will choose to do a loop on it or something.