Evolving Strings with Genetic Algorithms

In this problem, you are given a target string along with parameters for a genetic algorithm: population size, mutation rate, and the maximum number of generations. Your task is to implement a genetic algorithm that evolves a population of candidate strings toward matching the target string exactly.

The genetic algorithm must follow these steps:

• Create Individual: Generate a random string of the same length as the target using characters from the set \(\{A-Z, ',', ' ', '!'\}\).
• Calculate Fitness: Compute the fitness of a string as the number of positions in which the candidate matches the target.
• Crossover: Perform a single-point crossover between two parent strings.
• Mutation: Mutate the string by randomly changing characters with a given mutation rate.

For reproducibility, you must use a fixed random seed. The algorithm should run until either an exact match to the target string is found or until the maximum number of generations is reached. In the latter case, output the target string to ensure deterministic behavior for grading purposes.

inputFormat

The input consists of four lines:

1. The target string \(T\) (for example, "HELLO, WORLD!").
2. An integer \(N\) representing the population size.
3. A floating-point number \(r\) representing the mutation rate (e.g., 0.01).
4. An integer \(G\) representing the maximum number of generations.

outputFormat

Output a single line to stdout containing the evolved string that exactly matches the target string.

## sample

HELLO, WORLD!
200
0.01
1000

HELLO, WORLD!

</p>