CSE 143

Course Info

Tutorials

Getting Help

Check Scores

Other

CSE 143: The Python Strikes Back

CSE 142 Python Slides (for review):

Session #8 (Tuesday, March 8)

In this session Jordan will talk about how to make video games in Python.

Files:

Homework 6: Anagrams
Due: Tue 3/15, 11:30pm. Turn in HW6P here.
No late turnins accepted.

In unit 6 of the course we learned about recursive backtracking. Recursive backtracking is basically the same in Python; a method can call itself. There is no special syntax for it. The main change involved is in the types of collections used; we often just use lists in Python where in Java we would have used sets, stacks, arrays, etc.

For your assignment this week, create a Python file called anagrams.py that defines a class Anagrams much like in the Java Homework 6. Our solution to this program is 60 lines long.

Define the following operations in your class. These are described below in terms of the way they would be called by a client. In your code you must also declare a self parameter for each method.

  • constructor (dictionary) - Constructs an anagram solver over the given list of words, a la the constructor in the Java assignment. You may assume that the list of words passed to you is in sorted alphabetical order. You should raise an exception if the list is None.
  • words(phrase) - Returns a list of all words contained in the given phrase, a la getWords from the Java assignment. The words must appear in sorted alphabetical order in the list.
  • print_anagrams(phrase, max) - prints every anagram contained in the given phrase in the same order and format as in the Java assignment, a la print from the Java assignment. (We have to change the method name because print is a keyword in Python.) In the Java version we had 2 versions of print, one with a max and one without. In Python it is illegal to have two functions with the same name, but you can specify a parameter as optional by giving it a default value. You should do so with the max parameter, defaulting to 0 if no max is passed. See the past slides for how to do this. This method should raise an exception if the phrase passed is None or if the max passed is less than 0.

In this assignment you will interact with provided LetterInventory objects, so you should say the following at the start of your file: from letterinventory import *

A LetterInventory object has the following constructors and methods:

  • constructor (s) - Constructs a letter inventory to count the letters in the given string. Raises an exception if the string passed is None.
  • add(other) - Adds the letters in the given string or inventory to those in this one. For example, adding inventories [ehllo] and [hhio] yields [ehhhillo]. Or adding inventory [ehllo] plus string "hi ho" yields [ehhhillo]. Raises an exception if the string or inventory passed is None.
  • __contains__(other) - You can test whether a string or inventory s is contained in another inventory inv by writing: if s in inv: ...
  • empty() - Returns True if there are no letters in this inventory, or False if the inventory does contain letters.
  • __len__() - You can ask how many letters are contained in an inventory inv by writing: len(inv)
  • subtract(other) - Removes the letters in the given string or inventory from this one. For example, [ehhhillo] minus [ehho] yields [hill], or [ehhhillo] minus "he ho" yields [hill]. Raises an exception if the string/inventory passed is None or if the letters in the other string/inventory are not contained in this one.
  • __str__() - You can get a string representation of an inventory inv by writing: str(inv)

Files:

Session #7 (Tuesday, February 29)

In this session Roy talked about higher order fuctions in Python as well as Google's popular distributed algorithm MapReduce.

Homework 5: Grammar Solver
Due: Tue 3/8, 11:30pm. Turn in HW5P here.
No late turnins accepted.

In week 5 of the course we learned about recursion. Recursion is basically the same in Python; a method can call itself. There is no special syntax for it.

For your assignment this week, create a Python file called grammarsolver.py that defines a class GrammarSolver much like in the Java Homework 5.

Define the following operations in your class. These are described below in terms of the way they would be called by a client. In your code you must also declare a self parameter for each method.

  • constructor (rules) - constructs a grammar solver over the given list of rules, a la the constructor in the Java assignment. You should break apart the rules and store them into a dictionary (where the key is a non-terminal symbol and the value is some representation of the expansion rules that symbol can be expanded into), much like you would have used a Map in the Java version. You can break apart a string using its split method. Raises an exception if the list is None or has 0 length
  • symbols() - returns a list of the non-terminal symbols in your grammar, a la getSymbols from the Java assignment; the symbols must appear in sorted alphabetical order in the list (see the keys method of Python dictionaries)
  • contains(symbol) - returns True if the given string represents a non-terminal symbol in this grammar, a la contains from the Java assignment. Raises an exception if the string is None or has a length of 0
  • generate(symbol) - returns a string representing a randomly chosen expansion of the given symbol, a la generate from the Java assignment. If the given string is not a non-terminal in this grammar, assume it is a terminal and just return it. Must be written recursively. Raises an exception if the string is None or has 0 length

