2
\$\begingroup\$

I have this old graded homework, I am looking how to improve the or shorten the code, I have some lines with over 200 chars.

to_pairs(network) does the opposite.

n_friends(network, n) gets a network (the second presentation) and returns a set of names of persons that have exactly n friends.

lonely(network) returns a set of names of people with only a single friend.

most_known(network) returns the name of the person with most friends.

common_friends(network, name1, name2) returns a set of common friends of the two persons.



by_n_friends(network) returns a dictionary with keys from 1 to len(mreza) - 1 and the corresponding sets of people with that number

of friends. For instance, for the small network, the function must return {1: {"D"}, 2: {"A", "B"}, 3: {"C"}}. See the example for the large network in the tests.

suggestions(network) returns a list of pairs that are not friends but have at least one common friend. The pair must be sorted

alphabetically (e.g. ("Ana", "Berta") and not ("Berta", "Ana")).

clique(network, names) returns True if all persons from the group names know each other, and False otherwise.

most_commons(network) returns the pair with the most mutual friends.



strangers(network, names) returns True if the group names contains absolute strangers - not even one pair knows each other -, and False

otherwise.

is_cover(network, names) returns True if the group "covers" the entire network in the sense that every person in the network is either

in the group or is a friend with someone in the group.

triangles(network) computes the number of "triangles" - triplets of people who know each other.



minimal_cover(network) returns the smallest set of names that cover the network (in the sense described at function is_cover, above).

Here's the explanation and here's a picture. Big network: enter image description here

Small network: enter image description here

And here's my code:

def to_dict(pairs):
    from collections import defaultdict
    paired = defaultdict(set)
    for k, v in pairs:
        paired[k].add(v)
        paired[v].add(k)
    return dict(paired)
def to_pairs(network):
    return {(k, v) for k, vs in network.items() for v in vs if k < v}
def n_friends(network, n):
    return {k for k , v in network.items() if len(v) == n}
def lonely(network):
    return {k for k, v in network.items() if len(v) == 1}
def most_known(network):
    return max(network, key=lambda k: len(network[k]))
def common_friends(network, name1, name2):
    return set(network[name1].intersection(network[name2]))
def by_n_friends(network):
    return {x: {k for k, v in network.items() if len(v) == x} for x in range(1, len(network))}
def clique(network, names):
    import itertools as it
    return {tuple(sorted(y)) for y in (it.combinations(names, 2))} <= {tuple(sorted(x)) for x in to_pairs(network)}
def most_commons(network):
    friends = {}
    for pair in to_pairs(network):
        for elem in pair:
            friends.setdefault(elem, set()).update(pair)
    return next(iter(({pair for pair in to_pairs(network) if ({pair: len(friends[pair[0]] & friends[pair[1]]) for pair in to_pairs(network)})[pair] == (max({pair: len(friends[pair[0]] & friends[pair[1]]) for pair in to_pairs(network)}.values()))})))

def strangers(network,names):
    import itertools as it
    return not(bool([(x,y) for x in set(it.permutations(names, 2)) for y in to_pairs(network) if x == y]))
def suggestions(network):
    return {tuple(sorted([k,k1])) for k in network.keys() for k1 in network.keys() if k not in network[k1] and len(network[k] & network[k1]) != 0 and k != k1}
def is_cover(network, names):
    return not([k for k in network.keys() if k not in names and network[k] & names == set()])
def triangles(network):
    return len({tuple(sorted([k1,k2,k3])) for k1 in network.keys() for k2 in network.keys() for k3 in network.keys() if k1!=k2 and k2!=k3 and k1!=k3 and(k1 in network[k3] and k2 in network[k3] and k1 in network[k2])})
def minimal_cover(network):
    import itertools as it
    if len(network) <= 4:
        bar1 = list(map(set, list(network.keys())))
        for st in bar1:
            if is_cover(network,st):
                return st
    else:
        bar = list(map(set, sorted(it.combinations(list(network), 3))))
        for st in bar:
            if is_cover(network, st):
                return st

The homework is followed with unit tests made by the professor, I will not post them. Edit: The goal was to done the home work with one liners. Thank you.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Do you have to operate under the assumption that no data can be saved? I mean: could you for example save the count of each person's friends and use it later? You're repeating quite a lot of code as it is now. For instance lonely could be written as a call to n_friends(network, 1). \$\endgroup\$
    – ChatterOne
    Jan 22, 2017 at 15:06
  • \$\begingroup\$ @ChatterOne , oh no, I didn't realize that. Thank you. \$\endgroup\$ Jan 22, 2017 at 15:07

1 Answer 1

3
\$\begingroup\$

Longest lines can be rewritten thus:

def are_friends(network, a, b):
    return a in network[b]

def clique(network, names):
    """
    returns True if all persons from the group names know each other, 
    and False otherwise.
    """
    return all(are_friends(network, a, b) 
        for a, b in it.combinations(names, 2))

def most_commons(network):
    """the pair with the most mutual friends"""
    return max(to_pairs(network), 
        key = lambda p: len(common_friends(network, p[0], p[1])))

def suggestions(network):
    def has_common_friend(a, b):
        return len(common_friends(network, a, b)) > 0

    return [(a, b) 
        for a, b in it.combinations(sorted(network.keys()), 2) 
        if not are_friends(network, a, b) 
            and has_common_friend(a, b)]

def triangles(network):
    """the number of triplets of people who know each other."""
    return len(t for t in it.combinations(network.keys(), 3) if clique(t))

Reusing functions as also suggested by ChatterOne and more consistent use of itertools.combinations.

Also

  • Use built-in functions s.a. all, max whenever appropriate.
  • Remove unnecessary parens.
  • Divide long function calls and list comprensions.

to prevent lines getting too long.

\$\endgroup\$

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.