Solving Good Groups Using Dictionaries

Hello!

We’re going to solve a problem here using Python dictionaries. I’m assuming that you’ve already studied the first eight chapters of Learn to Code by Solving Problems. If you have, you know how powerful Python dictionaries can be. Whenever you need to make an association between two groups of data, a dictionary is likely what you want to use – that’s why we used dictionaries to solve two tough problems in Chapter 8!

Multiple Approaches

When you’re learning to program, there’s a lot to contend with. You have to learn the Python syntax; i.e. the rules for writing code that will even run. Then you have to learn how to put the pieces of syntax together to accomplish things, like fully solving a problem. You have to choose the proper data structures for storing your data, otherwise – as we learned in Chapter 8 – your code may be too slow.

You also need to decide on the overall solution approach for each problem. I think the fact that a problem can have multiple dramatically different solutions in the first place is a surprise to many beginning programmers… so much so that it may feel like there is really only one way to solve a problem. But that kind of thinking can lead to going down a garden path where the problem seems really challenging, the code is tricky, and there are many special cases to contend with. One of the skills to cultivate when moving from a beginning programmer to an intermediate programmer is detecting when this may be happening and revisiting the fundamental approach that we’re using.

It takes a lot of practice to be able to distinguish between two scenarios:

1. This problem is just really tough, no matter what we do! And
2. This problem is tougher than needed because of the solution approach that we’re using, and we can make it easier by finding a new approach.

We’re going to practice this skill now.

The problem we’ll solve is called Good Groups. It’s a problem from the 2022 Canadian Computing Competition (CCC). Don’t be intimidated! We’re going to take this down.

Please read the original problem description and then keep reading here.

I really like the Good Groups problem because there are at least two types of solutions, each of which I think some of my readers will naturally gravitate toward. Take some time to outline some solution ideas that come to mind as you read the problem description. (And don’t worry if nothing good seems to come to mind. Thinking about solving this problem, even if you feel that you’re not making progress, is very valuable. You might also be making some progress and not even know it!)

Check Each Group? Check Each Constraint?

I can come up with two main ideas for solving the problem:

1. Go through the groups and figure out how many constraints each one violates. For example, we’ll consider a group like DWAYNE BEN ANJALI, then check the constraints to figure out which ones are violated by this group.
2. Go through each constraint and figure out if there’s a group that violates that constraint. For example, we’ll consider a constraint like “ELODIE and CHI must be in the same group”, then check whether these people are really in the same group.

In the first solution, our outer loop will be over the groups; in the second, our outer loop will be over the constraints. In each case, we need a Python dictionary to help us avoid a slow search (as we did in the Cities and States problem in Chapter 8). But, in my opinion, one of these approaches makes the problem considerably easier compared to the other…

Solution 1: Check Each Group

This is our group-centric solution. We have to loop through each group and find the constraints that it violates. Here’s the code that I came up with.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
x = int(input())
# These are the constraints on students who must be in the same group
# The dictionary maps person p to the set of people that must be in p's group
same_constraints = {}
for i in range(x):
    names = input().split()
    name1 = names[0]
    name2 = names[1]
    if name1 not in same_constraints:
        same_constraints[name1] = set()
    same_constraints[name1].add(name2)
    if name2 not in same_constraints:
        same_constraints[name2] = set()
    same_constraints[name2].add(name1)

y = int(input())
# These are the constraints on students who must be in different groups
# The set is a set of pairs of people that must be in different groups
different_constraints = set()
for i in range(y):
    names = input().split()
    names.sort()
    different_constraints.add(tuple(names))

g = int(input())

different_violated = 0
same_violated = 0

for i in range(g):
    
    # **Different-group violations**
    names = input().split()
    names.sort()
    # There are three pairs of students to check for different-group violations
    check1 = (names[0], names[1])
    check2 = (names[1], names[2])
    check3 = (names[0], names[2])
    for constraint in [check1, check2, check3]:
        if constraint in different_constraints:
            different_violated = different_violated + 1
            different_constraints.remove(constraint)

    # **Same-group violations**
    for name in names:
        if name in same_constraints:
            for other in same_constraints[name]:
                if other not in names:
                    same_violated = same_violated + 1

