Week 10 – Assignment 2 Part 2

For the second part of Assignment 2, we had to implement four functions that performed operations on regex tree strings, ternary strings, or RegexTree objects.

I think the hardest part by far was finding the outermost root of binary trees for is_regex and build_regex_tree. When I first wrote it, I'd tried to find the root by using the built-in index function. My function involved finding the index of the rightmost ')' between the beginning of the string and r2's first '('. If r2 doesn't contain a '(', then just find the last ')' in the string. The index after that is the “root_index”. However, if there isn't any ')' in the string, then I just set the “root_index” as 1 as it should be right after the first item. Finally, I increased the index by 1 for every '*' in the string.

This was not one of the methods that the professor hinted to us in class, but I came to this conclusion on my own and it worked...although it's admittedly a very messy solution. In the end, my partner came up with a much better solution, where she simply found the indices of every '.' and '|' in the string. Then, if the difference between the '('s and ')'s before this index was equal to 1, then she knew that this was the outermost root index. The code for this method was, indeed, much shorter and more concise, so we went with this in the end. It was also one of the methods that the professor had suggested, but I hadn't understood it in class, so seeing my partner's code was very helpful to me.

Week 9 – Lab #8 and Exercise 3

This week's lab was better than last week's, at least for the first two BST_rec modules that we had to implement. But then we had to implement one method in the BST class and another in the _BSTNode class, and a third in the _BSTNone class, and I got kind of confused on what I should be calling. I couldn't figure out what would be different with the count_less in _BSTNone at first. In the end I realized that since every None in BST is represented by _BSTNone, and that class has a count_less method, I didn't have to write the “if...else” conditions because they would be taken care of by the methods of the different types of BSTNodes.

As for our third exercise, all I can say is that I did a lot of tracing for these functions to understand how the program should work.

For part a, I took a tree's preorder and inorder traversals, broke them down into left and right subtrees (while noting how I knew which part was the left, root, and right), and got the pre- and inorders of these subtrees, then repeated until I got to an empty tree, at which point I could backtrack and substitute a None into the new tree being made. I made several trees this way to make sure that my method of splitting the traversals was correct, then wrote the function according to how I'd done it while tracing. Then I traced through my function several times to make sure it was correct.

For part b I think that my code is longer than it needs to be, but also that it's quite clear. You could say that I had some trouble with this part; it took me at least two hours just to grasp the recursive nature of this problem, trying to understand and make use of the hint. But at one point something clicked and I proceeded to finish the function in another hour. It was that I needed to find the child with the deepest leaf. This seemed a lot more obvious after I realized it, but...well, of course. So with that, I recursively called the function on the left child (if there was no right child) or the right child (if there was no left child) or cal it on both children (if they exist) and find the one with the maximum depth and return that. 

Week 8 – Lab #7 and Assignment 2 Part 1

I think this lab was the first that I found quite difficult, aside from maybe the second one. I thought I'd understood the linked list structure, but when doing this lab, I had a lot of trouble coming up with the solutions. For instance, for the __setitem__, __delitem__, and insert methods, I didn't know how to find the position and modify the item at that position. I kept thinking of using the __getitem__ method to find the item at the given index, but then realized that I couldn't do anything with the returned value because it was just a value, not an attribute that I could set to modify the list.

def __setitem__(self, ind, val):
     if self.empty or ind < 0:

         raise IndexError

     else:

          self.__getitem__(ind) = val

But I did realize that this would not work, and I knew I should've been using recursion, but...I couldn't think of a way to do it. After some help from the T.A. I mostly got that we could keep checking a smaller and smaller portion of the list and somehow, at the end, when the index in question is the beginning of the list, it would be the item attribute of the LinkedList and we can set it as so. I'm currently still trying to understand this better.

As for Assignment 2, well, this was quite a confusing concept. It took me a long time to understand what we were “designing”, and then what we had to write and did not have to write for this section. After figuring out that we just had to create classes for the different types of RegexTrees and implement their attributes, it was easier to get started. However, I wasn't so sure about the inheritance choices that I made, because I think I still had some repeated code. I also used BarTree's __init__method in my DotTree class, which probably wasn't the best idea now that I think about it, but I didn't know how to get rid of that bit of duplicate code. All in all, I didn't find it too difficult to write but I was quite unsure of the design choices that I made.

Week 7 – Recursion

Though I've mostly been writing about recursion for my weekly topics (as that is what we've been learning), this post is to be solely dedicated to this very important concept.

Recursion is the concept of calling a function from within itself. Usually we would define a function and then call it after we've completely finished writing its body and output. But in recursion, we define a function and call it within its own body. This is very useful with objects whose structures are defined recursively, and we've seen it used with binary trees, linked lists, nested lists, and other types of the sort.

A binary tree, for example, has an internal node as its root and left and right children, which are also binary trees themselves. So to count the number of nodes in the tree, we would count the number of nodes in the left subtree, then count the number of nodes in the right subtree, then add 1 more node for the internal node at the root. This turns into a function like the following:

def count(n: Tree):

return 1 + sum([count(n) for n in t.children])

We use the count function inside its body because we are also counting the number of nodes in the tree's left and right children. And what are those children? Trees. So it only makes sense that we would use the same function for the same operation. And when there are no children, the recursive calls stop because t.children will have no values and the return value will only be 1. Then the function will begin to wind back up, counting 1 for each leaf and adding up the number of leaves in a child, then adding 1 for that node and combining the value with the value of the other child, and finally adding 1 to account for the root node.

