Teacher’s Notes:
=======================================
I have been coping with the loss of replit since they stopped supporting education. Thus, I have adapted this assignment for testing my students. They will be given one period (80min) to complete this programming task. The marking can be simplified by the table at the top of the document. They will also need to submit their code for evaluation.
For some reason, the tables are not copying into this document very well and you may need to create the table in your own document.
The solutions for the samples at my github account are:
Solutions:
|
Sample Number
|
Largest Group Type
|
Largest Group Size
|
|
1
|
B
|
25
|
|
2
|
Tie
|
|
|
3
|
B
|
53
|
|
4
|
C
|
54
|
|
5
|
A
|
44
|
Assignment:
=======================================
Bacterial Culture
|
Sample Number
|
Largest Group Type
|
Largest Group Size
|
|
1
|
|
|
|
2
|
|
|
|
3
|
|
|
|
4
|
|
|
|
5
|
|
|
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 can store the state of a 100 x 100 sample of bacteria. The program will read 100 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 respectively. 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. Note, that you can use any structure you like to store this data.
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".
You will run this program on 5 different bacterial samples and record the answer in the chart above. Each sample can be found at:
Sample Input 1
(using a 5x5 grid for simplicity)
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 = 100;//input.nextInt();
int width = 100;//input.nextInt();
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(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");
}
}
