EECS110 Homework 0, Spring 2009
Due: 11:59pm on Sunday April 5, 2009
Submission: submit your solutions at the submissions server
Problems:
Go to
http://cs.northwestern.edu/~akuzma/classes/EECS110s09/lab/lab0/lab0.htm
Week 0, Problem 1: Orientation Problem - Running Python
[30 points; individual]
Welcome!
By completing this first EECS 110 homework problem in orientation, we hope
to introduce you to three things:
1. Using the python computer language, which you'll use in EECS 110.
2. Using python's IDLE editor to write and save plain-text files (python programs).
3. Submitting files to the EECS 110 submission system.
If you have any account problems or other questions/concerns, please ask!
Opening up python/IDLE
1. These directions presume python is installed, which it should be on lab PCs. If you're on your own machine, visit one of these two links first in order to install Python:
for Windows PCs
for Macs
(Linux users probably already have python installed.)
2. On a PC, right-click on the link below and choose "Save Target As..." in order to download to the desktop the file named hw0pr1.txt from this link .
3. On a Mac computer, you can control-click to do download the file.
4. On your desktop, you should see the newly-downloaded file named hw0pr1.py. You may not see the .py extension, depending on the computer's settings.
5. Right-click that hw0pr1.py file and choose "Edit with IDLE" or "Open with IDLE." IDLE is the name of an editor and interactive "shell" -- basically an area for experimentation -- that comes with Python.
6. You should see an editing window with the contents of the hw0pr1.py file -- a python program. You might also see a "Python Shell" window. If you don't see the "Python Shell" window, you should get one by going to the editing window's "Run" menu and choosing "Python Shell."
Trying out python at the python shell
· The shell is an area for experimenting with the python language. The "prompt" is three greater-than signs >>>, which tells you that python is ready to go. You might try 6*7 as a first computation at the prompt. Caution: deep wisdom may result.
· Try computing a googol (ten to the hundredth power). The power operator in python is two asterisks **. So, you would type 10**100 at the prompt. Admittedly not too enlightening, but the L at the end of the result is python's indication that this is a Long number.
Running a program from a file
· Click on the editor window to return to the program in the hw0pr1.py file.
· You don't need to understand this code (not yet, at least). However, you might take a moment to see if you can guess the behavior of any of the pieces you see there...
· To run the program, hit the F5 key or choose "Run Module" from the "Run" menu.
· The shell window will automatically come up and start running the program. This program first asks you for your name, and the cursor will already be in the right spot to start typing. (The python shell is a bit picky about where the cursor is -- if you move it and start typing, odd things might happen...)
· Type in your name, hit Enter, and the program will finish running with a follow-up message.
· You can try again by repeating these steps and/or edit the program to change its behavior.
· To see how python handles errors, you might try removing one of the two equals signs in the if line, so that it reads if name = 'Ionut'. Then hit F5 to run -- it will tell you there is a "syntax error" and give you a chance to fix it.
· The second problem for this week's hw asks you to alter this program to play a (fairly lopsided) game of rock-paper-scissors. You can do that right away (during orientation) or you can come back to it later.
· For this problem, the final step is simply submitting the hw0pr1.py file. It's completely OK if you've changed it -- this is simply to ensure you can login and use the EECS 110 submission page.
Week 0, Problem 2: Rochambeau
[30 points; individual or pair]
A rock, paper, scissors program -- that never loses...
This second problem asks you to practice
· creating new python files (in this case, by copying old ones)
· writing a bit of your own code (by altering another program, if you wish)
· textual input and output in Python
The idea is this: alter the program in hw0pr1.py so that it invites the user to play a game of "rock-paper-scissors." What's more, the program should make sure that it always wins the game (taunting the graders who will be running your program is optional).
Creating a new file named hw0pr2.py
· To create a new file named hw0pr2.py, first make sure you have hw0pr1.py (download it again, if necessary), and then copy-and-paste it to a new file. Rename that file to hw0pr2.py
· Do I really have to use that name? Actually, no -- you can use whatever name you like for the homework assignment files, but when you submit them, you DO have to have them named as specified in the assignment. So, it's easiest to name them as the submission site is expecting from the very beginning.
How the program should work?
· The program should ask the user to choose rock, paper, or scissors. Then, it should repeat back to the user their choice, it should "reveal" its own choice, and then report the results. The program should always win -- of course, it will be cheating because it will know and use the opponent's input, but we will leave a true implementation of the game to next week. Briefly, in the game of rock-paper-scissors, rock defeats scissors, scissors defeat paper, and paper defeats rock.
· You may assume that the user will input one of rock, paper, or scissors. (But feel free to catch errors and report them, if you like!)
· You may write the dialog however you like, but here's an example dialog if you'd like one to follow. This is two distinct runs of the program:
>>>
Choose rock, paper, or scissors: scissors
You chose scissors - I chose rock
I win!
>>>
Choose rock, paper, or scissors: paper
You chose paper - I chose scissors
I win!
>>>
Problem 3: Picobot (empty room) [40 points; individual or pair]
Problem 4: Picobot (maze) [extra 30 points; individual or pair]
Picobot Overview
Introduction to Picobot
This problem explores a simple "robot," named "picobot," whose goal is to completely traverse its environment.
Picobot starts at a random location in a room -- you don't have control over Picobot's initial location. The walls of the room are blue; picobot is green, and the empty area is white. Each time picobot takes a step, it leaves a grey trail behind it. When Picobot has completely explored its environment, it stops automatically.
· picobot overview:
Surroundings
Not surprisingly, picobot has limited sensing power. It can only sense its surroundings immediately to the north, east, west, and south of it. For example,
· example picobot surroundings:
In the above image, Picobot sees a wall to the north and west and it sees nothing to the west or south. This set of surroundings would be represented as follows:
NxWx
The four squares surrounding picobot are always considered in NEWS order: an x represents empty space, the appropriate direction letter (N, E, W, and S) represents a wall blocking that direction. Here are all of the possible picobot surroundings:
· all possible picobot surroundings:
State
Picobot's memory is also limited. In fact, it has only a single value from 0 to 99 available to it. This number is called picobot's state. In general, "state" refers to the relevant context in which computation takes place. Here, you might think of each "state" as one piece -- or behavior -- that the robot uses to achieve its overall goal.
Picobot always begins in state 0.
The state and the surroundings are all the information that picobot has available to make its decisions!
Rules
Picobot moves according to a set of rules of the form
StateNow Surroundings -> MoveDirection NewState
For example,
0 xxxS -> N 0
is a rule that says "if picobot starts in state 0 and sees the surroundings xxxS, it should move North and stay in state 0."
The MoveDirection can be N, E, W, S, or X, representing the direction to move or, in the case of X, the choice not to move at all.
If this were picobot's only rule and if picobot began (in state 0) at the bottom of an empty room, it would move up (north) one square and stay in state 0. However, picobot would not move any further, because its surroundings would have changed to xxxx, which does not match the rule above.
Wildcards
The asterisk * can be used inside surroundings to mean "I don't care whether there is a wall or not in that position." For example, xE** means "there is no wall North, there is a wall to the East, and there may or may not be a wall to the West or South."
As an example, the rule
0 x*** -> N 0
is a rule that says "if picobot starts in state 0 and sees any surroundings without a wall to the North, it should move North and stay in state 0."
If this new version (with wildcard asterisks) were picobot's only rule and if picobot began (in state 0) at the bottom of an empty room, it would first see surroundings xxxS. These match the above rule, so picobot would move North and stay in state 0. Then, its surroundings would be xxxx. These also match the above rule, so picobot would again move North and stay in state 0. In fact, this process would continue until it hit the "top" of the room, when the surroundings Nxxx no longer match the above rule.
Comments
Anything after the pound sign (#) on a line is a comment (as in python). Comments are human-readable explanations of what is going on, but ignored by picobot. Blank lines are ignored as well.
An example
Consider the following set of rules:
# state 0 goes N as far as possible
0 x*** -> N 0 # if there's nothing to the N, go N
0 N*** -> X 1 # if N is blocked, switch to state 1
# state 1 goes S as far as possible
1 ***x -> S 1 # if there's nothing to the S, go S
1 ***S -> X 0 # otherwise, switch to state 0
Recall that picobot always starts in state 0. Picobot now consults the rules from top to bottom until it finds the first rule that applies. It uses that rule to make its move and enter its next state. It then starts all over again, looking at the rules and finding the first one from the top that applies.
In this case, picobot will follow the first rule up to the "top" of its environment, moving north and staying in state 0 the whole time. Eventually, it encounters a wall to its north. At this point, the topmost rule no longer applies. However, the next rule "0 N*** -> X 1" does apply now! So, picobot uses this rule which causes it to stay put (due to the "X") and switch to state 1. Now that it is in state 1, neither of the first two rules will apply. Picobot follows state 1's rules, which guide it back to the "bottom" of its environment. And so it continues... .
Installing picobot
· To properly install the program below, you should have Java installed on your machine. If that is not the case, you can download and install Java by following instructions on this link first.
· Right-click on this link and select “Save Target As…” to download file Picobot.zip on your desktop.
· Right-click on the downloaded file (Picobot.zip) and select “Extract All…” Once you click this option, a new directory, called Picobot, should show on your desktop.
· Open the newly created directory Picobot (by double clicking on it). You will then see another directory called Picobot. Click twice on it as well. You should see a number of files in that directory. The only two files that you should care about are
o picobot.jar (you might not see the extension .jar depending on your computer setup.)
o PicobotRules.txt (again, you might not see the extension .txt depending on your computer setup.)
· When you click twice on picobot.jar, you should see an empty square window, which is the beginning of assignment hw0pr3 that you will do below.
· When you click twice on PicobotRules.txt you will be able to edit these rules and solve a given problem, as we explain below.
The assignment
For this assignment, your task is to design two different sets of picobot rules:
· hw 0, problem 3 [40 points]:
o one set that will allow picobot to completely cover an empty square room. Edit file PicobotRules.txt to change the existing rules. Once you are done, save this file (by selecting file/save).
o Then, click twice on picobot.jar file to see how your rules work in practice. By selecting Go/Stop, you will execute your rules. By selecting Go/Stop the next time, you will stop the execution of the program. By selecting Step, you will be able to execute a single step of your rules. Remember to always
§ Close the picobot.jar after running it.
§ Save the PicobotRules.txt file after editing it.
o Once you are done, rename the PicobotRules.txt file to hw0pr3.txt and submit it in the usual way.
· hw 0, problem 4 [30 Extra points]: another set that will allow picobot to completely navigate a connected maze (without loops) with corridors one square wide. Edit file PicobotRules.txt by changing the line