So, as seen, we have no doubt focused a lot on recursion this semester. But what is so important about it? Why is it so useful that we are expected to know how it works and to be able to use it in any applicable situation?

The way I see it, our golden rule is a key reason: laziness. Recursion will usually provide the easiest and shortest solution to a problem.

It's the easiest to write, read, and understand code, which makes it less work for anyone doing anything with the program.

First, as the initial writer of the code, simply calling the function that you just wrote (since you know it does exactly what you want) is much easier than writing nested loops or having counter variables to try and keep track of how deep you are into the structure...and other things like that. In most cases a function involving a recursive structure will be very difficult to write non-recursively. Here, recursion is easier because it will automatically stop as long as you provide the action to perform when the base case is reached. You don't need to know when the base case is reached (and knowing this is hard because there will be many layers/depths, one within another, so you can't really count them), because the function will recognize that.

Afterwards, when the next person has to read your code, they will see the places where you've called the function recursively and think something like, 'Ah, they just did the same operation on the next level of this object.'. In other words, when reaching a level where we already know what happens, we can just stop and substitute the previously-found result. This is also what we do when writing recursive code.

Week 6 – Trees and Finishing Assignment 1

The recursive structure of trees allows their functions to perform the same action on each of their individual nodes and leaves as they do on the whole tree. This makes most functions and methods for trees recursive.

In the example we saw in lecture of the basic tree class, a tree had two attributes: its value and children. The value could be any object, but its children was a list of—well--more trees. This was what allowed the same actions to be done on both the tree and its subtrees, recursively, until it got to the leaves, stopped, and gradually made its way back to the entire tree. For instance, to count the number of nodes a tree had, one would count the initial node at the root of the tree and then add up the number of nodes of each child of the tree. Since each child was also a tree, one could use the same function to count the number of nodes for that child.

Other than binary trees, we looked at a type of unary tree called a linked list. A linked list had a head and a rest, and the rest was another linked list containing its own head and rest, and so forth. This made the linked list a recursive structure as well, and we could perform the same operations on each part of the linked list as the linked list itself.

Assignment 1, which I'd started last week, will be due this week. It took me a long time to understand the GUIController and ConsoleController modules, because I was confused about the differences between the graphics of a cheese/stool and the object cheese/stool. That was before I took the time to read the docstring in GUIViewables, which cleared up that CheeseView actually inherits from the Cheese class and the PlatformView class to represent the cheese, so I only had to actually work with the Cheese class. After that, I progressed fairly quickly with the ConsoleController functions and TOAHModel functions. Finally, for the tour_of_four_stools function in Tour.py, I initially did not use recursion to find the value of i; I had used that the most efficient value of i would always be equal to the floor of n/2, with n as the number of cheeses, and just recalculated this value every time I ran through tour_of_four_stools. However, after learning that we were expected to use a recursive solution to find i, I rewrote a function to find i essentially following the formula given in the handout. Other than this, I found my A1 coding process to be a generally smooth one.

Week 5 – More Recursion, Namespaces, and Assignment 1

This week we continued to learn about recursion. What helped me to understand recursion more easily was learning its structure, which consists of the general case and the base case(s). Writing recursive code for the base case first and then applying the concept to the general case makes the process, which can sometimes get messy, a lot clearer to me. We were also shown many different applications of recursion, such as in nested lists, writing a function that can return permutations, and drawing graphics. The turtle animation was very interesting and really showed me, visually, how powerful recursion can be.

We then looked at an example of namespaces to see the differences between defining variables globally, nonlocally, and locally. We were told that we should not reuse variable names even if they are not in the same scope.

I've also started to think about assignment 1. The code for the move_cheeses function that we were presented with in lecture has proven very helpful to my understanding of the recursive nature of this game. I plan to use the example code as the “base case” of the tour_of_four_stools function (which is one of the later parts of the assignment, so I'm not completely certain how it's going to work just yet, but I think it will help a lot). 

Week 4 - Recursion, Testing, and Exercise 2

This week, we looked some more at recursion, which is a very important concept in programming as it can make code easier to read and write, as well as much shorter. As a side note, I find that I really enjoy using shorthands such as list comprehensions and ternary if statements because they shorten code so much and, after understanding their structures, make code much faster to write. From my understanding, recursion is used when our function needs to do the same action (such as one or many calculations) for each part of a whole object. We traced through several example recursive functions in class, and I find it quite easy to understand if I just consider the state of the function at each step and its output.

We also learned about testing our code with unittest, which can provide more specific feedback than doctest. Personally I find writing the unittest functions very tedious, as there are so many cases that can be considered and yet the most of the testing code is relatively similar between the functions. Finding the different cases is the most difficult part. But I do understand the importance of testing code and ensuring that the program works as expected in every situation.

Exercise 2 was due yesterday; it was mainly about inheritance and raising exceptions. I did not find it very difficult, and I had a bit of fun playing around with the inheritance levels and program output. But one thing that I had a problem with was in part b, where the handout stated that “e2b.py” was to import only the exceptions in e2a.py, and not the raiser function. At first, I didn't know that passing raiser in as a function object allowed it to be used as a regular function inside reporter, so I'd thought that we had to pass a string of the function name. This cost me a lot of time because I tried to find out how to convert a string into a function. Afterwards, through some trial and error as well as reading the posts of my fellow classmates on Piazza, I realized my mistake and passed raiser in as an object, then called it in reporter and analyzed its results for e2b.py.