Recursion
and Blobs

Nicholas Duchon: Feb 16, 2019.

Outline

Blob Counting

This is the Blob counting algorithm developed in DJW 2nd edition, with a few modifications to make it a little easier to see how the algorithm works.

Grid (pp 257-259) to GridND: I have modified the visited array to show the order in which the elements in the array are visited, and changed the toString method to also print this array. Also added another constructor that will accept a 2-D int array (1's as true and 0's as false) to make it possible to examine a specific array.

BlobApp (pg 260) to BlobAppND: This will support the 2-D constructor, and has a simple example. The default array size is different also.

Note that the algorithm goes in this order:

up
down
left
right

And the recursion acts like a stack, remembering branches that were taken in the search by leaving the current cell to go to the next unmarked adjacent cell in the order shown above.

The checking order here is: up --> down --> left --> right. You can follow this by starting at 1 in this example and tracing the first blob through 76, the second blob from 77 through 79 and so on.

Newer Version: GridND2

Here are some comments about the methods:

main

sets the size of grid using constants in code
gets the probability of a cell being in a blob (true vs false)
calls the constructor
call blobCount to do the work
prints displays of the grid
prints the number of blobs found

GridND2

The int/int/int constructor:

rows,
columns,
percentage of cells that are true (in a blob)

Uses a random number generator to mark some cells as true

toString

converts the grids to a String representation
the true/false grid
the grid showing when each cell is visited
the grid showing which blob each cell belongs to

blobCount

clears the search cells and counters
goes through every cell looking for a true cell that has yet to be visited
calls markBlob to find all the cells connected to this one.
updates counters

markBlob - the recursive method searching for cells connected to this one

4 base cases concerning edges of grid
base case for cell not in any blob
base case for a cell that has already been visited
general case:

update counters
recursive search of neighbors: up, down, left then right

// File: GridND2.java
// Date: Mar 18, 2017
// Author: Nicholas Duchon
// Based on Dale/Joyce/Weems Chapter 4, BlobApp.java and Grid.java

//----------------------------------------------------------------------
// BlobApp.java          by Dale/Joyce/Weems                   Chapter 4
//
// Instantiates a Grid based on a percentage probability provided by the
// user and reports the number of blobs in the Grid.
//----------------------------------------------------------------------
// Nick Duchon - modifications
// Date: Oct 5, 2008
//----------------------------------------------------------------------
// Grid.java              by Dale/Joyce/Weems                  Chapter 4
//
// Supports grid objects consisting of blob and non-blob characters.
// Allows the number of blobs it contains to be counted.
//
// Modifications by Nicholas Duchon
//----------------------------------------------------------------------

import java.util.Scanner;
import java.util.Random;

public class GridND2 {
   int rows; // number of grid rows
   int cols; // number of grid columns

   boolean [][] grid;     // the grid containing blobs
   int     [][] visited; // used by blobCount
   int     [][] id;       // the id of each blob
   int index;             // number the order of visits to active cells
   int count;             // number of the visiting of a cell

   public static void main(String[] args) {
      Scanner conIn = new Scanner(System.in);

      final int GRIDR = 20;   // number of grid rows
      final int GRIDC = 20;   // number of grid columns

      // Get percentage probability of blob characters
      int percentage;
      System.out.print("Input percentage probability (0 to 100): ");
      if (conIn.hasNextInt())
         percentage = conIn.nextInt();
      else {
         System.out.println("Error: you must enter an integer.");
         System.out.println("Terminating program.");
         return;
      } // end geting input from the user

      System.out.println();

      // create grid
      GridND2 grid = new GridND2 (GRIDR, GRIDC, percentage);

      // display grid and blob count
      int c = grid.blobCount();
      System.out.println (grid);
      System.out.println ("\nThere are " + c + " blobs.\n");
   } // end main method

