MIT 6.189 Homework 3 Programming Exercises

Gentle Introduction to Python
#1

Just finished 3.1, sharing is caring. Any advice on anything is very much appreciated.

def not_repeated(list, number):
    for item in list:
        if item == number:
            return False
    return True

def list_intersection(list1, list2):
    intersection = []
    #iterate through both lists, comparing items
    for number1 in list1:
        for number2 in list2:
            #if they have a common element,
            if number1 == number2:
                #check if it is already accounted for.
                if not_repeated(intersection, number2):
                    intersection.append(number1)
    return intersection

print list_intersection([1, 3, 5], [5, 3, 1])
print list_intersection([1, 3, 6, 9], [10, 14, 3, 72, 9])
print list_intersection([2, 3], [3, 3, 3, 2, 10])
print list_intersection([2, 4, 6], [1, 3, 5])
#2

I found Exercise 3.1 – Additional List Practice particularly interesting because it does not elaborate upon what is meant by “elements that are common to both lists”. Obviously, if, for example, 3 appears once in both lists, it should appear once in the resulting list. If 3 occurs once in one of the lists and twice in the other, it should, in my opinion, occur once in the result. But, how should we handle a situation in which an item occurs twice in both lists? It is up to us to decide how we would like to define the problem, since the instructions are not specific about this. In the result, I would represent each item the number of times which is the minimum of the number of times that it occurs in each of the two original lists. So, if 3 occurs five times in one list and seven times in the other, it would appear five times in the result.

In any case, your solution, @Cedar Mora, works well. I did, however, copy your code and replace this …

if not_repeated(intersection, number2):

… with …

if number2 not in intersection:

… thus eliminating the need for the not_repeated function.

Here’s what I have for the solution, which reflects experimentation with how we define “elements that are common to both lists”. The code will run in Python 2 or 3.

# MIT 6.189 Homework 3 Exercise 3.1 Additional List Practice
# Three functions that implement list intersections
def list_intersection(list_1, list_2):
    # return intersection of list_1 and list_2
    return [item for item in list_1 if item in list_2]

print("list_intersection")
print(list_intersection([1, 3, 5], [5, 3, 1]))
print(list_intersection([1, 3, 6, 9], [10, 14, 3, 72, 9]))
print(list_intersection([2, 4, 6], [1, 3, 5]))
# but a problem occurs when duplicates appear in a list ...
print(list_intersection([1, 1, 2, 3, 5, 8, 13], [1, 3, 5, 7, 9, 11, 13]))
print(list_intersection([1, 3, 5, 7, 9, 11, 13], [1, 1, 2, 3, 5, 8, 13]))

def list_intersection_unique(list_1, list_2):
    # return intersection of list_1 and list_2 - essentially, set intersection
    # so, each item that appears in both lists appears once in the returned new list
    return list({item for item in list_1 if item in list_2})
print("list_intersection_unique")
print(list_intersection_unique([1, 1, 2, 3, 5, 8, 13], [1, 3, 5, 7, 9, 11, 13]))


def list_intersection_minimalist(list_1, list_2):
    # return a new list in which
    # each item appears the lesser of the number of times
    # that it appears either list
    new_list = []
    for item in set(list_1):
        new_list += [item] * min(list_1.count(item), list_2.count(item))
    return new_list

print("list_intersection_minimalist")
print(list_intersection_minimalist([1, 1, 1, 2, 3, 4], [1, 2, 1, 3, 7]))
print(list_intersection_minimalist([1, 2, 1, 3, 7], [1, 1, 1, 2, 3, 4]))

Output …

list_intersection
[1, 3, 5]
[3, 9]
[]
[1, 1, 3, 5, 13]
[1, 3, 5, 13]
list_intersection_unique
[1, 3, 5, 13]
list_intersection_minimalist
[1, 1, 2, 3]
[1, 1, 2, 3]

As indicated in the comments, a problem occurs with the first function, list_intersection, when one of the lists includes a repeated item.

1 Like
#3

