Recursion and Blobs - top of Musings page

By: Nicholas Duchon.


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:

  1. up
  2. down
  3. left
  4. 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:

// 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
 
 

ND.