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:

• 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.