Title: Exercises
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

More Challenging Problems

Common Birthdays

Create a method to compute the probability that at least two people in a room of n people have birthdays that fall on the same day of the year. Assume that there are 365 days in a year and assume further that the chance of a person being born on each day of the year is the same. A single trial experiment consists of filling an array of size n with integers that are randomly distributed from 1 through 365. If any two elements in the array have the samve value, then we say that the trial is true. Thus a true trial corresponds to the case when at least two people in the room were born on the same day of the year. Simulate the probability of running, say, 200 trials with n people in the room. Do this for n = 10, n=20 and n=25. You can use the expression:
(int)(Math.random() * 365 +1)
to compute the day of birth for each person. The number of true trials divided by 200 is the computed simulated probability. What value of n yields the probablility of at least 0.5 that there are shared birthdays in the room?

Person, Student, Marriage, Family classes

This is a bit open-ended. Try to demo the concepts that you have learned so far in representing the classes Person, Student, Marriage, and Family. Feel free to add to the following list of requirements:

- The Person class should at least contain a name, age, etc. Force the Person class to having a Name specified. Have methods like eat and sleep.
- The Student class extends the Person class. The Student class should contain variables that are related to student characteristics like GPA, major, maybe a list of courses taken, with grades received, etc. .... feel free to be creative
- A Marriage class contains 2 Persons.
- A Family class contains an array of Persons. How are you going to add members to your Family class? Have a method for your family eating dinner together.
- Have a static variable that contains the total number of people in your system
- How about if we put your all of your classes in a package and use the classes from another package.

Guessing Game

Write a program to play a number guessing game. The player thinks of a number between 1 and 100 and the computer tries to guess. The program prints out how many guesses the computer used. The player must respond to each guess by typing correct, too big, or too small.

Form Letter

Create a Form letter that has 2 parts that need to be customized. Your form letter consists of an array of strings. There are 2 key strings that can show up in the letter:

****CustomerName****

****CustomerOccupation****

Your program should prompt for the customer's name and occupation and write out the letter with the 2 key strings replaced with the value entered at the prompts.

Solve the problem twice. Once using a StringBuffer and the second time without using a StringBuffer.

Pack/Unpack

Create a Simple class called Student that has fields:

- firstName
- lastName
- age
- test1Score
- test2Score

We will introduce a technique that can be useful later if we want to extract data from an Excel spreadsheet, or create a file that can be imported as an Excel spreadsheet. Excel supports a format known as Comma delimited Data where each column is delimited by a comma.

In your Student class, add 2 methods:
String pack( );
void unpack(String str);

For example, if we are in a record where :
firstName = Clem
lastName = Hasselbach
age = 54
test1Score = 82
test2Score = 88

Then pack will generate a string that looks like:
Clem,Hasselbach,54,82,88

unpack can take in a string that might contain:
Sam,Hasselbach,15,91,89

and unpack will set the variables inside the class appropriately

HINT: to convert a string of "82" to an integer 82, you can use something like the following:
int value;
String str = "82";
value = Integer.parseInt(str);

Pack/Unpack Enhancement

Modify the previous example to allow the data packed to include commas. In order to not get confused with a comma that is meant for delimiting data, a comma that is part of the data should be paired with another comma.

In otherwords:
Sam,, Christopher,Hasselbach,15, 91, 89

should have a first name of :
Sam, Christopher

Hangman Game

In hangman, you guess a word by picking letters that you think are in the word. The object is to guess the word with the fewest missed letters. Create a hangman program. Your program should keep a sorted list of already picked letters for the user's convenience.

HINT: To keep a sorted list of already picked letters, I would recommend storing the letters in a StringBuffer. Insert each picked letter into the desired spot to keep the StringBuffer alphabetized.

Gathering Words from a Paragraph

Suppose that a paragraph can only have words separated by spaces, commas, periods, or question marks. Write a routine that collects an array of all of the words that start with a particular pattern. Your method should look like the following:

String [] getWords (String paragraph, String wordStart)

For example, the following call:


  String [] arrWords;
  String paragraph = "she sells sea shells down by the sea shore. shouldnt   she ship them in a shoe?"
  arrWords = getWords(paragraph, "sh") ;


// arrWords will contain the 7 words: she shells shore shouldnt she ship shoe

Sorting

Create a Simple class called Student that has fields:

- firstName
- lastName
- age
- test1Score
- test2Score

Create another class called class_records. Your class_records class should have contain an array of Student. Your class_records constructor should indicate the maximum class size. The class_records class should contain the following methods:

void addStudent( String firstName, String lastName, int age, int test1Score, int test2Score)

- void sortByLastName()
- void sortByAge()
- void printClass()

Sorting can be done with a for loop. Each iteration through the loop looks for the smallest value available in the unsorted part of the array and moving it to the top. Ask your instructor to draw pictures of this on the board.

In your main method, fill in your array with at least 5 students and call the methods in your class_records class to demonstrate that your Program works. This problem can be solved in many different ways with different levels of sophistication provided by java. Here are some of the levels you may go through:

- Brute force comparison of Student objects with a fixed size array in the class_records class. Read in your Students using MyInput from a file. Each line of input can be parsed in one of 2 ways. Use basic String methods or StringTokenizer.
- Make the Student class implement the Comparable interface (in java.lang) and use the standard compareTo method along with with a static modeFlag.
- Make the Student class implement the Comparable interface for one of the sorts + provide a Class which implements the Comparator interface (java.util) for the other sort.
- Replace arrays with some collection class like ArrayList
- Use the standard Collections class and Comparable + Comparator interface approach.

Binary Search

Starting with your solution to the Sorting problem, you can add a method to yur class_records class called:
binarySearch (String lastName)

Binary Searches provide a quick way to look up an item in a sorted list. The basic idea is to avoid searching the whole list. If the list is sorted and I first check the middle of the list then I can quickly decide to ignore either the top of the list or the bottom of the list. If you continue this process with the list that is left, you end up throwing out half of the list with each check. For a very large list, this is much more efficient that looking at each item in the list.

Rectanglar Region

Create a class Rectangle that represents a rectangular region of the plane. A rectangle should be described using 4 integers: two to represent the corrdinats of the upper left corner of the rectangle, giving its location; one for the width; and one for the height. Your rectangle class should include:

- appropriate constructors
- a toString() method
- a method translate() that takes two integer parameters, deltaX and deltaY, used to translate the location of the rectangle
- a method contains() that takes two integer parameters, xCoord, and yCoord and returns true if the point (xCoord, yCoord) lies within the rectangle
- a method intersection() that takes a Rectangle as a parameter and returns a new Rectangle that forms the intersection of the Rectangle upon which the method is operating, and the Rectangle parameter.
- a method union() that takes a Rectangle as a parameter and returns a new Rectangle that is the smallest Rectangle which contains the Rectangle upon which the method is operating, and the Rectangle parameter.

Fraction Arithmetic Class

A Fraction can be represented as 2 integers: a numerator and a denominator. For example: 2/3 . Normally, we always like to see our fractions reduced. For example, 25/50 is normally reduced to 1/2. Create a class that maintains a Fraction and allows for addition, subtraction and multiplication of fractions. Make sure that you always reduce your results. Fill in the details on the following Fraction class:


class Fraction
{
  int num=1;
  int denom=1;

  Fraction(int n, int d)
  {
    num = n;
    denom = d;
    reduce();
  }
  void reduce()
  {
  // REDUCING LOGIC
  // Create a variable called smaller = abs(min(num,denom))
  // Loop through all of the divisors from 2 ... smaller
  // If a divisor evenly divides num and denom, then do it
  // (use % operator to determine if a number is evenly divided)
  // Note that you will also want to reduce smaller, because you won't
  // need to go through all of the divisors as you find successful
  // reductions.

  }
  Fraction add(Fraction op)
  {
    //  a/b + c/d = (a*d + c*b)/ b*d
    //  Reduce your answer
  }

