cs1120 Problem Set 5: Wahoo! Auctions

Collaboration Policy - Read Very Carefully

Regardless of whether you work alone or with a partner, you are encouraged to discuss this assignment with other students in the class and ask and provide help in useful ways.

Remember to follow the pledge you read and signed at the beginning of the semester. For this assignment, you may consult any outside resources, including books, papers, web sites and people, you wish except for materials from previous cs1120, cs150, and cs200 courses. You may consult an outside person (e.g., another friend who is a CS major but is not in this class) who is not a member of the course staff, but that person cannot type anything in for you and all work must remain your own. That is, you can ask general questions such as "can you explain recursion to me?" or "how do lists work in Python?", but outside sources should never give you specific answers to problem set questions. If you use resources other than the class materials, lectures and course staff, explain what you used in your turn-in.

You are strongly encouraged to take advantage of the scheduled help hours and office hours for this course.

Purpose

• Learn to program using state and mutation.
• Learn how mutation changes the Python evaluation rules.
• Learn about databases and selection commands.
• Save the University from further cuts to "non-essential" services.
• Become acquainted with arrays, ArrayLists and Strings in Java.

Background

Fortunately, the University was able to get "Chapter 11" status from the Commonwealth, which gives it more power to control its own destiny by raising tuition and selling off assets. The Board of Transients has decided the time for drastic measures has arrived, and they will conduct an auction to raise money. To avoid paying fees to a commercial auction service, they have decided to exploit free labor from cs1120 students to develop an auction service for them.

Databases

Data in a database is stored in tables. The fields of a table describe the data and are not mutable. The entries of a table are the data, and can be changed.

We represent a table using a list of lists. The first element of the list is a list of the labels for the fields in the table (i.e. ["name","email"]). The rest of the elements of the list correspond to the entries in the table. All entries (including the list of lables) must all have the same number of elements.

Consider the following example table:

[["course_number","title","room"], \
    ["cs2330","Digital Logic Design","Rice Hall 240"], \
    ["cs3330","Computer Architecture","Olsson Hall 120"], \
    ["cs4102","Algorithms","Rice Hall 130"]] 

In order to work with these tables, the following definitions are provided in database.py:

# Make a table from a list of fields and a set of entries
def make_table(fieldlist,entries):
    return [fieldlist] + entries

# Make a table from just a list of fields
def make_new_table(fieldlist):
    return [fieldlist]

def table_fields(t):
    return t[0]
	
def table_entries(t):
    return t[1:]

In this problem set, we will be building an eBay-like auction service called Wahoo! Auctions.

For our Wahoo! Auctions service, we will need several different tables to keep track of the bidders, the items for sale, and the bids on those items. We use strings to describe the fields in a table. Those tables are defined in ps5.py:

bidders = make_new_table(["name","email"])
items = make_new_table(["item_name","description"])
bids = make_new_table(["bidder_name","item_name","amount"])
# bidders, items and bids are all tables in our database

Since new bids come in all the time, we will use mutation to update the state (i.e., the current information) stored in our database.

Inserting Entries

The table_insert procedure inserts an entry into a table.

You shouldn't need to change the definition of table_insert, but you should be able to understand it (defined in database.py):

def table_insert(table,entry):
    # We first need to check that the new entry has as many
    # elements as the other entries.  If it doesn't, we
    # give up and raise an error.
    if len(entry) != len(table_fields(table)):
        raise StandardError("New table entry has " + str(len(entry)) + \
            " values, but " + str(len(table_fields)) + "were expected")

    # Add the new element. The "append" function here is
    # the mutation equivalent of: table = table + [entry]
    table.append(entry)

Our auction service will need procedures for adding bidders, posting items for sale and bidding on items. We have provided a definition of add_bidder in ps5.py:

def add_bidder(name, email):
    table_insert(bidders, [name,email])

You should obtain the following interactions:

>>> table_display(bidders)
name                       email                      
-------------------------  -------------------------  

>>> add_bidder("Tim Koogle", "tk@yahoo.com")
>>> add_bidder("Katie Couric", "katie@cbs.com")
>>> add_bidder("Dave Matthews", "dave@dmb.com")
>>> table_display(bidders)

name                       email                     
-------------------------  ------------------------- 
Tim Koogle                 tk@yahoo.com              
Katie Couric               katie@cbs.com
Dave Matthews              dave@dmb.com              

Develop tests for your post_item and insert_bid procedures similar to the add_bidder examples above, and make sure they also work correctly.

Selecting Entries

For example,