    // Preconditions: rows and cols > 0
    //                0 <= percentage <= 100
    //
    // Instantiates a grid of size rows by cols, where locations are set to
    // indicate blob characters based on the percentage probability.
   public GridND2 (int prows, int pcols, int percentage) {
      rows    = prows;
      cols    = pcols;
      grid    = new boolean [rows][cols]; // true means cell part of a blob
      visited = new int     [rows][cols]; // true if location visited
      id      = new int     [rows][cols]; // which blob?

      // to generate random numbers
      Random rand = new Random();

      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++)
            grid [i][j] = (percentage > rand.nextInt(100));
   } // end int/int/int constructor

   public String toString() {
      String gridString = "";
      for (int i = 0; i < rows; i++) {
         for (boolean b: grid[i])
            gridString += b?"X":"-";
         gridString += "     ";
         for (int m: visited[i]) {
            gridString += String.format ("%4d", m);
         } // end for each row in the visited matrix also
         gridString = gridString + "\n";   // end of row
      } // end for each row of the grid

      for (int [] r: id) {
         gridString += "\n";
         for (int v: r)
            gridString += (v==0)?" .":String.format ("%3d", v);
      } // end for each row
      return gridString;
   } // end method toString

    // returns the number of blobs in this grid
   public int blobCount() {
      count = 0;
      index = 1;

      // initialize visited and id arrays
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++) {
            visited [i][j] = 0;
            id      [i][j] = 0;
         } // init visited and id arrays

      // count blobs
      for (int i = 0; i < rows; i++)
         for (int j = 0; j < cols; j++)
            if (grid[i][j] && visited[i][j] == 0) {
               count++;
               markBlob(i, j);
            } // end for each unvisited blob cell

      return count;
   } // end method blobCount

    // Mark position row, col as having been visited.
    // Check and if appropriate mark locations above, below, left,
    // and right of that position.
   private void markBlob(int row, int col) {
      if (row < 0   ) return; // these are out of grid locations
      if (row >= rows) return;
      if (col < 0   ) return;
      if (col >= cols) return;

      if (! grid [row][col]     ) return; // not in blobs
      if (visited [row][col] != 0) return; // already visited

      visited [row][col] = index++;
      id      [row][col] = count;

      markBlob(row - 1, col    ); // up
      markBlob(row + 1, col    ); // down
      markBlob(row    , col - 1); // left
      markBlob(row    , col + 1); // right
   } // end method markBlob

} // end class GridND2

Sample Output from Newer Version:

Input percentage probability (0 to 100): 50

XXX-----X---XXXX-X--        1   4   5   0   0   0   0   0 10   0   0   0 21 23 24 25   0 113   0   0
XX-X-XXXX-X-X--XXXX-        2   3   0 20   0 14 13 12 11   0 115   0 22   0   0 26 111 112 114   0
-X-XXX---X---X-X----        0   6   0 19 16 15   0   0   0 116   0   0   0 117   0 27   0   0   0   0
-X-XX-XXX-XXXX-XXX-X        0   7   0 18 17   0 56 55 57   0 121 120 119 118   0 28 100 101   0 122
XX---X-X-X-----X-XX-        9   8   0   0   0 123   0 54   0 124   0   0   0   0   0 29   0 102 110   0
---X--XXX-XXXXXX-X-X        0   0   0 125   0   0 62 53 52   0 44 43 39 38 31 30   0 103   0 126
-XX-XXXXXXXXX-X-XX--        0 73 74   0 64 63 61 58 51 50 45 42 40   0 32   0 109 104   0   0
XX--X-XX--X-X-XX-X--       75 72   0   0 65   0 60 59   0   0 46   0 41   0 33 37   0 105   0   0
-XXXXX--XXX--XXX-XX-        0 71 70 67 66 99   0   0 49 48 47   0   0 35 34 36   0 106 108   0
X-XX--XX---XX----X-X      127   0 69 68   0   0 91 92   0   0   0 128 141   0   0   0   0 107   0 142
-XX--XXXX--X-XX----X        0 98 76   0   0 89 90 93 97   0   0 129   0 146 147   0   0   0   0 143
--XXXXXX-XXXX-XX-X-X        0   0 77 78 87 88 95 94   0 134 131 130 138   0 148 149   0 150   0 144
X--X--X-XXX-XX---X-X      152   0   0 79   0   0 96   0 137 133 132   0 139 140   0   0   0 151   0 145
---XXX---X-X----X-X-        0   0   0 80 83 84   0   0   0 135   0 153   0   0   0   0 204   0 205   0
XX-XXX-X-X-X-XXX-X--      206 209   0 81 82 85   0 183   0 136   0 154   0 172 171 170   0 210   0   0
X---X--XX-XX-X-XX-XX      207   0   0   0 86   0   0 182 181   0 156 155   0 173   0 169 174   0 211 212
X-XX-XXXXXX----X-X-X      208   0 200 199   0 203 185 184 180 179 157   0   0   0   0 168   0 218   0 213
--XX--X--XX---XXX--X        0   0 201 198   0   0 186   0   0 178 158   0   0   0 166 167 176   0   0 214
X--XXXXX--XXXXXX--XX      219   0   0 197 194 193 187 190   0   0 159 160 163 164 165 175   0   0 217 215
--XXX-XXXX-XX-X-XX-X        0   0 202 196 195   0 188 189 191 192   0 161 162   0 177   0 220 221   0 216