print(different_violated + same_violated // 2)

IMO there’s a ton of stuff going on here. For example:

• We keep track of the different_constraints (19) using just a set of tuples, one tuple for each such constraint. But we store the same_constraints (4) in a more complicated way, as a dictionary that maps from a person’s name to the set of people involved with them in a same-group constraint.
• We use sorting when storing (22) and processing (34) the different-group constraints. Why? It’s so that we only have to consider three pairs of students. Consider the group DWAYNE BEN ANJALI. We would sort it to become ANJALI BEN DWAYNE. Now we have to look at each of the following pairs of students for different-group constraint violations:
  1. ANJALI BEN
  2. BEN DWAYNE
  3. ANJALI DWAYNE

If we didn’t sort, we’d also have to look at pairs that were out of sorted order, such as BEN ANJALI. Sorting just helps us cut down on the number of pairs we have to check.

• We remove (42) a different-group constraint once we use it. The reason is that we want to count each constraint only once – by removing it we’re guaranteed not to count it multiple times.
• We can see why we need the more complicated same_constraints data structure when we process the same-group constraints (47): it immediately gives us the set of people that must be in the same group as name. We then check whether each of those constraints is violated by this group (48).
• When we add up different_violated and same_violated to get the total violations (51), we divide same_violated by 2. Why? The reason is similar to the reason that we divided by 2 when solving Cities and States in Chapter 8: we double-count each violation of a same-group constraint, so we divide by 2 to undo that.

Solution 2: Checking Each Constraint

Feeling kinda overwhelmed by Solution 1? If you are, that’s actually a good thing :) because you’re starting to hone your ability to identify when a solution strategy is pushing against the grain.

Let’s compare that group-centric solution to our constraint-centric solution. We now have to loop through each constraint and determine whether it’s violated by some group. Here’s the code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
x = int(input())
same_constraints = []
for i in range(x):
    same_constraints.append(input().split())

y = int(input())
different_constraints = []
for i in range(y):
    different_constraints.append(input().split())

g = int(input())

name_to_group_num = {}

for i in range(g):
    names = input().split()
    for name in names:
        name_to_group_num[name] = i

different_violated = 0
same_violated = 0

# **Different-group violations**
for name1, name2 in different_constraints:
    if name_to_group_num[name1] == name_to_group_num[name2]:
        different_violated = different_violated + 1

# **Same-group violations**
for name1, name2 in same_constraints:
    if name_to_group_num[name1] != name_to_group_num[name2]:
        same_violated = same_violated + 1

print(different_violated + same_violated)

I feel like there’s a lot less going on here. Compared to our above solution:

• The same_constraints (2) and different_constraints (7) are just lists of pairs now.
• No more sorting anything.
• No more removeing anything.
• No more dividing anything by 2.

One important powermove in this solution is the name_to_group_num dictionary (13), which maps from each person’s name to the number of the group that they’re in. We need this for rocket-fast determination of whether a constraint is violated. A different-group constraint is violated if the dictionary tells us that the two people are actually in the same group (25); a same-group constraint is violated if the dictionary tells us that the two people are actually in different groups (30).

Keep Going!

There are many reasons for why learning to program is difficult. Writing the code in the first place is hard enough. At the same time, learners may choose a solution approach that leads to very tricky code, or more code than needed… and I just said that writing code is hard! More experienced programmers therefore have at least two advantages: being able to simplify the code that they’ll need to write before they even start writing it, and writing code more accurately for the code that they really do need to write.

If you’ve been struggling to learn to program, keep that in mind: soon you’re not only going to be better at the actual typing-in-the-code part of programming, but you’ll also get better at making that code more straightforward and less error-prone in the first place.

Practice, practice! Please check the growing list of exercises for even more practice with the material from the book.

Happy learning!