Files:

Links:

Session #6 (Tuesday, February 22)

In this session Roy talked about functional programming in python. This is a drastically different style of programming from the iterative approach we take with Java.

Homework 4: Assassin
Due: Tue 3/1, 11:30pm. Turn in HW4P here.
No late turnins accepted.

In week 4 of the course we learned about implementing linked lists. Python can do much the same thing, since variables that store objects in Python also do so by reference. So you can create a linked list in Python by creating many node objects, each with a next reference to another node.

The equivalent of null in Python is called None, and it behaves much the same way. You can test whether a variable is equal to None (best done by writing: if myVariable is None: ... rather than using ==), and you can store None in a variable, but None is not an object and cannot be dereferenced.

We are also going to practice exceptions in this assignment. To throw ("raise") an exception in Python, write the following: 

raise Exception("your message here")

For your assignment this week, create a Python file called assassinmanager.py that defines a class AssassinManager much like in the Java Homework 4. You must implement your class using a collection of linked nodes; you may not create any Python lists or other collection objects.

Define the following operations in your class. These are described below in terms of the way they would be called by a client. In your code you must also declare a self parameter for each method.

  • constructor (names) - constructs an assassin manager over the given list of names, a la the constructor in the Java assignment; raises an exception if the list is None or is empty (0 length)
  • print_kill_ring() - prints the current contents of your kill ring, a la printKillRing from the Java assignment
  • print_graveyard() - prints the current contents of your graveyard, a la printGraveyard from the Java assignment
  • kill_ring_contains(name) - returns True if your kill ring contains the given name and False if not, a la killRingContains from the Java assignment
  • graveyard_contains(name) - returns True if your graveyard contains the given name and False if not, a la graveyardContains from the Java assignment
  • game_over() - returns True if the game has ended and False otherwise, a la isGameOver from the Java assignment
  • winner() - returns a string representing the name of the person who has won the game (or None if the game is not over yet), a la getWinner from the Java assignment
  • kill(name) - removes the given name from the kill ring and puts it into the front of the graveyard, a la kill from the Java assignment. Raises an exception if the game is not over or if the kill ring does not contain the given name

You will interact with AssassinNode objects, so you should say the following at the start of your program: from assassinnode import *

An AssassinNode object has the following constructors and fields:

  • constructor (name, next = None) - constructs a new node to store the given name. You can optionally pass a reference to a next node, or if no next node is passed, None is used
  • name - a public data field representing this node's name as a string
  • killer - a public data field representing the person who killed this node as a string; initially None
  • next - a public data field representing a reference to the AssassinNode after this one, or None if there is no next node

Files:

Links:

Session #5 (Tuesday, February 15)

In this session Jordan talked about data structures in Python including, stacks, queues, maps and sets. He also talked about list comprehensions, the slick pythonic way to create data sctructures filled with data.

Session #4 (Tuesday, February 1)

In this session Jordan talked about the python math libray called Sage. The provided sage worksheet can be used by creating a free account at sagenb.org. The Sage library is hosted at UW and can be accessed as a web app through this website. Running Sage as a local library can be done, but we do not suggest or support it.

Provided files:

Homework 3: HTML Validator
Due: Tue Feb 15, 11:30pm. Turn in HW3P here.
No late turnins accepted.

In week 3 of CSE 143 we learned about using Java's collections such as lists, stacks, and queues. Python's built-in list type essentially serves as all of these structures. A list can serve as a queue just by looping over its elements. It can serve as a stack by using its append method to push and its pop method to pop. To peek, just examine the element at index [0] for a queue or the element at index [-1] for a stack.

For your assignment this week, create a Python file called htmlvalidator.py that defines a class HtmlValidator much like in the Java Homework 3.