1 1 1 . . . . . 2 . . . 3 3 3 3 . 3 . .
1 1 . 2 . 2 2 2 2 . 4 . 3 . . 3 3 3 3 .
. 1 . 2 2 2 . . . 5 . . . 6 . 3 . . . .
. 1 . 2 2 . 3 3 3 . 6 6 6 6 . 3 3 3 . 7
1 1 . . . 8 . 3 . 9 . . . . . 3 . 3 3 .
. . . 10 . . 3 3 3 . 3 3 3 3 3 3 . 3 . 11
. 3 3 . 3 3 3 3 3 3 3 3 3 . 3 . 3 3 . .
3 3 . . 3 . 3 3 . . 3 . 3 . 3 3 . 3 . .
. 3 3 3 3 3 . . 3 3 3 . . 3 3 3 . 3 3 .
12 . 3 3 . . 3 3 . . . 13 13 . . . . 3 . 14
. 3 3 . . 3 3 3 3 . . 13 . 15 15 . . . . 14
. . 3 3 3 3 3 3 . 13 13 13 13 . 15 15 . 16 . 14
17 . . 3 . . 3 . 13 13 13 . 13 13 . . . 16 . 14
. . . 3 3 3 . . . 13 . 18 . . . . 19 . 20 .
21 21 . 3 3 3 . 18 . 13 . 18 . 18 18 18 . 22 . .
21 . . . 3 . . 18 18 . 18 18 . 18 . 18 18 . 23 23
21 . 18 18 . 18 18 18 18 18 18 . . . . 18 . 24 . 23
. . 18 18 . . 18 . . 18 18 . . . 18 18 18 . . 23
25 . . 18 18 18 18 18 . . 18 18 18 18 18 18 . . 23 23
. . 18 18 18 . 18 18 18 18 . 18 18 . 18 . 26 26 . 23

There are 26 blobs.

Earlier version:

Here is a typical run:

Input percentage probability (0 to 100): 50 X-XX-X---XXXXXXXXX-X 1 0 77 78 0 80 0 0 0 44 45 48 49 52 53 56 57 75 0 81 X--X--X-XXXXXXXXX-X- 2 0 0 79 0 0 82 0 42 43 46 47 50 51 54 55 58 0 73 0 XXX---X-X--X---XXXXX 3 6 7 0 0 0 83 0 41 0 0 76 0 0 0 65 59 71 72 74 X-X-XX-XX----XXXX--- 4 0 8 0 16 15 0 39 40 0 0 0 0 69 66 64 60 0 0 0 X-X--X-X-X---XXXXX-X 5 0 9 0 0 14 0 38 0 84 0 0 0 68 67 63 61 70 0 85 --XXXXXX--X-X---X--X 0 0 10 11 12 13 17 37 0 0 87 0 90 0 0 0 62 0 0 86 ------X--XX---X---X- 0 0 0 0 0 0 18 0 0 89 88 0 0 0 91 0 0 0 92 0 -XX-XXX-----X---XX-- 0 36 35 0 24 23 19 0 0 0 0 0 93 0 0 0 94 95 0 0 --XXX-XX-X-X-XXX-XXX 0 0 34 33 25 0 20 22 0 99 0 101 0 108 109 121 0 96 97 98 -X--X-X--X-X-XXXX--- 0 123 0 0 26 0 21 0 0 100 0 102 0 107 110 120 119 0 0 0 ---XX---X--XXXX-X--X 0 0 0 28 27 0 0 0 124 0 0 103 104 106 111 0 118 0 0 125 -XXX-XX--XX-X-XXX--- 0 32 31 29 0 126 127 0 0 134 135 0 105 0 112 116 117 0 0 0 X--X--XXXXXX--XXX-XX 138 0 0 30 0 0 128 129 132 133 136 137 0 0 113 115 122 0 140 141 X------XX---X-X----X 139 0 0 0 0 0 0 130 131 0 0 0 143 0 114 0 0 0 0 142 --XX-X-----XXX-X---- 0 0 172 173 0 174 0 0 0 0 0 147 144 150 0 155 0 0 0 0 X---X---X--XXXXXXXXX 175 0 0 0 179 0 0 0 180 0 0 146 145 149 151 154 156 157 170 171 X-X---XX-X-X--XX-X-- 176 0 181 0 0 0 182 184 0 185 0 148 0 0 152 153 0 158 0 0 X--X--X-X--------X-- 177 0 0 186 0 0 183 0 191 0 0 0 0 0 0 0 0 159 0 0 X--XXX----X---XXXXXX 178 0 0 187 188 190 0 0 0 0 192 0 0 0 166 164 163 160 168 169 ----X-XXX-X-X--XXXX- 0 0 0 0 189 0 194 195 196 0 193 0 197 0 0 165 162 161 167 0 There are 35 blobs.

