Skip to content

Reducing Sets of Events

The Scavenger Hunt made it easy to identify the all-or-none sets of events as the children were simply grouped by last name. It is more common to have many sets of events that contain only 2 elements and it is up to you to combine the sets where possible and build a minimum number of completely independent sets. Let’s explore a short algorithm for doing that.

In the realm of sameness, there are two fundamental building blocks. The first is a single standalone item. The second is two items that need to be the same. For instance, A must be the same as B. Given a list of sets, where each set contains a single element or 2 elements that must be the same, the following pseudocode reduces that list to a minimum number of sets, where no 2 sets have any overlap.


Set-Merging Algorithm

master_list = list of sets, each containing 1 or 2 distinct elements

repeat
    new_list = empty list

    for each set m in master_list
        if m overlaps with any set n in new_list
            replace n with the union of m and n (m ∪ n)
        else
            append m to new_list

    master_list = new_list

until no more sets can be combined


This is a naive repeated overlap-merge: after each merge, the algorithm restarts scanning from the beginning until no overlaps remain. While simple to understand, it can be slow because every set is compared against every other set, and merges can trigger many repeated passes. In worst-case scenarios with heavily overlapping sets, the total work can grow to O(n³).

For the playground applications, this algorithm works wonderfully. For larger applications, however, it’s worth exploring more efficient approaches such as Union–Find (Disjoint Set Union), graph-based connected-component labeling, or interval/segment merging techniques that avoid repeated global rescans.

Test Your Skills

The following exercise gives you a chance to practice reducing a list of sets that might have overlap to a list of sets where no two sets overlap with each other. The number of distinct elements does not change, but any two sets that have overlap must be combined, resulting in a shorter list of all-or-none sets. Each set in the final list contains a group of elements that all must be the same in some way.

Exercise

Write a Python function to minimize a list of sets. Below is some starter code and a few test cases to help you verify your solution:

def minimize_all_or_none_sets(all_or_none_sets: list[set[str]]):

    # Reduce the number of sets in the list by
    # combining any sets that overlap.

    return all_or_none_sets


TESTS = [
            [{'A', 'B'}, {'C', 'D'}, {'E', 'F'}],  
            [{'A', 'B'}, {'B', 'C'}],  
            [{'A', 'B'}, {'B', 'C'}, {'C', 'D'}, {'E', 'F'}],
            [{'A', 'B'}, {'B', 'C'}, {'C', 'D'}, {'E', 'F'}, {'A'}, {'Z'}],
            [{'A', 'B'}, {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'X', 'Y'}, {'Z', 'Y'}, {'E', 'F'}, {'J', 'K'}, {'Z', 'P'}],
            [{'A'}, {'Z'}, {'Q'}, {'A', 'B'}, {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'X', 'Y'}, {'Z', 'Y'}, {'E', 'F'}, {'J', 'K'}, {'Z', 'P'}]
        ]


for test in TESTS:
    print(minimize_all_or_none_sets(test))
Expected answers for each test case... 
[{'A', 'B'}, {'C', 'D'}, {'E', 'F'}]

[{'A', 'B', 'C'}]  

[{'A', 'B', 'C', 'D'}, {'E', 'F'}]

[{'A', 'B', 'C', 'D'}, {'E', 'F'}, {'Z'}]

[{'A', 'B', 'C', 'D', 'E', 'F'}, {'P', 'X', 'Y', 'Z'}, {'J', 'K'}]

[{'A', 'B', 'C', 'D', 'E', 'F'}, {'P', 'X', 'Y', 'Z'}, {'Q'}, {'J', 'K'}]
  • The results above show all set elements sorted. Because sets are unordered, your results might not be in the same order. The elements of each set are what matters.

Thoroughly test your algorithm as it will be very helpful in the upcoming exercises!

A Few XP for Your Efforts

Before tackling your next exact cover problem, apply your new skills to the following puzzle and capture a few XP along the way!

Puzzle: Networking

Author: @Gladwell

Published Difficulty: Medium

Practice Makes Perfect

Puzzle: Snowflakes

Author: @Harry.B.

Published Difficulty: Medium

This puzzle is a slightly tougher test of your new skills. You’re given a 2D grid photo where each cell is either snow (*) or empty sky (.). Any two snow cells that touch vertically or horizontally belong to the same snowflake.

Your first step is to find all the snowflakes in the picture. There are more efficient ways to conquer this puzzle, but practicing the approach outlined above will serve you well if you later tackle Nurikabe. Notice the similarity between “building” snowflakes here and “building” islands in Nurikabe.

Start by treating each snow cell as its own snowflake. Then reduce the list using the algorithm above. The only difference is that snowflakes combine not by overlap, but by being adjacent. At the end, your list will contain only the complete snowflakes.