Define the following operations in your class:

  • tags - a field storing the current list of HTML tags to process (no getTags method is required; the client can access the tags field directly)
  • __init__(self, tags) - constructor that accepts a list of HTML tags (objects of type HtmlTag) to process; raises an exception if the queue of tags is None; if no queue is passed, defaults to an empty queue of []
  • add_tag(self, tag) - adds the given HtmlTag object to the end of the validator's queue; raises an exception if the tag is None
  • remove_all(self, element) - removes all tags that match the given element; raises an exception if element is None
  • validate(self) - prints indented output and errors in the list of HTML tags, much like the same method in the Java assignment

If you really implement these methods in the "Pythonic" way, you shouldn't need any loops in methods other than validate. You can solve them using built-in functions taught in this future sessions. (You also shouldn't need a for loop to print spaces for indentation.)

You will interact with HtmlTag objects, so you should say the following at the start of your program: from htmltag import *

An HtmlTag object has the following methods:

  • matches(other) - returns True if the given other tag matches this tag; that is, if they have the same element but opposite types, such as <body> and </body>.
  • is_self_closing() - Returns True if this tag doesn't require a matching closing tag; this will be True only for certain elements such as br and img.
  • __str__() - Returns a string representation of this HTML tag, such as "</table>". Allows the str() conversion function to be used on HtmlTag objects.

The other "get" methods are missing because the data in a tag such as its element and is_open_tag can be accessed directly through the fields.

Files:

Links:

Session #3 (Tuesday, January 25)

In this session Roy talked about many aspects of classes and inheritance in Python.

Provided files:

Homework 2: SortedIntList
Due: Sat 2/8, 11:30pm. Turn in HW2P here.
No late turnins accepted.

For your assignment this week, create a Python file called sortedintlist.py that implements a class SortedIntList. Each SortedIntList object stores a sorted list of values. You should extend our provided ArrayIntList class from the file arrayintlist.py. (The file names are misnomers because you could store any type of sortable value in the lists.) Your file should work with the provided testlist.py. You'll want to review the syntax for classes and (briefly) inheritance from weeks 8-9 before writing this program. Make sure to comment your class and methods using __doc__ strings.

Define (and/or override from ArrayIntList) the following operations on your list:

  • __init__(self, unique=False) - constructor with optional unique boolean parameter
  • append(self, value) - adds given value in sorted order
  • __contains__(self, value) - searches the list for a value using binary search
  • get_unique(self) - return whether only unique values are allowed
  • set_unique(self, unique) - set whether only unique values are allowed; if True, removes all duplicates from the list
  • max(self) - return the maximum element from the list; if list is empty, raises an exception
  • min(self) - return the minimum element from the list; if list is empty, raises an exception
  • __str__(self) - return a string representation of the list, such as "S:[4, 5, 5, 17, 17]" or "S:[4, 5, 17]U"

To do a binary search in Python, use the bisect, bisect_left, or insort functions. Documentation for these functions is at the link below. To use them, remember to write: from bisect import *

Since the provided testlist.py is not a very good or exhaustive test, you are encouraged to write your own testing code to make sure your list works. If you like, you can turn in your own testlist.py or share your testing code with others on the message board.

Files:

Links:

Session #2 (Tuesday, January 18)

In this session David lead the second part of a two-part python basics review. We will be learning about lists, objects and other odd and ends that we missed last time.

Provided files:

Homework 1: Tiles
Due: Tue 2/1, 11:30pm. Turn in HW1P here.
No late turnins accepted.

In week 1 of the course we learned about the idea of collections and using ArrayList. In week 2 we implemented an ArrayIntList collection together. Python also has collections built in; in particular, its built-in list type is much like an ArrayList.

For your assignment this week, create a Python file called tilemanager.py that implements a class TileManager. Each TileManager object stores a list of tiles. Each tile is represented as a Tile object; the Tile class is defined our provided file tile.py. Your tile manager will be created by the overall main program that is defined in tilemain.py. You'll want to review the syntax for classes and objects from 142 week 8 before writing this program.