>>> table_select(bids, item_name, lambda pitem : pitem == "CLAS")

So, to define table_select, you will first need to find the index of the selected field (e.g., "item_name" in the example). We have provided (in helper_functions.py) the list_find_element procedure that may be helpful for this. It takes as input a list and a value, and returns a number that indicates what is the first element of the input list that matches the input value. As usual, elements are numbered starting from 0. If none of the elements match, the return value is -1.

# Why do we need a separate helper function? (Feel free to skip this
# explanation) In this case, we need an extra variable n to keep track of
# how many elements we have seen in the list so far. Alternatively, we
# could define the recursive step as 1 + list_find_element_helper(list[1:],
# value, n+1), but then when we return -1, the entire length of the list
# will be added on top, which is not what we want.

def list_find_element_helper(list, value, n):
    if len(list) == 0:
        return -1
    elif list[0] == value:
        return n
    else:
        return list_find_element_helper(list[1:],value,n+1)

# List_find_element looks for a specific value in a list and returns its
# index in the list.  If the element is not in the list, we return -1.
def list_find_element(list,value):
    return list_find_element_helper(list,value,0)

def table_field_number(table,field):
    return list_find_element(table_fields(table),field)

Hence, you could start to define table_select as:

def table_select(table,field,predicate):
    fieldno = table_field_number(table,field)
    if fieldno == -1:
        raise StandardError("No matching field: " + str(field))
    ...

>>> print filter(lambda x : len(x) == 2, ["hi", "hello", "by", "bye"])
["hi", "by"]

If your table_select is working correctly, you should see interactions similar to these:

>>> setup_tables()

>>> print table_select(bids,"item_name",lambda x: x=="CLAS")
[['bidder_name', 'item_name', 'amount'], ['Dave Matthews', 'CLAS', 2000000], \
         ['Katie Couric', 'CLAS', 37000000]]

>>> table_display(table_select(bids,"item_name",lambda x: x=="CLAS"))
bidder-name                item-name                  amount
-------------------------  -------------------------  -------------------------
Dave Matthews              CLAS                       2000000
Katie Couric               CLAS                       37000000

>>> print table_entries(table_select(bids,"item_name",lambda x: x=="SEAS"))
[['Tim Koogle', 'SEAS', 10000000]]

>>> print table_entries(table_select(bids,"item_name",lambda x: x=="The Rotunda"))
[]

>>> print table_entries(table_select(bids,"amount",lambda x: x>10000000))
[['Tiki Barber', 'COMM', 79000000], ['Katie Couric', 'CLAS', 37000000]]

>>> print table_entries(
            table_select(
            table_select(bids,"amount",lambda x: x>10000000),
            "bidder_name",lambda x: x == "Katie Couric"))
[['Katie Couric', 'CLAS', 37000000]]

In ps5.py we define define the procedure get_bids procedure for making it easier to do table selects:

def get_bids(item):
    return table_entries(table_select(bids, "item_name", lambda x: x==item))

Highest Bids

Your get-highest-bid procedure should work like this:

>>> setup_tables()
>>> print get_highest_bid("SEAS")
['Tim Koogle', 'SEAS', 10000000]
>>> print get_highest_bid("Rotunda")
[]

Placing Bids

• Only allow bids by a bidder who is in the bidders table. If a bid is made by someone who is not in the bidders table, place_bid should report an error and not modify the bids table.
• Only allow bids on items that are up for sale. If a bid is made for an item that does not match the name of an item in the items table (or that matches multiple items), the place_bid procedure should report an error and not modify the bids table.
• Only allow a new bid on an item if the amount of the bid exceeds the amount of the highest earlier bid for the item. If a bid is made that is equal to or less than that amount, place_bid should report an error and not modify the bids table.
• Otherwise modify the bids table and return True to indicate success if the bid can be successfully placed.

To report an error, you can raise an exception. The popular StandardError exception takes as input a string describing the error message. For example: raise StandardError(bidder + " is not a legitimate bidder"). The exact prose of your error message doesn't matter — only that it clearly indicates what the problem is. So be as creative as you like with your error messages.

Note that you may run into a problem if you try to include something that is not a string in your error message. If, for example, you use the code "You bid $" + amount, where amount is an integer, then Python will raise an error, as strings and integers cannot be added together. To fix this, simply call the str function to convert something that is not a string into a string, as in "You bid $" + str(amount).

You should get interactions similar to these:

