Homework 2

From 118wiki

Jump to: navigation, search

Contents

Homework 2

Homework 2 is the first exercise of programming with network protocols.

Instructions

This homework is due by Midnight (11:59pm) on Thursday September 21, Monday September 25th, 2006.

Submit your solution using the submit command on one of the department's Linux machines to the course directory. (Note: if you don't already have an account on the departmental machines, I'll grant you an account for this course; please contact me to get your account.) Here are instructions on how to submit:

  1. In your directory, rename, move, or delete any directory named homework1
  2. Download media:Homework2.zip, and then execute "unzip Homework2.zip". This should create a directory called homework2. You will modify files in that directory to complete your homework.
  3. When your work is ready, run the submit script from your home directory by typing submit at the command prompt and hitting return/enter.
  4. When prompted for the File/directory name, enter homework2
  5. When prompted for the course put c118
  6. Next you will see a list of possible submission directories. For this assignment, reply homework2
  7. Done! For further help, please review the submit proceedure provided by CSG: submit.html
  8. Note: case does matter.
  9. Note: submitting the same homework assignment multiple times will overwrite the previously submitted homework with the same name and submit location.

Exercise BaseHTTPServer Module

The first part of the homework is to write a Python program called urlFormat.py which is an HTTP server. Your downloaded directory includes a program called showHeaders.py -- you can study this and learn how to use BaseHTTPServer, write your own Handler class, and customize your HTTP server.

To test showHeaders.py, you'll need two windows, one with a shell (where you run showHeaders.py, for example by using the "python" command) and in the other window you have a browser. In the browser, open the URL http://localhost:8100 and you should get a result from showHeaders.py. Try the following URLs from your browser

From the example of showHeaders.py, you see how an HTTP server can process both GET and POST methods of HTTP, and how responses are returned to the browser.

The first part of your homework is to write urlFormat.py, which converts the "path" part of the URI into a string and returns that string to the requestor; it breaks apart the path where '/' or '?' or '&' characters appear. You may debug your program using a browser, however the correctness of your solution will be tested using the testUrlFormat.py, also in the downloaded directory. The docstring of testUrlFormat.py has examples that precisely show how urlFormat.py should behave.

The Game of Nim

For the second part of the homework, you'll write an HTTP server for the game of Nim. In this simple game, there are four rows of coins in the shape of a pyramid:

       X
     X X X
   X X X X X 
 X X X X X X X

Two players take turns: in each turn, a player removes any positive number of coins from one row only (at least one coin from one row must be removed in a turn). The player to remove the last coin wins.

For programming the game, we label the rows from top to bottom, a, b, c, and d. Across each row we label the positions 1, 2, 3, ..., etc. Hence we have the following positions for the game: a1, b1, b2, b3, c1, c2, c3, c4, c5, d1, d2, d3, d4, d5, d6, d7.

A Game Protocol

Your game server will use a new (just for this assignment) network protocol. A client sends a game request to the server, following the format of the Nim Protocol, and the server responds. Here is the format of the client request:

  • First character is the request type, either 's', 'r', or 'g'.
  • The 's' request only asks the server to return the current Nim game state.
  • The 'g' request is a reset command, which tells the server to start the game over with coins at all positions.
  • If the request type is 'r' (r for remove), then characters follow which name positions for the Nim game. Examples follow
  r b3 

This example specifies that the coin at position b3 should be removed.

  r d4 d5 d6 

This example tells the server to remove coins at positions d4, d5 and d6.

Server responses have another format. The first character of the response is a character in the range '0'-'9' (representing a digit). Following the first character is a blank, then a string of all the positions (in the current Nim game) where there are coins. The positions in the response string are separated by blanks. Here is an example:

  0 a1 b1 b3 c1 c2 c3 c4 c5 d1 d5 d6 d7

The response code is 0, and we see that coins are missing from b2, d2, d3, and d4. Here are the response codes and their meanings:

  • 0 Normal response to 's' request
  • 1 HTTP error with the POST method: request string is too short
  • 2 Error of POST field: request does not have "command="
  • 3 Request error: request type was not 's', 'r', or 'g'
  • 4 Normal response to 'g' request
  • 5 Position error: should be a two-character string
  • 6 Illegal move: trying to remove coins from more than one row
  • 7 Row undefined: row different from 'a'-'d'
  • 8 Position not occupied: either position too great (like a5) or no coin at position
  • 9 Game ended: there are no coins

Error codes 1 and 2 make sense when we consider how the Nim Protocol is implemented.

Protocol Layering (above HTTP)

You may know that HTTP is implemented using TCP. We will implement the new Nim Protocol using HTTP. We will use the POST method of HTTP to send requests to the server, which will return responses. In effect, HTTP is the "envelope" which carries Nim Protocol requests and returns Nim Protocol responses. Normally, the POST method is used in browsers to transmit HTML form data. This form data is a string of keywords and values. For our Nim Protocol, there is just one keyword "command=" which has, as input string, the Nim request.

In the download directory there is a program nimTest.py, which you can use to test your Nim Game server. It's also possible to test your server using a browser, provided you somehow can have a form of the appropriate type. The html for such a form could look something like this:

          <html><body>some kind of title<p>
          Nim Game Position <p>X <br> X X X <br> ... <p>
          <form action="http://localhost:8100/" method="post">
          <p><label for="Command">command:</label><br>
          <textarea rows=5 cols=64 name=command></textarea><br>
          <input type="submit" value="Xmit"><input type="reset">
          </p>
          </form></body></html>

But the assignment doesn't ask you to do this fancier, browser version.


Homework 2 Solutions

Download media:Homework2Soln.zip to see sample solutions.

Personal tools