Well, I didn't start the assignment over the weekend as I had hoped I would have learned to do from my experience with Assignment 1. What can you do? I had a lot of math homework.
Anyway, thanks to the completely appropriate pushiness of my partner (the text read "When do you want to meet TOMORROW to work on the assignment", emphasis added), I settled in for ~3 hours of work on Wednesday (read: 2 hours of work on Wednesday). It was productive, we got a lot done. The first thing we did, after reading and understanding everything in the handout and given code that we needed for step 1, was write a function that converts trees into strings. Shortly after finishing it, we were slightly upset to realize that it wasn't actually necessary. Hmph. Oh well, it was a good learning experience, parsing trees into strings is not that different from parsing strings into trees, and it gave us a valuable unit testing method, wherein we could create a tree, turn it into a string, and then call our string_to_tree helper function on that string to see if it output the tree with which we started off. Would that we were working in abstract mathematics, where we could simply define our parser as f(x), and then the desired string_to_tree would be simply f^-1(x), the not-explicitly-defined inverse function that we then wouldn't have to compute (as long as we could prove its existence and uniqueness). For the practical solution, we have to get our hands a bit dirty.
We very quickly whipped up some code that worked on the easy cases, and then we had rules for what to do individually with each of *, ., and |. They even involved some nifty applications of find and rfind to look for a left bracket starting from the beginning of the string and for a right bracket from the end of the string respectively. However, we couldn't get those rules to execute in the right order. It got to the point where we could change which test cases pass and which fail by manipulating the order of the relevant lines in the function. Not very helpful. At that point, we had to grab some fried chicken before CSC165 in order to be able to absorb any of the material, so we bailed.
Next morning, I decided to get the exercise done. It passed all of the tests on the first pre-mark this time, possibly because I wrote better test cases. But, more importantly, as I was doing the assigned readings (gotta love 'Code Like a Pythonista'), I came across some code that did something similar to what we wanted string_to_tree to do (string_to_tree_to_do ). In the sample code for binary trees, there was a group of functions designed to work together to parse arithmetic expressions containing sums and products into tree representations. I read this carefully, and then using these ideas, wrote some code that worked for strings with bars and dots. After all, bars and dots work very similar to arithmetic's 'plus' and 'times', at least from a purely syntactic perspective, looking at regex strings. Even down to inclusion of brackets.
Making the code work around stars was a more daunting task. I added a star clause (if, else) closer and closer to the fundamental level, with better and better results each time, until eventually all the cases worked! I then realized that you ONLY need the star clause at the fundamental level, the rest are extraneous, which greatly simplified my code. I think we'll go forward with this approach, because it works, but I still would like to get our original code working, if only as a purely theoretical exercise. Maybe we could even compare runtime.
In any event, things are looking good, and we should have a match function done soon.
In the lab I was finally able to reduce the 4 binary tree cases I mentioned in my Week 7 cases down to one line of code. It's especially easy when doing a sum. You simply add the result of a recursive call on self.left IF self.left, else 0. So too for self.right. I'm confident that this way of thinking about trees can be applied to other problems as well. Just when I think I'm the master of recursion, it throws another piece of knowledge at me, and I become that much more appreciative of its beauty. I think the wide range of applications of recursions is indicative of the recursive nature of being. I'm glad to see the way in which computer science adds to our appreciation of the beauty of the universe, through understanding the ways in which it operates. I find that most subjects have this, otherwise they wouldn't be very interesting at all.
No comments:
Post a Comment