Blackjack (adding more features)

AP Computer Science Blackjack Continued

Representing Dealer and Player Hands

Last time we created a CardDeck class to simulate a deck of cards. Now we need a way to deal those cards and store them in 'hands' for a player and a dealer.

• Use arrays for the dealer and player hands
• put the arrays in CardDeck class.
• create 'dealPlayer' and 'dealDealer' methods to store cards in the arrays associated with each hand
• Use int variables to track the indexs of the hands and the deck
  • increment the index after each deal so we get the next card from the deck
  • increment the index for the appropriate hand
• create a method to display the hands with only one card turned over on the dealer
• create a method to display all the hands so that a winner can be determined by the user for now
• Hold off on creating a hand scoring mechanism

int playerHand[20];
int dealerHand[20];
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 (deckidx < 52) {
    return deck[deckidx++]; // return the top card and increment to the next card
  }
  else {
    return deck[deckidx-1];
  }
}

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

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

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

Bugs

I have a ',' in the print statement in the 'displayHands' routine. I have forgotten my style requirements that I use 'this' prepended to all field usage. I need to initialize the arrays for hand.

Fixed code with usage in 'main' method

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.playerHand[i]+" ");
  }
  System.out.println();
  System.out.println("Dealer Hand:  ");
  for (int j = 0; j < this.dcards; j++) {
    System.out.print(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();
    }

Make a card convert routine

The above example does not display the text based card. It would be nice to have a method that converts the integer representation into the text based representation. This can then be used in both the hand display method and the deck display method. Good design too use the same underlying method in both places means less chance for error. If there is an error found localizing it to one method means it's fixed everywhere when the bug is fixed in the conversion method. Call the method 'getCardText' and the method can just return a String (right? makes sense, it's just going to be a couple of characters). Let's modify the deck display routine (i.e. the 'display' method) to make use of this conversion routine as well (don't forget I use method, routine, and function interchangeably I hope it's not too confusing).

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);    // Why does this work??
}

Digression on the String Class

I flagged the return statement with a comment. Do you the reader understand why that code actually works? There is really a great deal of Java compiler magic happening in that one statement. It's the same magic that happens implicitly in a System.out.print method call. 'faceVal' and 'suit' are 'String' fields in the CardDeck class. 'substring' is a method in the 'String' class that returns a 'String' class (or object if you prefer). The 2 calls to substring (one for 'faceVal' and the other for 'suit') will get done first. Then the compiler will be faced with what to do with 'String' + 'String'. It turns out that the '+' operator has built in meaning when dealing with Strings. It will concatenate the 2 strings together (which essential glues them together) to form a new String. It would be the same as if we used the 'concat' method of the 'String' class:

return this.faceVal.substring(card_val,card_val+1).concat(this.suit.substring(card_suit,card_suit+1));

Either return statement works. I prefer the '+' operator because it gives me a natural split to place the long method calls on separate lines.

Back to the final code

So now fixing up all the routines the code is now:

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);
}

    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();
    }
}

Output

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

Conclusion

Not bad. The class can shuffle, deal hands, and display hands. In the next installment let's work on the 'main' method to accept a bankroll and bets. Have it accept input to HIT or STAND on the player hand. The dealer can just take 1 card for now as it's hand playing rule. Hopefully we can simulate a game

Author: Nasty Old Dog

Modulo Part II

AP Computer Science Modulo Part II

Fun with Modulo

Back to uses of modulo. Rather than expound on the virtues of modulo.

Let's make a simple blackjack game.

This will be a multi-part blog so first let's define what the game will be. Then start building the pieces.

Simple Blackjack Rules

• Dealer and player try to make a hand as close to 21 without going over
• Player goes first
  • may HIT (take a card) or STAND (done dealer's turn)
• Dealer goes next must HIT or STAND according to rules
  • Hand <= 16 dealer must HIT
  • Hand > 16 dealer must STAND
• Any hand that goes over 21 is BUST and loses immediately regardless if the dealer hasn't dealt his hand
• Player starts with a Bankroll (total amount of money he has to bet with)
• Player places a bet before the cards are dealt.
• Player may bet any amount up to the value of his bankroll

Task

Design a text based input and output program to play the game of blackjack according to the rules above. Use single letter designations for the type of card (A,2,3,..,8,9,T,J,Q,K) and single letter for the suit (H,D,S,C).

You may only use a one dimensional array for the storage of a deck of cards

You must be able to shuffle the deck of cards randomly using the random number generator supplied by Java with no repeats.

Design Analysis

• loop until player hits return rather than a value for a bet (ie. not betting ends the game)
• print a prompt with the current bankroll when asking for a bet
• deal hands displaying both cards of the player and XX for the hole card of dealer
• accept user input H or S for HIT or STAND check for bust after each HIT
• Display the hand with all the cards after each HIT
• When S start the dealer's play hitting or standing according to the rules
• At each HIT of the dealer redisplay the hands
• when dealer stands determine the winner
• update bankroll according to whether player won or lost
• ** use only a one dimensional array to store the deck of cards **
• Need a shuffle routine (it can't just be random()*52 I may get duplicates)

Where to Start: A Deck of Cards

• The deck of cards there are 52 cards lets not worry about suits represent them by a number from 0 - 51
• Let's create a CardDeck object to house them in.
• The constructor will just initialize the one dimensional array in cardinal order
• Let's put a shuffle method to shuffle the deck

class CardDeck {
int deck[] = new int[52];

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

void display()
{
  for(int i=0; i < 52; i++) {
    System.out.print(i + " ");
  }
  System.out.println();
}

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

  card.display();
}

And the output from the above program:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 

SHUFFLE

Obviously I want to use the random number generator but how? I could randomly select a number from 0 to 51 and move it to a new array that would become the shuffled deck. I could then shift all the values down and then pick a random number from 0 to 50, and so on until I've randomly moved all the values.

But think for a second what if I just swap the random value for the one at the end. Then pick again from 0 - 50 (ie. n-1) and so on. But then I have to do descending loops which I don't like to do. But think for a minute. If I move throught the array one at a time starting at 0 (like a for loop would) I could pick a random index and then swap the ith index with the random index. This way I just need to pick a random number between i and 51 swap and repeat the loop.

void shuffle()
{
  int rindex;
  int swap;

  for (i = 0; i <= 52; i++) {
    // this will probably need some debugging 
    rindex = Math.rand()*(52-i)+i;
    swap = card[i];
    card[i] = card[rindex];
    card[rindex] = swap;
  }
}

The random number generator needed some debugging and some casting ¹. I will just display the code after debug. I did it again on the 'display' routine too, I forgot the deck[] reference and just displayed i instead. So here is the class definition so far:

public class CardDeck {

    int deck[] = new int[52];

    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;
        }
    }

    void display() {
        for (int i = 0; i < 52; i++) {
            System.out.print(deck[i] + " ");
        }
        System.out.println();
    }

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

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

Output

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 
43 15 34 41 27 14 17 2 3 36 48 12 45 7 37 4 39 13 44 8 16 29 23 46 19 10 18 42 51 1 25 0 38 20 28 31 35 9 50 21 40 11 30 32 47 24 22 6 49 26 5 33 

So how are we going to get the suits and face values of the cards from a single number? If you guessed modulo because I'm writing about modulo you're correct. There are 13 different cards for each suit and 4 different suits. It will be as easy as taking the card number and modulo 13 for value and modulo 4 for suit. To represent them in text in a more card appropriate way let's create 2 strings to hold the text values:

String faceVal = "A23456789TJQK";
String suit = "HDSC";

Then change 'display' to print the 2 character representation of each card.

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.faceVal.substring(card_val,card_val+1) + 
                          this.suit.substring(card_suit,card_suit+1) + " ");
    }
    System.out.println();
}

Output of cards in text

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 
9S 9C TS 9D 7D KC 5H 4C AH JD 6S QC QS 5S AC AD JS 2C 3S 5C 3H 8S 6D KS TH 5D 7C 3D JH JC 3C TC 6C 8H 2S 2D QH AS 6H KH 4H QD 4S 7S 4D TD KD 2H 8C 7H 8D 9H 

The output of your program should be the same for the top line when you initialize the deck. But you should get a different second line the results after a shuffle has taken place. That's because different computers will have different random number sequences depending on what you random seed is and how many times you run the program.

The Program So Far

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;
        }
    }

    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.faceVal.substring(card_val,card_val+1) + 
                              this.suit.substring(card_suit,card_suit+1) + " ");
        }
        System.out.println();
    }

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

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

Next Steps

We've only just begun. In the next part we will work on how we deal hands to the player and dealer. I'm going to try to do this in one class definition only. Yes, that's poor object oriented design but let's see what that would look like and then for the final part let's refactor the program into a more appropriate object oriented example.

(To Be Continued)

Footnotes:

¹ Casting
The compiler is able to make some decisions of how to represent various base types as other base types. For instance double to int. A double is what we think of as a decimal number. The compiler with a 'casting' directive can return just the whole number portion of the decimal number. Placing the base type in parenthesis instructs the computer to make that modification.
For example: (int) 32.25 → 32
Likewise: (double) 32 → 32.0
This is a nice way of telling the compiler you are purposefully looking for it to make those modifications.