>>> setup_tables()
>>> print place_bid("Tim Koogle","SEAS",20000000)
True
>>> print place_bid("Katie Couric","SEAS",18000000)
#Traceback ... 
#    StandardError: Bid amount does not exceed previous highest bid: 
#                                            ['Tim Koogle', 'SEAS', 20000000]

>>> print place_bid("Katie Couric","SEAS",22000000)
True
>>> print place_bid("Dave Matthews","The Rotunda",1000000)
#Traceback ... 
#    StandardError: The Rotunda is not for sale!

>>> print place_bid("Wes Weimer","SEAS",10000000000)
#Traceback ... 
#    StandardError: Wes Weimer is not a legitimate bidder

Ending the Auction

winners = make_new_table(["item_name","bidder_name","winning_amount"])

>>> setup_tables()
>>> table_display(end_auction())
item_name   bidder_name    winning_amount
----------  -------------  ----------------
SEAS        Tim Koogle     10000000
CLAS        Katie Couric   37000000
COMM        Tiki Barber    79000000
SIS         Bono           1

# Note: there was no winning bid on item "CS1120", so it
# does not appear in the answer.

Try some sample auctions to demonstrate your program. See if you can make enough money to save the University, but be careful not to sell off too many important assets — we will revisit the University in Charlottansville in Problem Set 6.

Introduction to Java

The Java programming language is a popular choice for solving problems in modern computer science practice. Java is an object-oriented and statically-typed language: we will cover what those concepts mean in more detail in class.

For now, we will go through a series of simple exercises designed to make sure that we can all write simple Java programs and translate our knowledge of Python to our knowledge of Java. You'll find that the underlying algorithms and concepts remain the same, but that Java has different syntax.

Hello, world.

public class PS5 {
  // class code goes here
}

In Java, comments start with //. (In Python, they start with #.)

Inside your PS5 class, you’ll need to make a main method. Because Java programs can be quite large, the special main method tells Java where to start running your program. Unlike Python, Java is very specific about what code it executes when you run your program. Java will only run the code you put inside a function named main, so it's up to you to make sure you call any other code you want to execute! Your main function should be defined like this, inside your PS5 class:

public class PS5 {

  public static void main( String[] args ) {
    // Put your code here
  }

}

Inside your main function, you need to call Java's print function. Java's print function is called System.out.println and looks like this:

public static void main( String[] args ) {
  System.out.println("String to be printed");   
} 

print "String to be printed" 

The line System.out.println("String to be printed"); is saying "I want to print a line, and the function to do so is in the System class's output section."

You now know enough to write your first Java program.

Java Arrays and Iteration

public static void main( String[] args ) {   
  int [] numbers = {8, 6, 7}; 
  System.out.println( numbers.length );
  System.out.println( numbers[0] ) ; 
} 

numbers = [8, 6, 7] 
print len(numbers)
print numbers[0]

3
8

We're going to print the largest element in a Java array. We specify an array using the following syntax:

int [] myArray = {1, 2, 3};

Be careful when initializing a Java array: once you give it a size, you can't make it any bigger or smaller later! You can change the value of any element, you just can't add or subtract any elements from a Java array. (That's annoying, so we'll see how to work around that in the next problem.) You access elements of an array the same way you access elements of a Python list: container [ index ]

Using this information, we will make an "author list" array that holds the UVA ID strings of you and all of your partners (if any). We want it to be a public global variable that anyone (notably including our grading system!) can see. So we'll put it outside of main.

public static String [] authors = { "mst3k" } ; 

public static void main( String[] args ) {   
  // ...
} 

authors = ["mst3k"] 

# ...

If you look closely, you'll see that we had to tell Java that the author list will hold Strings. Don't worry about the public static part for now.

public static void main( String[] args ) {   
  if (5 > 3) {
    System.out.println("This is true."); 
  } 
  if (22 > 44) {
    System.out.println("Alpha."); 
  } else { 
    System.out.println("Beta."); 
  } 
  // you must give the type of each new variable
  int x = 77; 
  System.out.println(x);
} 

if 5 > 3:
        print "This is true." 
if 22 > 44:
        print "Alpha."
else:
        print "Beta."
x = 77 
print x

This is true.
Beta.
77

Note how Java uses { curly braces } instead of : and tabbing to indicate control structure grouping. We'll also need to be able to iterate over every element in an array. Both Python and Java use a for loop to do this, but the syntax is a little different:

public static void main( String[] args ) {   
  int [] myArray = { 8, 1, 6, 2, 7 } ; 
  int x = 3; 
  for (int i = 0; i < myArray.length ; i = i + 1) {
    System.out.println(myArray[i]);
    if (myArray[i] > x) {
      System.out.println("... is greater than x!"); 
    } 
  } 
} 

