We had already finished the string_to_tree method in the initializer of regextree. What was left was writing the match function. Some of the rules were quite easy to convert to code, but dot and star were quite difficult. For star, I couldn't quite figure out how to slice up the string into equally sized pieces to see if the given string matched both, so I did what was somewhat of a brute force solution, and wrote the program to iterate over all possible slices of the string. This was a later source of lost marks on the assignment, much to my chagrin, but it worked.
Dot was a different case. For dot, you actually are supposed to iterate over all possible ways of breaking up a string s into s1 and s2, so my code did that, and I received full marks. I thought that my code for star was the perfect synthesis of recursion and iteration, but it turns out that dot is a better example of that. The difference is that in dot, iteration was necessary in order to make recursive calls on multiple possible cases. In the code for star, I just used iteration to try different recursive calls until one worked. Kind of like shooting at a pop can with a shotgun loaded with buckshot. Did I hit the target? Yes. Did I also hit a large part of my neighbour's fence that was behind the target? Indeed I did. And it turns out that I later had to pay property damage later.
I had some code that I thought was great, and I thought it worked on all possible test cases. But there was one that I couldn't get it to work on. It was regex_match(RegexTree('(((1.0)|(0****.1*)*).(0|0))'), '0010'). This expression was too ludicrously complicated to be able to identify what the problem was, so i gradually narrowed it down to matching '(0***.1)') and '001'. What went wrong, was that if there were 3 or more stars attached to the left argument of a Dot, the code didn't work. 2 stars? Fine. 3 stars on the right argument? Totally fine. 2 on the left and 3 on the right? No problemo, compadre.
I puzzled over this for a while before I actually stepped through it, only to discover, much to my surprise, that the node that match was working on was not DotNode(StarNode(StarNode(StarNode(RegexTreeNode('0', []))), RegexTreeNode('1', [])) as it should have been, but something completely wrong and stupid.
string_to_tree wasn't working! This whole time I programmed under the assumption that that code would be the last thing to survive world war 3! It was the only support beam of my CN Tower, my life-raft in a choppy ocean of regexes, and suddenly it was gone. I was devastated. I wasted a whole bunch of time trying to fix the problem in regex match, when the problem was in string to tree the whole time.
I guess this shows the importance of rigorous unit testing. I could have saved myself hours if I had known where the problem was where it arose, or if I had solved it before even starting the match function. I will make sure to include unit testing of more difficult and varied test cases in the future. If only there were a program that could perfectly find any possible bug in a program that could arise on any possible input. Alas, reality intrudes, in the form of the Halting Program. Nothing seems to be perfect or absolute in this all-too-human universe of ours, but I take comfort in that nothing seems broken entirely beyond recognition either.
I located the problem, stared at it, and gave up. I sent it off to my partner (outsourced it to far Asia, I like to say), and she took her turn staring at it. She almost had a solution, although she described it as quite roundabout (I never took the trouble to understand it, I was too busy trying to come up with my own). Eventually, I solved the problem with a while loop! A bit of iteration that I learned more so from the labs and readings than from the lecture, or from Assignment 1, the tour of Anne Hoy (I still think that's hilarious, especially after I learned that Hanoi is in fact in my partner's ancestral country. That was a semi-embarassing conversational, in which I revealed my hereditary geographical ineptitude. My father likes to say that I get it from my mother).
Definitely this course has been focused on recursion over iteration as the master technique to solve all (or at least a broad class of) problems. I don't know what 108 was like, I didn't take it. But I tend to think that I will be able to teach myself iteration, as it is a lot easier for the human mind to understand, particularly in terms of what the computer is doing. Human brains aren't 'programmed' to think recursively, as Prof. Heap emphasizes. I'll certainly have to pick up some of it if I can expect the demands of CSC207 and 209 not to pull a lever to open the trap door beneath my feet, only to reveal that I was in an airplane 36, 000 feet in the air, leaving me to a parachuteless free fall into a lifetime of working as a cashier at McDonalds. I have a lot of academic performance stress.
Anyways, the rest of this week was spent on sorting algorithms, and I'll get into those next post. Toodles!
Dot was a different case. For dot, you actually are supposed to iterate over all possible ways of breaking up a string s into s1 and s2, so my code did that, and I received full marks. I thought that my code for star was the perfect synthesis of recursion and iteration, but it turns out that dot is a better example of that. The difference is that in dot, iteration was necessary in order to make recursive calls on multiple possible cases. In the code for star, I just used iteration to try different recursive calls until one worked. Kind of like shooting at a pop can with a shotgun loaded with buckshot. Did I hit the target? Yes. Did I also hit a large part of my neighbour's fence that was behind the target? Indeed I did. And it turns out that I later had to pay property damage later.
I had some code that I thought was great, and I thought it worked on all possible test cases. But there was one that I couldn't get it to work on. It was regex_match(RegexTree('(((1.0)|(0****.1*)*).(0|0))'), '0010'). This expression was too ludicrously complicated to be able to identify what the problem was, so i gradually narrowed it down to matching '(0***.1)') and '001'. What went wrong, was that if there were 3 or more stars attached to the left argument of a Dot, the code didn't work. 2 stars? Fine. 3 stars on the right argument? Totally fine. 2 on the left and 3 on the right? No problemo, compadre.
I puzzled over this for a while before I actually stepped through it, only to discover, much to my surprise, that the node that match was working on was not DotNode(StarNode(StarNode(StarNode(RegexTreeNode('0', []))), RegexTreeNode('1', [])) as it should have been, but something completely wrong and stupid.
string_to_tree wasn't working! This whole time I programmed under the assumption that that code would be the last thing to survive world war 3! It was the only support beam of my CN Tower, my life-raft in a choppy ocean of regexes, and suddenly it was gone. I was devastated. I wasted a whole bunch of time trying to fix the problem in regex match, when the problem was in string to tree the whole time.
I guess this shows the importance of rigorous unit testing. I could have saved myself hours if I had known where the problem was where it arose, or if I had solved it before even starting the match function. I will make sure to include unit testing of more difficult and varied test cases in the future. If only there were a program that could perfectly find any possible bug in a program that could arise on any possible input. Alas, reality intrudes, in the form of the Halting Program. Nothing seems to be perfect or absolute in this all-too-human universe of ours, but I take comfort in that nothing seems broken entirely beyond recognition either.
I located the problem, stared at it, and gave up. I sent it off to my partner (outsourced it to far Asia, I like to say), and she took her turn staring at it. She almost had a solution, although she described it as quite roundabout (I never took the trouble to understand it, I was too busy trying to come up with my own). Eventually, I solved the problem with a while loop! A bit of iteration that I learned more so from the labs and readings than from the lecture, or from Assignment 1, the tour of Anne Hoy (I still think that's hilarious, especially after I learned that Hanoi is in fact in my partner's ancestral country. That was a semi-embarassing conversational, in which I revealed my hereditary geographical ineptitude. My father likes to say that I get it from my mother).
Definitely this course has been focused on recursion over iteration as the master technique to solve all (or at least a broad class of) problems. I don't know what 108 was like, I didn't take it. But I tend to think that I will be able to teach myself iteration, as it is a lot easier for the human mind to understand, particularly in terms of what the computer is doing. Human brains aren't 'programmed' to think recursively, as Prof. Heap emphasizes. I'll certainly have to pick up some of it if I can expect the demands of CSC207 and 209 not to pull a lever to open the trap door beneath my feet, only to reveal that I was in an airplane 36, 000 feet in the air, leaving me to a parachuteless free fall into a lifetime of working as a cashier at McDonalds. I have a lot of academic performance stress.
Anyways, the rest of this week was spent on sorting algorithms, and I'll get into those next post. Toodles!
No comments:
Post a Comment