Below is a recursive solution to Exercise OPT.1 – Palindromes!.

For a base case, empty strings and one-character strings are the same forwards or backwards, so they are defined here as palindromes. With longer strings, if the first and last characters match, and the inside is a palindrome, the entire string is a palindrome.

# palindrome.py
# May 23, 2015
def is_palindrome(s):
    if type(s) != str:
        return False
    # base case before the or; recursive case after the or
    if len(s) <= 1 or s[0] == s[-1] and is_palindrome(s[1: -1]):
        return True
    return False

strs = [False, 17, "", "a", "as", "ask", "ewe", "emma", "dromedary", "racecar"]
for s in strs:
    print("%s --> %s" % (s, is_palindrome(s)))

Output:

False --> False
17 --> False
 --> True
a --> True
as --> False
ask --> False
ewe --> True
emma --> False
dromedary --> False
racecar --> True
#4

Following is a solution to Exercise 3.6 - Your First Class, where we are asked to implement a Queue class.

To test the class, an instance is created, twenty integers are generated, then, depending on their values, they are inserted into the Queue or items are removed from the Queue.

Contrary to the instructions given for this exercise, this Queue returns None, rather than the specified string, when remove is called on the Queue while it is empty. Actually, is not made clear whether the message "The queue is empty" should be returned by the Queue itself, when that condition occurs, or whether we should test for that condition outside the Queue, and display the message under that circumstance. In my opinion, we should not code that message directly into the Queue class. So, in this implementation, the value None is returned when that occurs. Admittedly, that is not a perfect solution, because None is a valid value that a Queue could contain as an item. In that case, if we pop the Queue and receive the value None, we will not know whether None was in the Queue or whether it was empty.

Another possible solution would be to design the Queue to raise an appropriate exception when it is popped while empty.

Opinions and suggestions are welcome.

Sorry about the lack of syntax coloration. The three grave method mangles the indentation for this code, for some reason, so I had to revert to using the </> button.

# Queue.py
# Mechanical MOOC
# MIT OCW 6.189 Homework 3
# Exercise 3.6 - Your First Class

import random

class Queue(object):
    class __Node:
        # private class
        def __init__(self, cargo):
            self.cargo = cargo
            self.next = None

    def __init__(self):
        # Initialize an empty Queue.
        # private attributes
        self.__front = None
        self.__back = None
        self.__len = 0 # number of nodes in the Queue

    def insert(self, cargo):
        # Add a new node to the front to contain the cargo.
        node = self.__Node(cargo)
        if self.__front == None:
            # The Queue was empty.
            self.__front = node
        else:
            # The Queue was not empty.
            self.__back.next = node
        self.__back = node
        self.__len += 1

    def remove(self):
        # Remove the front node and return its cargo.
        if self.__front == None:
            # The Queue was empty, so return None.
            return None
        # The Queue was not empty, so update the pointers and return the front cargo.
        cargo = self.__front.cargo
        self.__front = self.__front.next
        if self.__front == None:
            self.__back = None
        self.__len -= 1
        return cargo

    def isEmpty(self):
        # Is the Queue empty?
        return self.__front == None

    def __str__(self):
        # Return a string representation of all the cargo in the Queue nodes.
        qList = []
        p = self.__front
        while p != None:
            qList.append(p.cargo)
            p = p.next
        return "front: %s :back" % (str(qList))
    
    def __len__(self):
        # defines the Python built-in Python len() function for this class
        return self.__len

# Create and test a new Queue by adding and removing random integers.
q = Queue()
for i in range(20):
    n = random.randint(0, 9)
    print("n -> " + str(n))
    if n >= 5:
        x = q.remove()
        print(("removed %s") % (str(x)))
    else:
        q.insert(n)
        print(("inserted %s") % (str(n)))
    print("%s - length: %s" % (q, len(q)))

Example output:

n -> 2
inserted 2
front: [2] :back - length: 1
n -> 8
removed 2
front: [] :back - length: 0
n -> 7
removed None
front: [] :back - length: 0
n -> 1
inserted 1
front: [1] :back - length: 1
n -> 7
removed 1
front: [] :back - length: 0
n -> 3
inserted 3
front: [3] :back - length: 1
n -> 3
inserted 3
front: [3, 3] :back - length: 2
n -> 8
removed 3
front: [3] :back - length: 1
n -> 6
removed 3
front: [] :back - length: 0
n -> 5
removed None
front: [] :back - length: 0
n -> 4
inserted 4
front: [4] :back - length: 1
n -> 7
removed 4
front: [] :back - length: 0
n -> 5
removed None
front: [] :back - length: 0
n -> 2
inserted 2
front: [2] :back - length: 1
n -> 2
inserted 2
front: [2, 2] :back - length: 2
n -> 0
inserted 0
front: [2, 2, 0] :back - length: 3
n -> 7
removed 2
front: [2, 0] :back - length: 2
n -> 4
inserted 4
front: [2, 0, 4] :back - length: 3
n -> 4
inserted 4
front: [2, 0, 4, 4] :back - length: 4
n -> 1
inserted 1
front: [2, 0, 4, 4, 1] :back - length: 5
#5

Is 3.6 in our homework already? I didn’t see it in the email.

#6

I hadn’t checked how far we were to go in Handout 3; this becomes another incident for me to confess in the Failure Party thread. :blush:

1 Like
#7

Here is my try at 3.6. I also included optional exercise 2 here since it was almost exactly the same code. I implemented the queue using a list as an attribute of the object.

class Queue():
    def __init__(self):
        self.queue = []
    def insert(self, item):
        self.queue.append(item)
    def remove(self):
        if len(self.queue) == 0:
            return "Queue is empty."
        else:
            return self.queue.pop(0)

q = Queue()

q.insert('Sometimes')
print q.queue
print q.remove()
q.insert('the')
q.insert('big')
print q.queue
q.insert('brown')
print q.remove()
print q.remove()
print q.remove()
print q.queue
print q.remove()

From the Python documentation, it looks like a list is a rather inefficient implementation, so they offer the deque (double queue) object instead as a more efficient alternative. However, I thought it would kind of be cheating to use it, so I just stuck with the list.

@Glenn, I’m not quite sure I understand what all of your code does What’s the main idea of how your code works? How have you implemented the queue?

And now Opt 2:

class Stack():
    def __init__(self):
        self.queue = []
    def insert(self, item):
        self.queue.append(item)
    def remove(self):
        if len(self.queue) == 0:
            return "Queue is empty."
        else:
            return self.queue.pop()

q = Stack()

q.insert('1')
print q.queue
print q.remove()
q.insert('2')
q.insert('3')
print q.queue
q.insert('4')
print q.remove()
print q.remove()
print q.remove()
print q.queue
print q.remove()

It is almost literally exactly the same code. The only real difference is that pop(0) is now pop() (meaning that I am taking from the top of the list, not the bottom of the list), along with some minor differences including the name of the class and the test cases.

#8

And now optional exercise 1. We wrote a function to test if a sentence or word is a palindrome. I decided to try both the recursive and iterative approaches. I liked @Glenn’s recursive implementation because of its simplicity and compactness. However, I decided to go for features instead. The code directly below is able to process palindrome sentences as well as words, but it’s significantly longer and more complicated. First, the recursive solution:

def is_palindrome(string):
    #Processing input
    formatted = ""
    for character in string:
        if character.isalnum(): #grab letters and numbers
            character = character.lower() #lower capital letters
            formatted = formatted + character #add character to good string
    string = formatted #renaming good string to complete processing

#p2pu kept moving the lines below one identation level left, so I had to add this comment to fix it.
    if len(string) <= 1:
        return True
    elif string[0] == string[-1]:
        return is_palindrome(string[1:-1])
    else:
        return False

print is_palindrome('A Man, a Plan, a Canal: Panama!')
print is_palindrome('Anna')
print is_palindrome('Ana')
print is_palindrome('Able was I ere I saw Elba.')
print is_palindrome('kayak')
print is_palindrome('yummy')

