Computer Science 15-100, Fall 2008
Class Notes:  Two-Dimensional Arrays

1. Arrays Methods
   1. deepToString
   2. deepEquals
2. Allocation
   1. Fixed-Size Array
   2. Variable-Sized Array
   3. Statically-Allocated Array
3. Printing
4. Swap
   1. Swap Elements
   2. Swap Rows
   3. Swap Columns
5. Copy Rows
   1. Broken Copy Rows
   2. Working Copy Rows
6. Example:  Two-Dimensional Board Search

Two-Dimensional Arrays

1. Arrays Methods
    
   1. deepToString

      import java.util.Arrays;
      class MyCode {
        public static void main(String[] args) {
          int[][] a = { { 4, 2, 8 },
                        { 3, 1, 5 }
                      };
          System.out.println(Arrays.toString(a));  // surprised?
          System.out.println(Arrays.deepToString(a));
        }
      }
      

   2. deepEquals

      import java.util.Arrays;
      class MyCode {
        public static void main(String[] args) {
          int[][] a = { { 4, 2, 8 },
                        { 3, 1, 5 }
                      };
          int[][] b = { { 4, 2, 8 },
                        { 3, 1, 5 }
                      };
          System.out.println(Arrays.equals(a,b));  // surprised?
          System.out.println(Arrays.deepEquals(a,b));
        }
      }

2. Allocation
    
   1. Fixed-Size Array

      import java.util.*;
      class MyCode {
        public static void main(String[] args) {
          Scanner scanner = new Scanner(System.in);
          int[][] a = new int[2][3];
      
          System.out.print("Enter 2x3=6 integers: ");
          for (int i=0; i<2; i++)
            for (int j=0; j<3; j++)
              a[i][j] = scanner.nextInt();
      
          System.out.println("Here are those 6 integers in a 2x3 2d-array:");
          System.out.println(Arrays.deepToString(a));
        }
      }

   2. Variable-Sized Array

      import java.util.*;
      class MyCode {
        public static void main(String[] args) {
          Scanner scanner = new Scanner(System.in);
          System.out.print("Enter # of rows: ");
          int rows = scanner.nextInt();
          System.out.print("Enter # of cols: ");
          int cols = scanner.nextInt();
      
          int[][] a = new int[rows][cols];
      
          System.out.print("Enter " + rows + "x" + cols + "=" + (rows*cols) + " integers: ");
          for (int i=0; i<rows; i++)
            for (int j=0; j<cols; j++)
              a[i][j] = scanner.nextInt();
      
          System.out.println("Here are those " + (rows*cols) +" integers in a " +
                             rows + "x" + cols + " 2d-array:");
          System.out.println(Arrays.deepToString(a));
        }
      }

   3. Statically-Allocated Array

      import java.util.*;
      class MyCode {
        public static void main(String[] args) {
          int[][] a = { { 4, 2, 8 },
                        { 3, 1, 5 }
                      };
      
          int rows = a.length;
          int cols = a[0].length;
      
          System.out.println("Here are the " + (rows*cols) +" integers in a " +
                             rows + "x" + cols + " 2d-array:");
          System.out.println(Arrays.deepToString(a));
        }
      }

3. Printing

   import java.util.*;
   class MyCode {
     public static void main(String[] args) {
       int[][] a = { { 4, 2, 8, 3, 5, 9, 6, 7, 3 },
                     { 3, 1, 5, 2, 1, 5, 9, 3, 0 },
                     { 2, 2, 1, 8, 6, 2, 5, 1, 4 }
                   };
       System.out.println("Printed with deepToString:");
       System.out.println(Arrays.deepToString(a));
   
       System.out.println("And printed with printArray:");
       printArray(a);
     }
   
     public static void printArray(int[][] a) {
       int rows = a.length;
       int cols = a[0].length;
       for (int row=0; row<rows; row++) {
         for (int col=0; col<cols; col++) {
           if (col > 0) System.out.print(", ");
           System.out.print(a[row][col]);
         }
         System.out.println();
       }
     }
   }

   Even Better printArray Method:
   (using System.out.format, which you are not yet responsible for!)

   import java.util.*;
   class MyCode {
     public static void main(String[] args) {
       int[][] a = { { -34, 2, 8, 3, 5, 9, 6, 7, 3 },
                     { 3, 1, 55, 2, 1, 5, 9, 3, 0 },
                     { 2, 2, 181, 8, 6, 2, 5, 1, 4 }
                   };
       System.out.println("Printed with deepToString:");
       System.out.println(Arrays.deepToString(a));
   
       System.out.println("And printed with an even-better printArray:");
       printArray(a);
     }
   
     // even better version!
     public static void printArray(int[][] a) {
       int rows = a.length;
       int cols = a[0].length;
       System.out.print("[ ");
       for (int row=0; row<rows; row++) {
         if (row > 0) System.out.print("  ");
         System.out.print("[");
         for (int col=0; col<cols; col++) {
           if (col > 0) System.out.print(", ");
           System.out.format("%3d",a[row][col]); // field-width = 3
         }
         System.out.println("]");
       }
       System.out.println("]");
     }
   }

