Matching first and last of items in list

Question

My goal is to iterate over a list of names and return True only if they can be arranged so the last letter of a name is the same as the first letter of the next name.

class Team(object):
    def __init__(self, names):
        self.names = names

    def __iter__(self):
        from collections import Counter
        first = Counter(map(lambda n: n[0].lower(), self.names))
        last = Counter(map(lambda n: n[-1].lower(), self.names))
        diff = last - first
        return any(diff.values()) <= 1

def isCoolTeam(team):
    return bool(Team(team))

print(isCoolTeam(["Rob", 
 "Bobby", 
 "Billy"]))

It should return False, but for some reason every input returns true.

Answer 1

Here are a few modifications. It doesn't seem to make sense to convert a Team to a boolean, so I wouldn't define __bool__ but explicitely define is_cool instead.

Also, I think you wanted to check if no difference is higher than 1. In this case, you'd need all(v <= 1 for v in diff.values()):

class Team(object):
    def __init__(self, names):
        self.names = names

    def is_cool(self):
        from collections import Counter
        first = Counter(map(lambda n: n[0].lower(), self.names))
        last = Counter(map(lambda n: n[-1].lower(), self.names))
        diff = last - first
        return all(v <= 1 for v in diff.values())

print(Team(["Rob", "Bobby", "Billy"]).is_cool())
# False
print(Team(["Rob", "Nick", "Bobby", "Yann"]).is_cool())
# True

There's still a (big) problem with the logic, though:

print(Team(["Ab", "cd", "ef"]).is_cool())
# True

I don't think a Counter is enough to solve this problem. You'll probably need to define a graph and see if there's a path connecting every name. NetworkX might help.

Here's a description of the related graph problem.

Answer 2

Your problem is one of pairing elements. You want to match a particular first letter with a corresponding last letter, over and over again, until all the names are exhausted.

If you think about it, when you are done you will have one unpaired first letter at the start, and one unpaired last letter at the end:

Rob->Bobby->Yannick->Karl->Luigi->Igor->Renee->Edmund->David->Diogenes

That means the subtraction of letter counts should be 1, in both directions: there should be 1 first letter unmatched, and 1 last letter unmatched (first-last, and last-first). But, if there are repeated letters, even this may not be enough. You want to check the length of the list (to make sure it's valid) and then check for the differences being <= 1.

Suppose you have a list of length 0: the counts of first/last letters will be empty but the list is too short.

Suppose you have a list of length 1: the counts of first/last letters will be 1 and 1, which meets the requirements.

Suppose you have a list of length 2:

• Suppose there is no overlap: ['rob', 'diane'] Then the total counts of first/last letters will be 2 and 2, violating the requirement.

• Suppose there is no overlap, but shared letters: ['brad', 'betty'] Then the total counts of the first/last letters will be 2 and 2, but arranged differently. I think you should sum the counts. ;-)

• Suppose there is total overlap: ['bob', 'bob']. This leaves empty subtractions, which meets the requirement.

• Suppose there is partial overlap: ['bob', 'betty']. This leaves counts of {b:1} and {y:1} respectively, so it works.

You have to deal with cases where the difference is empty, where the difference has one element that contains a count of 2+, and where the difference has more than one element with counts of 1 or more.

I don't think you want any(). I think you need an aggregating function of some kind. I suspect sum() will work.

Answer 3

The function any() returns a boolean (True / False) and all booleans are less than or equal to (<=) 1.

This means that the line:

return any(diff.values()) <= 1

will always evaluate to True.