However, I think the code is inefficient, since the digestion (removal of punctuation and conversion of capital letters) part will have to be run each time the function is called (I think), which is redundant. So, I prefer iteration in this case:

#Checks if alphanumberic strings with spaces and punctuation are palindromes.
def is_palindrome(string):
    #Processing input
    formatted = ""
    for character in string:
        if character.isalnum(): #grab letters and numbers
            character = character.lower() #lower capital letters            
            formatted = formatted + character #add character to good string 
    string = formatted #renaming good string to complete processing

#p2pu kept moving the lines below one identation level left, so I had to add this comment to fix it.
    #Checking if input is palindrome
    while len(string) >= 1:
        if string[0] == string[-1]:
            string = string[1:-1]
            #Sets string to be everything from its second letter to second to last letter.
        else:
            return False
    return True 

print is_palindrome('A Man, a Plan, a Canal: Panama!')
print is_palindrome('Anna')
print is_palindrome('Ana')
print is_palindrome('Able was I ere I saw Elba.')
print is_palindrome('kayak')
print is_palindrome('yummy')

The digestion to remove punctuation and remove capital letters is done only once. Much more efficient.

Maybe I should do something besides program today, like eat something.

#9

It was implemented using what’s called a linked list. A linked list consists of a set of nodes, each of which contains a data item and a pointer to the next adjacent node toward the back of the list.

The motivation for using a linked list was to avoid the inefficiency connected with popping element 0 of a long list.

In this implementation, each item in an instance of the Queue is stored in the cargo attribute of an instance of a private class, __Node, which represents a node in the linked list. The other attribute of __Node, called next, points to the next instance of __Node in the Queue, if there is one. In the last __Node in the Queue, the next pointer has the value, None, because there are no __Nodes in back of that one.

There is a __front and a __back attribute in the Queue class. To iterate through the Queue, we can start with the __Node pointed to by __front, do whatever we need to with its cargo, then use its next pointer to get to the next __Node, and handle its cargo, repeating the process until we reach the back of the Queue.

Note that when the Queue is created, via its __init__ method, it is assigned a __len of 0. There are no __Nodes in the Queue yet, so the __front and __back pointers are set to None. Whenever we insert a __Node, we assign the __back attribute of the Queue to point to it. The first time we insert, we also have to initialize __front. We update __len whenever we insert or remove an item.

The special methods __str__ and __len__ have been implemented here. They enable the Python built-in functions, str and len to be applied to any instance of Queue, and specify what those functions will return.

#10

Thanks for your palindrome implementation. The “digestion” is nice, which is something that I could not do, and simultaneously maintain simplicity, with the recursion.

… and speaking of digestion, make sure you eat something today - something more filling than commas and spaces. :slight_smile:

1 Like
#11

Well dang that’s pretty impressive. I don’t think they were expecting quite that much, but I guess nothing wrong with making challenges for yourself. Do you write Python professionally? Because you should, I think.

#12

I use Python at work sometimes but not for anything that would be considered to be a professional project.

While the instructions did not ask us to use a linked list for the Queue, I just thought it would be interesting to try to deal with the efficiency issue regarding the remove operation.

1 Like
#13

Were we really only supposed to do 3.1? I thought “Complete sections 3.1 from Handout 3” was a typo and you meant 3.1 to 3.6 - I guess I was wrong.

ANYHOW: I did 3.2 (fun!) but my code seems long to me. Can anyone show me how to make this code below more elegant? Maybe by using dictionaries?

-Bram

def ball_set(court):
    for i in range(0, 12):
        for j in range(0, 12):
            court[i, j] = 0
    return court

def ball_place(ball, court):
    for i in range(ball[0]-ball[2]-1, ball[0]+ball[2]):
        if i > -1:
            for j in range(ball[1]-ball[2]-1, ball[1]+ball[2]):
                if j > -1:
                    court.get((i, j), 0)
                    hit = court[i, j]
                    if hit == 1:
                        court[i, j] = 2
                    else:
                        court[i, j] = 1
    return court