4. Swap
    
   1. Swap Elements

      import java.util.Arrays;
      class MyCode {
        public static void swap(int[][] a, int i0, int j0, int i1, int j1) {
          int temp = a[i0][j0];
          a[i0][j0] = a[i1][j1];
          a[i1][j1] = temp;
        }

        public static void main(String[] args) {
          int[][] a = { { 3, 4, 2 },
                        { 2, 6, 8 },
                        { 9, 5, 1 }
                      };
          System.out.println(Arrays.deepToString(a));
          swap(a,0,1,2,0); // swap a[0][1] with a[2][0]
          System.out.println(Arrays.deepToString(a));
        }
      }

   2. Swap Rows

      import java.util.Arrays;
      class MyCode {
        public static void swapRows(int[][] a, int row0, int row1) {
          int cols = a[0].length;
          for (int col=0; col<cols; col++)
            swap(a, row0, col, row1, col);
        }

        public static void swap(int[][] a, int i0, int j0, int i1, int j1) {
          int temp = a[i0][j0];
          a[i0][j0] = a[i1][j1];
          a[i1][j1] = temp;
        }

        public static void main(String[] args) {
          int[][] a = { { 3, 4, 2 },
                        { 2, 6, 8 },
                        { 9, 5, 1 }
                      };
          System.out.println(Arrays.deepToString(a));
          swapRows(a,0,1);
          System.out.println(Arrays.deepToString(a));
        }
      }

   3. Swap Columns

      import java.util.Arrays;
      class MyCode {
        public static void swapCols(int[][] a, int col0, int col1) {
          int rows = a.length;
          for (int row=0; row<rows; row++)
            swap(a, row, col0, row, col1);
        }

        public static void swap(int[][] a, int i0, int j0, int i1, int j1) {
          int temp = a[i0][j0];
          a[i0][j0] = a[i1][j1];
          a[i1][j1] = temp;
        }

        public static void main(String[] args) {
          int[][] a = { { 3, 4, 2 },
                        { 2, 6, 8 },
                        { 9, 5, 1 }
                      };
          System.out.println(Arrays.deepToString(a));
          swapCols(a,0,1);
          System.out.println(Arrays.deepToString(a));
        }
      }

5. Copy Rows
    
   1. Broken Copy Rows

      import java.util.Arrays;
      class MyCode {
        public static void main(String[] args) {
          int[][] a = { { 1, 2, 3 },
                        { 4, 5, 6 }
                      };
          a[0] = a[1];  // BROKEN!!! Not how you copy rows!
                        // Note:  this is the cause of a very common, very nasty
                        // bug when deleting full rows in Tetris!

          // After we "copy" row 1 into row 0, we change the original
          // and the copied rows, but what happens...?
          a[0][2] = 99;
          a[1][0] = -99;

          System.out.println(Arrays.deepToString(a));
        }
      }

   2. Working Copy Rows

      import java.util.Arrays;
      class MyCode {

        // Copies all the values from the srcRow into the dstRow.
        public static void copyRow(int[][] a, int srcRow, int dstRow) {
          int cols = a[0].length;
          for (int col=0; col<cols; col++)
            a[dstRow][col] = a[srcRow][col];
        }
      
        public static void main(String[] args) {
          int[][] a = { { 1, 2, 3 },
                        { 4, 5, 6 }
                      };
      
          copyRow(a, 1, 0); // copy all values from row 1 into row 0
      
          // After we "copy" row 1 into row 0, we change the original
          // and the copied rows, but what happens...?
          a[0][2] = 99;
          a[1][0] = -99;
      
          System.out.println(Arrays.deepToString(a));
        }
      }

6. Example:  Two-Dimensional Board Search

   import java.util.Arrays;
   class MyCode {
   
     // Returns true if the given board contains the given string.
     // Tests every possible starting location.
     public static boolean contains(char[][] board, String s) {
       int rows = board.length;
       int cols = board[0].length;
       for (int row=0; row<rows; row++)
         for (int col=0; col<cols; col++)
           if (contains(board,s,row,col))
             return true;
       return false;
     }
   
     // Returns true if the given board contains the given string,
     // starting from the given startRow and startCol location.
     // Tests every possible direction from there, where a direction
     // is determined by drow,dcol (the change in rows and cols).
     public static boolean contains(char[][] board, String s,
                                    int startRow, int startCol) {
       int rows = board.length;
       int cols = board[0].length;
       for (int dRow=-1; dRow<=1; dRow++)
         for (int dCol=-1; dCol<=1; dCol++)
           if (((dRow != 0) || (dCol != 0)) &&
               (contains(board,s,startRow,startCol,dRow,dCol)))
             return true;
       return false;
     }
   
     // Returns true if the given board contains the given string,
     // starting from the given startRow and startCol location,
     // heading in the given drow,dcol direction.
     public static boolean contains(char[][] board, String s,
                                    int startRow, int startCol,
                                    int dRow, int dCol) {
       int rows = board.length;
       int cols = board[0].length;
       for (int i=0; i<s.length(); i++) {
         int row = startRow + i*dRow;
         int col = startCol + i*dCol;
         if ((row < 0) || (row >= rows) || (col < 0) || (col >= cols))
           // we're off the board, so we did not match
           return false;
         if (board[row][col] != s.charAt(i))
           // we're on the board, but we don't match
           return false;
       }
       return true;
     }
   
     public static void main(String[] args) {
       char[][] board = { { 't', 'a', 'c', 'w' },
                          { 'n', 'o', 'o', 'c' },
                          { 'd', 'o', 'g', 'x' }
                        };
   
       String[] terms = { "cat", "cod", "coon", "dog", "ox",
                          "caw", "cow", "con", "dogs", "ax" };
   
       // The first 5 terms are on the board, the last 5 are not
       for (int i=0; i<terms.length; i++)
         System.out.println(terms[i] + ": " + contains(board, terms[i]));
     }
   }

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem