The first l̶o̶v̶e̶ assignment

This week I won't post about the technical learning we did, but rather talk about our first assignment, the impressions it gave me and comparison to my previous CS assignments. 

The context of assignment was simple: There were 3 stools with a stack of cheeses on it. Sometimes, these cheeses would have to be moved one by one (and without placing larger cheese on top of a smaller one) to another stool for maintenance (or for whatever reason... There has to be one for us to have an assignment). The 3 stool problem was quite simple and explained in details. But then, we were introduced the real problem, where we had 4 stools instead of 3. Even though, having an extra stool makes the cheese movement problem a lot simpler, it didn't make our assignment any easier.

Our goal was to create a TOAH model (Tower of Ann Hoi, the name of the puzzle) that would support already existing code for playing this game on a GUI controller. We would then have to write the code for a console controller, keeping in mind that our model has to work with both, and finally, we would have to make another module that would solve a 4-stool TOAH puzzle in the most efficient way.

This is an illustration of the 3-stool puzzle 

Even though, everyone told me that the last part of the assignment is the most challenging part, I felt somewhat overwhelmed in the very beginning. The reason for that was my inability to comprehend some parts of the docstring and the GUI-controller code that was already written. I didn't know what data-structures to use and what methods to write. For example, the docstring for TOAH model class contained a list of methods, and many of those simply had to return a corresponding internal value, which made me confused about whether I just need to create a variable or was it an actual method. (It turned out to be a method, as I later understood).

After the initial attempt, I put of the assignment for more than 2 weeks, after which I could come back and finally finish the first part in one day. I felt a significant boost of inspiration when I was able to play the game manually after hours fixing mistakes and looking for solutions. 

Then the "hard" part of the assignment came: creating an algorithm to move cheeses with 4 stools. In fact, the actual algorithm was already given to us, but it had a twist. 

While there was a set and definite way to move 3 cheeses, the 4 cheese case required us to move some amount of cheeses to an intermediate stool, then move the rest with our definite 3-stool strategy, and then move the rest of the cheeses. The twist is in the "some amount". We weren't given a definite formula for "some", and while it existed, we were still strongly advised to use a recursive algorithm to find "some" (otherwise, you would have to convince the markers in your understanding of the formula you found on google). 

Eventually, I managed to find the best solution, but I still don't know whether I wrote the best algorithm for that. I used a formula given in the handout that gave us the number of moves with a given "some". Since I didn't know a straight way to go, I just used an exhaustive search, trying every possible "some" (this number was always smaller than the amount of cheeses that we had to move), and then used the one that resulted in the least amount of moves. (it was possible to use a constant for every case, but it would provide sub-optimal performance).