def ball_collide(ballone, balltwo):
    court = {}
    answer = 0
    ball_set(court)
    ball_place(ballone, court)
    ball_place(balltwo, court)
    for i in range(0, 12):
        for j in range(0, 12):
            print court[i, j],
            if court[i, j] == 2:
                answer = 1
        print
    if answer == 1:
        return True
    else:
        return False


ball1 = [5, 5, 2]
ball2 = [2, 8, 3]
print ball_collide(ball1, ball2)


# Test Cases for Exercise 3.2
# print ball_collide((0, 0, 1), (3, 3, 1)) # Should be False
# print ball_collide((5, 5, 2), (2, 8, 3)) # Should be True
# print ball_collide((7, 8, 2), (4, 4, 3)) # Should be True
#14

Nothing wrong with a little more practice, right? :tired_face:

You might eliminate the court, and instead compute the distance between the balls with the pythagorean theorem.

I find that it sometimes helps to draw pictures on paper showing the relationships between variables.

Imagine two circles, one on the top vertex and one on the right vertex.

You can find a by subtracting the x-component of one of the balls by the x-component of the other ball. Same with b, except using the y-components.

You can compare the distance between the balls to the sum of their radii, as follows:

  • If the distance between the balls is greater than the sum of their radii, they are not colliding.
  • If it the distance between them is less than the sum of their radii, they are colliding.

If you would like me to give an example, I would be happy to, if you like, but I think you might learn more by trying it yourself.

1 Like
#15

I think at this point, we have the go-ahead to complete all of MIT 6.189 Handouts 1, 2, and 3 and all but the last of the Codecademy units. We need all the concepts from those resources, anyway, to do the Tetris project.

I like @Cedar Mora’s advice on 3.2 – Collision Detection of Balls. The essence of the solution is the Pythagorean theorem. Make sure you take the coordinates and the radius of each ball into account. You don’t need to set up a court, since the problem focuses on considering two balls at a time, and not an entire scenario.

#16

Well, here is my attempt at exercise 3.6. It’s not as concise as @Cedar_Mora 's example…Just a slightly different approach. It works. It seems like @Glenn’s version is the most efficient in the long run… But I am barely hanging on trying to understand this stuff. My brain can’t handle efficiency at the moment… Just lots of hand holding :baby:

Class Queue(object):

    def __init__(self):
        self.elements = []

    def insert(self, element):
        self.elements.append(str(element))#converts any integers to string
        print element, "- added to queue line"

    def remove(self):
        if len(self.elements) == 0:
            print "This queue is empty"
        else:
            remove_oldest = self.elements[0]#gets first-in element
            self.elements = self.elements[1:]#new list with first-in element removed
            print remove_oldest, "<- first-in-first-out element"

queue_line = Queue()
#empty list test
print "current queue line :", queue_line.elements
#adding elements to list
queue_line.insert("sam")
queue_line.insert("bob")
queue_line.insert("carl")
queue_line.insert(4)
#check that elements in list
print "current queue line :", queue_line.elements
#remove the first-in element
queue_line.remove()
#check list again
print "current queue line :", queue_line.elements
#remove other elements from list
queue_line.remove()
queue_line.remove()
queue_line.remove()
#list empty at this point, should print "This queue is empty"
queue_line.remove()
1 Like
#17

Gosh, that was wicked easy, @Cedar_Mora and @Glenn Glenn! Not as much teaching value about matrices, though.

ball1 = [7, 8, 2]
ball2 = [4, 4, 3]
#print ball_collide(ball1, ball2)

def pythagora(b1, b2):
    sidesquaresum = abs(ball1[0]-ball2[0])**2 + abs(ball1[1]-ball2[1])**2
    hypo = sidesquaresum**.5
    if b1[2]+b2[2] < hypo:
        return False
    else:
        return True

print pythagora(ball1,ball2)
1 Like