  Fraction subtract(Fraction op)
  {

    //  a/b - c/d = (a*d - c*b)/ b*d
    //  Reduce your answer
  }

  Fraction multiply(Fraction op)
  {

    //  a/b * c/d = (a*c)/ b*d
    //  Reduce your answer

  }

  public String toString()
  {
    return num + "/" + denom;
  }

  public static void main(String[] args)
  {
    Fraction f1 = new Fraction(1, 20);
    Fraction f2 = new Fraction(3, 8);

    System.out.println("f1 = " + f1);
    System.out.println("f2 = " + f2);
    System.out.println("f1+f2 = " + f1.add(f2));
    System.out.println("f1-f2 = " + f1.subtract(f2));
    System.out.println("f1*f2 = " + f1.multiply(f2));
  }
}




Complex Arithmetic Class

A complex number contains a real part and an imaginary part. For example:
a + bi

Create a Complex class that supports Complex addition, subtraction and multiplication. In the following class, fill in the details to match the comments:

PLEASE ASK IN CLASS IF COMPLEX ARITHMETIC NEEDS MORE EXPLAINATION


class Complex
{
  double real=0.0;
  double imag=0.0;

  Complex(double r, double i)
  {
    real = r;
    imag = i;
  }

  Complex add(Complex op)
  {
    //(a, bi) + (c,di) = (  (a+b), (c+d)i)
  }

  Complex subtract(Complex op)
  {
    //(a, bi) - (c,di) = (  (a-b), (c-d)i)
  }

  Complex multiply(Complex op)
  {
   //(a, bi) * (c,di) = (  (ac-bd), (ad+bc)i)
  }

  public String toString()
  {
    return real + "R " + imag+"I";
  }

  public static void main(String[] args)
  {
    Complex z1 = new Complex(1.0, 5.0);
    Complex z2 = new Complex(3.0, 7.0);

    System.out.println("z1 = " + z1);
    System.out.println("z2 = " + z2);
    System.out.println("z1+z2 = " + z1.add(z2));
    System.out.println("z1-z2 = " + z1.subtract(z2));
    System.out.println("z1*z2 = " + z1.multiply(z2));
  }
}


Matrix Arithmetic Class

Matrices can be added and subtracted if they have the same dimensions. Matrices can be multiplied if the number columns in the first matrix matches the number of rows in the second matrix. The following class sketches Matrix arithmetic --> Fill in the details.

PLEASE ASK IN CLASS IF MATRIX ARITHMETIC NEEDS MORE EXPLAINATION

class Matrix
{
  int[][] vals;

  Matrix(int[][] a)
  {
    vals = a;
  }

  Matrix add(Matrix op)
  {
    // #rows in vals ==> vals.length
    // #cols in vals ==> vals[0].length
    // #rows in op   ==> op.length
    // #cols in op   ==> op[0].length


    // If the dimensions of vals and op are not the same return null,
    // and print out an error message

    // OTHERWISE,
    // Create an answer array (retval) with the same dimensions as vals
    // Create 2 nested loops to effectively do the arithmetic
    // retval[i][j] = vals[i][j] + op.vals[i][j];
    // return an instance of the Matrix class containing retval
  }

