Assignment 1: Basics of Python and String Manipulation
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Autumn 2011
The reading for this assignment is Chapters 1-4 in Introduction to Python for Artificial Intelligence.
Due Friday, October 7 through Catalyst CollectIt at 2:00 PM.

You should turn in two files: (1) a file named a1.py of function definitions, and (2) a file a1examplesplus.txt of example calls, results and answers to questions. For the file of examples, you can use a combination of input and output together with comment lines (beginning with a pound sign) to show that you have verified each of your answers on the computer. For each function, show a demonstration on the same example shown on this page, and two additional examples: one shorter (or smaller), and one longer (or larger) and more interesting (use your imagination).
 

Defining Functions (30 points). Write Python function definitions for the following requirements (worth 5 points each, except for numbers 2 and 4, which are worth 10 points each). You should be able to infer what each function should do by a combination of reading its name and examining the relationship between its input and ouput on the given examples. Note that the functions that accept lists as arguments must be able to handle lists of any length. For this assignment your functions do not have to validate the types of their inputs. That is, you may assume that they will be called with arguments of the proper types.

In problem 2, you may find it helpful to write a helping function that can translate one character, and you may find the various string methods to be useful: islower(), isupper(), isdigit(), index(), and join(). You might also consider using the functions map(), and list(). The mod operator ('%') may also be helpful. 

1. eleven_x_squared_plus_1(7) -> 540  

2. subcipher("abc Iz th1s Secure? n0, no, 9!", 8) -> "IJK qH BP9A aMKCZM? V8, VW, 7!"

3. pairs([2, 5, 1.5, 100, 3, 8, 7])  ->  [[2, 5], [1.5, 100], [3, 8], [7]]

4. past_tense(['program', 'debug', 'execute', 'crash', 'repeat', 'eat']) ->
 ['programmed', 'debugged', 'executed', 'crashed', 'repeated', 'ate']
Use the following rules for forming the past tense of a regular verb in English: (a) If the verb ends in 'e', add 'd'. (Example: 'execute' becomes 'executed'.) (b) If the verb ends with a 'y' immediately preceded by a consonant, change the 'y' to 'i' and add 'ed'. (Example: 'try' becomes 'tried'.) (c) If the word ends in one vowel (not two vowels) followed by one consonant (but not 'y' or 'w'), then repeat the consonant and add 'ed'. (Example: 'debug' becomes 'debugged'. (d) For the irregular verbs to have, to be, to eat, and to go, handle these as special cases. (e) In all other cases, add 'ed'. (Example: 'repeat' becomes 'repeated'.) You don't have to handle irregular verbs other than those mentioned in (d).
Generating Possibilities (20 points). Write a definition for a Python function bead_strings that takes one argument: a list that represents what beads are available, and returns a list of all the possible strings of beads that can be constructed using all the available beads. An example input list is [['R',2],['Y',3]], which means that there are 2 red beads and 3 yellow beads. The possible strings of beads for this input are the following 
'RRYYY'
'RYRYY'
'RYYRY'
'RYYYR'
'YRRYY'
'YRYRY'
'YRYYR'
'YYRRY'
'YYRYR'
'YYYRR'
Updates and Corrections If necessary, updates and corrections will be posted here and mentioned in class or on the mailing list.
Update to problem 4: You don't have to handle irregular verbs except those mentioned in (d).
Update to the bead_strings problem: You should not use the built-in permutations function, but code your own method of generating the possibilities.