Week 11: A2 Continued

Ok, looking back at fixing regex_match: as a review, the problem I was having was that my code did not account for valid string matches that were less than one character long for bar and dot trees.

This meant my code was fundamentally wrong, since I used range(0, len(string)), which would not execute at all where len(string) == 0.

The mistake was easily remedied by initializing the variables I was using outside of my range loop, so I would have some values to work with regardless of the length of the string:

        s1 = ''

        s2 = ''

        for i in range(0, len(s)):

            if regex_match(r.children[0], s1) and \

               regex_match(r.children[1], s2):

                return True

            s1 = s[0:i]

            s2 = s[i:]

Which made the code work out, thankfully. Come to think of it, this bugged me at first when I approached this function, but I forgot to account for it: this makes me realize another important aspect of coding, which is very similar to story writing: it cannot be 'edge of your seat' work, it must be planned before hand, and whenever you think of potential test cases, issues, or ways to throw off your protagonist, write them down!

Ok: the last issue with the code was this:

AssertionError: None is not true : Rejects valid match: (DotTree(Leaf('e'), Leaf('e')), '')

Which reminded me that the same problem I was trying to address previously had still not been solved.
With a little bit of thinking and a lot of redundancy, I came up with a working solution:

        s1 = ''

        s2 = ''

        if regex_match(r.children[0], s1) and \

               regex_match(r.children[1], s2):

                return True

        for i in range(0, len(s)):

            if regex_match(r.children[0], s1) and \

               regex_match(r.children[1], s2):

                return True

            s1 = s[0:i]

            s2 = s[i:]

Week 10: Looking over A2

Since I'm writing this a few weeks late, I realize there may be errors here, but I decided to work out all the kinks in my A2 code, just for kicks (alliteration!).

I'll start with the first error:

 AssertionError: False is not true : Rejects valid regex: ((0|1)*|2)*

For my A2 code, I used several helper functions, and turns out that some were quite useless:

I made a function called num_parentheses, and used it in balanced_parentheses:

def balanced_parentheses(s: str) -> bool:

    if num_parentheses(s) == 2:

        return s[0] == '(' and s[-1] == ')' 

    if len(s) == 1:

        return s == '0' or s =='1' or s =='2' or s == 'e'

    i = []

    for char in s:

        if char == '(':

            i.append('(')

        if char == ')':

            if len(i) == 0:

                return False

            else:

                i.pop()

    return len(i) == 0

Look familiar? This is very similar to Dan's code for stacks and balanced parentheses, minus the stack ADT.

The problem here was very straightforward:

  if num_parentheses(s) == 2:

        return s[0] == '(' and s[-1] == ')' 

This code would lead to an error for any regex which did not have ')' as the last character, such as ((0|1)*|2)*. Upon taking it out, the code worked for this case, as well as the next failure (grumble).

Another failure in my code was:

AssertionError: None is not true : Rejects valid match: (DotTree(Leaf('e'), Leaf('2')), '2')

In order to figure out the mistake in my code, I scrutinized the section handling DotTrees:

if r.symbol == '.':

        for i in range(0, len(s)):

            s1 = s[0:i+1]

            s2 = s[i+1:]

            if regex_match(r.children[0], s1) and \

               regex_match(r.children[1], s2):

                return True

Looking at the length of the string s, I realized that my code did not account for the special case where s is one character long! All I needed to add was this:

if len(s) == 1:

            return regex_match(r.children[0], '') and \

                   regex_match(r.children[1], s) or\

                   regex_match(r.children[1], '') and \

                   regex_match(r.children[0], s)

And the code worked.

For the next failure:

AssertionError: None is not true : Rejects valid match: (DotTree(StarTree(Leaf('1')), StarTree(Leaf('2'))), '2222')

This time, the problem with my code was that I assumed no matter what, the string would be at least 1 character long in order to match, especially with the Bar and Dot operators. I'll leave this for next week's post, so I have some information left to cover.

Week 9-Lead Up to Test 2...among other horrors

This week I have a legitimate reason for posting quite late: the E3 deadline was delayed through March 16, and in lieu of prematurely posting my garbage code, I decided to save my large set of steadfast followers (count: 0) the pain of failing E3.

E3 part 2 seemed to be giving several of my fellow coders quite an itch: naturally, this lead me to suspect my code. Turns out I was finding simply the maximum node sum rather than the maximum sum of the maximum path length. Following instructions is a bit more difficult than previously imagined.

And now began my turmoil: I finished A2 while listening to Korpiklaani, but could not figure out e3b, and the matter rests unresolved.


As for preparation for Test 2: I will continue to attempt e3, and monitor berkeycolortran's blog.

Week 8- Assignment 2 in the Works, among other things

This post is way too late for week 8, and I was officially shamed by being excluded from berkeycolortran's list of good blogs - though I admit the exclusion was well deserved (and, wish as I might, I cannot call myself an exception).

As for reviewing concepts which were bugging me, I looked over another student's blog, with a very good explanation of binary tree traversal for all neophytes, and a nice narrative piece about coding for a tree class which also helped with my comprehension of the material.

After the very melodramatic piece for last week, I have decided to write something a bit more relevant to course material, regarding assignment 2 (which I did NOT rip off from brekeycolortran: I started this draft at the beginning of week 8).

Assessing assignment 2 left me quite addled. Upon initial perusal, it seemed to me that the class constructors would take regex strings and make a literal copy in an internal attribute. Not the case at all.

Looking over the discussion board quickly highlighted certain things: a node and reference model was optimal, and each operator or regex 'type' (as implied in the write up) required its own subclass.

Initially, I created a garbage code with no useful inheritance:

class Regex:

    '''creates a regex'''

    #need some way to check legal input '012e' or proper regex

    def __init__(self: 'Regex', regex) -> None:

        self._regex = regex

    def __repr__(self: 'Regex') -> str:

        return 'Regex(' + repr(self._regex) + ')'

    def __eq__(self: 'Regex', other: 'Regex') -> bool:

        return self._regex == other._regex

class RegexOne(Regex):

    '''creates a regex tree of length one'''

    def __init__(self: 'RegexOne', regex) -> None:

        self._root = regex

        

        

    def __repr__(self: 'RegexOne') -> str:

        '''returns a constructor form of the object'''

        return 'RegexOne(' + repr(self._root) + ')'

    

    def __eq__(self: 'RegexOne', other: str) -> bool:

        '''return True iff each node in self is equal to each node in other'''

        return other._root == self._root

class RegexStar(Regex):

    def __init__(self: 'RegexStar', only_child ) -> None:

        '''creates a regex with root *'''

        self._root = '*'

        self._only_child = only_child

        

    def __repr__(self: 'RegexStar') -> str:

        return 'RegexStar(' + repr(self._only_child) + ')'

    def __eq__(self: 'RegexStar', other) -> bool:

        return (other._root == self._root and \

               self._only_child == other._only_child)

class RegexBarDot(Regex):

    def __init__(self: 'RegexBarDot', operator, left_child, right_child) -> None:

        '''creates a regex with root | or . '''

        

        if operator != '|' and operator != '.':

            raise Exception('Choose root | or .')

        self._root = operator

        self._left_child = left_child

        self._right_child = right_child

    def __repr__(self: "RegexBarDot") -> str:

        return 'RegexBarDot(' + repr(self._root) + ',' + repr(self._left_child) + ',' + repr(self._right_child)\

               + ')'

    

    def __eq__(self, other):

        return other._root == self._root and other._left_child == self._left_child \

                   and other._right_child == self._right_child

class RegexBar(RegexBarDot):

    def __init__(self:'RegexBar', left_child, right_child) -> None:

        #why must these variables be instantiated again in the subclass

        self._root = '|'

        self._left_child = left_child

        self._right_child = right_child

class RegexDot(RegexBarDot):

    def __init__(self: 'RegexDot', left_child, right_child) -> None:

        self._root = '.'

        self._left_child = left_child

        self._right_child = right_child

I tried to create a more useful superclass by taking the parameters of (self=Regex, operator=None, left_child=None, right_child=None), but again, this wouldn't work with the regex of size one, which would then have to choose between giving a value to the right_child, left_child, or even operator for its root.

Looking over Dan's code (after week8) made me look at the relationships between the classes in a different way: Binary Tree inherited from Regex Tree, and even used a Regex Tree type as a parameter for its constructor. As well, we were allowed to use some helped functions, which I failed to notice. Another important thing I missed was the distinction of Unary and Binary Trees within the code, which seems obvious now.

As a side node, The Shattered Medallion comes out May 20th. SQL.

Week 7- Post-Midterm Recovery

Unlike the case for my academically inclined acquaintances, midterm was a bit of a reality check for me. I realized several important things, and have decided to formulate a list as a reminder:

a) TRACE YOUR FLIPPING CODE, don't just hope that the coding gods will magically bless your code and will somehow make it run for ALL your test cases - no matter how pretty it looks.

b) Study. I know, probably the most challenging thing for me to do, being a disoriented clot.

c) Focus in class. Try not to think about some illogical quasi-philosophical nonsense that usually pollutes your head.

d) Realize that everything might not go according to plan; instead of running around in circles, arms a-flailing, I should come up with another improved plan, accounting for the mistakes I made. After all, Benjamin Disraeli did say: 'To be conscious that you are ignorant is a great step in knowledge' ; where to go after that he conveniently decided to leave out.

e) Plan B (sorry for the lettering ambiguity, bad choice of variable names): Accept that you made a serious mistake and start from the top. Or, move to a Scandinavian country and work as a farm hand shoveling the pleasant surprises farm animals leave in their respective stalls (which doesn't sound too bad, actually, minus the noxious smells).

EDIT: In no way was this post intended to offend Scandinavian farm laborers

Week 6- Assignment 1

Waiting too long to begin the assignment is causing plenty of running around (like a headless chicken). I still need to clarify concepts based on recursion, as well as most of the content covered after it.

In order to complete the assignment this week, I relied heavily on tracing: repeatedly going over my code in order to pinpoint where things were going haywire. Currently my sketchbooks are covered in incomprehensible scrawls regarding cheese and stools. This raised plenty of questions at the dinner table when I grumbled something about 'that dang cheese problem' under my breath while supposedly doing homework.

Using recursion within the assignment was a bit intuitive: in some cases, it couldn't be avoided, since we needed to use the function/method itself within it's implementation.

Finding 'i' values was probably the most challenging for me: I had to repeatedly compute and compare values in order to find the pattern: something tells me there was probably a more efficient method for this task.

Week 5- Recursion Revisited

     This week I relied on other people for coming to terms with recursion; I found this lecture on Recursion, with eerie parallels to our class (N.B. the lecture is on Scratch, so code snobs may not approve). It gives a good summary of recursion, as well as new metaphors and bad jokes.

   I also looked over berkey colortran's blog, which provided an example of backwards recursion to better understand it. At this point, I started to practice more elementary recursive functions, from the Python Practice Book, as well as Python course (which also mentions that without a base case, a recursive function could lead to an infinite loop).

Product using + and - operators only:

def product(num1, num2):

  if num2 == 1:
     return num1
  else:
     return num1 + product(num1, num2 - 1)

Flattening a list:

This was a bit hair wrenching for me, since it was more procedural:
1) check if an element is a list
2)  a. flatten element if it is a list
     b. append element if it is not a list
3) continue till list ends

def flatten_list(lst):

  new_lst = []
  for element in lst:
    if isinstance(element, list):
       for x in flatten_list(element):
          new_lst.append(x)
    else:
        new_lst.append(element)
   return new_lst

I traced this code to see if it would work:
lst = [1, [2, [3, 4]], 5]

def flatten_list(lst)
new_lst = [],  element = 1
new_lst = [1], element = [2, [3, 4]]
        | new_lst = [], element = 2
        | new_lst = [2], element = [3, 4]
        |        | new_lst = [], element = 3
        |        | new_lst = [3], element = 4
        |        | new_lst = [3, 4]
        | new_lst = [2], x = 3
        | new_lst = [2, 3], x = 4
        | new_lst = [2, 3, 4]
