I need help with the exercises for checkpoint 1 and checkpoint 2!

1. Introduction

The objectives of this lab are to give you some practice using arrays and ArrayLists.

Your first step is to create a new project in your workspace, named project7. Inside that project, create a package lab7.

The following classes will be needed for the first checkpoint. Add them to the lab7 package:

Card.java **given at the bottom Deck.java **given at the bottom

2. Arrays

An array is a sequence of values of the same type, similar to the way that a String is a sequence of characters. The individual elements or cells of the array can be accessed individually, similar to the way we can access individual characters of a string using charAt.

Here is a simple example:

public class ArrayExample { public static void main(String[] args) { // Declares a variable whose type is "array of int" int[] arr; // Creates an array of four elements. All values are zero by default. arr = new int[4]; // Assign some values arr[0] = 17; arr[1] = 42; arr[2] = arr[1] - arr[0]; // Print out all four elements (note the fourth one is still zero) for (int i = 0; i < arr.length; i += 1) { System.out.println(arr[i]); } System.out.println(); } } 

(Import ArrayExample.java into your lab7 package to try this yourself.)

From the example we can summaries the basic properties:

Arrays are objects, and are (usually) created with the new keyword.

Newly created arrays are filled with default values (0 for primitives, null for objects).

Arrays are fixed in size, but individual cells can be modified.

The type of the elements can be any primitive type or object type.

Cells are accessed using an index and square brackets. Indices start at zero.

The number of elements is given by the .length attribute. Note this is not a method, so there are no parentheses.

We commonly use loops to iterate over the elements

Some hints for testing

There are two things above we do frequently when learning about arrays: creating small arrays for testing, and printing out the contents of an array.

Simple arrays can be created and initialized at the same time just by listing the elements in curly braces. (The compiler automatically figures out the length.)

You can print the contents of an array using the static method Arrays.toString. The utility class Arrays is in the package java.util and has many methods for working with arrays.

So we could rewrite the above example as:

import java.util.Arrays; public class ArrayExample2 { public static void main(String[] args) { int[] arr = {17, 42, 25, 0}; System.out.println(Arrays.toString(arr)); } } 

3. Loops With Arrays

By now you have seen a lot of loops that involve strings. For example, here is a loop that counts the number of p's in a string:

 public static int countPs(String s) { int total = 0; for (int i = 0; i < s.length(); i += 1) { if (s.charAt(i) == 'p') { total += 1; } } return total; } 

Suppose instead you want to count the number of positive values in an array of integers. The code is almost the same:

 public static int countPositiveNumbers(int[] numbers) { int total = 0; for (int i = 0; i < numbers.length; i += 1) { if (numbers[i] > 0) { total += 1; } } return total; } 

Example: filling an array

When working with strings, you can write a loop that creates a new string by repeatedly adding on a new character. That kind of strategy doesn't work with arrays, because we have to know the length of the array in advance.

A common problem is to parse a stream of input and use the values to initialize an array. The simplest case would be a string containing numbers separated by whitespace, such as "3 5 7 9 12". The problem is that before parsing the input, we don't know how big to make the array. One solution is to parse the input twice: once to count the items, and then again to fill the array.

