More Recursion

Double Recursion

Introduction

Recursion is a wonderful thing once you've mastered it. There are often problems in Computer Science that have simple, concise solutions once recursion is applied to the problem. One of the biggest problem for beginners occurs when they try to follow the recursive calls of a routine that makes two or more calls to itself. The problem becomes evident in what I term a double recursion. Once you understand how to trace the calls in this type of routine you will be able to apply the analysis to any number of calls.

What exactly is a double recursion? It's a method that calls itself twice. This is different from a method that chooses one type of recursive call over another. In this case every call to the method will spawn 2 more calls to the method. This then recurses down spawning 2 more calls until the test case is met and the method calls start to return back up the chain. The problem for the beginning student is that this type of arrangement maps out a 'tree' of calls and the student must perform a manual 'depth' first search of the call tree.

Trees

Trees are a data structure object that crop up in computer science and while it is not necessary to program one for the AP Computer Science exam a brief description of terminology for trees is useful to the discussion here. Students when trying to figure out a double recursion forget about what the computer is doing and bounce back and forth between a 'depth' first search of the method calls and what is know as a 'breadth' first search.

A diagram will explain this much better than words.

Depth First Search

In a depth search first you must follow the branches all the way down then go back up and follow any other branches etc. The numbering of the boxes shows how we visit the nodes. This is the same for recursion when 2 or more recursive calls are made. You must follow the first recursive trail and then back up and follow the next call in a similar fashion to this tree.

Breadth First Search

The mistake is to try to account for both calls at the same time when you enter the first call sequence. The computer doesn't do it this way it blindly follows the trail of the first call then when it comes back it handles the second. So breadth first search is a mistake of reading the program as you would a story. You complete the paragraph then go off to see what the next sequence is. The following diagram is the WRONG way to follow a recursion tree:

I almost don't want to show you this for fear you will worry about it. But rememeber you must follow the first call sequence down until the test case is reached. Then you pop back up at each stage to handle the second call. Forget about breadth first and stick to the order of the first diagram. Recursion is naturally a depth first search.

Make the computer do it

While you must learn to draw out the call structure by hand. There is no reason not to experiment with having the computer do it for you. With the appropriate use of output statements and a little bookkeeping in a program example we can make the computer account for how the recursion is happening. First let's create a single recursive method that logs it's calls then we can add a double recursion to the example. In the end you will have a program that maps out it's call tree in a textual representation. From there you only need to be able to draw a sketch on the test and you should be ready for any recursive problem thrown at you.

class DoubleRecurse {

    public static void singleRecursion(int[] vals, int m) {
        if (m >= 0) {
            System.out.print(vals[m] + "  ");
            singleRecursion(vals, m - 1);
        }
    }