Code:
//---------------------------------------------------------------------- // BlobApp.java          by Dale/Joyce/Weems                   Chapter 4 // // Instantiates a Grid based on a percentage probability provided by the // user and reports the number of blobs in the Grid. //---------------------------------------------------------------------- // Nick Duchon - modifications // Date: Oct 5, 2008 import java.util.Scanner; public class BlobAppND { static int [][] test = {{1,1,0,1},                    {0,1,0,1},                    {1,1,0,1},                    {0,1,1,1}                   }; // end test array public static void main(String[] args) {     Scanner conIn = new Scanner(System.in);     final int GRIDR = 20;   // number of grid rows     final int GRIDC = 20;   // number of grid columns     // Get percentage probability of blob characters     int percentage;           System.out.print("Input percentage probability (0 to 100): ");     if (conIn.hasNextInt())       percentage = conIn.nextInt();     else     {       System.out.println("Error: you must enter an integer.");       System.out.println("Terminating program.");       return;     }     System.out.println();     // create grid     GridND grid = new GridND(GRIDR, GRIDC, percentage); //     Grid grid = new Grid(test);         // display grid and blob count     int c = grid.blobCount();     System.out.println(grid);     System.out.println("\nThere are " + c + " blobs.\n"); } // end main } // end class BlobAppND

//---------------------------------------------------------------------- // Grid.java              by Dale/Joyce/Weems                  Chapter 4 // // Supports grid objects consisting of blob and non-blob characters. // Allows the number of blobs it contains to be counted. //---------------------------------------------------------------------- import java.util.Random; public class GridND { protected int rows;         // number of grid rows protected int cols;         // number of grid columns     protected boolean [][] grid;     // the grid containing blobs int [][] visited;            // used by blobCount int index = 1; public GridND (int [][] g) {     rows = g.length;     cols = g[0].length;     grid = new boolean [rows][cols];     visited = new int [rows][cols]; // true if location visited     for (int r = 0; r < g.length; r++)       for (int c = 0; c < g[r].length; c++)         grid [r][c] = (g[r][c] == 1)?true:false; } // end 2-d int constructor public GridND (int rows, int cols, int percentage) // Preconditions: rows and cols > 0 //                0 <= percentage <= 100 // // Instantiates a grid of size rows by cols, where locations are set to // indicate blob characters based on the percentage probability. {     this.rows = rows;     this.cols = cols;     grid = new boolean [rows][cols];     visited = new int [rows][cols]; // true if location visited     // to generate random numbers     int randInt;     Random rand = new Random();     for (int i = 0; i < rows; i++)       for (int j = 0; j < cols; j++)       {         randInt = rand.nextInt(100); // random number 0 .. 99         if (randInt < percentage)           grid[i][j] = true;         else           grid[i][j] = false;       } } // end int int int constructor public String toString() {     String gridString = "";     for (int i = 0; i < rows; i++)     {       for (int j = 0; j < cols; j++)       {         if (grid[i][j])           gridString = gridString + "X";         else           gridString = gridString + "-";        }        gridString += "     ";        for (int j = 0; j < cols; j++) {          gridString += String.format ("%4d", visited[i][j]);        } // end for each row in the visited matrix also       gridString = gridString + "\n";   // end of row     }     return gridString; } // end toString method public int blobCount() // returns the number of blobs in this grid {     int count = 0;         // initialize visited     for (int i = 0; i < rows; i++)       for (int j = 0; j < cols; j++)         visited[i][j] = 0;           // count blobs     for (int i = 0; i < rows; i++)       for (int j = 0; j < cols; j++)         if (grid[i][j] && visited[i][j] == 0)         {           count++;           markBlob(i, j);         }        return count; } // end blobCount method private void markBlob(int row, int col) // Mark position row, col as having been visited. // Check and if appropriate mark locations above, below, left, // and right of that position. {     visited[row][col] = index++;        // check above     if ((row - 1) >= 0)           // if its on the grid       if (grid[row - 1][col])       // and has a blob character         if (visited[row - 1][col] == 0)   // and has not been visited           markBlob(row - 1, col);       // then mark it         // check below     if ((row + 1) < rows)        // if its on the grid       if (grid[row + 1][col])       // and has a blob character         if (visited[row + 1][col] == 0)   // and has not been visited           markBlob(row + 1, col);       // then mark it         // check left     if ((col - 1) >= 0)           // if its on the grid       if (grid[row][col - 1])       // and has a blob character         if (visited[row][col - 1] == 0)   // and has not been visited           markBlob(row, col - 1);       // then mark it         // check right     if ((col + 1) < cols)        // if its on the grid       if (grid[row][col + 1])       // and has a blob character         if (visited[row][col + 1] == 0)   // and has not been visited           markBlob(row, col + 1);       // then mark it } // end method markBlob } // end class GridND