 public static int[] readNumbers(String text) { // count the items in the string Scanner scanner = new Scanner(text); int count = 0; while (scanner.hasNextInt()) { scanner.nextInt(); count +=1; } // now create an array the right size, and put each element into the next cell int[] nums = new int[count]; int index = 0; scanner = new Scanner(text); while (scanner.hasNextInt()) { int num = scanner.nextInt(); nums[index] = num; index += 1; } return nums; } 

(Import ArrayExample3.java into your lab7 package to try this yourself.)

(There are other ways to solve this problem too, for example, using partially filled arrays or ArrayList.)

Exercise

Write a static method

public static int[] getPositiveNumbers(int[] numbers) 

that, given an array of integers, returns a new array containing just the positive values in the given array. (Hint: count them first.)

Exercise

Write a static method

public static int[] randomExperiment(int max, int iters) 

that generates iters random numbers in the range 0 through max - 1 and returns an array counts in which the the element counts[i] is the number of times that value i was generated. Write a main method that does this with max = 10 and iters = 1000 and prints the result.

4. Modifying an array

Unlike strings, arrays are mutable. Even though the length is fixed, the individual cells can be modified. For example, we could take an array of integers and double each of the values.

import java.util.Arrays; public class ArrayExample4 { public static void main(String[] args) { int[] test = {1, 2, 3, 4}; System.out.println("Before: " + Arrays.toString(test)); doubleAll(test); System.out.println("After: " + Arrays.toString(test)); } public static void doubleAll(int[] arr) { for (int i = 0; i < arr.length; i += 1) { arr[i] = arr[i] * 2; } } } 

(Import ArrayExample4.java into your lab7 package to try this yourself.)

The output from running this is

Before: [1, 2, 3, 4] After: [2, 4, 6, 8] 

The important thing to notice is that the method returns void. It does not create a new array, it modifiesthe given array. The variable test is just a reference to an object. When it is passed to the doubleAll method, the variable arr is a reference to the same object in memory.

Swapping elements

Many operations on arrays (such as sorting) involve rearranging the existing elements rather than modifying them. A basic step is to swap the elements at two indices.

import java.util.Arrays; public class ArrayExample5 { public static void main(String[] args) { int[] test = {10, 20, 30, 40, 50}; System.out.println("Before: " + Arrays.toString(test)); swap(test, 1, 4); System.out.println("After: " + Arrays.toString(test)); } // exchange the element at index i with the element at index j public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } 

(Import ArrayExample5.java into your lab7 package to try this yourself.)

When we run this the output is:

Before: [10, 20, 30, 40, 50] After: [10, 50, 30, 40, 20] 

Example: reversing an array

The idea is to reverse the order by swapping elements instead of creating a whole new array. To reverse a sequence of things, what happens? The first element becomes the last one, and the last element becomes the first one; then the second element becomes the next-to-last, and the next-to-last becomes second; and so on.

 public static void reverse(int[] arr) { int front = 0; int rear = arr.length - 1; while (front < rear) { swap(arr, front, rear); // move indices towards the center front += 1; rear -= 1; } } 

(Import ReverseArray.java into your lab7 package to try this yourself.)

5. Example: Selecting distinct random elements

In the preceding examples we have practiced writing loops using arrays of integers. This example is somewhat more realistic and involves an array of objects.

Imagine that for programming a card game we have a Card class and we represent a standard 52-card deck with an array of 52 Card objects. How would you "deal" a hand of 5 cards, that is, how would you select 5 cards at random? Suppose your array is called cards, and suppose that you have an instance rand of java.util.Random available. You might start with something like this:

 Card[] hand = new Card[5]; for (int i = 0; i < 5; i += 1) { int index = rand.nextInt(52); hand[i] = cards[index]; } 

What's wrong with this? Well, although unlikely, it is entirely possible to get a hand with five aces or other duplicates. What we need is to sample from the deck "without replacement", that is, we need a way to select 5 distinct objects from the array.

Here is one possible algorithm for doing this.

First, choose an random index in the range 0 through 51.

Exchange that element with the last one.

Choose a random index in the range 0 through 50. (Notice that the first element selected can't be selected again, since it's in position 51.)

Exchange that element with whatever is in position 50.

Choose a random index in the range 0 through 49.

...and so on, until you've made 5 selections.

When done, the last 5 elements of the array are the ones you want.

In general you might be selecting a larger number of elements, so you would use a loop, where in the ith iteration you select an index in the range 0 through (array length - i).

6. Checkpoint 1

Your task is to implement the algorithm described informally in the previous slide. You'll need the files Card.java and Deck.java. It is not strictly necessary that you understand all of the provided code, but it contains plenty of examples of manipulating arrays.

Implement your algorithm in the method select(int k) of the Deck class (look for the TODO marker):

 /** * Returns a new array containing k elements selected * at random from this deck. */ public Card[] select(int k) { // TODO return null; } 

As always we suggest you start by writing the algorithm in pseudocode.

You can test your class by writing a short main method, for example:

public class DeckTest { public static void main(String[] args) { Deck deck = new Deck(); Card[] hand = deck.select(5); System.out.println(Card.toString(hand)); } } 

Note the utility method toString(Card[] arr) in the Card class for displaying an array of cards as a string.

Now you can play poker with the person next to you in lab :).

Checkpoint 1

Demonstrate your code for the three preceding exercises to the TA (getPositiveNumbers, randomExperiment, and the select method)

Show the TA the confirmation page from the Lab and TA Evaluation survey.

Optional: What do you think should happen if you call select a second time on the same Deck? Try modifying the class so that, for example, if you first select 5 cards, then the second time you call select it will only select cards from the remaining 47.

Aside: Testing code that uses randomization

When you are testing code, if you find a bug you want to be able to repeat it. Then, when you fix the code, you can try the same thing again and make sure it doesn't still occur. When you are testing code that uses randomization, how can you make the results repeatable?

The answer is to "seed" the random number generator with a known value. The seed value is used internally by the generator to initialize the algorithms it uses. The useful thing is that instances of Random that are created with the same seed will always produce exactly the same sequence of pseudorandom values. So, for example, if we change the DeckTest like this:

public class DeckTest { public static void main(String[] args) { Random rand = new Random(42); // "seed" the random number generator with a value we choose Deck deck = new Deck(rand); // construct the deck to use that generator Card[] hand = deck.select(5); System.out.println(Card.toString(hand)); } } 

The results will be the same every time you run the program. This is useful for testing. That's the reason for having the second constructor for Deckthat lets you pass in the Random of your choice.

An instance of Random created with the default constructor just uses an arbitrary value for the seed that is likely to be different for different runs of the program (e.g. a number based on the system clock). When you are using random values for a game, this usually makes the results sufficiently unpredictable.

7. Sorting Arrays

There are many ways to sort an array. One of the simplest sorting methods, especially for shorter arrays, is the Selection Sort algorithm. (Wikipedia has a great article on Selection Sort.)

The idea is pretty simple. Think about it like this: What element should end up at index 0 in the sorted array? It should be the smallest element, right? So, find the smallest element, and move it to index 0. We also have to save the element that started out at index 0, so we swap it. Then do the same thing for index 1, and so on.

The implementation of any sorting algorithm may vary depending on exactly how you want the items ordered. For numbers, we can just compare their values. The Card objects have both a suit and a rank. One idea would be to order cards by suit, CLUBS, DIAMONDS, HEARTS, SPADES, and then within a suit, order the cards by their rank: A, 2, 3... J, Q, K. That's what this example does:

 private void sortWithSuit() { for (int i = 0; i < cards.length - 1; ++i) { // Step 1: find the "minimal" element to the right of position i int indexOfMin = findIndexOfMin(i); // Step 2: swap the minimal element into position i swap(i, indexOfMin); } } /** * Returns the index of the minimal element to the right of position 'start', * where cards are ordered first by suit, and within the same suit, by rank. * * @param start * first index at which to look * @return index of the smallest element to the right of 'start' */ private int findIndexOfMin(int start) { int indexOfMin = start; for (int j = start + 1; j < cards.length; ++j) { // look at the two cards, the minimal one we've found, // and the one at the current position j Card min = cards[indexOfMin]; Card current = cards[j]; // if current has a lower suit than the current min, then it should come // first if (current.getSuit().compareTo(min.getSuit()) < 0) { indexOfMin = j; } else if (current.getSuit().equals(min.getSuit())) { // suits are the same, so compare ranks if (current.getRank() < min.getRank()) { indexOfMin = j; } } // otherwise, current does not come before min, so ignore it } return indexOfMin; } 

You can find the code above as part of the PokerHand class. A PokerHand is constructed from an array of five cards and has some methods for determining the value of the hand in a game.

PokerHand.java **given at the bottom

DeckTest2.java **given at the bottom

Algorithms that depend on sorting

By sorting the array first, we can answer questions about the hand more simply. For example, a poker hand is called a flush when all the cards have the same suit. If the hand is unsorted, we have to look at all the cards to determine whether it's a flush. If the hand is sorted by suit, we only have to look at the first and last cards. Here is a method you can see in the PokerHand class that determines whether the hand is a flush:

public boolean isFlush() { sortWithSuit(); //After sorting the first card's suit and the last card's suit is only equal if //the cards have the same suit. return hand[0].getSuit().equals(hand[hand.length - 1].getSuit()); } 

Notice that even if we had a strange game in which a hand was 100 cards, we could still determine whether the hand is a flush by looking at just the first and last cards, as long as we've kept the array sorted by suit. This is called a "constant-time" algorithm, since it takes the same amount of time regardless of the size of the array. (In contrast, an algorithm that has to look at every card is called "linear time" because the time it takes is proportional to the size of the array.)

8. Checkpoint 2

1. Write the sortNoSuit() method in PokerHand.java (on the previous page). You can look at the similar sortWithSuit() method for help.

2. Write the isStraight() method. A straight is whenever you have 5 cards in a row, for example: 4, 5, 6, 7, 8.

3. Write the isFullHouse() method. A full house is whenever you have a pair and a triple: K, K, A, A, A.

4. Run the DeckTest2 program (also on the previous page). Which random seeds create a full house?

CODES THAT ARE GIVEN:

Card.java:

package lab7; /** * Class representing a playing card with possible rank 1 through 13 and four * possible suits. */ public class Card { /** * Constants for the four suits. */ public enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES }; /** * Suit for this card. */ private final Suit suit; /** * Rank for this card. */ private final int rank; /** * Names used for displaying strings. */ private final String[] NAMES = {"Dummy", // element 0 not used "Ace", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Jack", "Queen", "King"}; /** * Constructs a card with the given rank and suit. Ranks are assumed to be in * the range 1 through 13. * * @param givenRank * rank for this card * @param givenSuit * suit for this card */ public Card(int givenRank, Suit givenSuit) { rank = givenRank; suit = givenSuit; } /** * Returns the rank for this card. * * @return rank for this card */ public int getRank() { return rank; } /** * Returns the suit for this card. * * @return suit for this card */ public Suit getSuit() { return suit; } /** * Returns a String representation of this card. */ public String toString() { return NAMES[rank] + " of " + suit; } /** * Returns a String representation of a given array of cards. * * @param arr * array of Card objects * @return a String representation of the given array */ public static String toString(Card[] arr) { StringBuilder sb = new StringBuilder(); sb.append("["); for (int i = 0; i < arr.length; ++i) { if (i > 0) { // every element after first one has comma before it sb.append(", "); } sb.append(arr[i]); } sb.append("]"); return sb.toString(); } } 

Deck.java

package lab7; import java.util.Random; import lab7.Card.Suit; /** * Class representing a standard 52-card deck of playing * cards from which cards can be selected at random. */ public class Deck { /** * The cards comprising this deck. */ private Card[] cards; /** * The random number generator to use for selecting cards. */ private Random rand; /** * Constructs a new deck with a default random number generator. */ public Deck() { rand = new Random(); init(); } /** * Constructs a new deck with the given random number generator. */ public Deck(Random givenGenerator) { rand = givenGenerator; init(); } /** * Returns a new array containing k elements selected * at random from this deck. */ public Card[] select(int k) { // TODO return null; } /** * Initializes a new deck of 52 cards. */ private void init() { cards = new Card[52]; int index = 0; for (int rank = 1; rank <= 13; ++rank) { cards[index] = new Card(rank, Suit.CLUBS); index += 1; cards[index] = new Card(rank, Suit.DIAMONDS); index += 1; cards[index] = new Card(rank, Suit.HEARTS); index += 1; cards[index] = new Card(rank, Suit.SPADES); index += 1; } } } 

ArrayExample.Java

package lab7; public class ArrayExample { public static void main(String[] args) { // Declares a variable whose type is "array of int" int[] arr; // Creates an array of four elements. All values are zero by default. arr = new int[4]; // Assign some values arr[0] = 17; arr[1] = 42; arr[2] = arr[1] - arr[0]; // Print out all four elements (note the fourth one is still zero) for (int i = 0; i < arr.length; i += 1) { System.out.println(arr[i]); } System.out.println(); } } 

ArrayExample3.java

package lab7; import java.util.Arrays; import java.util.Scanner; public class ArrayExample3 { public static void main(String[] args) { String s = "3 5 7 9 12"; int[] result = readNumbers(s); System.out.println(Arrays.toString(result)); } public static int[] readNumbers(String text) { Scanner scanner = new Scanner(text); int count = 0; while (scanner.hasNextInt()) { scanner.nextInt(); count +=1; } int[] nums = new int[count]; scanner = new Scanner(text); int index = 0; while (scanner.hasNextInt()) { int num = scanner.nextInt(); nums[index] = num; index += 1; } return nums; } } 

ArrayExample4.java

package lab7;

import java.util.Arrays; public class ArrayExample4 { public static void main(String[] args) { int[] test = {1, 2, 3, 4}; System.out.println("Before: " + Arrays.toString(test)); doubleAll(test); System.out.println("After: " + Arrays.toString(test)); } public static void doubleAll(int[] arr) { for (int i = 0; i < arr.length; i += 1) { arr[i] = arr[i] * 2; } } } 

ArrayExample5.java

package lab7; import java.util.Arrays; public class ArrayExample5 { public static void main(String[] args) { int[] test = {10, 20, 30, 40, 50}; System.out.println("Before: " + Arrays.toString(test)); swap(test, 1, 4); System.out.println("After: " + Arrays.toString(test)); } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } 

ReverseArray.java

package lab7; import java.util.Arrays; /** * Class containing some utilities for manipulating arrays. */ public class ReverseArray { public static void main(String[] args) { int[] test = {1, 2, 3, 4, 5, 6, 7, 8, 9}; System.out.println("Before: " + Arrays.toString(test)); reverse(test); System.out.println("After: " + Arrays.toString(test)); } /** * Reverses the contents of the given array. * @param arr */ public static void reverse(int[] arr) { int front = 0; int rear = arr.length - 1; while (front < rear) { swap(arr, front, rear); // move indices towards the center front += 1; rear -= 1; } } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } 

PokerHand.java

package lab7; /** * Creates a standard 5 card hand for poker, and identifies which type of hand * it is, e.g. straight, flush, or full-house. */ public class PokerHand { /** * The 5 cards comprising a hand. */ private Card[] cards; /** * Creates a hand using the 5 cards passed in. */ public PokerHand(Card[] cards) { this.setHand(cards); } /** * Sets the cards in the hand. * * @param cards * a 5 card array. If not 5 cards, a RuntimeException is thrown. */ public void setHand(Card[] cards) { if (cards.length == 5) { this.cards = cards; } else { throw new RuntimeException("Wrong number of cards. "); } } /** * Determines whether or not a hand is made up of cards from a single suit. * Should work with more than 4 suits, and any number of cards. * * @return true iff all the cards have the same suit */ public boolean isFlush() { sortWithSuit(); return cards[0].getSuit().equals(cards[cards.length - 1].getSuit()); } /** * Determines whether or not a hand is made up of consecutively increasing * ranks. E.g. 2, 3, 4, 5, 6. Should work with more than 4 suits, and any * number of cards. * * @return true iff we have a straight */ public boolean isStraight() { sortNoSuit(); // TODO Finish this method return false; } /** * Looks if we have a pair and a three of a kind in the hand. * * @return true iff we have a full house. */ public boolean isFullHouse() { sortNoSuit(); // TODO Finish this method return false; } /** * Sorts the cards by their suit and then their rank. */ private void sortWithSuit() { for (int i = 0; i < cards.length - 1; ++i) { // Step 1: find the "minimal" element to the right of position i int indexOfMin = findIndexOfMin(i); // Step 2: swap the minimal element into position i swap(i, indexOfMin); } } /** * Returns the index of the minimal element to the right of position 'start', * where cards are ordered first by suit, and within the same suit, by rank. * * @param start * first index at which to look * @return index of the smallest element to the right of 'start' */ private int findIndexOfMin(int start) { int indexOfMin = start; for (int j = start + 1; j < cards.length; ++j) { // look at the two cards, the minimal one we've found, // and the one at the current position j Card min = cards[indexOfMin]; Card current = cards[j]; // if current has a lower suit than the current min, then it should come // first if (current.getSuit().compareTo(min.getSuit()) < 0) { indexOfMin = j; } else if (current.getSuit().equals(min.getSuit())) { // suits are the same, so compare ranks if (current.getRank() < min.getRank()) { indexOfMin = j; } } // otherwise, current does not come before min, so ignore it } return indexOfMin; } /** * Sorts the cards according to their rank, ignoring their suits. */ private void sortNoSuit() { // TODO Finish this method. } /** * Swaps the cards i and j in the hand. * * @param i * the first card to swap * @param j * the card to swap with */ private void swap(int i, int j) { Card c = cards[i]; cards[i] = cards[j]; cards[j] = c; } /* * (non-Javadoc) * * @see java.lang.Object#toString() */ @Override public String toString() { if (isFullHouse()) { return "a Full House!"; } else if (isFlush()) { if (isStraight()) { return "a Straight Flush!"; } else { return "a Flush!"; } } else if (isStraight()) { return "a Straight!"; } return "Nothing"; } /** * Prints out the suit and rank of each card in the hand in order. */ public void printHand() { for (int i = 0; i < 5; i++) { System.out.print(cards[i].getSuit() + ":" + cards[i].getRank() + ", "); } System.out.println(); } } 

DeckTest2.java

package lab7; import java.util.Random; /** * Computes which random seeds create specific "good" hands for standard 5-card * poker. * */ public class DeckTest2 { public static void main(String[] args) { for (int i = 0; i < 6000; i++) { Random rand = new Random(i); Deck deck = new Deck(rand); // construct the deck using generator Card[] hand = deck.select(5); PokerHand poker = new PokerHand(hand); if (poker.toString() != "Nothing") { System.out.println("The key: " + i + ", is " + poker); poker.printHand(); } } } }