  Matrix subtract(Matrix op)
  {
    // If the dimensions of vals and op are not the same return null,
    // and print out an error message

    // OTHERWISE,
    // Create an answer array (retval) with the same dimensions as vals
    // Create 2 nested loops to effectively do the arithmetic
    // retval[i][j] = vals[i][j] - op.vals[i][j];
    // return an instance of the Matrix class containing retval

  }
  Matrix multiply(Matrix op)
  {
    // If the number of cols in vals does not = the number of rows
    // in op, then we can't multiply.  In this case return null and
    // print out an error message.

    // OTHERWISE,
    // Create a new retval array with the same number of rows as vals, and
    // the same number of cols as op.
    //
    // Perform the calculation:
    // retval[i][j] = Sum over k (vals[i][k] * op.vals[k][j]
    // The index k goes from 0 ... (#rows in op -1)
    // return an instance of the Matrix class containing retval

  }
  public String toString()
  {
    StringBuffer sb = new StringBuffer();
    for (int i=0; i < vals.length; i++)
    {
        for (int j=0; j < vals[i].length; j++)
        {
           sb.append(" " +vals[i][j]);
        }
        sb.append("\r\n");
    }
    return sb.toString();
  }
  public static void main(String[] args)
  {
    int[][] a1 = {{1,2}, {2,3}, {3,4}};
    int[][] a2 = { {1,2,3}, {4,5,6}};
    Matrix m1 = new Matrix(a1);
    Matrix m2 = new Matrix(a2);

    System.out.println("m1 = ");
         System.out.println( m1);
    System.out.println("m2 = ");
         System.out.println( m2);
    System.out.println("m1+m2 = ");
         System.out.println(m1.add(m2));
    System.out.println("m1-m2 = ");
         System.out.println( m1.subtract(m2));
    System.out.println("m1*m2 = ");
         System.out.println( m1.multiply(m2));

    int [][]a3 = {{1,2, 3}, {2,3,4}, {3,4,5}};
    int [][]a4 = { {1,2,3}, {4,5,6}, {2,3,4}};
    m1 = new Matrix(a3);
    m2 = new Matrix(a4);

    System.out.println("m1 = ");
        System.out.println( m1);
    System.out.println("m2 = ");
        System.out.println( m2);
    System.out.println("m1+m2 = ");
        System.out.println( m1.add(m2));
    System.out.println("m1-m2 = ");
        System.out.println( m1.subtract(m2));
    System.out.println("m1*m2 = ");
        System.out.println( m1.multiply(m2));

  }
}


Factorization

Create a Factors class that contains 2 methods.

The factors method produces an Vector class containing the factorization of a number. For example if a pass in the number 540 into the factors method, I get the following pairs of numbers in my class:
(2,2) (3,3), (5,1) which represents
540 = 2^2 * 3^3 * 5

The primes method is passed an integer like 540 and returns a Vector class containing all of the prime numbers between 1 and 540.

Game of Life

Create an N by M sized board for the game of life. I would recommend that you create a 1 cell size boarder that contains a no-life zone around the outside of the board --- this makes it easier to calculate the game of life rules.

Start the game out with Randomly populated cells. You might want a parameter for the probability of life in each cell. Cells with life will contain an "X", cells without life will just have a ".".

Your game should allow you to step through the cycles in the game of life.

The rules for each cycle go as follows:

- A cell that is empty gets a new birth if there were exactly 3 populated neighbors on the previous iteration.
- A populated cell stays populated cell if there were either 2 or 3 neighbors on the previous iteration.

To initialize your Life board, you can do one of 2 things:

- Initialize your matrix Randomly
- Allow the user to input where he wants his cells populated to start with.

Generic Card Game

Suppose you have a simple card game you can play with the computer that has the following rules:

- Game starts with deck of cards being shuffled
- Program gets 7 cards and you get 7 cards.
- You always start the hand by playing your first card.
- There is no trump, and Ace is the highest card in a suit.
- You win if you get 4 or more tricks
- You want your program to later work for other kinds of card games where the rules are somewhat different.

Create a Card Class, a Deck Class, and a Game class

The Card class can print its contents. The Card class can also evaluate 2 cards to determine which one is larger. The Card class can return whether it matches the Suite of another card. The Card class can also return its numeric value (i.e. 2,3,.... 11=jack, 12=queen, 13=king, 14=ace).

