Modules - Data Structures, Recursion
Teacher’s Notes:
=======================================
This is a very challenging exercise if students are not familiar with recursion.
Below my solution is the code for a bacteria map generator so that you can make new maps of whatever size you may want to use. You can also change the distribution of different bacteria strains by altering the chance of generating each one.
Assignment:
=======================================
A biological researcher places three different types of bacteria (A, B, and C) into a petri dish to see how quickly they grow when placed together. After a while, the researcher takes a cross section of the dish that is a single cell in thickness and analyzes it to find the largest culture of each type of bacteria. They then note the size of the largest colony of each bacterial strain. In this case, a colony is defined as the largest connected group of a given type of bacteria.
Write a program that reads an integer x that represents the length of the sample and another integer y that represents the width of the sample. The program will then read x Strings that are made up of the characters X, A, B, and C. The character X indicates an uninfected portion of the petri dish. The letters A, B, and C indicate a section of the petri dish that is infected by Bacteria A, Bacteria B, and Bacteria C repspectively. These strings each represent one row of the petri dish sample. Bacteria in colonies are said to be connected if they are adjacent (up, down, left or right) of each other.
Your program should then output the type and size of the largest colony by outputting the character of the bacteria type and the size of the largest colony. If there are two or more colonies of different bacteria that are the same size, the program will print out the word "Tie".
Sample Input 1
5
5
AXBCC
CBCCB
BACBB
AAAAX
ACXBC
Sample Output 1
A6
Explanation of Sample Output 1
Looking at the Strings as a grid, you will see that the A in the lower left corner is part of a group (colony) of Bacteria A. This is adjacent to the A above it which is in turn connected to 3 other A's horizontally. The second of these A's is connected to the A in the middle row and thus, there are 6 A's in this group. Other letters form groups but none of them are as large as this group.
Solution (JAVA):
=======================================
import java.util.Scanner;
public class Main {
public static int count(char[][] grid, int x, int y, char letter){
int sum = 1;
char oldLetter = letter;
grid[x][y] = 'X';
if(grid[x+1][y] == oldLetter)
sum += count(grid, x+1, y, letter);
if(grid[x-1][y] == oldLetter)
sum += count(grid, x-1, y, letter);
if(grid[x][y+1] == oldLetter)
sum += count(grid, x, y+1, letter);
if(grid[x][y-1] == oldLetter)
sum += count(grid, x, y-1, letter);
return sum;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int length = input.nextInt();
int width = input.nextInt();
/*
In this section, I am reading in the character strings and storing them in a 2D array. I am also adding a border of X's around the map. When I start the recursion, I will start it at (1,1) instead of (0,0). Since the border is all of X's, the recursion will never go out of bounds and thus, I do not need to check if the array is out of bounds (Since that can't happen).
*/
char[][] grid = new char[length+2][width+2];
for(int y = 0; y < width+2; y++)
grid[0][y] = 'X';
for(int x = 1; x < length+1; x++)
grid[x] = ("X" + input.next() + "X").toCharArray();
for(int y = 0; y < width+2; y++)
grid[length+1][y] = 'X';
//Test code for printing the grid to make sure I loaded it right
/*
for(int x = 0; x < grid.length; x++) {
for(int y = 0; y < grid[0].length; y++) {
System.out.print(grid[x][y]);
}
System.out.println();
}
*/
int maxA = 0, maxB = 0, maxC = 0, currentCount = 0;
char currentLetter = 'X';
for(int x = 1; x < length+1; x++)
for(int y = 1; y < width+1; y++)
if(grid[x][y] != 'X')
{
currentLetter = grid[x][y];
currentCount = count(grid,x,y,currentLetter);
if(currentLetter == 'A' && currentCount > maxA)
maxA = currentCount;
if(currentLetter == 'B' && currentCount > maxB)
maxB = currentCount;
if(currentLetter == 'C' && currentCount > maxC)
maxC = currentCount;
}
if(maxA > maxB && maxA > maxC)
System.out.println("A" + maxA);
else if(maxB > maxA && maxB > maxC)
System.out.println("B" + maxB);
else if(maxC > maxB && maxC > maxA)
System.out.println("C" + maxC);
else
System.out.println("Tie");
}
}
Bacteria Pattern Generator:
=========================================
/*
You can adjust the distribution of each bacterium species by altering the double values below. I have set it in this example to be 20% chance to generate a bacteria A, an additional 15% chance to generate bacteria B (20%+15% = 35% --> that's why it is 0.35) and an additional 25% chance to generate bacteria C (35% + 25% = 60%).
*/
public class Builder {
public static void main(String[] args) {
double percentageInfectionA = 0.2;
double percentageInfectionB = 0.35;
double percentageInfectionC = 0.60;
char[][] dish = new char [100][100];
for(int x = 0; x < dish.length; x++)
for(int y = 0; y < dish[0].length; y++)
{
if(Math.random()<= percentageInfectionA)
dish[x][y] = 'A';
else if(Math.random()<= percentageInfectionB)
dish[x][y] = 'B';
else if(Math.random()<= percentageInfectionC)
dish[x][y] = 'C';
else
dish[x][y] = 'X';
}
//TEST CODE:
for(int x = 0; x < dish.length; x++)
{
for(int y = 0; y < dish[0].length; y++)
{
System.out.print(dish[x][y]);
}
System.out.println();
}
}
}