new_lst = [1], x = 2
new_lst = [1, 2], x = 3
new_lst = [1, 2, 3], x = 4
new_lst = [1, 2, 3, 4], element = 5
new_lst = [1, 2, 3, 4, 5]

So, it should work: but there is a lot of redundancy, and recursion seems moot here.
I printed the values for element and x in the shell:

>>> flatten_list([1, [2, [3, 4]], 5])
element is 1
element is [2, [3, 4]]
element is 2
element is [3, 4]
element is 3
element is 4
x is 3
x is 4
x is 2
x is 3
x is 4
element is 5
[1, 2, 3, 4, 5]


Back to the drawing board.
     

Week 4- Qubits and Recursion

     So this week's topic gave a myriad of interesting things to cover for this post. I'll start with a bit of fascinating information. We've heard of bits, which normally store information as 0's or 1's; quantum bits, or qubits, can store information in quantum computers as | 0〉 and  | 1〉  at the same time, using something called quantum superposition- where an electron in an atom can be both excited and at ground state at the same time, that is, until we observe it; then it will be in either | 0〉 or | 1〉 (ground state or excited, respectively).  Apparently this can allow for much faster calculations, because each particular set of electron positions can correspond to a calculation, so one atom can do two at a time! Very different from classical computing, which only does one at a time. This was mentioned along with a wad of impenetrable jargon within various research articles.

   As well, I found a site on Recursion, which explains the concepts in an applied sense. From what I understand, the simplification of the concept is as follows: calling a function within itself in order to break down and simplify the problem in some way such that after each recursive call it gets closer to the base case.

Week 3- Exceptions & Queues

       In order to gain a better understanding of queues and stacks, I read over the Python documentation for Queues: it recommended using deque from the collections module in order to reduce the run time for enqueue and dequeue, using queue.popleft() and queue.append(). Using the module testqueue.py, the time for 10000 through 100000 items remained nearly constant: around 0.05 seconds, whilst for the lab, if I remember correctly, the time increased linearly with the increase in items. I will try to find out more about the implementation of the queue.popleft() in order to discover why this is more efficient than manually shifting the index of each element every time front() or dequeue() is used.

    Another benefit of using the Python documentation is that it seems to be following the progression of our course, so reading along from 5. Data Structures helps to reinforce ideas introduced in the lectures.

   I also looked to the Python shell in order to help me figure out how Exceptions work: the help function for Exception mentioned "Exception" as well as "BaseException," so I am trying to understand the difference between them- especially since Python documentation recommended only making subclasses inheriting from Exception, rather than BaseException.

Note: This is extremely embarrassing, but I was looking over the Abstract Data Types section for our lecture reading, and, quite unequivocally, it mentions "An abstract data type....does not specify the implementation of [its] methods..."

 

Week 2- OOP Continued

January 14, 2014

    The first lab section for the semester was a bit terrifying: the readings 'Code Like a Pythonista' contained strange new content, and lab comrades seemed to be much more adept at generating code for the given problems. At home, I got to work: I read over the given 'Code like a Pythonista' sections again, practiced the new material in IDLE, and redid the lab again at home.

  I also looked over http://ddc-csc148slog.blogspot.ca/, a blog written by another student in 148, and it provided a good summary of the new Abstract Data Types we encountered this week.

Week 1 - Object Oriented Programming

January 12, 2014

    Most of the concepts covered this week were review of the Classes section in CSC108, and I completed the given readings as well as Exercise 2: but some concepts are bugging me, and I will approach the course instructor or the lab TA about these.

    With regards to the practice questions at the end of the reading: the answer to question 5 in 1.5 did not seem intuitive, so I attempted to write the code for it. I began with figuring out the geometric solution, as suggested, and with writing a Point and a Line class - I tried to use the given methods, like get_line_to, as well as new ones (intersection_point and right_bisector, written as a list of [slope, b]). I noticed redundancy in my code, so I tried to change the methods of my thinking. I have not resolved this problem yet.