The Deck class has methods: shuffle and creating Hands.

The Game class creates a deck of cards, and creates 2 sorted hands. The computer plays one hand and the user selects his cards from the other hand.

Here is a starting point if you want one:

generic card starting point

Black Jack

Create a Black Jack Game. Create a small class called Card which contains a card. A Card contains 2 integer member variables. The first variable can take on the string values:

1. Club
2. Diamond
3. Heart
4. Spade

The other variable can take on the string values:

1. Two
2. Three
3. Four
4. Five
5. Six
6. Seven
7. Eight
8. Nine
9. Ten
10. Jack
11. Queen
12. King
13. Ace

A deck of cards contains 52 cards and each card is unique. You need a routine to shuffle your deck. HINT: shuffling can be done by having a for loop that goes through each card in the deck and swaps it with some random other card.

The dealer and the player start out with one card hidden and one card showing. The player must get as close to 21 as he can. If the player goes over 21, he loses. Cards 2-10 are worth their numeric value. A Jack, Queen, and King all add 10 points. An Ace can be 1 or 11 points. Once the player stops, the dealer can play cards off the top of the deck until he either wins or goes over 21.

I have a sample solution shown below. I would recommend that you try to create your own version. When you get stuck, take a peak at the sample solution.

Bj.java: Sample Code --


 // Card implements a single Card
import tools.*;
class Card
{
    String [] id1_name={"Two", "Three", "Four", "Five", "Six", "Seven",
               "Eight", "Nine", "Ten", "Jack", "Queen", "King", "Ace"};

    String [] id2_name={"Clubs", "Diamonds", "Hearts", "Spades"};
    int id1;
    int id2;
    boolean isInDeck=true;

    Card(int i1, int i2)
    {
        id1 = i1;
        id2 = i2;
    }
    void setStatus(boolean inDeck)
    {
        isInDeck = inDeck;
    }

    boolean getStatus()
    {
        return isInDeck ;
    }


    int getCardId1()
    {
        return id1;
    }

    int getCardId2()
    {
        return id2;
    }

    String name()
    {
        String str;
        str = id1_name[id1] + " of " + id2_name[id2];
        return str;
    }
}

// Deck implements a Deck of Cards

class Deck
{
    Card[] deck = new Card[52];
    int nextCardNum = 0;
    int cardsInDeck = 52;

    Deck()
    {
        int count = 0;
        for (int i= 0; i < 4; i ++)
        {
            for (int j=0; j < 13; j++)
            {
                deck[count++] = new Card(j,i);
            }
        }
    }
    void printDeck()
    {
        for (int i=0; i < deck.length; i++)
            System.out.println(i + ": card = " + deck[i].name());
    }
    void Shuffle()
    {
        int iSwap;
        Card c;
        System.out.println("Suffling Deck");
        for (int i=0; i < deck.length; i++)
        {
            iSwap =(int)( Math.random() * deck.length);
            c = deck[i];
            deck[i] = deck[iSwap];
            deck[iSwap] = c;
        }
        nextCardNum = 0;
    }
    Card nextCard()
    {
        Card retCard;

        if (cardsInDeck <= 0)
            return null; // Deck of cards is empty

        do
        {
            retCard = deck[nextCardNum++];
            if (nextCardNum >= deck.length)
                Shuffle();
        }while (! retCard.getStatus()); // keep going if card isn't in deck

        retCard.setStatus(false); // Card leaves the deck
        cardsInDeck -= 1;
        return retCard;
    }

    void returnCards(int num, Card[] cards)
    {
        for (int i=0; i < num; i++)
        {
            cardsInDeck += 1;
            cards[i].setStatus(true); // Return cards to deck
        }
    }

}

// Black Jack Main Class
public class Bj extends Deck
{
// Create the player's hand and the dealer's hand
    Card[] phand = new Card[26]; // Overkill size
    Card[] dhand = new Card[26]; // Overkill size
    int dealerCardCount = 0;
    int playerCardCount = 0;
    MyInput in = new MyInput();


