CSci2110 - Problem Set 1

Due: January 22nd 2015 by 11:59 pm

Revisions History:
Created Dec 30, 2014
Added more recursion examples. See RecursionExamples.

Assignment Goals:

1. Review/learn more Java features including text file handling, exceptions, and multi-dimensional arrays.
2. Give you experience designing algorithms based on non-trivial recursive enumeration
3. Practice with code craft requirements. See the code craft requirements document BEFORE you start this assignment.

Question 1: A League of Teams

Implement a class called Team that represents a team that plays other teams in a league. Each Team instance should keep track of its name,  and the number of wins, losses and ties in the current competition. Thus a Team object has four protected or private fields or instance variable:

name of type String
wins of type int
losses of type int
ties of type int

Implement a class called League that represents a group of teams. Each League  instance should keep track of the number of teams in the League, the teams themselves, and its name. Thus a League instance has three protected or private fields (instance variables):

name of type String
size of type int
teams an array of Teams

For the Team 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 and sets the initial value of the wins, ties and  losses instance variables to zero
• a toString method that returns a String representing the Team object's name, and wins, ties and  losses record.
  e.g., "The Tigers have 2 wins, three ties, and 2 losses."
• an totalPoints method that returns the team's total points where a win is worth 2, a tie worth 1 and a loss worth 0.
• a gamesPlayed method that returns the total number of games that the team has played
• a main method that contains at least the testing in the following example main

public static void main(String args[]) {
Team teamA = new Team("Ottawa Senators");
Team teamB = new Team("Montreal Canadians");

//simulate the playing of two games
System.out.println(teamA.getName() + " just beat " + teamB.getName());
teamA.setWins(teamA.getWins() + 1);
teamB.setLosses(teamB.getLosses() + 1);
System.out.println(teamA.getName() + " just tied " + teamB.getName());
teamA.setTies(teamA.getTies() + 1);
teamB.setTies(teamB.getTies() + 1);

//Now print out some statistics
System.out.println(teamA.toString());
System.out.println(teamB.toString());
System.out.print("The " + teamA.getName() + " have ");
System.out.print(teamA.totalPoints() + " points and played ");
System.out.println(teamA.gamesPlayed() + " games.");
System.out.print("The " + teamB.getName() + " have ");
System.out.print(teamB.totalPoints() + " points and played ");
System.out.println(teamB.gamesPlayed() + " games.");
}
}

For the League class, implement the following instance methods:

• public get (accessing) methods and protected set (modifying) methods for appropriate fields (instance variables)
• a zero-argument constructor (i.e., one that takes no parameters)
• a constructor that accepts a name
• a toString method that returns a String representing the League object's name, and number of teams.
  e.g., "The University league with 8 teams."
• an addTeam method that given a team adds it to the league
• a showTeams that prints a listing of the teams in the league and their standings (wins, losses, draws).
• recordWinAndLoss(Team winner, Team loser) - record a won game given two Teams
• recordTie(Team teamA, Team teamB) - record a tied game given two Teams
• teamWithName(String aName) - Find and return the team with the given name. If none exists, return null
• recordTie(String teamAName, String teamBName)  - record a tied game given the names of the two Teams
• recordWinAndLoss(String winningTeamName, String losingTeamName)  - record a tied game given the names of the two Teams
• totalGamesPlayed() - Return the total number of games played in the League
• firstPlaceTeam() - Return the team with the most points
• lastPlaceTeam()  - Return the team with the least points
• a main method that contains appropriate testing

Question 2: Cross Sums

Kakro, also known as cross sums, is a recent puzzle craze. You can find Kakro puzzles in a number of newspapers and on the web (See here or here for example).. These puzzles look a bit  like "math based" crossword puzzle. The numbers, that appear in the black margins, represent the sums of the digits that you will insert into the empty squares. A number above a diagonal line refers to the empty squares to the right of that number, and a number below a diagonal line refers to the squares below that number. No zeros appear in the puzzle, and no digit is repeated in a particular number. An example taken from the Dell Magazine Cross Sum page is given below.

a) Create a java class called Kakro to represent a puzzle. I should contain at least the following public methods:

• Kakro(String filename) - A constructor that reads a sample puzzle from the specified text file. For the puzzle shown directly below you will find the associated text file, kakro here. If you create an text files that youYou may want to investigate the Scanner class to help you. Be sure to handle the "file not found" exception and any error in reading the file gracefully using Java's exception mechanism.

• display() - This method display the current state of the puzzle. You can either learn a little bit about Java Graphics and display the puzzle that way or figure out a way to display a puzzle readably in text on the console.

b) Now comes the interesting part! Add to your Kakro class a method called solve(int location) which uses recursion to complete a Kakro puzzle. To solve the puzzle use a brute force recursive method that tries all possibilities. The key recursive routine might look something like this:

     solve(int location)
       If location == gridSize // puzzle has been solved
          display();
          return true;
       else
          Check each integer v between 1 and 9
              if v is OK in location //meaning that row, col and no duplicates 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 enumeration you might want to look over the Maze_Search program and the Sudoko program.

c) 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.

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

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

Be sure follow all of the code craft requirements carefully! Be sure to do sufficient testing!

Bonus: Round Robin Scheduling

Extend your League of Teams application to support Round Robin Scheduling of a competition among the teams in a league and a simulation of a completion.

You should add to your League class a method called scheduleCompetition() which creates a competition object that holds a two dimensional array of game objects where a game object holds two teams. scheduleCompetition() should first reinitialize to zero all win, loss and tie records. The schedule it creates should be a round robin schedule. See here for a description of how to create such a schedule. You can assume that there are enough fields so that all the games in a round can be played simultaneously. You may also assume that there is an even number of teams.

You should also create a simulation method called simulateCompetition() which "plays" all games in each round of the competition deciding each game using a random number generator.

Lastly, you should create appropriate toString and display methods to display the result of a competition.