Define the following operations in your TileManager class:

  • __init__(self) - initialize a new tile manager object. Initially the manager is not storing any tile.
  • add_tile(self, rect) - add the given tile to the end of the tile manager's list of tiles.
  • draw_all(self, panel) - should cause all of the tiles in the tile manager to draw themselves onto the given drawing panel. You do not need to do this yourself directly by calling methods on the panel object; each Tile object already has a draw method that it can use to draw itself. You just need to pass on the panel object to each tile to do the rest of the work. Draw the tiles in order from bottom (start) to top (end) of your manager's list.
  • rise(self, x, y) - This is exactly the same as the raise method in the Java version, but Python uses raise as a keyword so the name had to be changed. The graphical user interface ("GUI") calls this method on your tile manager when the user left-clicks. It passes you the x/y coordinates the user clicked. If these coordinates touch any tiles, you should move the topmost of these tiles to the very top (end) of the list. If the coordinates do not touch any tiles, no action or error should occur.
  • lower(self, x, y) - The GUI calls this method on your tiles manager when the user Shift-left-clicks. If these coordinates touch any tiles, your method should move the topmost of these tiles to the very bottom (beginning) of the list. If the coordinates do not touch any tiles, no action or error should occur.
  • delete(self, x, y) - The GUI calls this method on your tile manager when the user right-clicks (or Ctrl-clicks). If these coordinates touch any tiles, your method should delete the topmost of these tiles from the list. If the coordinates do not touch any tiles, no action or error should occur.
  • delete_all(self, x, y) - The GUI calls this method on your tile manager when the user Shift-right-clicks (or Shift-Ctrl-clicks). If these coordinates touch any tiles, your method should delete all of these tiles from the list. If the coordinates do not touch any tiles, no action or error should occur.

The Python Tile class has the following fields and methods:

  • x, y, width, height, color - Fields of the object. You may access them directly, because Python doesn't do encapsulation as well as Java.
  • draw(panel) - Draws the tile onto the given drawing panel. For example, you could ask a tile my_tile to draw itself on a drawing panel p by writing my_tile.draw(p) .
  • __str__() - Converts the tile into a string. For example, you could print the state of a tile my_tile by writing print("Tile is " + str(my_tile)) .

Tile doesn't have any accessor methods like getX or getHeight. The Python way to do this is to just have public fields and refer to them directly. (Gasp!)

Provided files:

Links:

Session #1 (Tuesday, January 11)

In this session David will lead the first part of a two-part python basics review which will continue next week. We will be learning about everything from variable to file processing. If you ever wanted to learn python in the past this is a good chance to be introduced to much of the language.

Files:

Python Books and Tutorials:

If you want to learn more Python on your own, here are some good online books and tutorials to read.

General info about the CSE 143 Python program:

This quarter in CSE 143, we will conduct a special optional program to offer students a chance to learn a second programming language as you're learning Java. The second language's name is Python.

This program is targeted at people who already participated in our Python program during CSE 142 in a past quarter. If you didn't, you can still try to follow along, but it may be more difficult.

What is Python?

Python is a language that's good for writing programs to process text and other data. It's used heavily in the Linux operating system and at companies like Google.

Why would I want to learn Python, in addition to Java?

Learning two programming languages is a bit like growing up in a bilingual family: you'll not only learn those two languages well, but you may also learn some higher concepts about programming and programming languages in general.

In addition, Python is used in a lot of other fields and disciplines, so it can be useful to have experience in it. Lastly, Python is a powerful language that does a lot of things more easily than Java, so it can be fun rewriting your past Java programs in Python and seeing how much shorter and cleaner they can be solved.

What will I do if I participate in this program?

The work involved in this program would be the following:

  • Reading each week's posted links and info for that week's material
  • Completing optional Python programming projects each week as desired

Primarily, these projects will consist of solving the same problem as that week's Java programming assignment, but in Python, and perhaps with minor modifications to the assignment spec.

What reward do I get for doing this? Do I have to do it?

Participation is entirely optional. The reward for doing these projects will be small, to make sure that Python doesn't give students with prior experience an unfair advantage over new programmers. Right now, we're planning to reward students with 1 free late day for each Python program submitted. No grade points will be added or subtracted in any way for participating in this project.

How do I participate or learn more?

Just look at the slides and/or links above, and if you find it interesting, try writing the Python program for that week. If you finish it, you can turn it in from a link that we'll put up above on this page.

If you want to install and run Python programs on your own computer, follow our Python Installation Instructions below: