To download and install Python on your home machines see this page. Remember that this is only to enable you to play with the assignment at home: The final version turned in must work on the ACS Linux machines. While you can use Windows/Mac etc. to begin working with Python, the code you turn in must be that required for the Linux environment.
Code for all programming assignments should be well documented. Documentation entails providing documentation strings for all methods, classes, packages, etc., and comments throughout the code to explain the program logic. Comments in Python are preceded by # and extend to the end of the line. Documentation strings are strings in the first line of a function, method, etc., and are accessible using help(foo) where foo is the name of the method, class, etc. It is understood that some of the exercises in this programming assignment require extremely little code and will not require extensive comments.
The overall objective of this assignment is to introduce you to Python. Emphasis will be placed on text and string manipulations and should use some of Python’s facilities for iterating over structures.
The assignment is spread over five python files
and three files
that you need to download.
The first five files contain several skeleton Python functions, with missing bodies, i.e. expressions, which currently contain the text raise Failure("to be written").
Your task is to replace the text in those files with the the appropriate Python code for each of those expressions. An emphasis should be placed on writing code that is concise and easy to read.
Your functions/programs must compile and/or run on a ACS Linux machine (e.g. ieng6.ucsd.edu) as this is where your solutions will be checked. While you may develop your code on any system, ensure that your code runs as expected on an ACS machine prior to submission. You should test your code in the directories from which the zip files (see below) will be created, as this will approximate the environment used for grading the assignment.
Most of the points, will be awarded automatically, by evaluating your functions against a given test suite. test.ml contains a very small suite of tests which gives you a flavor of of these tests. At any stage, by typing at the UNIX shell :
> python < test.py | grep "130>>" > log
you will get a report on how your code stacks up against the simple tests.
The last line of the file log must contain the word ``Compiled" otherwise you get a zero for the whole assignment.
If the code you submit does not compile with make, you will get 0 for the assignment.
If for some problem, you cannot get the code to compile, leave it as is with the raise ... with your partial solution enclosed below as a comment.
The second last line of the log file will contain your overall score, and the other lines will give you a readout for each test. You are encouraged to try to understand the code in test.py, and subsequently devise your own tests and add them to test.py, but you will not be graded on this.
Alternately, inside the Python shell, type:
>>> import test
.
.
.
130>> Results: ...
130>> Compiled
and it should return a pair of integers, reflecting your score and the max possible score on the sample tests. If instead an error message appears, your code will receive a zero.
Your solutions to this assignment will be stored in separate files under a directory called solution/, inside which you will place your modified files: misc.py, vector.py, decorators.py, streams.py. There should be no other files in the directory
After creating and populating the directory as described above, create a zip file called cse130_pa6.zip by going into the directory solution and executing the UNIX shell command:
> zip cse130_pa6.zip *
Once you have created the zip file with your solutions, you will use the turnin program to submit this file for grading by going into the directory solution/ and executing the UNIX shell command:
> turnin -c cs130f -p pa6 cse130_pa6.zip
turnin will provide you with a confirmation of the submission process; make sure that the size of the file indicated by turnin matches the size of your zip file. See the ACS Web page on turnin for more information on the operation of the program.
All classes used in this assignment should be new-style Python classes which have either object as a base class or only other new-style classes as base classes.
class foo(object):
pass
class bar(foo):
pass
None doesn’t print a line when it is the return value of a function.None, 0 and [] are all treated as False when used as a predicate (eg in an if statement.)for-loops.Write the code for a Vector class that will implement fixed length vectors and a variety of operations over them.
Add a constructor to the Vector class. The constructor should take a single argument. If this argument is either an int or a long or an instance of a class derived from one of these, then consider this argument to be the length of the Vector instance. In this case, construct a Vector of the specified length with each element is initialized to 0.0. If the length is negative, raise a ValueError with an appropriate message. If the argument is not considered to be the length, then if the argument is a sequence (such as a list), then initialize with vector with the length and values of the given sequence. If the argument is not used as the length of the vector and if it is not a sequence, then raise a TypeError with an appropriate message.
Next implement the __repr__ method to return a string of python code which could be used to initialize the Vector. This string of code should consist of the name of the class followed by an open parenthesis followed by the contents of the vector represented as a list followed by a close parenthisis.
Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from vector import *
>>> Vector(3)
Vector([0.0, 0.0, 0.0])
>>> Vector(3L)
Vector([0.0, 0.0, 0.0])
>>> Vector([4.5, "foo", 0])
Vector([4.5, 'foo', 0])
>>> Vector(0)
Vector([])<br>
>>> Vector(-4)
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "vector.py", line 14, in __init__
raise ValueError("Vector length cannot be negative")
ValueError: Vector length cannot be negative
Implement the functions __len__ and __iter__ in Vector. The function __len__ should return the length of the Vector. The function __iter__ should return an iterator object that can iterate over the elements of the Vector. This is most easily done using yield(). See this for more information.
Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from vector import *
>>> [x*2 for x in Vector([3,3.25,"foo"])]
[6, 6.5, 'foofoo']
>>> len(Vector(23))
23
Implement the + and += operators for Vector.
The second arguments to + and += can be any sequence of the same length as the Vector. All of these should implement component-wise addition. See this for more information on how to implement these operators. Other arithmetic operators are implemented in a similar way; however they are not required for this assignment. Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from vector import *
>>> Vector([6,8,2]) + Vector([4,-3,2])
Vector([10, 5, 4])
>>> Vector([6,8,2]) + [4,-3,2]
Vector([10, 5, 4])
>>> (6,8,2) + Vector([4,-3,2])
Vector([10, 5, 4])
>>> v=Vector(["f","b"])
>>> v += ("oo", "oo")
>>> v
Vector(['foo', 'boo'])
Add the method dot which takes either a Vector or a sequence and returns the dot product of the argument with current Vector instance. Recall that the dot product is defined as the sum of the component-wise products. The behavior of this function if any elements are not numeric is undefined. Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from vector import *
>>> Vector([6,8,2]).dot(Vector([4,-3,2]))
4
Implement the __getitem__ and __setitem__ methods to allow element level access to the Vector. Indexing should be 0 based (as in C). If the index is negative, it should translate to the length of the Vector plus the index. Thus, index -1 is the last element. If the index is out of range, your implementation should raise an IndexError with an appropriate message.
This behavior should be identical to that of a list.
These methods should preserve the length of the Vector. Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from vector import *
>>> v=Vector(7)
>>> v[4]
0.0
>>> v[4] = "foo"
>>> v[4]
'foo'
>>> v
Vector([0.0, 0.0, 0.0, 0.0, 'foo', 0.0, 0.0])
Extend your implementation of the __getitem__ and __setitem__ methods to allow slice-level access to the Vector. These methods should preserve the length of the Vector. If an assignment to a slice would change the length of the vector, raise a ValueError exception. The semantics otherwise should mimic those of list. Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from vector import *.
>>> v=Vector(7)
>>> v[2:4]=[4,4]
>>> v
Vector([0.0, 0.0, 4, 4, 0.0, 0.0, 0.0])
>>> v[6:2:-3]=[-1,-2]
>>> v
Vector([0.0, 0.0, 4, -2, 0.0, 0.0, -1])
Implement comparison functions for Vectors. Two vectors should be considered equal if each element in the first Vector is equal to the respective element in the second Vector.
A particular vector a, should be considered greater than another b, if the largest element of a is greater than the largest element of b.
If the largest elements of both are equal, then compare the second-largest elements, and so forth. If every pair compared in this fashion is equal, then a should not be considered greater than b, but a should be considered greater than or equal to b.
If a is greater than b, then b is less than a. When a Vector is compared to something that isn’t a Vector, they should never be equal, and the result should be the same as if the respective comparison function were called in in the class object.
Note: This is a nonstandard method for comparing vectors, and for a pair of vectors a and b, even though a >= b we may not have either of a > b or a = b.
Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from vector import *
>>> a=Vector([1,3,5])</font><br>
>>> b=Vector([5,1,3])</font><br>
>>> c=Vector([4,5,4])</font><br>
>>> a < b
False
>>> a > b
False
>>> a >= b
True
>>> a > c
False
>>> a < c
True
>>> a >= c
False
>>> a == c
False
>>> a == a
True
>>> a != c
True
>>> a !=[1,3,5]
True
Here are some links on *args and **args - tutorial, - manual
In the file decorators.py there is an example decorator, profiled and stub code for decorators that you will be writing. At the bottom of the file are many examples of decorated functions. The expected output for these functions is available in decorators.out.
Complete the definition for the decorator traced. When the decorated function is called, the decorator should print out an ASCII art tree of the recursive calls and their return values. The format of the tree should be as follows:
Print a pipe symbol followed by a space (|) for every level of nested function calls,
Print a comma then a minus sign then a space (,-) next,
Print the name of the function being traced followed by an open parenthesis followed by the repr() of all of the arguments. Arguments should be seperated by a comma followed by a space (,). After the normal arguments, print all the keyword arguments in the form keyword then equals sign then repr() of the value of the keyword argument. The keyword arguments should also be seperated by a comma followed by a space. Keyword arguments should be printed in the order returned by dict.items().
Next, increase the nesting level and call the function itself.
At the original nesting level, print a pipe symbol followed by a space (|) for every level of nested function calls,
Print a backquote then a minus sign then a space(\- `)
Finally, print the repr() of the return value.
The return value of the function should be return to the caller after all printing is complete. If an exception occurs in the funciton, the nesting level must be adjusted to the appropriate level where the exception is caught. See change for an example.
Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from decorators import *
>>> @traced
>>> def foo(a,b):
>>> ...if a==0: return b
>>> ...return foo(b=a-1,a=b-1)
>>> ...
>>> foo(4,5)
,- foo(4, 5)
| ,- foo(a=4, b=3)
| | ,- foo(a=2, b=3)
| | | ,- foo(a=2, b=1)
| | | | ,- foo(a=0, b=1)
| | | | `- 1
| | | `- 1
| | `- 1
| `- 1
`- 1
1
Complete the definition of the memoized decorator.
When the decorated function is called, the decorator should check to see if the function has already been called with the given arguments.
If so, the decorator should return the value the the function returned when it was last called with the given arguments.
If the function last threw an exception when called with the given arguments, the same exception should be thrown again.
If the function has not been called with the given arguments, then call it and record the return value or exception. Then return the return value or raise the thrown exception.
Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from decorators import *
>>> from time import sleep
>>> @memoized
>>> def foo(a):
>>> ...sleep(a)
>>> ...return a
>>>
>>> foo(5)
# 5 second pause
5
>>> foo(5)
# practically instantaneous
5
In this problem, you will use generators to improve your password cracker from PA5, by not building a giant data structure to hold all candidate attempts.
You can read more about generators from the discussion notes:
Write a function words_in_line which will take a string and return a list of all the words in the line. Words are defined to be any sequence of non-whitespace characters. Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from streams import *
>>> words_in_line(" Hello World!")
['Hello', 'World!']
Write a function streamify which takes a function, f and returns a function which takes an object, l which may be iterated over. The function, f may be assumed to take an item returned by an iterator over l and will return a list. The function returned by streamify should iterate over all items returned by the iterator over l and call f on each one.
It should then iterate over the items returned by f and yield them.
Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from streams import *
>>> ws=streamify(words_in_line)
>>> for x in ws(iter(["Hello World!", "Hello Python!", "Goodbye Everybody"])):
>>> ... print x
Hello
World!
Hello
Python!
Goodbye
Everybody
You can then define a function words_in_file which will return a stream of all the words in a file as follows:
words_in_file = compose(streamify(words_in_line),open)
Once you have done this at the prompt you should see something like:
>>> from streams import *
>>> for w in words_in_file("words"): print w
stroam
asarta
sinklike
...
Using this technique and the functions transform_digits, transform_capitalize and transform_reverse from PA5, to create a function, transformed_words_in_file, which will return an iterator over all possible transformations of all the words in a file.
You must use compose and streamify, and you must not define a raw function using def. Your new function will be be used in crack_pass_file.
Once you have implemented the function, you should get the following behavior at the Python prompt:
>>> from streams import *
>>> crack_pass_file("passwd","words","out")
#...several minutes pass...
Ctrl-C
Traceback (most recent call last):
...
KeyboardInterrupt
The file out should contain something like the following:
checani=asarta
root = ...
... = ...
... = ...