ClusterDetection

Find the largest square cluster in a matrix.

Exercise

1. Create the matrix

• The matrix should be a 2D array consisting of two randomly distributed values or characters, e.g. 'X' and 'O'.
• Being able to change the ratio of the values could be advantageous.

2. Find the clusters

• Find the positions and sizes of all square submatrices of a certain minimum size that only contain one of the characters.
• Ideally, clusters should not intersect.

3. Print the result

• Print the matrix and highlight the largest cluster by changing the text color.
• If more than one cluster of that size is present, highlight all of them.
• Optionally printing a summary would make sense.

4. Performance test [optional]

• Measure the runtime of each function.
• Test the functions with different parameters and see how well they scale.

My solution

Starting the program you will be greeted with a small menu.

Menu options

Run once: Creates one random matrix, finds square clusters and prints the results.

Performance test: Executes a set of test cases, calculates the average runtimes and prints out the timings.

Help: Prints a description of the options.

Quit: Ends the program.

Parameters

Run once:

• Size of the matrix
• Enable highlighting all clusters
• Enable overlapping
• Minimum cluster size to be recognized
• Factor to increase the probability for 'X' to appear

Performance test:

• Amount of test cases
• Runs per case
• Size of the matrix at the start
• Size increment for every new case

Parameters can be set via the function calls in main

if choice is "1":
    run(matrix_size=15, show_all_clusters=False, no_overlap=True)
elif choice is "2":
    performance_test(cases=15, runs=3, start_size=10, increment=10)

Examples

Multiple large clusters

Show all clusters

Overlap enabled

Performance test