The last part of the assignment was definitely challenging, but in a different way from the first part. Instead of looking for how to write code, I had to discuss possible ways to minimize the number of moves with other students (I even tried taking a derivative of a recursive function to find a minimum... It wasn't a good idea with my current math knowledge...). But eventually, it worked, and seeing how the puzzle is solved by itself for any number of cheeses is something that makes completing CS assignments more satisfactory than for any other course.

Scope and visibility

Last time, we've talked about recursion, and how we can use it. We are still focused on recursion in general, but meanwhile, we've temporarily changed our gears for a few lectures to learn about scope and visibility of variables.

In computer science, scope is not what most Call of Duty or Counter-Strike players would think is. Scope of an object is related to where it is "seen" and therefore, where it can be used. Generally, scopes are defined to be "local", "modular" and "global". The scope of a particular object or variable is usually defined from where it was "declared" (there's not formal declaration in python, so we'll interpret it as where it was first used).

Variables can be created within a module, a function or a class, or globally, within the whole program. This doesn't mean, though, that these are the only levels of scope that we can have. For example, a variable inside a function would be considered to have "local" scope, but then, we can also define another function within our function, where we would define another variable that would also be local, but have different scope level comparably to the variable from the outer function.

Since python doesn't have privacy settings for variables, the importance of the scope really comes down to when and how you can use a given variable, especially when there are two variables with an equivalent identifier (for example, 'x' that is defined in the module and 'x' that is defined within a function).

By default, python looks within the inner-most local scope first, meaning that the 'x' within the function would be considered first. If such is not found, python will look for outer local, modular, and then, global. If a corresponding variable wasn't found anywhere, you will receive an error saying that a variable is not defined.

A question that many people have at this point is: "But what if we have an 'x' in our function when we really want to access the 'x' in the module?".
This is where namespaces and key word 'global' comes in handy.

Using a namespace allows you to specify directly what variable should be used (for example, you can specify a variable within a specific module or class by stating it's name first:  'name.variable'.)

You can also use keyword 'global' to specify that you want to refer to a global variable. As I see it so far, this keyword only allows you to create and assign values to objects/variables on a global context, but not necessarily read a global variable if you already have one with the same name. For example, if you use
global x
x = 25
Then you will get a global variable 'x', even if this code was written within a function that is soon to be terminated (this variable would exist globally even if the function ceased to exist).
If variable 'x' already existed, you would change its value to 25.

There are still things that I don't seem to understand on a 'definite' level, but I seem to have enough intuition to know when and how I am able to use variables.

Recursion

    This week, as promised, we have learned the basic concepts of recursion. The general idea was not a novelty for me, since I already had some experience with recursion, but the actual use and application of these concepts were somewhat new to me (and quite interesting). 

    As with classes and objects, recursion can be foudn in some real world examples. Some of the occurances of recursio can be found in the following pictures:   

     These images may be interesting or funny, depending on viewer's point of view, but since this blog is about computer science, we will be looking into application of the recursion concepts in computer science.

In computer science, the most basic definition of example would be a function call from within its own definition.

For example:

def Func(i):

    print(i)

    Func(i+1)

    If this example is confusing, you can imagine what happens step by step: You enter the function at the header with some argument (let's say, i = 1). Then you print it, evaluate i+1, and then... You enter the function at the header with...

    As you have probably imagine, this example would create an analogy of an infinite loop and would keep printing numbers from 1 to infinity (or rather until an error occurs).

    Of course, we already know how to create infinite loops, and there would be no point in creating the concept if recursion for that. But there are things that can only be achieved with recursion (or at least, it would be preferable, more efficient and easier).

    A more useful example of recursion was presented to us on the lectures. Let's say, we wanted to compute a summ of all numbers in a arbitrarily nested list (meaning that this list may contain any number of other list inside, which may also contain other lists, etc.

    We already know how to use for loops and add up numbers of the list (or we can use "sum" function to do so). The only problem is that when we try to add a list to a number, python gets really mad. This is where recursion can save the day.

    When we were constructing this recursive function, we had to rely on a basic case; or something that we already know how to solve. As I mentioned above, we already know how to add up numbers in a list, using for loop. The concept of recursion comes in handy when we realize that the nested lists are simply smaller problems inside of a big one. 

    Using this knowledge, we taught our function to reduce the problem to its simpliest case. Our function behaved this way: If the problem is simple (basic case) - solve it and return the result. If the problem is complicated (an entry of a list is another list and not a number) - solve that problem separatelly by calling our function again with only the inner list as an argument. After the inner list was summed up, it is returned to the previous caller (which is the first instance of our function) and then used as a number, representing the sum of numbers in the list. And if the inner list contains another list, same approach would be taken until there are only numbers.

This process can be easily understood from the following example:

lst = [1, 2, [3, 4], 5].

    We can't simply add all entries from this list, so we use our function. The first two elements are just numbers, so we can easily sum them up. The third element, though, is another list. In this case, we call our function again, but only on that list.

Now, our function only has to work with 

[3, 4]

This case is easy, 3 + 4 is 7, so we return this value. Now, our main list would look like

[1, 2, 7, 5]

Now, it's another simple case: 1 + 2 + 7 + 5 = 15, so we return our value.

    You can imagine any list with other lists as elements, so you convert every list into a single number element, starting from the lowest-level list (deepest ones). Until your whole list consists only of numbers, in which case, you simply return the sum.

Object-Oriented Programming

In our first weeks of class, we have learned about object oriented programming and its difference from traditional ways of programming that we were used to in 108. This was not a new material for me, since I already had experience with objects and classes, but I knew that I will have things to learn due to lack of practical experience with classes. Although, I had good intuition about classes and knowledge from some programming books that I've read. A good way of explanation of what is a class in those books was a microwave (it also explained importance of functions to make programs universal and allow users to chose their own cooking time and other parameters). Basically, every object can be classified (sometimes it's not that easy... For example, many people struggle to classify watermelon as a fruit or vegetable). Those objects will have some common properties shared among them, but not necessarily their values. In the example of microwaves, each microwave has the cooking part (the one that emits microwaves), but different microwaves have different power or even location of that part within the microwave. Also, some microwaves have additional properties, such as clock, while others may only have timer.
   Some classes can be inherited. For example, you may have a general class of vehicles, where every vehicle must have a steering wheel, but then, you get different kinds of vehicles, such as SUV or trucks, which also have a steering wheel, but differ in some other properties (number of wheels, ability to attach a trailer, etc. Every SUV is a car, but not every car is SUV. In python, every class is inherited from class "object" (similarly how everything in the world is made of atoms... or whatever is the smallest unit of matter). Object is everything (not money...).
   I also didn't mention methods. These are like... Things that objects do. For example, every car can drive, and the speed at which it drive depends on its properties (engine power/mass). Every truck can attach a trailer, but not every vehicle can (this method is unique to trucks). Methods work in similar way to properties, and they are just functions within methods, so I'll omit this explanation from this, already lenghty post.
    See how it goes next week with recursions, which should be very interesting, which should be very interesting, which should be very interesting, which should be very interesting, which should be very interesting, which should be very interesting, which should be very interesting...