1
\$\begingroup\$

Can you comment, review or suggest things for this? Maybe it should be broken into two methods?

friends is a list of strings of 'T' or 'F' characters representing a friendship relation.

For example for 3 people we could have

friends = ['FTF','TFT','FTF']

This means that

  • person 0 is friends with person 1 (since friends[0][1] == 'T'),
  • person 1 is friends with both person 0 and person 2 and
  • person 2 is friends with person 1.

The method below finds the number of friends, friends of friends and friends of friends of friends of a person for each person as well as the person with the highest such count

def mostThreeFriends(self,friends):
    best = 0
    self.nFriends = {}
    for i in range(0,len(friends)):
        count = 0
        for j in range(0,len(friends[i])):
            if i == j:
                continue
            # direct friends
            if friends[i][j] == 'T':
                count += 1
            else:
                doneCounting3 = False
                # check whether i and j have a friend k in common
                for k in range(0, len(friends)):
                    if doneCounting3:
                        break
                    if k == i or k == j:
                        continue
                    if friends[i][k] == 'T' and friends[j][k] == 'T':
                        count += 1
                        break
                    else:   
                        for p in range(0, len(friends)):
                            if p == k or p == i:
                                continue
                            if friends[i][p] == 'T' and friends[p][k] == 'T' and friends[k][j] == 'T':
                                count += 1
                                doneCounting3 = True
                                break
        self.nFriends[i] = count
        best = max(best, count)

    return best
\$\endgroup\$
1
  • \$\begingroup\$ For ['FFT', 'FFF', 'FTF'], what do you believe the friend count for person 0 should be, and why? \$\endgroup\$ Jun 5 '15 at 21:00
3
\$\begingroup\$

There seems to be no reason to define self.nFriends as an instance variable. Define it instead as a function local one.

Then you have no use for the self parameter, so consider making it a stand-alone function, or at least a staticmethod.

Stick to PEP 8. No reason not to. I'll be working with a PEP 8-ified version of the code.

Instead of initializing best and doing a manual reduction with max, instead make a count_three_friends iterable and use max to reduce it:

def count_three_friends(friends):
    n_friends = {}
    for i in range(0, len(friends)):
        ...
        n_friends[i] = count
        yield count

def most_three_friends(friends):
    return max(count_three_friends(friends))

n_friends is not used. Remove it.

You can flatten this a bit by taking account of early loop exits:

def count_three_friends(friends):
    for i in range(0, len(friends)):
        count = 0
        for j in range(0, len(friends[i])):
            if i == j:
                continue
            # direct friends
            if friends[i][j] == 'T':
                count += 1
                continue

            done_counting3 = False
            # check whether i and j have a friend k in common
            for k in range(0, len(friends)):
                if done_counting3:
                    break
                if k == i or k == j:
                    continue
                if friends[i][k] == 'T' and friends[j][k] == 'T':
                    count += 1
                    break
                for p in range(0, len(friends)):
                    if p == k or p == i:
                        continue
                    if friends[i][p] == 'T' and friends[p][k] == 'T' and friends[k][j] == 'T':
                        count += 1
                        done_counting3 = True
                        break

        yield count

Change range(0, ...) to just range(...).

Try to use enumerate and replace 'T'/'F' with booleans. I'll initially use enumerate and discard the second parameter to keep the transition small.

Then consider that your structure is

for each person:
    and each other person:
        if friends, count += 1
        or indirect friends, count += 1

The "or indirect friends" bit could be a separate function to avoid the done_counting3 variable:

def indirect_friend(friends, i, j):
    for k, _ in enumerate(friends):
        if k == i or k == j:
            continue

        # If  friends[i] is friends with friends[k]
        # and friends[j] is friends with friends[k]
        if friends[i][k] and friends[j][k]:
            return True

        for p, _ in enumerate(friends):
            if p == k or p == i:
                continue

            if friends[i][p] and friends[p][k] and friends[k][j]:
                return True

def count_three_friends(friends):
    for i, _ in enumerate(friends):
        count = 0

        for j, _ in enumerate(friends):
            # Don't look at self-friending
            if i == j:
                continue

            # Direct or once-indirect friend
            if friends[i][j] or indirect_friend(friends, i, j):
                count += 1

        yield count

def most_three_friends(friends):
    return max(count_three_friends(friends))

Note that

# If  friends[i] is friends with friends[k]
# and friends[j] is friends with friends[k]

seems to be wrong; this means

most_three_friends([[0, 1, 0], [0, 0, 0], [0, 1, 0]])

gives 2 despite no person's friend having any friends. This of course will only happen if the friendship graph is non-symmetric, but you've not required that it is.

I suggest reversing the second line to

# and friends[k] is friends with friends[j]

by changing friends[j][k] to friends[k][j].


Now, instead of getting deeper into how this could be improved, I'm going to express this as a matrix transformation. Consider the matrix X.

[[X, X, X],
 [X, X, X],
 [X, X, X]]

The kth person's list of friends is the list X[k, :] - take a single of the first dimension and the first of the second.

The matrix X[k, :, newaxis] in Numpy is thus the same with another dimension:

[[a],
 [b],
 [c]]

Now, this can be multiplied with the original as

[[a],     [[X, X, X],     [[a*X, a*X, a*X],
 [b],  *   [X, X, X],  =   [b*X, b*X, b*X],
 [c]]      [X, X, X]]      [c*X, c*X, c*X]]

This operation thus filters the friend list by the person's friends. You can then do an any along the y-axis to find once-indirect friends.

(friends[k, :, newaxis] * friends).any(axis=1)

The magic of Numpy's broadcasting lets us do all k at the same time by just taking a slice.

(friends[:, :, newaxis] * friends).any(axis=1)

This is a bit cryptic, but it's also an extremely powerful way of modelling the situation. For example, to calculate the transitive closure of friendship (find the number of people you are friends through any number of indirections), such a model becomes extremely helpful.

To use this, one could do

from numpy import array, identity, newaxis

def friend_problem(friends, iterations=2):
    # Include self-friendships for transitivity
    graph = arcs = friends | identity(len(friends), dtype=bool)

    # Apply search to graph
    for _ in range(iterations):
        graph = (graph[:, :, newaxis] * arcs).any(axis=1)

    # Subtract one for the self-friendship
    return graph.sum(axis=-1).max() - 1

And call it with

friends = array([[0, 1, 0], [0, 0, 0], [0, 0, 0]], dtype=bool)
friend_problem(friends)

Note that this works for any number of iterations; one can trivially do friends-of-friends-of-friends-of-friends-of-friends. This is not optimal for full transitive closure, but it's fine for small iteration counts. It's should also be a fair bit faster.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.