    public static void main(String[] args) {
        int[] myArray = {5, 4, 3, 2, 1, 0};

        singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output

run:
0  1  2  3  4  5  
BUILD SUCCESSFUL (total time: 0 seconds)

So the code goes to the end of the array and prints each value. This reverses the order of the array. This is because the print happens before the recursive call back into singleRecursion. If the print statement is moved to after the method call the recursion goes all the way to m = -1 which ends the recursion then as the computer starts to come back up from it's decent into the recursion values will be printed in normal order indexed from 0 - 5 to print the values as they appear in the intialization of myArray.

Here is the class with the print statement moved after the recursive call:

class DoubleRecurse {

    public static void singleRecursion(int[] vals, int m) {
        if (m >= 0) {
            singleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
        }
    }

    public static void main(String[] args) {
        int[] myArray = {5, 4, 3, 2, 1, 0};

        singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 1

run:
5  4  3  2  1  0  
BUILD SUCCESSFUL (total time: 1 second)

Exposing Recursion

Let's add some print statements to expose the recursion more explicitly in the output. One way to display the recursion is to present the output from each call on a separate line. By using field variables we can also track the number of calls and the depth (or level) of the recursion. The depth field can be used to prepend spaces so that deeper levels of recursion are indented in the output.

The changes will include making this object oriented by taking away the static method and making it a plain method call to singleRecursion. This will mean that a DoubleRecurse object needs to be instantiated in the main method so the method can be used. But it means that the new fields will be available for any new recursive methods added to the class. The new code with the tracking fields and the new output statements follows:

class DoubleRecurse {
    // Track number of calls
    int calls = 0;
    // Track level
    int depth = 0;

    void indent(int spaces)
    {
        for (int i = 0; i < spaces; i++) {
            System.out.print("  ");
        }
    }

    public void singleRecursion(int[] vals, int m) {
        calls++;
        depth++;

        // track calls depth and m
        indent(depth);
        System.out.println("calls = " + calls 
                + "  depth = " + depth 
                + "  m = " + m);

        if (m >= 0) {
            singleRecursion(vals, m - 1);
            indent(depth);
            System.out.println(vals[m]);
        }
        else {
            indent(depth);
            System.out.println("test case met no more recursion start backing out");
        }

        depth --;
    }

    public static void main(String[] args) {
        DoubleRecurse recursion = new DoubleRecurse();
        int[] myArray = {5, 4, 3, 2, 1, 0};

        recursion.singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 2

run:
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

BUILD SUCCESSFUL (total time: 0 seconds)

Double Recursion

Now that there are tools to display the recursive calls, the program can be modified to track a doubly recursive call. Rather than change the singleRecursion method a new method called doubleRecursion can be added.

In the new code there are 4 method calls. The original singleRecursion method that does no tracking. A new method called singleRecursionTrack that has the tracking fields and output statements. Then the single recursion modified to do double recursion and it's tracking counterpart named doubleRecursion and doubleRecursionTrack respectively

class DoubleRecurse {
    // Track number of calls
    int calls = 0;
    // Track level
    int depth = 0;

    void indent(int spaces)
    {
        for (int i = 0; i < spaces; i++) {
            System.out.print("  ");
        }
    }

    public void singleRecursion(int[] vals, int m) {        
        if (m >= 0) {
            singleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
        }
    }

    public void singleRecursionTrack(int[] vals, int m) {
        this.calls++;
        this.depth++;

        // track calls depth and m
        indent(this.depth);
        System.out.println("calls = " + this.calls 
                + "  depth = " + this.depth 
                + "  m = " + m);

        if (m >= 0) {
            singleRecursionTrack(vals, m - 1);
            indent(this.depth);
            System.out.println(vals[m]);
        }
        else {
            indent(this.depth);
            System.out.println("test case met no more recursion start backing out");
        }

        this.depth--;
    }

    public void doubleRecursion(int[] vals, int m) {        
        if (m >= 0) {
            this.doubleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
            this.doubleRecursion(vals, m - 3);
        }
    }

    public void doubleRecursionTrack(int[] vals, int m) {
        this.calls++;
        this.depth++;

        // track calls depth and m
        indent(this.depth);
        System.out.println("calls = " + this.calls 
                + "  depth = " + this.depth 
                + "  m = " + m);

        if (m >= 0) {
            this.doubleRecursionTrack(vals, m - 1);
            indent(this.depth);
            System.out.println(vals[m]);
            this.doubleRecursionTrack(vals, m - 3);
        }
        else {
            indent(this.depth);
            System.out.println("test case met no more recursion start backing out");
        }

        this.depth --;
    }


    public static void main(String[] args) {
        DoubleRecurse recursion = new DoubleRecurse();
        int[] myArray = {5, 4, 3, 2, 1, 0};

        recursion.singleRecursion(myArray, myArray.length-1);
        System.out.println();
        recursion.singleRecursionTrack(myArray, myArray.length-1);
        System.out.println();
        recursion.calls = 0;  // start new recursion reset calls to track
        recursion.doubleRecursion(myArray, myArray.length-1);
        System.out.println();
        recursion.doubleRecursionTrack(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 3

run:
5  4  3  2  1  0  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

5  4  3  2  5  1  5  4  0  5  4  3  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
              calls = 8  depth = 7  m = -3
              test case met no more recursion start backing out
          4
            calls = 9  depth = 6  m = -2
            test case met no more recursion start backing out
        3
          calls = 10  depth = 5  m = -1
          test case met no more recursion start backing out
      2
        calls = 11  depth = 4  m = 0
          calls = 12  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 13  depth = 5  m = -3
          test case met no more recursion start backing out
    1
      calls = 14  depth = 3  m = 1
        calls = 15  depth = 4  m = 0
          calls = 16  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 17  depth = 5  m = -3
          test case met no more recursion start backing out
      4
        calls = 18  depth = 4  m = -2
        test case met no more recursion start backing out
  0
    calls = 19  depth = 2  m = 2
      calls = 20  depth = 3  m = 1
        calls = 21  depth = 4  m = 0
          calls = 22  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 23  depth = 5  m = -3
          test case met no more recursion start backing out
      4
        calls = 24  depth = 4  m = -2
        test case met no more recursion start backing out
    3
      calls = 25  depth = 3  m = -1
      test case met no more recursion start backing out

BUILD SUCCESSFUL (total time: 0 seconds)

This gives a good trail of when calls take place and at what level but it is still not completely obvious when the first recursive call is taking place and when the second is. By adding a field to the doubleRecursion the call number can be saved separately from the total calls. Adding 2 printlns before the calls (indenting for the current depth of course) now highlights exactly where the processing is being done.

public void doubleRecursionTrack(int[] vals, int m) {
    int current_call = 0;

    this.calls++;
    current_call = this.calls;
    this.depth++;

    // track calls depth and m
    indent(this.depth);
    System.out.println("calls = " + this.calls 
            + "  depth = " + this.depth 
            + "  m = " + m);

    if (m >= 0) {
        indent(this.depth);
        System.out.println("call = " + current_call + " enter first recursion");
        this.doubleRecursionTrack(vals, m - 1);
        indent(this.depth);
        System.out.println(vals[m]);
        indent(this.depth);
        System.out.println("call = " + current_call + " enter second recursion");
        this.doubleRecursionTrack(vals, m - 3);
    }
    else {
        indent(this.depth);
        System.out.println("test case met no more recursion start backing out");
    }

    this.depth --;
}

Output 3

run:
5  4  3  2  1  0  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

5  4  3  2  5  1  5  4  0  5  4  3  
  calls = 1  depth = 1  m = 5
  call = 1 enter first recursion
    calls = 2  depth = 2  m = 4
    call = 2 enter first recursion
      calls = 3  depth = 3  m = 3
      call = 3 enter first recursion
        calls = 4  depth = 4  m = 2
        call = 4 enter first recursion
          calls = 5  depth = 5  m = 1
          call = 5 enter first recursion
            calls = 6  depth = 6  m = 0
            call = 6 enter first recursion
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
            call = 6 enter second recursion
              calls = 8  depth = 7  m = -3
              test case met no more recursion start backing out
          4
          call = 5 enter second recursion
            calls = 9  depth = 6  m = -2
            test case met no more recursion start backing out
        3
        call = 4 enter second recursion
          calls = 10  depth = 5  m = -1
          test case met no more recursion start backing out
      2
      call = 3 enter second recursion
        calls = 11  depth = 4  m = 0
        call = 11 enter first recursion
          calls = 12  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 11 enter second recursion
          calls = 13  depth = 5  m = -3
          test case met no more recursion start backing out
    1
    call = 2 enter second recursion
      calls = 14  depth = 3  m = 1
      call = 14 enter first recursion
        calls = 15  depth = 4  m = 0
        call = 15 enter first recursion
          calls = 16  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 15 enter second recursion
          calls = 17  depth = 5  m = -3
          test case met no more recursion start backing out
      4
      call = 14 enter second recursion
        calls = 18  depth = 4  m = -2
        test case met no more recursion start backing out
  0
  call = 1 enter second recursion
    calls = 19  depth = 2  m = 2
    call = 19 enter first recursion
      calls = 20  depth = 3  m = 1
      call = 20 enter first recursion
        calls = 21  depth = 4  m = 0
        call = 21 enter first recursion
          calls = 22  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 21 enter second recursion
          calls = 23  depth = 5  m = -3
          test case met no more recursion start backing out
      4
      call = 20 enter second recursion
        calls = 24  depth = 4  m = -2
        test case met no more recursion start backing out
    3
    call = 19 enter second recursion
      calls = 25  depth = 3  m = -1
      test case met no more recursion start backing out

BUILD SUCCESSFUL (total time: 2 seconds)

Conclusion

This should help when trying to follow recursion. Certainly in an exam situation they don't allow an IDE to code with, but with some paper, pencil and a little fortitude even the average student should be able to build a recursion tree by hand. The AP question makers understand there is limited time so the example provided here is much more complex in terms of the number of calls a student will have to track.

A study recommendation
If you find yourself getting the recursion problems wrong in your practice tests, code them up with indentation and tracking information. Most likely you are making a simple mistake drawing out the call tree. The output from your code should enlighten you on the proper call pattern.

Date: 2013-03-26T16:55-0400

Author: Nasty Old Dog

AP Comp Sci Sorting Algorithms

Sorting

Introduction

The AP Computer Science test expects you to know 3 sorting methods.

• Selection sort
• Insertion sort
• Merge sort

The blackjack program I have put together needs sorting too. When a hand is scored in Blackjack Aces can be either 1 or 11 in favor of the highest hand you can make without going over 21. By sorting the hands with Aces last the hand can be scored quite easily. So this seemed to be good time to go over sorting.

The Selection sort and Insertion sort are quite easy to implement. Why not start with the easiest part first? To keep it simpler still only int arrays will be used for sorting.

Selection Sort

In selection sort you visit each element of the array up to the second to last element. At each step you look through the array from i to the end, find the smallest value and swap it for the ith element. The pseudo-code should clarify:

int sortArray[] = {4,5,9,6,1,0,3,8,7,2};
int tmp, tmp_idx;

for (int i=0; i < sortArray.length - 1; i++)
{
  tmp = sortArray[i];
  tmp_idx = i;
  for (int j = i + 1; j < sortArray.length; j++) 
  {
    if (sortArray[j] < tmp) {
      tmp = sortArray[j];
      tmp_idx = j;
    }
  }
  // swap the values if the i-th was the smallest this swap doesn't do anything
  // you could test for that if you wanted (which is the way it's done in 
  // the final code)
  sortArray[tmp_idx] = sortArray[i];
  sortArray[i] = tmp;
}

Insertion Sort

Start at the second element and visit the rest of the list. Check the elements before the ith position and see if it is less than any previous elements. If not it stays where it is and move on. This has the appearance of removing the number shifting the elements before it to create a space and placing the number where it belongs.

In the actual implementation you visit each previous element starting at the element immediately to the left and do compare-swaps until one of 2 conditions apply either the number is now at the begining of the list or the element to the immediate left is less. This method accomplishes the shifting of the elements and the comparisons in a way more neatly suited for looping. Again, pseudo-code should help your understanding.

int sortArray[] = {4,5,9,6,1,0,3,8,7,2};
int tmp, tmp_idx;
int j;

for (int i = 1; i < sortArray.length; i++)
{
  for (j = i; j > 0 && sortArray[j] < sortArray[j - 1]; j--)
  {
     // swap
     tmp = sortArray[j];
     sortArray[j] = sortArray[j - 1];
     sortArray[j - 1] = tmp;
  }
}

Create a Sort Lab

To experiment with these I have created a SortLab class. I have borrowed the shuffle method (from the blackjack program) and reworked it for use in the SortLab class. I did this the old fashioned way by cutting and pasting and then changing the names to fit the names of the SortLab fields. The constructors allow you to default to an int array of size 10 or to experiment with other sizes. The arrays are intialized with positive whole numbers. Then they are shuffled to use for sorting. A display method is implemented to print out the values in the array. There is also a swap method to switch values. The selection sort is implemented in 2 different ways. One with an inline swap and a check if a swap is necessary (the first element could have been the lowest of all remaining elements). The other using the swap method with no check.

public class SortLab {

    int[] labArray = null;
    int len = 10;

    public SortLab(int n) {
        this.len = n;
        labArray = new int[this.len];
        for (int i = 0; i < this.len; i++) {
            labArray[i] = i;
        }
        this.shuffle();
    }

    public SortLab() {
        this(10);
    }

    // This shuffle routine adapted from the work done previously
    private void shuffle() {
        int rindex;
        int swap;

        for (int i = 0; i < this.len; i++) {
            rindex = (int) ((Math.random() * ((double) (this.len - i))) + i);
            swap = this.labArray[i];
            this.labArray[i] = this.labArray[rindex];
            this.labArray[rindex] = swap;
        }
    }

    void swap(int k, int l) {
        int tmp;

        tmp = this.labArray[k];
        this.labArray[k] = this.labArray[l];
        this.labArray[l] = tmp;
    }

    public void display() {
        for (int i = 0; i < this.len; i++) {
            System.out.print(this.labArray[i] + "  ");
        }
        System.out.println();
    }

    public void selection() {
        int tmp, tmp_idx;

        for (int i = 0; i < this.len - 1; i++) {
            //select the ith element save value and index
            tmp = this.labArray[i];
            tmp_idx = i;
            // Check if selected is the lowest of the remaining array
            // if not switch them
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    // found something less save it and it's index
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            // if tmp_idx != i then swap the values (move the lowest val in)
            if (tmp_idx != i) {
                this.labArray[tmp_idx] = this.labArray[i];
                this.labArray[i] = tmp;
            }
        }
    }

    // Alternate implementation of selection sort using swap function 
    public void selectionA() {
        int tmp, tmp_idx;
        for (int i = 0; i < this.len - 1; i++) {
            tmp = this.labArray[i];
            tmp_idx = i;
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            swap(i, tmp_idx);
        }
    }

    public void insertion() {
        int j;

        for (int i = 1; i < this.len; i++) {
            for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
                this.swap(j, j - 1);
            }
        }
    }

    public static void main(String[] args) {
        SortLab select = new SortLab();
        SortLab selectA = new SortLab();
        SortLab insert = new SortLab();

        System.out.println("Selection Sort");
        System.out.print("unsorted: ");
        select.display();
        select.selection();
        System.out.print("sorted:   ");
        select.display();
        System.out.println("SelectionA Sort");
        System.out.print("unsorted: ");
        selectA.display();
        selectA.selectionA();
        System.out.print("sorted:   ");
        selectA.display();
        System.out.println();
        System.out.println();
        System.out.println("Insertion Sort");
        System.out.print("unsorted: ");
        insert.display();
        insert.insertion();
        System.out.print("sorted:   ");
        insert.display();
    }
}

Output 1

run:
Selection Sort
unsorted: 4  7  2  6  1  5  3  9  8  0  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 1  3  9  6  8  7  5  4  2  0  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 4  5  9  6  1  0  3  8  7  2  
sorted:   0  1  2  3  4  5  6  7  8  9  
BUILD SUCCESSFUL (total time: 0 seconds)

AP Exam

One way they may ask you about these sorts is to show you interim passes on the list and ask you what type of sort is being done. With a few simple additions our SortLab class can print out interim results to show you how this would look. By placing print statement at the end of the outer loop you can get a print out that shows you the developing sorted lists.

Look at the bottom of the outer loop in each of the 3 sort implementations. I have also added a fourth routine that implements insertion sort with an explicit shift of elements. Some practice exams implement insertion sort in this fashion. Take a look at the output trail it's operation is no different than the first insertion sort. But it uses an extra inner loop.

 public void selection() {
     int tmp, tmp_idx;

     for (int i = 0; i < this.len - 1; i++) {
         //select the ith element save value and index
         tmp = this.labArray[i];
         tmp_idx = i;
         // Check if selected is the lowest of the remaining array
         // if not switch them
         for (int j = i + 1; j < this.len; j++) {
             if (this.labArray[j] < tmp) {
                 // found something less save it and it's index
                 tmp = this.labArray[j];
                 tmp_idx = j;
             }
         }
         // if tmp_idx != i then swap the values (move the lowest val in)
         if (tmp_idx != i) {
             this.labArray[tmp_idx] = this.labArray[i];
             this.labArray[i] = tmp;
         }
         System.out.print("interim:  ");
         this.display();
     }
 }

 // Alternate implementation of selection sort using swap function 
 public void selectionA() {
     int tmp, tmp_idx;
     for (int i = 0; i < this.len - 1; i++) {
         tmp = this.labArray[i];
         tmp_idx = i;
         for (int j = i + 1; j < this.len; j++) {
             if (this.labArray[j] < tmp) {
                 tmp = this.labArray[j];
                 tmp_idx = j;
             }
         }
         swap(i, tmp_idx);
         System.out.print("interim:  ");
         this.display();
     }
 }

 public void insertion() {
     int j;

     for (int i = 1; i < this.len; i++) {
         for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
             this.swap(j, j - 1);
         }
         System.out.print("interim:  ");
         this.display();
     }
 }

 public void insertionShift()
 {
     int j;
     int tmp;

     for (int i = 1; i < this.len; i++) {
         // take ith element find where it should be inserted
         tmp = this.labArray[i];
         for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
             // no need to do anything
             // when the loop ends j will be the insertion position
         }
         // Shift elements from j to i-1 over 1
         for (int k = i - 1; k >= j; k--)
         {
             this.labArray[k + 1] = this.labArray[k];
         }
         this.labArray[j] = tmp;
         System.out.print("interim:  ");
         this.display();
     }
 }

 public static void main(String[] args) {
     SortLab select = new SortLab();
     SortLab selectA = new SortLab();
     SortLab insert = new SortLab();
     SortLab insertA = new SortLab();

     System.out.println("Selection Sort");
     System.out.print("unsorted: ");
     select.display();
     select.selection();
     System.out.print("sorted:   ");
     select.display();
     System.out.println("SelectionA Sort");
     System.out.print("unsorted: ");
     selectA.display();
     selectA.selectionA();
     System.out.print("sorted:   ");
     selectA.display();
     System.out.println();
     System.out.println();
     System.out.println("Insertion Sort");
     System.out.print("unsorted: ");
     insert.display();
     insert.insertion();
     System.out.print("sorted:   ");
     insert.display();
     System.out.println("Insertion Sort with Explicit Shift");
     System.out.print("unsorted: ");
     insertA.display();
     insertA.insertion();
     System.out.print("sorted:   ");
     insertA.display();
}

Output 2

run:
Selection Sort
unsorted: 9  6  2  1  3  7  8  4  0  5  
interim:  0  6  2  1  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  3  6  7  8  4  9  5  
interim:  0  1  2  3  4  7  8  6  9  5  
interim:  0  1  2  3  4  5  8  6  9  7  
interim:  0  1  2  3  4  5  6  8  9  7  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 9  0  5  7  2  8  4  3  1  6  
interim:  0  9  5  7  2  8  4  3  1  6  
interim:  0  1  5  7  2  8  4  3  9  6  
interim:  0  1  2  7  5  8  4  3  9  6  
interim:  0  1  2  3  5  8  4  7  9  6  
interim:  0  1  2  3  4  8  5  7  9  6  
interim:  0  1  2  3  4  5  8  7  9  6  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 3  0  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Insertion Sort with Explicit Shift
unsorted: 1  9  3  8  5  7  6  4  0  2  
interim:  1  9  3  8  5  7  6  4  0  2  
interim:  1  3  9  8  5  7  6  4  0  2  
interim:  1  3  8  9  5  7  6  4  0  2  
interim:  1  3  5  8  9  7  6  4  0  2  
interim:  1  3  5  7  8  9  6  4  0  2  
interim:  1  3  5  6  7  8  9  4  0  2  
interim:  1  3  4  5  6  7  8  9  0  2  
interim:  0  1  3  4  5  6  7  8  9  2  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9    
BUILD SUCCESSFUL (total time: 1 second)

Conclusion

That's 2 of the 3 sorts you need to know about. Questions on the AP may show code and of course try to hide what is really going on. If there is an inner loop shifting multiple elements then placing the value in after the shift think insertion sort. The insertion sort above combines the compare and the shift together but the effect is the same. Selection sorts you should see a single swap of 2 values then back out to the main loop. I like to think of it as "select the lowest value and swap it to the current front of the line".

Merge Sort should be next but its implementation is simplified by recursion. So before we go into Merge Sort I want to revisit recursion in my next blog post. Then tackle merge sort. Then I will get back to finishing up blackjack.

You should also visit wikipedia they have some nice animations of how these sorts work.

References

1. Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Reading, MA: Addison-Wesley, 1983.
2. "Selection Sort." Wikipedia. Wikimedia Foundation, 25 Mar. 2013. Web. 26 Mar. 2013. http://en.wikipedia.org/wiki/Selection_sort
3. "Insertion Sort." Wikipedia. Wikimedia Foundation, 22 Mar. 2013. Web. 26 Mar. 2013. http://en.wikipedia.org/wiki/Insertion_sort
4. Litvin, Maria, and Gary Litvin. Be Prepared for the AP Computer Science Exam in Java. Andover: Skylight, 2009.

Date: 2013-03-28T17:58-0400

Author: Nasty Old Dog

Blackjack Almost a Real Game

AP Computer Science Adding Some User Input/Output

Introduction

When we last left our Blackjack program we had put in place a model for dealing with a deck of cards, Shuffling the deck and a way to distinguish 'hands' for dealer and player. Now let's scaffold in some user I/O (input/output). Sounds impressive but it's just a series of prints, printlns and getLines. To be able to repeat the process for multiple games (or hands) there will need to be a loop of some sort (keyword repeat at the beginning of the sentence is the give away for a loop).

I am trying to plow through this program for you so you have a fairly large project to look at. Since the target audience for these AP Computer Science Blogs are beginning programmers I am trying to get you to see the utility of what you have learned so far. I hope that your experience with computer science has been positive. It's really not that difficult a subject and for the thoughtful student provides a virtual world where almost anything is possible. The field is really limitless and is bound only by your imagination and time.

For those of you who have been turned off by the experience of taking AP Computer Science and feel you were crazy to think this was interesting, don't let this experience jade you. AP Computer Science is a one size fits all type of course with restrictions on what should do. It may be that your imagination finds the restrictions too limiting and burdensome. At the university level you will find Professors that love Computer Science so much they have chosen to specialize in the subject. I would give it another chance at the university level. You may find that the right instructor with a broad base of experience was all you needed to get your mind around the subject.

When you do take college courses remember you have at your disposal the Professor of the course and his or her teaching assistants. That means you have multiple people with exellent experience to help you master the subject. In High School AP there is the teacher alone, if you don't connect with their perspective you are out of luck. In college you will have professors, teaching assistants, and fellow students each with a different perspective. You should be able to find someone that can connect with you to help you master this subject.

The game loop pseudocode

The design process here is:

• guess at the calls
• get the structure of the code in place
• then cut and paste into the IDE and see what the real calls are supposed to be

The Pseudo Code

Pay attention to the comments below they help in understanding what is going on

CardDeck card = new CardDeck();

String user_inp = new String("");
int bankroll = 1000;
int bet = 0;           // if the user bets 0 quit the game loop

// game loop just loop forever
while(true) {
  // Tell the user the amount of the bank roll 
  System.out.println("Bankroll = " + bankroll);
  // get bet
  System.out.print("Enter the amount you want to bet: ");
  user_inp = System.in.getLine();
  bet = Integer.toInt(user_inp);

  // bet == 0 is the signal to quit loop and end program
  if (bet == 0) { 
    break;
  }

  card.shuffle();

  card.dealPlayer();
  card.dealDealer();
  card.dealPlayer();
  card.dealDealer();

  card.displayHands();

  // Need a loop to handle HIT or STAND commands
  while(true) { 
    System.out.print("Player Hand hit or stand? ");
    user_inp = System.in.getLine();
    if (user_inp.equals("HIT")) {
      card.dealPlayer();
      card.displayHands();
    }
    else if (user_inp.equals("STAND")) {
      break;
    }
    else {
      // If we end up here it's because of a typo or wiseguy
      // print error response and go back to looping
      System.out.println("I don't understand: " + user_inp);
    }
  }

  // Manually control dealer hand the same way
  // We will swap this out for code that will run the dealer rules 
  // automatically
  while(true) { 
    System.out.print("Dealer Hand hit or stand? ");
    user_inp = System.in.getLine();
    if (user_inp.equals("HIT")) {
      card.dealDealer();
      card.displayHands();
    }
    else if (user_inp.equals("STAND")) {
      break;
    }
    else {
      // If we end up here it's because of a typo or wiseguy
      // print error response and go back to looping
      System.out.println("I don't understand: " + user_inp);
    }
  }

  // Code to score the game and settle the bet will go here

}

Pseudo code to real code

• I need to use the Scanner class to get user input there is no System.in.getLine
  • I defined uinp to be a scanner for System.in
  • I replaced the System.in.getLine's with uinp.nextLine()
• The String user_inp doesn't need a constructor just " "
• There is no toInt in the Integer class use getInteger instead

import java.util.Scanner;

public class CardDeck {

    int deck[] = new int[52];
    String faceVal = "A23456789TJQK";
    String suit = "HDSC";

    public CardDeck() {
        for (int i = 0; i < 52; i++) {
            deck[i] = i;
        }
    }

    void shuffle() {
        int rindex;
        int swap;

        for (int i = 0; i < 52; i++) {
            // each time through the loop there are less numbers to randomize
            // 52 - i to be exact. But then everything from 0 to i-1 has already
            // been selected at random so add i to the random number to get the
            // appropriate index
            rindex = (int) ((Math.random() * ((double) (52 - i))) + i);
            swap = deck[i];
            deck[i] = deck[rindex];
            deck[rindex] = swap;
        }
    }

    public String getCardText(int crd) {
        int card_val = crd % 13;
        int card_suit = crd % 4;
        return this.faceVal.substring(card_val, card_val + 1)
                + this.suit.substring(card_suit, card_suit + 1);
        //return this.faceVal.substring(card_val, card_val+1).concat(
        //this.suit.substring(card_suit, card_suit+1));
    }

    void display() {
        int card_val;
        int card_suit;
        for (int i = 0; i < 52; i++) {
            //card_val = deck[i]%13;
            //card_suit = deck[i]%4;
            System.out.print(this.getCardText(deck[i]) + " ");
        }
        System.out.println();
    }
    int playerHand[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int dealerHand[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int dcards = 0; // the number of cards in the dealer hand so far
    int pcards = 0; // the number of cards in the player hand so far
    int deckidx = 0; // the location of the next card to be dealt

    public int deal() {
        if (this.deckidx < 52) {
            return this.deck[this.deckidx++]; // return the top card and increment to the next card
        } else {
            return this.deck[this.deckidx - 1];
        }
    }

    public void dealPlayer() {
        this.playerHand[pcards] = deal();
        this.pcards++;
    }

    public void dealDealer() {
        this.dealerHand[dcards] = deal();
        this.dcards++;
    }

    public void displayHands() {
        System.out.println("Player Hand  ");
        for (int i = 0; i < this.pcards; i++) {
            System.out.print(this.getCardText(this.playerHand[i]) + " ");
        }
        System.out.println();
        System.out.println("Dealer Hand:  ");
        for (int j = 0; j < this.dcards; j++) {
            System.out.print(this.getCardText(this.dealerHand[j]) + " ");
        }
        System.out.println();
        System.out.println();
    }

    public static void main(String[] args) {
        CardDeck card = new CardDeck();

        card.display();
        card.shuffle();
        card.display();

        card.dealPlayer();
        card.dealDealer();
        card.dealPlayer();
        card.dealDealer();

        card.displayHands();
        // Start game intialize bankroll to 500
        // Start game loop <CR> on bet means quit
        // CardDeck card = new CardDeck();

        String user_inp = " ";
        int bankroll = 1000;
        int bet = 0;           // if the user bets 0 quit the game loop

        // Need a Scanner for user input
        Scanner uinp = new Scanner(System.in);

        // game loop just loop forever
        while (true) {
            // Tell the user the amount of the bank roll 
            System.out.println("Bankroll = " + bankroll);
            // get bet
            System.out.print("Enter the amount you want to bet: ");
            user_inp = uinp.nextLine();
            bet = Integer.getInteger(user_inp);

            // bet == 0 is the signal to quit loop and end program
            if (bet == 0) {
                break;
            }

            card.shuffle();

            card.dealPlayer();
            card.dealDealer();
            card.dealPlayer();
            card.dealDealer();

            card.displayHands();

            // Need a loop to handle HIT or STAND commands
            while (true) {
                System.out.print("Player Hand hit or stand? ");
                user_inp = uinp.nextLine();
                if (user_inp.equals("HIT")) {
                    card.dealPlayer();
                    card.displayHands();
                } else if (user_inp.equals("STAND")) {
                    break;
                } else {
                    // If we end up here it's because of a typo or wiseguy
                    // print error response and go back to looping
                    System.out.println("I don't understand: " + user_inp);
                }
            }

            // Manually control dealer hand the same way
            // We will swap this out for code that will run the dealer rules 
            // automatically
            while (true) {
                System.out.print("Dealer Hand hit or stand? ");
                user_inp = uinp.nextLine();
                if (user_inp.equals("HIT")) {
                    card.dealDealer();
                    card.displayHands();
                } else if (user_inp.equals("STAND")) {
                    break;
                } else {
                    // If we end up here it's because of a typo or wiseguy
                    // print error response and go back to looping
                    System.out.println("I don't understand: " + user_inp);
                }
            }

            // Code to score the game and settle the bet will go here

        }
    }
}

Output

run:
AH 2D 3S 4C 5H 6D 7S 8C 9H TD JS QC KH AD 2S 3C 4H 5D 6S 7C 8H 9D TS JC QH KD AS 2C 3H 4D 5S 6C 7H 8D 9S TC JH QD KS AC 2H 3D 4S 5C 6H 7D 8S 9C TH JD QS KC 
5S AS 9C 4H QS 8D 7H 7D AC JH 9D TS KD QD 2H 6S 4S KC 2C 7C QC 6D 3H 3S 5C QH 6H KS 8C 4C 2D 5D KH TD 9H JC 8H 4D 5H 2S JS 7S 6C 8S TH JD 3D TC AH 3C AD 9S 
Player Hand  
5S 9C 
Dealer Hand:  
AS 4H 

Bankroll = 1000
Enter the amount you want to bet: 10
Exception in thread "main" java.lang.NullPointerException
        at apcompsci.CardDeck.main(CardDeck.java:129)
Java Result: 1
BUILD SUCCESSFUL (total time: 19 seconds)

Debugging

If you use the program above 129 is not the right line number I have extra comments produced in the IDE that I don't cut and paste. So the problem is at the bet = Integer.getInteger line. It seems that our user input is not working so well. I'm not sure what is wrong here. Stepping through the code in the debugger shows the 'user_inp' variable gets assigned "10", I am probably using the Integer class incorrectly. Let's take a different tact.

For AP purposes you can use the Scanner class routines (nextInt). That seems to work so I changed the following:

//            user_inp = uinp.nextLine();
//            bet = Integer.getInteger(user_inp).intValue();
            bet = uinp.nextInt();

Output 2

run:
AH 2D 3S 4C 5H 6D 7S 8C 9H TD JS QC KH AD 2S 3C 4H 5D 6S 7C 8H 9D TS JC QH KD AS 2C 3H 4D 5S 6C 7H 8D 9S TC JH QD KS AC 2H 3D 4S 5C 6H 7D 8S 9C TH JD QS KC 
7S 6H 2C 4S 2S 4D TH 5H QH AH 7H TD 3C JC 4C AC KH KD TC 9H 6C 5S 2H 3H 2D QC 3D KC JS 6S 8C 8S 9D TS QD 7D KS 8H 5C AD JD 7C 4H 9C 6D 3S QS 5D JH AS 9S 8D 
Player Hand  
7S 2C 
Dealer Hand:  
6H 4S 

Bankroll = 1000
Enter the amount you want to bet: 10
Player Hand  
7S 2C 6D AD 
Dealer Hand:  
6H 4S JD 9D 

Player Hand hit or stand? I don't understand: 
Player Hand hit or stand? HIT
Player Hand  
7S 2C 6D AD JH 
Dealer Hand:  
6H 4S JD 9D 

Player Hand hit or stand? STAND
Dealer Hand hit or stand? HIT
Player Hand  
7S 2C 6D AD JH 
Dealer Hand:  
6H 4S JD 9D 5S 

Dealer Hand hit or stand? STAND
Bankroll = 1000
Enter the amount you want to bet: 0
BUILD SUCCESSFUL (total time: 34 seconds)

There is one major problem I left the old code from the previous blog in as a debugging aid. That's why there are four (4) cards instead of two (2) when we play the game. I need to reset the hands to no cards before we start the game.

It also looks like the CR after I input the bet gets registered as input. I will leave this error alone since it is a minor annoyance and tests the input error portion of the code (I will try to fix it in a later post).

Let's create a resetHands method. It will set all the cards in the hands to 0 and reset the card indexes for each hand. Let's place it in the code so it fixes the above problem. Let's also assume we win every hand and modify the bankroll accordingly.

public void resetHands()
{
  for (int i = 0; i < playerHand.length; i++) {
    playerHand[i] = 0;
    dealerHand[i] = 0;
  }
  dcards = 0;
  pcards = 0;
}

// Now after the first displayHands add this method call before we start:
        // Reset hands
        card.resetHands();

        // CardDeck card = new CardDeck();

        String user_inp = " ";

// Then at the end of the main loop lets add the following code:
            // Code to score the game and settle the bet will go here
            // For now assume we win every time
            bankroll = bankroll + bet;

            // reset hands to play a new game
            card.resetHands();

Output 3

run:
AH 2D 3S 4C 5H 6D 7S 8C 9H TD JS QC KH AD 2S 3C 4H 5D 6S 7C 8H 9D TS JC QH KD AS 2C 3H 4D 5S 6C 7H 8D 9S TC JH QD KS AC 2H 3D 4S 5C 6H 7D 8S 9C TH JD QS KC 
3S 2S QD 8H QC 5D AH TC 7C TD 9D 5S QH 4H JH KD 6C 2D 6H QS 6S JC TH 9S 4S 3H 2H AD KH KS 3C AS KC 5H 9C 7H AC JD 6D 4C 8D 9H 8S JS 2C 7S TS 5C 8C 7D 4D 3D 
Player Hand  
3S QD 
Dealer Hand:  
2S 8H 

Bankroll = 1000
Enter the amount you want to bet: 10
Player Hand  
5C 8S 
Dealer Hand:  
8D 4C 

Player Hand hit or stand? I don't understand: 
Player Hand hit or stand? HIT
Player Hand  
5C 8S 6C 
Dealer Hand:  
8D 4C 

Player Hand hit or stand? STAND
Dealer Hand hit or stand? HIT
Player Hand  
5C 8S 6C 
Dealer Hand:  
8D 4C TC 

Dealer Hand hit or stand? STAND
Bankroll = 1010
Enter the amount you want to bet: 0
BUILD SUCCESSFUL (total time: 40 seconds)

Not bad we actually won the hand for real (your results may vary). Under the rules of Blackjack the dealer had to HIT the 8,4 (12 points) since it's 16 or less. But even if we had lost we increase the bankroll anyway for now.

Conclusion

So this isn't quite polished. The program needs to score each hand after a deal and it must step through the dealer rules. It should also hide one card of the dealer until the player 'STANDS'. But the user can now step through some games and do the calculations themselves to see if it would be a winning or losing game. Don't worry we will massage this into a useable program.

To be continued.

Final Code

import java.util.Scanner;

public class CardDeck {

    int deck[] = new int[52];
    String faceVal = "A23456789TJQK";
    String suit = "HDSC";

    public CardDeck() {
        for (int i = 0; i < 52; i++) {
            deck[i] = i;
        }
    }

    void shuffle() {
        int rindex;
        int swap;

        for (int i = 0; i < 52; i++) {
            // each time through the loop there are less numbers to randomize
            // 52 - i to be exact. But then everything from 0 to i-1 has already
            // been selected at random so add i to the random number to get the
            // appropriate index
            rindex = (int) ((Math.random() * ((double) (52 - i))) + i);
            swap = deck[i];
            deck[i] = deck[rindex];
            deck[rindex] = swap;
        }
    }

    public String getCardText(int crd) {
        int card_val = crd % 13;
        int card_suit = crd % 4;
        return this.faceVal.substring(card_val, card_val + 1)
                + this.suit.substring(card_suit, card_suit + 1);
        //return this.faceVal.substring(card_val, card_val+1).concat(
        //this.suit.substring(card_suit, card_suit+1));
    }

    void display() {
        int card_val;
        int card_suit;
        for (int i = 0; i < 52; i++) {
            //card_val = deck[i]%13;
            //card_suit = deck[i]%4;
            System.out.print(this.getCardText(deck[i]) + " ");
        }
        System.out.println();
    }
    int playerHand[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int dealerHand[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int dcards = 0; // the number of cards in the dealer hand so far
    int pcards = 0; // the number of cards in the player hand so far
    int deckidx = 0; // the location of the next card to be dealt

    public int deal() {
        if (this.deckidx < 52) {
            return this.deck[this.deckidx++]; // return the top card and increment to the next card
        } else {
            return this.deck[this.deckidx - 1];
        }
    }

    public void dealPlayer() {
        this.playerHand[pcards] = deal();
        this.pcards++;
    }

    public void dealDealer() {
        this.dealerHand[dcards] = deal();
        this.dcards++;
    }

    public void resetHands() {
        for (int i = 0; i < playerHand.length; i++) {
            playerHand[i] = 0;
            dealerHand[i] = 0;
        }
        dcards = 0;
        pcards = 0;
    }

    public void displayHands() {
        System.out.println("Player Hand  ");
        for (int i = 0; i < this.pcards; i++) {
            System.out.print(this.getCardText(this.playerHand[i]) + " ");
        }
        System.out.println();
        System.out.println("Dealer Hand:  ");
        for (int j = 0; j < this.dcards; j++) {
            System.out.print(this.getCardText(this.dealerHand[j]) + " ");
        }
        System.out.println();
        System.out.println();
    }

    public static void main(String[] args) {
        CardDeck card = new CardDeck();

        card.display();
        card.shuffle();
        card.display();

        card.dealPlayer();
        card.dealDealer();
        card.dealPlayer();
        card.dealDealer();

        card.displayHands();
        // Reset hands
        card.resetHands();

        // CardDeck card = new CardDeck();

        String user_inp = " ";
        int bankroll = 1000;
        int bet = 0;           // if the user bets 0 quit the game loop

        // Need a Scanner for user input
        Scanner uinp = new Scanner(System.in);

        // game loop just loop forever
        while (true) {
            // Tell the user the amount of the bank roll 
            System.out.println("Bankroll = " + bankroll);
            // get bet
            System.out.print("Enter the amount you want to bet: ");
//            user_inp = uinp.nextLine();
//            bet = Integer.getInteger(user_inp).intValue();
            bet = uinp.nextInt();
            // bet == 0 is the signal to quit loop and end program
            if (bet == 0) {
                break;
            }

            card.shuffle();

            card.dealPlayer();
            card.dealDealer();
            card.dealPlayer();
            card.dealDealer();

            card.displayHands();

            // Need a loop to handle HIT or STAND commands
            while (true) {
                System.out.print("Player Hand hit or stand? ");
                user_inp = uinp.nextLine();
                if (user_inp.equals("HIT")) {
                    card.dealPlayer();
                    card.displayHands();
                } else if (user_inp.equals("STAND")) {
                    break;
                } else {
                    // If we end up here it's because of a typo or wiseguy
                    // print error response and go back to looping
                    System.out.println("I don't understand: " + user_inp);
                }
            }

            // Manually control dealer hand the same way
            // We will swap this out for code that will run the dealer rules 
            // automatically
            while (true) {
                System.out.print("Dealer Hand hit or stand? ");
                user_inp = uinp.nextLine();
                if (user_inp.equals("HIT")) {
                    card.dealDealer();
                    card.displayHands();
                } else if (user_inp.equals("STAND")) {
                    break;
                } else {
                    // If we end up here it's because of a typo or wiseguy
                    // print error response and go back to looping
                    System.out.println("I don't understand: " + user_inp);
                }
            }

            // Code to score the game and settle the bet will go here
            // For now assume we win every time
            bankroll = bankroll + bet;

            // reset hands to play a new game
            card.resetHands();
        }
    }
}

Author: Nasty Old Dog