Author: Nasty Old Dog

AP Computer Science - A Digression on Matrices

AP Computer Science Digression into Matrices

Unfinished business

My last article on modulo was a little long winded but let's expand on what we have done on the Matrix1d class. I want to show you how to make methods that perform operations on matrices. Matrix mathmatics are certainly important and whole languages have been created to deal with it. Two languages were discussed in the last article but Matlab is yet another language that deals with mathematics and matrices. It was the language used at MIT recently to do video processing to determine if a person is breathing or not. They created matrix processing routines that amplified the movements of video so they could enhance small motions undetectable to the human eye. So matrix mathematics is certainly a major area of study in Computer Science.

But first there was an error I found in my 'displayMatrix' method when working on the code. It turns out that since we intialized the matrix to be the values of the 1 dimension element. I used just the index in the print statements, giving the apperance of displaying the correct memory locations since the values were the same. However, I should have used the index along with mat1d hence printing mat1d[i], to print the values of the matrix. I fixed it in my code and here is the correct code. I am providing all the mistakes I make to give you the ability to see the common errors even experienced programmers make. I will do so for a few more articles. This will help you find mistakes by reading the code, rather than letting the compiler do all the work. At any rate the new code for displayMatrix follows

void displayMatrix() {
    for (int i = 0; i < this.n * this.n; i++) {
        if (i % n == 0) {
            System.out.println();
        }
        System.out.print(this.mat1d[i] + " ");  // this statement was corrected
    }
    System.out.println();
}

Matrix multiply

Matrices can be multiplied. In our case we are only creating n x n matrices, so multiplication can mean a couple of things. A trivial multiply would be to multiply common elements together and report the new matrix as the individual multiplications. The other multiply is known as Matrix Multiplication (more on that later). First an example to clarify simple matrix multiplication:

1 2      1 3         1 6
3 4  x   2 4    =    6 16

That is pretty straight forward and extending this to the n x n case is trivial. However, what would be helpful would be some methods to access and store based on 2 dimensional indexes. So first lets extend the Matrix1d class to do just that. We already defined a getElement method previously so now we just need a storage method we will call setElement. The definition is as follows:

public int setElement(int r, int c, int value)
{
  int index = (r*this.n) + c
  this.mat1d[index] = value;
}

Syntax error in the above code do you see it?

There is also a bit of a design issue. setElement returns a value of int but why? I'm just setting the value so that should be void. The IDE flagged this when I pasted it so I will change it.

Now the object oriented-ness of this may be a little confusing. I will explain after we plow through making the code. All that is missing is our multiply method so let's code that.

public int simpleMultiply(Matrix1d m)
{
  // check that the current Matrix1d (this) is the same size as the parameter m
  if (this.n != m.n) {  
    // I'm starting to access the fields directly in multiple objects
    // probably time to write getter and setter methods and refactor the code
    // if I am in this code section the matrices are not the same size 
    // return 0 for false the multiplication did not take place
    return 0;
  }

  // If we make it to here the matrices can be multiplied together
  for (int i = 0; i < this.n; i++) {
    for (int j = 0; j < this.n; j++) {
      this.setElement(i,j,this.getElement(i,j)*m.getElement(i,j));
    } 
  }
  return 1;
}

Recode the main method to test this on the 2x2 example above. But wait our Matrix1d class definition does not let us initialize the matrix except by chosing consequtive integers. We could define 2 matrices then use 'setElement' to replace the ones we want. Let's try that first (we will revisit this to allow us to define an array of values to initialize the matrix.

public static void main(String args)
{
  Matrix1d mat1 = new Matrix1d(2);
  Matrix1d ans = new Matrix1d(2);

  // Let's replace the values we need if you look at the 2x2 matrices all that's
  // changed is the 2 and 3 are swapped from their original ordinal positions
  mat1.setElement(0, 0, 1);
  mat1.setElement(0, 1, 2);
  mat1.setElement(1, 0, 3);
  mat1.setElement(1, 1, 4);

  ans.setElement(0, 0, 1);
  ans.setElement(0, 1, 3);
  ans.setElement(1, 0, 2);
  ans.setElement(1, 1, 4);


  if (ans.simpleMultiply(mat1)) {
    ans.displayMatrix();
  }
  else {
    System.out.println("Size error");
  }
}

Now there are 2 not so obvious errors above. The first one is that simpleMutiply returns an int not a boolean (this is something that the C programming language lets you do but Java does not). So we will need to change the if statement to have '== 1' in it. The other is that the String args should be String[] args. Arguments in the main method come in as an array of Strings. So fix those 2 bugs and the output of our multiply routine should be:

1 6 
6 16 

Matrix Multiplication (the real thing)

So while the above is a form of multiplying matrices it is not full blown matrix multiplication. To multiply 2 matrices in it's standard meaning means to multiply the rows of one matrix with the columns of the other and sum the terms to form new elements of the matrix that will become the answer. So if A and B are the matrices I want to Matrix Multiply and I will use C as the new matrix obtained by the operation. Matrix multiplication is defined as follows:

C_i,j = Σ A_i,k * B_k,j (k = 0,…,n-1)

To program this you will need 3 nested loops. Two (2) nested loops for the i and j of each element of C and an inner loop inside of those to sum up all the k multiplications.

public Matrix1d matrixMultiply(Matrix1d b)
{
  // Object oriented I will use the A object to do the calculation give it B
  // and return a new matrix for the return value which of course is C
  // Create C
  Matrix1d c = new Matrix1d(this.n);

  for (int i =0 ; i < this.n; i++) {
    for (int j = 0; j < this.n; j++) {
      c.setElement(i,j, 0); //zero out the element to accumulate the sum
      for (int k = 0; k < this.n; k++) {
        c.setElement(i, j, c.getElement(i,j) + this.getElement(i,k) * b.getElement(k,j);
      }
    }
  }
  return c;
}

Mistake above. Fixed in final version again see if you can sight read and find the error.

Interestingly enough in our representation of a matrix as a linear array we only need modulo in order to display rows and columns given the internal index of the array. If I didn't need to display this in matrix form I could almost write an entire matrix package without modulo. However, in the routines to convert a row and column into an index modulo is implicit. If you notice we use the formula:

array index = divisor * quotient + remainder

What is the remainder? Of course the answer we get when doing a modulo operation.

A better way of setting up a matrix

The use of setElement calls is a little cumbersome. It would be nicer if a list of numbers could be input directly and the class would take care of placing them in the storage array directly. This is easy enough to accomplish by creating a new constructor that allows an int array to be the parameter.

Matrix1d(int size, int[] vals)
{
  // vals size would have to be a square of some n that needs to be 
  // determined. For now rather than handling an error just assume only
  // an appropriately sized array is given and that the size of the 
  // matrix is provided as a parameter

  this.n = size;
  this.mat1d = vals;

}

Add the following statements to the main method to test:

// Test the array initialization
int[] matarr = {2,4,6,8,10,12,14,16,18};
Matrix1d mat2 = new Matrix1d(3,matarr);
mat2.displayMatrix();

Identity Matrix

Just as 1 x n = n (multiplicative identity). So to in Matrix Multiplication there exists an Identity Matrix we can call 'I' that creates a matrix multiplicative identity: A x I = A. Pretty interesting, let's see if our newly created matrix class is up to the task. First what does the Identity Matrix look like? It's a matrix of nxn elements with 1's in the diagonal spaces from 0,0 .. n,n.

1 0 0     1 0 0 0 
0 1 0     0 1 0 0 
0 0 1     0 0 1 0
          0 0 0 1

The preceding are 3 x 3 and 4 x 4 identity matrices We can use our new constructor to create an identity matrix. Add the following lines to main to test the constructor

int[] identity3 = {1,0,0,0,1,0,0,0,1};

Matrix1d mat3 = new Matrix1d(3,identity3);
Matrix1d mat4 = mat2.matrixMultiply(mat3);
mat4.displayMatrix();

Output

1 6 
6 16 

7 10 
15 22 

2 4 6 
8 10 12 
14 16 18 

2 4 6 
8 10 12 
14 16 18 

Let's modify main to printout the identity matrix as well. The final version of the main method is:

    public static void main(String[] args) {
        Matrix1d mat1 = new Matrix1d(2);
        Matrix1d ans = new Matrix1d(2);

        // Let's replace the values we need if you look at the 2x2 matrices all that's
        // changed is the 2 and 3 are swapped from their original ordinal positions
        // and the other corner elements are 1 and 4 respectively
        mat1.setElement(0, 0, 1);
        mat1.setElement(0, 1, 2);
        mat1.setElement(1, 0, 3);
        mat1.setElement(1, 1, 4);

        ans.setElement(0, 0, 1);
        ans.setElement(0, 1, 3);
        ans.setElement(1, 0, 2);
        ans.setElement(1, 1, 4);

        if (ans.simpleMultiply(mat1) == 1) {
            ans.displayMatrix();
        } else {
            System.out.println("Size error");
        }

        Matrix1d mmult = mat1.matrixMultiply(mat1);
        mmult.displayMatrix();

        // Test the array initialization
        int[] matarr = {2,4,6,8,10,12,14,16,18};
        Matrix1d mat2 = new Matrix1d(3,matarr);
        mat2.displayMatrix();

        int[] identity3 = {1,0,0,0,1,0,0,0,1};

Matrix1d mat3 = new Matrix1d(3,identity3);
Matrix1d mat4 = mat2.matrixMultiply(mat3);
mat3.displayMatrix();
mat4.displayMatrix();

Output

1 6 
6 16 

7 10 
15 22 

2 4 6 
8 10 12 
14 16 18 

1 0 0 
0 1 0 
0 0 1

2 4 6 
8 10 12 
14 16 18 

Conclusion

That's all for matrices for now. This should give you some exposure of how we use computers to solve math problems. We basically try to model what we do in math and make the computer go through the tedious processing. Next we will revisit modulo in a more interesting way.

References

1. Eulerian Video Magnification MIT CSAIL web address: http://people.csail.mit.edu/mrub/vidmag/

Final Version of Code

public class Matrix1d {

    int n = 10;
    int mat1d[] = null;

    public Matrix1d(int n) {
        this.n = n;
        this.mat1d = new int[this.n * this.n];
        // intialize the elements to count up from 0
        for (int i = 0; i < this.n * this.n; i++) {
            mat1d[i] = i;
        }
    }

    public Matrix1d(int size, int[] vals)
{
  // vals size would have to be a square of some n that needs to be 
  // determined. For now rather than handling an error just assume only
  // an appropriately sized array is given and that the size of the 
  // matrix is provided as a parameter

  this.n = size;
  this.mat1d = vals;

}

// put our code to get an element here
    int getElement(int row, int col) {
        return this.mat1d[row * this.n + col];
    }

    void display() {
        int r, c;

        for (int i = 0; i < this.n * this.n; i++) {
            r = i / this.n;   // integer divide gives us the row for the element

            // for the column it's the left over after the integer divide
            // col = i - (r * n) which sin r was calculated with int division is just
            // the remainder. Well since we want to look professional we know that's 
            // modulo. So to look like we know what's going on let's use modulo
            c = i % this.n;
            System.out.println("matrix[" + r + "][" + c + "] = " + this.mat1d[i]);
        }
    }

    void displayMatrix() {
        for (int i = 0; i < this.n * this.n; i++) {
            if (i % n == 0) {
                System.out.println();
            }
            System.out.print(this.mat1d[i] + " ");
        }
        System.out.println();
    }

    public void setElement(int r, int c, int value) {
        int index = (r * this.n) + c;
        this.mat1d[index] = value;
    }

    public int simpleMultiply(Matrix1d m) {
        // check that the current Matrix1d (this) is the same size as the parameter m
        if (this.n != m.n) {
            // I'm starting to access the fields directly in multiple objects
            // probably time to write getter and setter methods and refactor the code
            // if I am in this code section the matrices are not the same size 
            // return 0 for false the multiplication did not take place
            return 0;
        }

        // If we make it to here the matrices can be multiplied together
        for (int i = 0; i < this.n; i++) {
            for (int j = 0; j < this.n; j++) {
                this.setElement(i, j, this.getElement(i, j) * m.getElement(i, j));
            }
        }
        return 1;
    }

    public Matrix1d matrixMultiply(Matrix1d b)
{
  // Object oriented I will use the A object to do the calculation give it B
  // and return a new matrix for the return value which of course is C
  // Create C
  Matrix1d c = new Matrix1d(this.n);

  for (int i =0 ; i < this.n; i++) {
    for (int j = 0; j < this.n; j++) {
      c.setElement(i,j, 0); //zero out the element to accumulate the sum
      for (int k = 0; k < this.n; k++) {
        c.setElement(i, j, c.getElement(i,j) + this.getElement(i,k) * b.getElement(k,j));
      }
    }
  }
  return c;
}

    public static void main(String[] args) {
        Matrix1d mat1 = new Matrix1d(2);
        Matrix1d ans = new Matrix1d(2);

        // Let's replace the values we need if you look at the 2x2 matrices all that's
        // changed is the 2 and 3 are swapped from their original ordinal positions
        // and the other corner elements are 1 and 4 respectively
        mat1.setElement(0, 0, 1);
        mat1.setElement(0, 1, 2);
        mat1.setElement(1, 0, 3);
        mat1.setElement(1, 1, 4);

        ans.setElement(0, 0, 1);
        ans.setElement(0, 1, 3);
        ans.setElement(1, 0, 2);
        ans.setElement(1, 1, 4);

        if (ans.simpleMultiply(mat1) == 1) {
            ans.displayMatrix();
        } else {
            System.out.println("Size error");
        }

        Matrix1d mmult = mat1.matrixMultiply(mat1);
        mmult.displayMatrix();

        // Test the array initialization
        int[] matarr = {2,4,6,8,10,12,14,16,18};
        Matrix1d mat2 = new Matrix1d(3,matarr);
        mat2.displayMatrix();

        int[] identity3 = {1,0,0,0,1,0,0,0,1};

Matrix1d mat3 = new Matrix1d(3,identity3);
Matrix1d mat4 = mat2.matrixMultiply(mat3);
mat3.displayMatrix();
mat4.displayMatrix();
    }
}

Author: Nasty Old Dog

Modulo

AP Computer Science Modulo it's Just Remainder

Think Mathematically

Computer Science is technically a branch of Mathematics and yet pure mathematical thinking may cause problems when you try to understand the temporal relationships (temporal fancy word for timing) of computer programing. For example if you try to understand the following (based on your understanding of algebra):

j = j + 1

The above statement makes no sense, algebraically. But in Computer Science this really means take the current value of j add 1 to it, store the answer back in j. In Programming names are not algebraic variables they are memory locations whose value depends on the timing of instructions. When the above example gets compiled the instructions to the computer get ordered in a certain way and the processor acts on each statement one at a time in the order they are found. It is confusing to the beginning Computer Scientist because they have years of mathematics where the variable was only going to be one value and it was their job to find out what it is.

Another human thought process getting in our way is the fact that we read English from left to right. For the human to understand what is happening they have to read in the whole sentence then work backwards:

• Start on the expression on the right hand side
  • interpret what is happening here (j + 1)
• Then figure out what will happen because of the equals sign

The late Ken Iverson realized this back in the early 1960's Dr. Iverson created a whole notation that would allow a mathematician to represent algorithms. The seminal treatise was captured in his book A Programming Language. IBM hired Dr. Iverson to implement this notation on a computer. He created a new programmming language called APL.

Dr. Iverson came up with a brilliant realization (among many) that our traditional way of resolving precedence (the order we do operations in mathematics) was in reality arbitrary and ambiguous. While most computer languages (like Java) strived to duplicate tradition, Dr. Iverson¹ said there is no operator precedence we just read a statement from RIGHT to LEFT (yes the opposite of what you've been taught all these years) and do the operation when we first hit it. If the programmer needs to ensure certain operations happen first rewrite your equation or use parenthesis to organize which operations go first (so parentheses are the same in any language). The beauty of this realization in our simple example above, reading Right to Left gives us a sense of the temporal considerations when running the program.

1 is added to j and the result stored back in j

Reading right to left provides a better understanding of what happens and when. You begin to think more about how the computer sees things. Java uses a traditional precedence mechanism for mathematical formulas. Reading right to left will not be that helpful for complex statements.

The budding computer scientist needs to be ready to think mathematically in non-traditional ways. Indeed, Dr. Iverson even invented new mathematic symbols and had to create his own font to even print the new operations. He was striving for a new mathematical world where the opertator relationships would be defined in a standard way so you could map your mathematical talents and apply them to a computer in a useful way. This is much the same as Dirac notation for quantum mechanics or Laplace transforms for differential equations. Create a new mathematics that abstracts away tedious details and helps the mathematician to think and get their hands around a new environment.

When you are able to map your mathematics skills into solving the programming assignments, you will be surprised at your own intuition and creativity. You will be able to simplify a problem because you saw the mathematical tricks that reduced 100 lines of code down to 10.

Tricks of the Trade: Modulo

One computer math trick you need to be aware of is modulo. There are many reasons to use Modulo. Indexing into 2 dimensional arrays (matrix after its mathematical counterpart) as an example. It is usually used when we are trying to map large a set of numbers into a smaller set. Many indexing operations will take advantage of modulo (the Java operator %). Modulo is rooted in long division. You know what it is and what it does even if you don't recognize the name.

Modulo = Remainder

Remember doing long division all those years ago in Elementary School? You used an algorithm and your knowledge of the "times" tables and would come up with 2 answers. One was the quotient the other was the remainder. The amount of stuff left over since the division did not go in evenly.

Remainder was always a throw away item in school we reported it but didn't use it very much. But it turns out it's very useful in many aspects of programming. In fact for games you use it all the time with out knowing about it. Most random number generators use modulo by a prime number. In fact the very architecture of the CPU registers has modulo built in. If you were to add 10 to (2³²-1) you would overflow the register but the number left in the register would wrap around 0 and what would be left is 9.

The best thing about modulo is it's a built in mathematics operation. If we had to duplicate the functionality programatically it would make our code too complex. The reality is that complex code is error prone code and we may not take into account every eventuality. By using computer mathematics we have a much better likelihood the code will operate properly. Hopefully by using a mathmatics solution there will be much smaller set of lines of code to debug. It's much easier to find a mathematical error in one line than a logic error in multiple nested if statements

First Example Simulating Multidimensional Arrays

Let's pretend Java didn't provide the ability to declare multidimensional arrays. But they do give us single dimensional arrays. For simplicity sake lets just simulate square matrices (NxN).

Specifications

1. Call the class Matrix1d
2. Using only one array field and any number of individual support fields
3. The actual elements shall be 'int's just to simplify
4. Create a class that constructs a 2 dimensional array given the size N
5. Use Method getElement(int row, int col)
6. Create a display method display() that prints a list of elements and their indexes and prints the matrix in standard matrix format

Lets work on 4 first. There are N columns so the first N elements of the 1d array should represent the first row of the matrix. The second row would be the next N elements … the Nth row would be the last N elements. You should be able to figure out the equation to map a row and column into a single address in our 1d array:

row * N + col

The code for this is:

int getElement(int row, int col) 
{
  return this.mat1d[row * this.n + col];
}

Let's store N in field int n and using the mat1d name for the array let's code the class so far with a possible constructor:

class Matrix1d {
int n = 10;
int mat1d[] = null;

Matrix1d(int n)
{
  this.n = n;
  this.mat1d = new int [this.n * this.n];
  // intialize the elements to count up from 0
  for (int i = 0; i < this.n*this.n; i++) 
  { 
    mat1d[i] = i;
  }
}

// put our code to get an element here
int getElement(int row, int col) 
{
  return this.mat1d[row * this.n + col];
}

void display()
{
  int r,c;

  for (int i = 0; i < this.n*this.n; i++)
  {
    r = i/this.n;   // integer divide gives us the row for the element

    // for the column it's the left over after the integer divide
    // col = i - (r * n) which sin r was calculated with int division is just
    // the remainder. Well since we want to look professional we know that's 
    // modulo. So to look like we know what's going on let's use modulo
    c = i%n
    println("matrix["+r+"]["+c+"] = " + mat1d[i];
  }
}

Now the above code has a few syntax errors in it.

• I'm missing public in front of my class definition
• I forgot a semicolon in the 4th line from the bottom (c = i%n)
• I'm missing the close parenthesis int the println statement and the 'System.out.' before the println

Now these are mistakes you make all the time that the IDE (eclipse, netbeans, etc) point out to you immediately. How did I get the code with those mistakes? Because I coded it in a separate editor I use to write these blog articles and then copied the code and pasted it into Netbeans. Rather than fix my article I thought I would point out to you that you can program outside of the IDE. It's actually helpful to your design. Code out large chunks of code, think about what you want to do, then as a separate step (once you have your logic in place) fix the syntax. It helps to keep you focused on your real problem instead of being side tracked by fixing semicolons or missing keywords.

There is also another problem above in my style of coding Java I am missing 'this.' on my fields. Instead I am addressing them directly by name. I find it helpful to reference object fields by using the 'this' keyword. It is a reminder that this code takes place inside an object. That object would have been constructed somewhere else in the code by calling 'new' on the constructor in the class definition for the object.

Ultimately in object oriented programming fields should be addressed directly as little as possible (even using the 'this' directive). Indeed, I would normally refrain from using them at all and instead implement 'getter' and 'setter' methods to change and access the fields. Now you may be thinking: "It seems kind of dumb for such a simple program" and I agree. For this simple program it's not necessary and only adds clutter to the code with out expressing any central logic. This again is why I like to prepend 'this' to the field. It's a reminder that if this simple little program actually becomes part of a library that another programmer would use, it needs to be buffed up with 'getter' and 'setter' methods and replace my direct references to object fields using the get and set method calls.

Now let's add a main method to test the class so far:

static void main(String[] args)
{ 
  // Create a 5 x 5 matrix
  Martix1d mymatrix = new Matrix1d(5);

  mymatrix.display();
}

Again I just coded this directly in my article editor now I will copy and paste into the IDE and see what mistakes pop up.

There are two mistakes in the main method code see if you can find it.

In the meantime once I fixed all the mistakes in the code above here is what we get as the output:

matrix[0][0] = 0
matrix[0][1] = 1
matrix[0][2] = 2
matrix[0][3] = 3
matrix[0][4] = 4
matrix[1][0] = 5
matrix[1][1] = 6
matrix[1][2] = 7
matrix[1][3] = 8
matrix[1][4] = 9
matrix[2][0] = 10
matrix[2][1] = 11
matrix[2][2] = 12
matrix[2][3] = 13
matrix[2][4] = 14
matrix[3][0] = 15
matrix[3][1] = 16
matrix[3][2] = 17
matrix[3][3] = 18
matrix[3][4] = 19
matrix[4][0] = 20
matrix[4][1] = 21
matrix[4][2] = 22
matrix[4][3] = 23
matrix[4][4] = 24

Did I happen to mention Modulo?

Please review the code so far as it pertains to Modulo. You need to see how modulo is taking a single number and converting it into a column index. This is believe it or not a non-trivial use of a computer program. If you enter the field or do electronics as a hobby you may have to program in a language that doesn't have multidimensional arrays. But that shouldn't stop you from making them yourself out of the tools you do have available. If the project you are working on needs multi-dimensional arrays to simplify the code build your own.

Certainly Java has multidimensional arrays. But what if you wanted to fill the contents of a multidimensional array with the values in a 1 dimensional array? How would we do that? We could adapt our code without much of a problem, but how would you do it if you weren't an expert with modulo?

Better Display or at least more mathematical display

For those of you who have already been introduced to matrices you will agree that our display method does not look like a matrix in a math book. Let's create a new method call displayMatrix that will display the values in rows or columns we don't need the indexes. But we will use modulo to tell us when to start printing elements in a new row. I won't go into the design but try to do it yourself. I provide my solution with the full code listing. One problem with the output from my implementation below, the matrix printed out isn't very square. Single digit numbers get different spacing than double digit. I'll address that in the next installment.

Conclusion

I'm not finished with modulo 2 more articles are coming one to implement 2 dimensional arrays as a Java multidimentional array and fill it with consecutive numbers or from numbers in a single dimensional array. Modulo will play a role there. The second article will be a Blackjack program and how modulo helps us to determine the type of card ace through ten, jack, quesn, king. Modulo will also help determine the suit spades, diamonds, clubs, hearts.

I hope that my taking you through an actual design process didn't bore you to much. I will probably continue in that vein because these programs don't go from mind to paper with out some syntax errors. I thought it might be helpful to you to see how some one else thinks through the process and how far they take it before commiting to compile the code.

/**
 *
 * @author Nasty Old Dog
 */
public class Matrix1d {

    int n = 10;
    int mat1d[] = null;

    Matrix1d(int n) {
        this.n = n;
        this.mat1d = new int[this.n * this.n];
        // intialize the elements to count up from 0
        for (int i = 0; i < this.n * this.n; i++) {
            mat1d[i] = i;
        }
    }

// put our code to get an element here
    int getElement(int row, int col) {
        return this.mat1d[row * this.n + col];
    }

    void display() {
        int r, c;

        for (int i = 0; i < this.n * this.n; i++) {
            r = i / this.n;   // integer divide gives us the row for the element

            // for the column it's the left over after the integer divide
            // col = i - (r * n) which sin r was calculated with int division is just
            // the remainder. Well since we want to look professional we know that's 
            // modulo. So to look like we know what's going on let's use modulo
            c = i % this.n;
            System.out.println("matrix[" + r + "][" + c + "] = " + this.mat1d[i]);
        }
    }

    void displayMatrix() {
        for (int i = 0; i < this.n * this.n; i++) {
            if (i % n == 0) {
                System.out.println();
            }
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create a 5 x 5 matrix
        Matrix1d mymatrix = new Matrix1d(5);

        mymatrix.display();
        mymatrix.displayMatrix();
    }
}

References

1. Iverson, K.E., A Programming Language, Wiley, 1962-05. Available at J Software Site

Footnotes:

¹ The late Dr. Iverson's work lives on at a company he created: J Software. He also updated APL (so to speak) with it's sister the programming language J. J has versions for most platforms even the iPhone and iPod. The difference between J and APL is that J reverts back to standard characters yet all of the interesting operators are there. Dr. Iverson also improves on APL in the terminology used to describe the language. Dr. Iverson maps the language contructs into English grammar equivalents. This way comments are started by NB. the english equivalent for NB note bene (note well), operators are now verbs, Variables are nouns, etc. It's a great language one I highly recommend. Read more at http://wwww.jsoftware.com

By the way in J the operator, I mean verb, for modulo is called residue and it uses the "|" symbol instead of a "%" like in Java. You also must put the numbers in reverse, why because the entire language J is read from Right to Left. So the J equivalent of Java's 121%5 would be 5|121. You may think it's confusing, I prefer to think of it as amazing that I can change the way a computer does things to suit my whims and fancies.

Author: Nasty Old Dog