    void newGame()
    {
        returnCards(playerCardCount, phand);
        returnCards(dealerCardCount, dhand);
        playerCardCount = 0;
        dealerCardCount = 0;

        Shuffle();

        // Deal 2 cards to the dealer and the player

        for (int i = 0; i < 2; i ++)
        {
            phand[i]  = nextCard();
            dhand[i]  = nextCard();
            dealerCardCount += 1;
            playerCardCount += 1;
        }
    }

    // Evaluate the total point value for a hand (dealer's or player's)
    int evaluate(int num, Card[] c)
    {
        int sum = 0;
        int value2;
        for (int i= 0; i < num; i++)
        {
            value2 = c[i].getCardId1() + 2;
            if (value2 > 10)
                switch (value2)
                {
                case 11: //Jack
                case 12: //Queen
                case 13: //King
                    value2 = 10;
                    break;
                case 14: // Ace
                    if (sum + 11 <= 21)
                        value2 = 11;
                      else
                        value2 = 1;
                    break;
                }
             sum += value2;
        }
        return sum;

    }

    // Display the current status of the hands
    void display(boolean showDealer)
    {
        // Print out the dealer's visible hand and
        // Current Player's hand along with the evaluation
        System.out.println("*************************************");
        System.out.println("Player Total = " + evaluate(playerCardCount, phand));

        // print out user's cards
        for (int i = 0; i < playerCardCount; i++)
            System.out.println(phand[i].name());
        System.out.println(" -- ");
        if (showDealer)
        {
            System.out.println("Dealer Total = " + evaluate(dealerCardCount, dhand));

           // print out dealer's cards
            for (int i = 0; i < dealerCardCount; i++)
                System.out.println(dhand[i].name());

        }
        else
        {
            System.out.println("Dealer is showing: " + phand[0].name());
        }
        System.out.println("/////////////////");

    }

    // Player wants to take a new card
    void hitme()
    {
        phand[playerCardCount++] = nextCard();
    }

    // Dealers turn to finish out the game
    // Dealer returns whether the Player won or lost the game
    boolean dealerPlay()
    {
        // dealer now sees what the Player has chosen,
        // so the dealer keeps taking cards until he
        // either loses or wins
        int playerTotal, dealerTotal;

        playerTotal = evaluate(playerCardCount, phand);
        if (playerTotal > 21) return false; // player is busted

        for(;;)
        {
            dealerTotal = evaluate(dealerCardCount, dhand);
            if (dealerTotal > 21) return true; // dealer is busted
            if (dealerTotal >= playerTotal)
                return false; // dealer wins

            dhand[dealerCardCount++] = nextCard();
        }
    }
    void playGame()
    {
        String response;
        boolean wantsHit;

        newGame();

        do
        {
            display(false); // print out current status
            System.out.println("Do you want another hit?");
            response = in.get();
            wantsHit = response.equals("y");
            if (wantsHit)hitme();
            if (evaluate(playerCardCount, phand) > 21)
            {
                // If the player is busted we automatically finish game
                System.out.println("You are Busted: > 21");
                break;
            }
        } while (wantsHit);
        System.out.println("\n\n\n");

      // Now that the player has taken all of his cards,
      // dealerPlay contains the dealer's logic for trying to beat
      // the player

        if (dealerPlay())
            System.out.println("You win!!!!  :-)");
          else
            System.out.println("You Lose :-(");
        display(true);
    }

    public static void main(String[] args)
    {
        Bj bjGame = new Bj();
        String response;
        for (;;)
        {
            System.out.println("\n\n\nDo you want to play Black Jack ?");
            response = bjGame.in.get();
            if (response.equals("y"))
                bjGame.playGame();
            else
                break;
        }
    }
}




Last Updated: March 1, 2004 0:28 AM