CSci2110 - Problem Set 1

Due: Thursday January 24th before 11:55pm
Preparation: You may find it useful review Chapters 1 & 2 of the textbook and read carefully Chapter 3 section 5 on recursion..
Goal: Warm-up on Objects and Classes plus practice with recursion

Revisions History:
- Created Jan. 4th 2013

1) Customers, AirLineTickets and Flights

Implement a class called Customer that represents a passenger on the airline DalhousieAir. Each Customer instance should keep track of its name, its address, its membership number in DalhousieAir's frequent flyer club, and the number of points accumulated in that club. Thus a Customer object has four  fields or instance variable:

name of type String
address of type String
membershipNumber of type int
membershipPoints of type int

Implement a class called Flight that represents a flight on DalhousieAir. Each Flight instance should keep track of its flight number, its origin, its destination, and its departure date and time. Thus a Flight instance has four fields (instance variables):

flight number of type int
origin of type String
destination of type String
departure of type String

Implement a class called AirlineTicket that represents a ticket for a flight on DalhousieAir. Each AirlineTicket instance should keep track of its passenger, its flight, and its price. Thus an AirlineTicket instance has three fields (instance variables):

passenger of type Customer
flight of type Flight
price of type double

For the Customer class, implement the following instance methods:

• public get (accessing) methods and protected set (modifying) methods for the fields (instance variables)
• a zero-argument constructor (i.e., one that takes no parameters)
• a constructor that accepts a name, address, and membership number, and sets the initial value of the membership points to zero
• a toString method that returns a String representing the Customer objects name, address, membership number, and membership points.
• e.g., "Ming Chiang, 147 Hobson Road, Ottawa, #123456, 1500 points"
• an applyPoints method that takes an AirlineTicket as a parameter, calculates the points value of the ticket, and adds that value to the Customer objectís membership points. The applyPoints method should return the new value of the membership points. The points for a given AirlineTicket object are to be calculated by dividing the price of the AirlineTicket object by 100 and rounding to the nearest integer.

For the AirlineTicket class, implement the following instance methods:

• public get (accessing) methods and protected set (modifying) methods for the fields (instance variables)
• a zero-argument constructor (i.e., one that takes no parameters)
• a constructor that accepts a passenger, a flight, and a price
• a toString method that returns a String representing the AirlineTicket object. The String should include the passengers name, the flight number, the origin, the destination, the departure, and the price. e.g., "Ming Chiang, Flight 1030, Ottawa to Calgary, 03/02/99 7:50 pm, $600.00"

For the Flight class, implement the following instance methods:

• public get (accessing) methods and protected set (modifying) methods for the fields (instance variables)
• a zero-argument constructor (i.e., one that takes no parameters)
• a constructor that accepts flight number, origin, destination, and a departure
• a toString method that returns a String representing the Flight object. The String should include the flight number, the origin, the destination, and the departure. e.g., "Flight 1030, Ottawa to Calgary, 03/02/99 7:50 pm"

Testing:

Be sure to test your code thoroughly. Create a class called TestTicket with several static test methods for testing your Customer, AirlineTicket, and Flight objects.

Choose meaningful test cases. You are responsible for developing a convincing test plan, i.e., for convincing the TAs that your methods work properly. Here is an example of a test method:

public static void test1() {

       Customer anisa;
       AirlineTicket ticketAnisa;
       Flight flightCalgary;
       anisa = new Customer();
       anisa.setName("Anisa Shane");
       anisa.setAddress("101 Shangrala Street, Calgary");
       anisa.setMembershipNumber(123456);
       anisa.setMembershipPoints(0);
       flightCalgary = new Flight(101, "Ottawa", "Calgary", "03/02/99 7:50 pm");
       ticketAnisa = new AirlineTicket(anisa, flightCalgary, 600.00);
       System.out.println(anisa);
       System.out.println(flightCalgary);
       System.out.println(ticketAnisa);
       System.out.println(anisa.applyPoints(ticketAnisa));
       System.out.println(anisa);
}

Note: Submit a printout of your Customer, AirlineTicket, and Flight classes and their methods along with a copy of the output generated by the testing. Include comments in your code and ensure that all of the output is clearly explained. Be sure to focus on encapsulation. Make everything private that it is reasonable to do so. Testing will be marked!

2) Sudoku

SUDOKU is a type of puzzle that some people love to solve. Personally, I find this odd because computers are MUCH better at this sort of thing! In Sudoku you start with a 9 * 9 grid in which some cells are filled with numbers in the range 1-9.

To solve a SUDOKU puzzle, you must complete the grid such that every number from 1 to 9 appears exactly once in:

• Each of the nine vertical columns
• Each of the nine horizontal rows
• Each of the nine 3 x 3 boxes

a) Write a Java program that uses recursion to solve SUDOKU puzzles. Your program should read the original grid from a text file using a method like readFile/1.

int gridSideLength;
int gridSize;

public static void readFile(String fileName) {
   try {
      Scanner scanner = new Scanner(new File(fileName));

	   gridSideLength = scanner.nextInt(); 
      gridSize = gridSideLength * gridSideLength;
      s = new int [gridSideLength] [gridSideLength];

      for (int row = 0;row <gridSideLength;row++)
         for (int col = 0; col < gridSideLength; col++) 
            s[row][col] = scanner.nextInt(); 

      scanner.close();
   } catch (FileNotFoundException e) {
        e.printStackTrace();}
}

     solve(int location)
       If location == gridSize // puzzle has been solved
          display_solution;
          return true;
       else
          Check each integer v between 1 and gridSideLength
              if v is OK in location //meaning that row, col and square conditions are met
                 set location to v
                 return solve(nextEmptyLocation(l))
              else return false

If you are unsure of how to go about designing a recursive solution you might want to look over the Maze_Search program.

b) Augment your program so that it reports timing statistics. If we call a Trial testing a single integer at a single location, how many trials per second does you code make. Show the output of your timing results in your testing.

c) Will your code always find a solution? Argue why or why not.

d) Using big-oh notation describe the complexity of your method.

Bonus Marks:

1. Modify your program so that it generates ALL solutions not just the first solution that it finds. Sudoko puzzles are surposed to have exactly one solution but if you randomly generate the starting state this may not be true.
2. Modify your program so that it works for gridSizeLengths = i * i, for i = 1, .., n. Note: i = 3 is the usualy case. How large a value of n can your program handle?
3. Add a new output feature at draws the recursion tree that your Sudoku program walks using Graphviz (http://www.graphviz.org). Basically you will need to create an output routine that generates a file in "dot language" that Graphviz can use to draw your recursion tree.