myArray = [8, 1, 6, 2, 7]
x = 3
for i in range(len(myArray)):
        print myArray[i]
        if myArray[i] > x:
                print "... is greater than x!"

8
... is greater than x!
1
6
... is greater than x!
2
7
... is greater than x!

Note that in Java you must put ( parentheses ) around the conditional for each if. Java for loops are often used as follows:

for( int i = 0; i < array_size; i=i+1 ) {
  // put loop body code here
}

for( index initialization; loop condition; index modifier ) {
  // put loop body code here
}

We now have enough information to write a Java procedure that finds the largest value in an array of ints.

public class PS5 {
  // author list definition

  public static void main(String [] args) {
    // code to print out "Hello, world."
    int [] myArray = {8,6,7,3,9,0,5}; 
    System.out.println( find_best( myArray ) );
  }

  public static int find_best(int [] array) {
    // ... code? ...
    for (int i=0; i < array.length; i=i+1) {
      // code involving array[i] 
    } 
    return 0 // replace with best element 
  } 
} 

Hint: You might make a local int variable best that holds the best value you've seen so far. Since you know the input array is non-empty, you might start by assigning the value of the zero-th element of the array into best. Then, inside the for loop, check to see if each element is bigger than best. If it is, reassign best to hold the new value. Finally, return best.

Sorting an ArrayList

ArrayList allows us to make variable-sized collections of objects. But with this added flexibility comes a little extra work. First, we have to tell Java that we want to use ArrayList objects. We do that by adding the following line of code before and outside our class:

import java.util.ArrayList;

public class PS5 {
  // ...
} 

import java.util.ArrayList;

public class PS5 {

  public static void main( String[] args ) {
    ArrayList<Integer> myArrayList = new ArrayList<Integer>();
  }
} 

myArrayList.add(element);       // Python: lst = lst + [element] 

myArrayList.addAll(otherArrayList); // Python: lst = lst + other_list

myArrayList.get(index);         // Python: lst[element] 

myArrayList.remove(index);  // removes the index-th element

myArrayList.size();  // Python: len(lst) 

We now know enough Java to write a procedure that sorts ArrayLists of Integers. We've learned a few ways to sort numbers. Let's try the "selection sort" or "find best sort":

public static ArrayList<Integer> sort(ArrayList<Integer> lst) {

  // 1. if the lst.size() is 0, return lst

  // 2. Find the index corresponding to the highest number in lst.
  //      This will be like your find_best code above, but will work
  //      on ArrayLists. You'll probably use "for" and ".get()". 
  //      We might call this index "best_index".

  // 3. Note the value associated with best_index in lst.

  // 4. Make a new empty ArrayList and add the best value from Step 3 to
  // it.

  // 5. Remove the best_index-th element from lst.

  // 6. Make a recursive call to sort() on the new, smaller lst. 

  // 7. Add all of the elements from the result of the recursive call
  // to the list you made in step 4, and return it.
} 

public class PS5 {
  // author list definition

  public static void main(String [] args) {
    // code to print out "Hello, world."
    ArrayList<Integer> myArrayList = new ArrayList<Integer>();
    myArrayList.add(8);
    myArrayList.add(6);
    myArrayList.add(7);
    myArrayList.add(5);
    myArrayList.add(3);
    myArrayList.add(0);
    myArrayList.add(9);
    System.out.println( sort(myArrayList) );
  }

  public static ArrayList<Integer> sort(ArrayList<Integer> toSort) {
    // ...
  } 
} 

Counting Letters in a String

String s = "Hello";                     // s = "Hello"
System.out.println( s );                // print s 
System.out.println( s.length() );       // print len(s)
System.out.println( s.substring(1,3) ); // print s[1:3] 
System.out.println( s.equals("Hi") );   // print s == "Hi" 

Note that you should not use == to compare two strings. Instead, use string1.equals(string2).

Let's write a procedure that counts the number of times a target letter appears in a string.

public static int countLetter( String toCount, String targetLetter ) {
  // Your code here
}

public class PS5 {
  // author list definition

  public static void main(String [] args) {
    // code to print out "Hello, world."
    System.out.println( countLetter("java junkies", "a") );
    System.out.println( countLetter("lorelai leigh gilmore", "l") );
    System.out.println( countLetter("", "w") );
  }

  public static int countLetter(String myString, String targetLetter) {
    // ...
  } 
} 

Welcome to Java!