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.
Thursday, 31 October 2013
Slog Entry Week 7
When Prof. Heap was coding in lecture this week, he used the tuple packing notation that we learned in last week's lab. I thought that was pretty slick. Both because of the advantages of tuple packing (it reduces confusion by assigning multiple variables in the same step) and because it was excellent integration of tutorial and lecture. The labs are a really great learning opportunity, and a lot of the coding that I do in a week is done in lab. Once I got a high-functioning partner relationship going, I really started enjoying the labs. I know Week 6 especially we finished all of the code in no time, with very few instances of the dreaded "getting stuck". It occurred to me that not only are labs enjoyable (and marked independently), but they're being utilized effectively to increase the amount that we can learn from lecture and tutorial combined. They make it possible to fit more content in the course without simply swamping the student with material, as I am experiencing in some other courses at the moment. *cough* Every math course *cough*.
My only other experience with labs was with first year physics last year, and I really strongly disliked them. Firstly, my TA barely spoke English at all, so his explanations and 'help' were completely useless. Secondly, the groups were too large to be high-functioning. I mean, you've got 4 people doing a lab report that ultimately has to be written by one person. Inevitably, someone ends up useless, and just through lack of assertiveness (not lack of intelligence), I end up that person.
Beyond that there's increased risk of having a personality clash. In a group of 2 people, there's one possible personality conflict, and if that happens, you just change groups. In physics, the groups were immutable. In a 4 person group, applying some basic combinatorial methods, we obtain that there are
(4 * 3) / 2! = 6
personal relationships, sextupling the risk of clash. And this happened, with at least 2 of the connections.
Also, in a 2 person group, generally both people have laptops anyway. But if there are no laptops, it doesn't take that long for one person to just grab the keyboard and try out the idea that they think will work but whose validity they can't convince their partner of.
The pair-programming thing is genius too. As much as my egotistical side hates to admit it, I do code better and faster when there's someone looking over my shoulder. There's a bunch of little stupid mistakes that I still make, that I think I'll always make (not putting the thing that you want to print in brackets; did anyone else learn to code on Python 2?). More importantly, if there's some fundamental flaw in the theory backing my approach to a problem, either simply by explaining my method aloud I'll realize it, or my partner will be able to (eventually) convince me of it, and we save valuable time. From the ansatz (German for approach, educated guess in Mathematics), I'll often be able to glean valuable insight into what a more effective solution might be, and if not, my partner has cooked one up in between bouts of fuming as I write my misguided code. In the end, we get a better finished product with less precious time wasted.
The exercise was not too challenging. Or so I thought. I wrote out my code, commenting as I went and running doctests like a good little CSC148 student. By the end, it passed all of the tests, and I was confident in its codified virility. The next day, when I checked the premark, I viewed the strangest result since my code for Exercise 1 failed the 'easy' tests and passed the 'hard' ones.
My e5a code failed three tests and passed five, e5b passed three and failed 5. In both cases, one of the passes was the PEP8 style checker, so it's actually much worse than it sounds. I was baffled. I had no idead what could have gone wrong, until I actually went and took a look at my code. It turns out I had unwittingly (or witlessly, if you prefer) written my function so that it only worked on symmetrical trees. Duh. That's, like, the most obvious of the potential problems. I clearly should have checked it. In the future, I will be more careful to write an exhaustive set of tests.
This is an interesting psychological phenomenon that I've noticed when I'm programming. Often, I'll rush through the process of actually writing the code so that I can start testing less mediately (not quite immediately, but better than completely mediate). Almost without exception, my code with fail (often raising an exception of its own in the process(or)). Looking back at my script, I'll often notice some problem completely unrelated to the specific failure that got me looking at the code, and fix that, only to encounter the same failure. Eventually I fix the right problem, but the moral is that even just by thinking the code failed, you gain a piercing critical lens through which to give your code a second look, producing results leagues ahead of the initial ansatz. Perhaps when coding by hand on a test or exam, I should mentally simulate a run of the program that ends in a failure, so that I can trick my self into a more detail orientated state with which to take that all too important second look.
Perhaps I should just code slower and more thoughtfully, and not run the test before I've taken the second look.
I went back, tried a few things, and settled on code that broke the problem down into 4 cases that correspond to the truth table for existence of a left node and existence of a right node. I had one case for two children trees, one for trees with only a left node, one for trees with only a right node, and one for trees with no children and a lot of disposable income (leaves). Although this made the code work in every test case, I was vaguely dissatisfied. I felt there was a more efficient solution somewhere. It wasn't until Week 8's lab that I would find out what this was...
Monday, 21 October 2013
Slog Entry Week 6
This week was pretty much all about the midterm. I didn't know exactly what to expect, but I thought to myself, "what are the things that the professor mentions every week?". So I figured that there would probably be a question on the midterm involving a list comprehension, and one involving recursion.
As it turned out, question 1 was computing some instances of a recursive function.
Question 2 involved writing a recursive function that uses a list comprehension.
Question 3 was implement a class with two methods that use list comprehensions.
Luckily my guess was spot on.
I hope it turns out alright, I feel pretty confident about my performance, although I'm not sure if I was supposed to write an initializer for the subclass FunctionalList. Hopefully in the absence of a subclass initializer it just calls the superclass constructor. Hopefully.
I went in to question 1 with a bit of an edge, because during the assignment I had computed a bunch of those M(n,i) least number of moves calculations by hand. I was trying to figure out which n's it was working optimally for (where n is the number of cheeses to move). Before I wrote a function to calculate the optimal split, I tried n // 2, which is optimal for some cases but not others. In the darkest hour I hard coded a bunch of control flow that used n // 2 for n = 5, 6, 9 and (n + 1) // 2 for n = 3, 11, 15 ... etc. It was hideous and confusing, but it worked up to n = 14, with no discernible pattern for the optimal i. In hindsight, if there was a discernible pattern, it wouldn't be an open problem in mathematics. But it was early in the morning, and I was pretty heavily caffeinated.
As it turned out, question 1 was computing some instances of a recursive function.
Question 2 involved writing a recursive function that uses a list comprehension.
Question 3 was implement a class with two methods that use list comprehensions.
Luckily my guess was spot on.
I hope it turns out alright, I feel pretty confident about my performance, although I'm not sure if I was supposed to write an initializer for the subclass FunctionalList. Hopefully in the absence of a subclass initializer it just calls the superclass constructor. Hopefully.
I went in to question 1 with a bit of an edge, because during the assignment I had computed a bunch of those M(n,i) least number of moves calculations by hand. I was trying to figure out which n's it was working optimally for (where n is the number of cheeses to move). Before I wrote a function to calculate the optimal split, I tried n // 2, which is optimal for some cases but not others. In the darkest hour I hard coded a bunch of control flow that used n // 2 for n = 5, 6, 9 and (n + 1) // 2 for n = 3, 11, 15 ... etc. It was hideous and confusing, but it worked up to n = 14, with no discernible pattern for the optimal i. In hindsight, if there was a discernible pattern, it wouldn't be an open problem in mathematics. But it was early in the morning, and I was pretty heavily caffeinated.
Slog Entry Week 4
I liked this exercise because it was really math-heavy, and I like geometry. I hard coded separate classes for each shape, which worked on the first-time through, even before I was running any static analysis. I do all my coding in PyCharm now, back then I was using IDLE. I was forced away from IDLE because it would occasionally throw random syntax errors on completely syntax error free strings (I ran the same code in PyCharm and it was fine). I think it was having trouble distinguishing between opening and closing quotations, even though there was no difference in visual representation in the editor, or in key on the keyboard. Anyway, I couldn't figure out how to fix it, so I switched to PyCharm.
It was only after submitting that I chanced to glimpse my friend's code for the same exercise during a Settlers of Catan based social gathering. The __str__ method had a lot of if/else control flow that checked for angle = 90 and base = width to determine the type of quadrilateral. I thought that was pretty slick. Although it was less readable (IMO) due to a lot of indentation levels and long blocks of code, it probably accomplished the same goal with less duplicate code, which is respectable. It really got me thinking about how to write code with the least duplication, in one line if possible.
In the lab, my partner and I were slowed down by the unit testing step. We didn't really know how it worked, so we expected a lot more automation than is reasonably possible. I think our first attempt was to put "unittest" at the end of our code, and expect it to figure out what we wanted our code to do, and if it did that. Pretty optimistic.
We got the tests working once we understand that each test works by basically asserting that some statement is true. I was proud to be able to tell my dad that we learned unit testing in Computer Science. He's a programmer, and he works in QA, so the vast majority of his job is running unit tests and enforcing unit testing standards. It was this week that he started drilling into my head that you should write unit tests for your code as you write your code, because you can avoid a lot of problems that way, and detect bad code before you pack it up and ship it off to QA. I didn't really get it until I stayed up until 4:00 one night/morning trying to get my three stools algorithm to work. More on that later.
It was only after submitting that I chanced to glimpse my friend's code for the same exercise during a Settlers of Catan based social gathering. The __str__ method had a lot of if/else control flow that checked for angle = 90 and base = width to determine the type of quadrilateral. I thought that was pretty slick. Although it was less readable (IMO) due to a lot of indentation levels and long blocks of code, it probably accomplished the same goal with less duplicate code, which is respectable. It really got me thinking about how to write code with the least duplication, in one line if possible.
In the lab, my partner and I were slowed down by the unit testing step. We didn't really know how it worked, so we expected a lot more automation than is reasonably possible. I think our first attempt was to put "unittest" at the end of our code, and expect it to figure out what we wanted our code to do, and if it did that. Pretty optimistic.
We got the tests working once we understand that each test works by basically asserting that some statement is true. I was proud to be able to tell my dad that we learned unit testing in Computer Science. He's a programmer, and he works in QA, so the vast majority of his job is running unit tests and enforcing unit testing standards. It was this week that he started drilling into my head that you should write unit tests for your code as you write your code, because you can avoid a lot of problems that way, and detect bad code before you pack it up and ship it off to QA. I didn't really get it until I stayed up until 4:00 one night/morning trying to get my three stools algorithm to work. More on that later.
Slog Entry Week 3
At this point in the course I still had little to no idea of what I was doing.
This assignment was when I really internalized the idea that Python documentation can be your friend. It was the readings from the documentation on try and except clauses that helped me figure out how to finish the assignment.
This lab went a lot better than the first lab. My partner and I were communicating through writing code, rather than lengthy dialogue where we were each trying to make each other understand our way of thinking, which is nearly impossible.
This assignment was when I really internalized the idea that Python documentation can be your friend. It was the readings from the documentation on try and except clauses that helped me figure out how to finish the assignment.
This lab went a lot better than the first lab. My partner and I were communicating through writing code, rather than lengthy dialogue where we were each trying to make each other understand our way of thinking, which is nearly impossible.
Monday, 14 October 2013
Slog Entry Week 5
A Couple of Definitions:
Object Oriented Programming:
This is the way Python works. In Python, to accomplish programming goals, you define classes. Within that class, objects have attributes. The class also has methods that work with its objects. This is very intuitive, because it allows you to think about any object in Python as an analogue to a physical object with physical properties. An object is just a particular instance of a broader class of things. As soon as you initialize an object of a class, you know what attributes it has and what you can do with it.
Recursion:
Recursion is the process of a function calling itself. Recursive functions have a base case and a recursive step. The base case is the simplest possible instance of the task. The goal of the recursive step is to break the task down into base cases. Often this is a matter of calling the function itself with different parameters, in an attempt to solve some subtask within the task as a base case. Recursion is useful for solving problems where the solution is simply breaking it down into simpler problems and solving them, like solving for the nth Fibonacci number, for example.
This was also the week that the assignment was due. Phew! What a load of work! For the week leading up to the deadline, I felt like I didn't have any courses except CSC148. It was a full time job.
My partner and I got the first couple of steps going the previous week, and decided that over the weekend I would work on the algorithm to solve the three stools (and then the four stools) problem, while my partner worked on implementing DomainStools so that it provided a flawless visual representation. I left the bulk of the task to Sunday, and I spent a lot of time staring at the computer screen. After spending a lot of time coming up with the code for the three stools solution, Prof. Heap posted some high functioning sample code that accomplished the same task. I was a little bit frustrated. However, I do think that working out the code myself helped improve my understanding of what was happening during the solution, and of recursion in general.
When I later began working on the four stools solver, my hands were tied by the lack of 4 arguments designed for the stools in the tour_of_four_stools function. I mucked around a for a couple of hours in this framework, wrote sole complicated code that involved a lot of control flow to designate which stool was the beginning, which were the two interim stools and which was the destination. However, I couldn't quite get it to work, so I wrote a separate helper function that took all four stools as arguments, and it was really easy to write. It worked almost the first time through.
The only problem was that many of the cases were sub-optimal, as according to figures from Piazza and other academic studies of the four stools problem that I found on Google. My algorithm was more efficient than the three stools 2**n - 1, but sub-optimal. I initially hard-coded a different formula for the optimal split up to n == 14, but eventually came to my senses and wrote a split(n) function that returned the optimal i for any n. This required writing an M(n, i) function that recursively calculated the least number of moves to solve the four stools problem with n cheeses and a split of i, using the recursive formula given on the assignment.
One of the things I found interesting was that my M(n, i) function called the split function, to determine the optimal split to use in each call of itself, while the split(n) function called the M(n, i) function to compare the minimal number of moves for each split. They built an interdependent recursive network that still boggles my mind a little bit. Intuitively, it almost seems like they are both defined circularly, so neither should work, but they both do, through the magic/science of recursive calls.
Overall, I really enjoyed this assignment, because of the mathematical aspect. A lot of the time while working on it, I really had a strong sense that I was using computer science to do mathematics, which was a really good feeling. I'm a mathematics specialist, and one of my reasons for studying computer science is to learn enough coding so that I'll be able to write programs to help me conduct mathematical research, and I really felt like I was making progress towards that goal. In addition, the approach to problem solving is very similar in Mathematics and Computer Science. Often, I'll get stuck, and have no idea how to proceed. It's good to review the readings, and your objectives, and all of your previous code, but a lot of the time it comes down to just trying something. Even if it's a bad idea, you can always Ctrl + z it away, and you might get a better idea from the attempt, or be able to refine it into a working solution. These problems that we use computers to solve often quickly escalate beyond the grasp of human understanding. That's where the science comes in. You do an 'experiment' with some new code, see what happens and learn from it. If it doesn't work, figure out why and refine the approach or try a new one. If it does, and you don't quite understand why, there's a lot to be gained from figuring out why it works. Then you can solve an analogous problem confidently.
All in all, I learned a lot about programming, and about problem solving, from this assignment. This may be a bit overoptimistic, but I'm starting to finally feel like I can write and understand code!
Object Oriented Programming:
This is the way Python works. In Python, to accomplish programming goals, you define classes. Within that class, objects have attributes. The class also has methods that work with its objects. This is very intuitive, because it allows you to think about any object in Python as an analogue to a physical object with physical properties. An object is just a particular instance of a broader class of things. As soon as you initialize an object of a class, you know what attributes it has and what you can do with it.
Recursion:
Recursion is the process of a function calling itself. Recursive functions have a base case and a recursive step. The base case is the simplest possible instance of the task. The goal of the recursive step is to break the task down into base cases. Often this is a matter of calling the function itself with different parameters, in an attempt to solve some subtask within the task as a base case. Recursion is useful for solving problems where the solution is simply breaking it down into simpler problems and solving them, like solving for the nth Fibonacci number, for example.
This was also the week that the assignment was due. Phew! What a load of work! For the week leading up to the deadline, I felt like I didn't have any courses except CSC148. It was a full time job.
My partner and I got the first couple of steps going the previous week, and decided that over the weekend I would work on the algorithm to solve the three stools (and then the four stools) problem, while my partner worked on implementing DomainStools so that it provided a flawless visual representation. I left the bulk of the task to Sunday, and I spent a lot of time staring at the computer screen. After spending a lot of time coming up with the code for the three stools solution, Prof. Heap posted some high functioning sample code that accomplished the same task. I was a little bit frustrated. However, I do think that working out the code myself helped improve my understanding of what was happening during the solution, and of recursion in general.
When I later began working on the four stools solver, my hands were tied by the lack of 4 arguments designed for the stools in the tour_of_four_stools function. I mucked around a for a couple of hours in this framework, wrote sole complicated code that involved a lot of control flow to designate which stool was the beginning, which were the two interim stools and which was the destination. However, I couldn't quite get it to work, so I wrote a separate helper function that took all four stools as arguments, and it was really easy to write. It worked almost the first time through.
The only problem was that many of the cases were sub-optimal, as according to figures from Piazza and other academic studies of the four stools problem that I found on Google. My algorithm was more efficient than the three stools 2**n - 1, but sub-optimal. I initially hard-coded a different formula for the optimal split up to n == 14, but eventually came to my senses and wrote a split(n) function that returned the optimal i for any n. This required writing an M(n, i) function that recursively calculated the least number of moves to solve the four stools problem with n cheeses and a split of i, using the recursive formula given on the assignment.
One of the things I found interesting was that my M(n, i) function called the split function, to determine the optimal split to use in each call of itself, while the split(n) function called the M(n, i) function to compare the minimal number of moves for each split. They built an interdependent recursive network that still boggles my mind a little bit. Intuitively, it almost seems like they are both defined circularly, so neither should work, but they both do, through the magic/science of recursive calls.
Overall, I really enjoyed this assignment, because of the mathematical aspect. A lot of the time while working on it, I really had a strong sense that I was using computer science to do mathematics, which was a really good feeling. I'm a mathematics specialist, and one of my reasons for studying computer science is to learn enough coding so that I'll be able to write programs to help me conduct mathematical research, and I really felt like I was making progress towards that goal. In addition, the approach to problem solving is very similar in Mathematics and Computer Science. Often, I'll get stuck, and have no idea how to proceed. It's good to review the readings, and your objectives, and all of your previous code, but a lot of the time it comes down to just trying something. Even if it's a bad idea, you can always Ctrl + z it away, and you might get a better idea from the attempt, or be able to refine it into a working solution. These problems that we use computers to solve often quickly escalate beyond the grasp of human understanding. That's where the science comes in. You do an 'experiment' with some new code, see what happens and learn from it. If it doesn't work, figure out why and refine the approach or try a new one. If it does, and you don't quite understand why, there's a lot to be gained from figuring out why it works. Then you can solve an analogous problem confidently.
All in all, I learned a lot about programming, and about problem solving, from this assignment. This may be a bit overoptimistic, but I'm starting to finally feel like I can write and understand code!
Subscribe to:
Posts (Atom)