Spreading Spores

Modules - CSE2130 Data Structures

Teacher’s Notes:

=======================================

This was inspired by the USACO Problem "Cowntact Tracing" at https://usaco.org/index.php?page=viewproblem2&cpid=1037

This is not nearly the same problem but I did want to credit the source of inspiration.

I have included a Spore Pattern Generating Program that will help you generate test input strings. The generator has a 5% chance of generating an infected plant. You can increase this but it will be likely that all plants will end up infected if you change this number to be too high.

You can also modify this problem to ask how many days it would take for all plants to be infected.

Assignment:

=======================================

Spreading Spores

A large greenhouse owner keeps his plants in a row. Recently, some of the plants have been infected by fungal spores. After each day, an infected plant will infect the plants immediately adjacent to it. Once infected, the plant will not become healthy again. An infected plant cannot be infected by another infected plant. The length (L) of the row will always be such that 100 <= L <= 500;

You will be given a string composed of the letters "C" and "S" representing the current status of the plants where an "C" means that a plant is clear of any spores and "S" means that the plant is infected with spores. Write a program that will show what the status of the plants will be after seven (7) days.

*Note that the sample input and output may look like it is made of several rows but it is actually a single long string that is wrapping around multiple lines.

Sample Input 1:

CCCCCCSCSCCCCCCCCCCCCCCCCCCCCCSCCCCSCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCSCCCCCCCCCCCCCCCCCCCCCCSCCCCCCCCCCCCCCCSCCCCCCCCCCCSCCCCCSCCCCCCCCCCSCCCCSCCCCCCCCCCCSCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCSCCCCCCCCCCCCCCCSCSCCCCCCCCCCCSCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCSSCCCCCCCCCCCCCCCCCCSCCCCCCCCCCSCCCCCCCCCCCCCCCCCCCCCCSCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCSSSCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCSCCCC

Sample Output 1:

SSSSSSSSSSSSSSSSCCCCCCCSSSSSSSSSSSSSSSSSSSSCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCSSSSSSSSSSSSSSSCCCCCCCCSSSSSSSSSSSSSSSCSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCSSSSSSSSSSSSSSSCSSSSSSSSSSSSSSSSSSSSSSSSSSSSSCCCCCCCCCCCCCCCCCCCCCCCSSSSSSSSSSSSSSSSCCCCSSSSSSSSSSSSSSSSSSSSSSSSSSCCCCCCCCSSSSSSSSSSSSSSSCCCCCCCCCCCCCCCCCCCCCCCSSSSSSSSSSSSSSSSSCCCCCCCCCCCCCCCCCCCCCCCCSSSSSSSSSSSS

Solution (JAVA):

=======================================

import java.util.Scanner;

public class SpreadingSpores {

   public static void main(String[] args) {

       char[] originalConfiguration = new Scanner(System.in).next().toCharArray();
       char[] newConfiguration = new char[originalConfiguration.length];

       for(int day = 0; day < 7; day++)
       {
           for(int x = 0; x < newConfiguration.length; x++)
               newConfiguration[x] = 'C';

           for(int x = 0; x < originalConfiguration.length; x++) {
               if(originalConfiguration[x] == 'S') {
                   newConfiguration[x] = 'S';
                   if(x > 0)
                       newConfiguration[x-1] = 'S';
                   if(x < newConfiguration.length-1)
                       newConfiguration[x+1] = 'S';

               }
           }
           originalConfiguration = newConfiguration;
           newConfiguration = new char[originalConfiguration.length];
       }

       for(int x = 0; x < originalConfiguration.length; x++)
           System.out.print(originalConfiguration[x]);
       System.out.println();
   }

}

Spore Pattern Generator (JAVA):

=======================================

public class SporePatternGenerator {

   public static void main(String[] args) {
       String pattern = "";
       int randomSize = (int)(Math.random()*401+100);

       for(int x = 0;x < randomSize; x++)
           pattern += Math.random()>=0.05?"C":"S";

System.out.println(pattern);
}

}