 # MIT 6.189 Homework 3 Programming Exercises

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])

``````

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

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 == 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
ewe --> True
emma --> False
dromedary --> False
racecar --> True
``````

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:  :back - length: 1
n -> 8
removed 2
front: [] :back - length: 0
n -> 7
removed None
front: [] :back - length: 0
n -> 1
inserted 1
front:  :back - length: 1
n -> 7
removed 1
front: [] :back - length: 0
n -> 3
inserted 3
front:  :back - length: 1
n -> 3
inserted 3
front: [3, 3] :back - length: 2
n -> 8
removed 3
front:  :back - length: 1
n -> 6
removed 3
front: [] :back - length: 0
n -> 5
removed None
front: [] :back - length: 0
n -> 4
inserted 4
front:  :back - length: 1
n -> 7
removed 4
front: [] :back - length: 0
n -> 5
removed None
front: [] :back - length: 0
n -> 2
inserted 2
front:  :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
``````

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

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. 1 Like

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.

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 == 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 == 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.

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 `pop`ping 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 `__Node`s 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 `__Node`s 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.

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. 1 Like

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.

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

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-ball-1, ball+ball):
if i > -1:
for j in range(ball-ball-1, ball+ball):
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 = {}
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:
print
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
```

Nothing wrong with a little more practice, right? 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

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.

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 ``````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#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
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

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-ball2)**2 + abs(ball1-ball2)**2
hypo = sidesquaresum**.5
if b1+b2 < hypo:
return False
else:
return True

print pythagora(ball1,ball2)
```
1 Like