CS 151: Programming Assignment 1

Introduction to Python [60 points]
due Wednesday, January 30, 11:55pm

Part 1: Getting Started

• Python uses colons and indentation to indicate blocks.  Indentation is critical in Python.  The colon at the end of a line indicates the start of a block of code, all of which must be indented to the same degree.  For example, the "return False" line is outside the for-loop because it is indented at the level of the function body, not the for-loop body.
• Variables are not declared in Python.  The L is understood to be a list and the x an element in the list, but it's up to the user to enforce this.  Return values are also not specified.  If a function includes a return statement, that's what it returns.  If it does not, then it returns nothing.
• The for-loop in Python is a little different from what you might be used to.  It specifies that the variable i should take on each value in the list L.  The "range" function is very useful in getting for-loops in Python to behave like "normal" for-loops.  (See the documentation on for-loops).
  
• The line in quotes at the top of the function is a special comment called a "docstring".  It is displayed when the user asks for documentation about this function by typing help(listSearch) at the Python prompt.  (Try this below).  The parts of the line starting with the symbol # are regular comments.

>> import search ; reload(search) ; from search import *

Part 2: Programming in Python

1. Simple functions [20 points].  Complete the following problems in a file called pa1pr1.py.
   • Write a function called TwoToTheN(n) that calculates 2^n in log(n) time.
   • Write two functions, one called mean(L) and the other called median(L) that return the average and the median of a list of numbers, respectively.  You may implement this functions recursively or iteratively.
   • Assume a tree is represented as a nested list of lists.  E.g., the tree
                        4
                      / /\ \
                     / /  \ \
                   10 3   14 1
                   /\      |
                  33 2     12
     Would be represented as the list [4, [10, [33], [2]], [3], [14, [12]], [1]].  Notice that this tree is neither binary nor ordered in any way and that the leaves are all lists of length 1.  Write two functions: BFS(Tree, elem) and DFS(Tree, elem) that perform a breadth first search and depth first search, respectively, of the tree and return whether or not elem is in Tree.  You will probably want to read about how lists can be used as Stacks and Queues in the Python documentation.
     
2. Objects [20 points]. Complete this problem in a file called pa1pr2.py
   In this problem you will develop an object for managing a game of Tic Tac Toe.  While we covered the basics of creating objects in Python in class, you will probably want to refer to Python's documentation on creating classes.  Create a class called TTTBoard that defines the following functions:
   
   • __init__(self): Initialize a 3x3 tic tac toe board (remember to avoid magic numbers in your code)
   • __repr__(self): Returns a string representation of the board
   • makeMove(self,player,pos): Places a move for player in the position pos on the board if possible.  Note that the board positions are numbered starting with 0 in the upper left and proceeding left to right, then down the board, as follows:

      0 | 1 | 2
     ---|---|---
      3 | 4 | 5
     ---|---|---
      6 | 7 | 8
     

      player is a character ("X" or "O") pos is an integer.  Returns True if the move was made and False if not (because the spot was full, or outside the boundaries of the board).
   • hasWon(self,player): Returns True if player has won the game, and False if not
   • gameOver(self): Returns True if someone has won or if the board is full, False otherwise
   • clear(self): Clears the board to reset the game
   You may represent the board however you like.  You may define other functions as well.  You may wish also to define a function that allows two players to play the game to make sure your above functions are working correctly.
   
   
3. GUI development [20 points].  Complete this problem in a file called pa1pr3.py
   Finally, you will develop a GUI for your Tic Tac Toe game you developed above.  Although we will cover the basics of designing GUIs with TkInter in class, you will probably also need to rely on the TkInter documentation.
   You may or may not build GUIs in future assignments, but GUI building is fun, and it will give you more practice with objects in Python.  :)
   
   
   Your goal is to create a simple GUI for playing an interactive game of TicTacToe like the one above.  At a minimum, it should have the following functionality:
   
   • At the beginning of the game, it should display an empty 3x3 tic tac toe board
   • When a player clicks on an empty square, it should place that player's move in that square.  It should not allow a player to place a move in a non-empty square.  It does not have to give an error message, but it should not change turns until the current player has made a legal move.
   • It should automatically alternate between players' turns.  It would be nice if your GUI displayed whose turn it is, but it does not have to.
   • It should detect when the game if over and display a message about who won (or if there was a tie).  It should not allow moves to be placed on a game that is finished.
   • It should have a button that resets the game and clears the board.
   Feel free to be as creative as you like, but all you need to implement is this basic functionality.  You should use the Tic Tac Toe class you wrote in the last problem here.  To do so, include the line:
   
   from pa1pr2 import *
   
   at the top of your file.
   
   
4. Install the AIMA code [0 points]
   Your last task is to install the code associated with the book.  Go to http://aima.cs.berkeley.edu/python/readme.html and follow the instructions for downloading and installing the code on your machine.  Make sure you have it working by running one or more of the doctests (don't worry if you don't understand what they do).  E.g., go to the directory where you installed the code and type at the command line (NOT in Python):
   
   $ python doctests.py -v search.py
   
   IMPORTANT: Over the course of the semester I may ask you to implement algorithms whose implementations already exist in this code repository.  When completing your programming assignments do not look at or use the AIMA code unless the assignment specifically tells you to do so.  For this assignment, feel free to look through or run the code if you like.