8
\$\begingroup\$

I was wondering how I can make this code more pythonic. More professonal-looking and more readable. The code runs perfectly fine.

# Uses Python 3
"""
Finds the closest pair of point from a set of points on a plane
by brute-force (O(n^2)) and divide-and-conquer algorithms (O(nlog(n))).
Input: x,y coordinates (float)
Output: minimum distance (float)& closest pair (complex number)
@ Author: RA
"""

import sys


# Brute force algorithm.

def brute_force(xpoints):  # px will be passed to the function
    n = len(xpoints)
    if n < 2:
        return float('inf'), (None, None)
    else:
        sep = float('inf')  # set the initial minimum to infinity
        pair = ()
        for i in range(n - 1):
            for j in range(i + 1, n):
                if abs(xpoints[i] - xpoints[j]) < sep:
                    sep = abs(xpoints[i] - xpoints[j])
                    pair = (xpoints[i], xpoints[j])

    return sep, pair


# Divide and Conquer


def divide_n_conquer(xpoints, ypoints):
    n = len(xpoints)
    if n <= 3:
        return brute_force(xpoints)

    xmedian = int(n / 2)

    yl, yr = [], []
    for p in ypoints:
        if p.real < xpoints[xmedian].real:
            yl.append(p)
        else:
            yr.append(p)

    (l_sep, l_pair) = divide_n_conquer(xpoints[:xmedian], yl)  
    (r_sep, r_pair) = divide_n_conquer(xpoints[xmedian:], yr)

    (sep, pair) = (l_sep, l_pair) if l_sep < r_sep else (r_sep, r_pair)

    sep_strip, pair_strip = split(xpoints, ypoints, sep)  

    if sep_strip < sep:
        sep = sep_strip
        pair = pair_strip

    return sep, pair


def split(xpoints, ypoints, sep):
    xdivider = xpoints[int(len(xpoints)/2)].real
    ystrip = [item for item in ypoints if
              abs(item.real - xdivider).real < sep]  

    ns = len(ystrip)  # Number of points in the strip
    sep = float('inf')
    pair = ()
    if ns > 1:

        for i in range(ns - 1):
            for j in range(i + 1, min(i + 8, ns)):
                if abs(ystrip[i] - ystrip[j]) < sep:
                    sep, pair = abs(ystrip[i] - ystrip[j]), (ystrip[i], ystrip[j])

    return sep, pair


if __name__ == '__main__':
    _input = sys.stdin.read()
    data = list(map(int, _input.split()))
    n = data[0]
    x = data[1::2]
    y = data[2::2]
    p = [complex(x, y) for x, y in zip(x, y)]  
    px = sorted(p, key=lambda p: p.real)  # points sorted by x
    py = sorted(p, key=lambda p: p.imag)  # points sorted by y
    print("{0:.9f}".format(divide_n_conquer(px, py)[0]))
\$\endgroup\$
6
\$\begingroup\$

Just reviewing brute_force.

  1. There's no docstring.

  2. There's no need to write comments if they just repeat what it says in the code:

    sep = float('inf')  # set the initial minimum to infinity
    

    Use comments to explain things that are hard to deduce from reading the code.

  3. The special case for n < 2 is unnecessary. If n is less than 2, then the loop over i will be empty and no pairs will be tested.

  4. There are some superfluous parentheses. In Python the comma operator has higher precedence than assignment, and so, instead of:

    pair = (xpoints[i], xpoints[j])
    

    you can write:

    pair = xpoints[i], xpoints[j]
    
  5. The expression abs(xpoints[i] - xpoints[j]) gets computed twice in some cases: this could be avoided by storing the result in a local variable.

  6. When looping over the distinct pairs of a sequence, use itertools.combinations, like this:

    from itertools import combinations
    
    def brute_force(points):
        """Find the pair (p, q) in the sequence points with the closest
        separation. Return the tuple (separation, (p, q)).
    
        """
        sep = float('inf')
        pair = None, None
        for p, q in combinations(points, 2):
            pq_sep = abs(p - q)
            if pq_sep < sep:
                sep = pq_sep
                pair = p, q
        return sep, pair
    
  7. This could be turned into a single expression using min and operator.itemgetter:

    from itertools import combinations
    from operator import itemgetter
    
    def brute_force(points):
        """Find the pair (p, q) in the sequence points with the closest
        separation. Return the tuple (separation, (p, q)).
    
        """
        return min(((abs(p - q), (p, q)) for p, q in combinations(points, 2)),
                   key=itemgetter(0), default=(float('inf'), (None, None)))
    

    (This needs to be Python 3.4 or later since it uses the default keyword argument.)

    Not everyone finds this style of programming readable, so it would be totally reasonable to stop with the version in §6 above and not try to squash everything into a single expression.

\$\endgroup\$
  • 2
    \$\begingroup\$ Nice answer. The last example though looks a bit...too much when it comes to "more readable" ^_^ \$\endgroup\$ – Grajdeanu Alex. Apr 7 '18 at 11:55
1
\$\begingroup\$

Three comments on the general style of your code, skipping what's already said in the other answer.

1. Express co-ordinate ideas in similar form.

For an external user, both functions brute_force and divide_n_conquer are identical. There is no reason for these functions to have different signatures. Suggestion: arguments for brute_force and for divide_n_conquer should be identical.

Variable naming: why l_sep, l_pair and yl (not l_y)?

2. Use definite, specific, concrete language.

Variable names such as l_sep, l_pair, sep, ns, are not clear without context. If you cannot come up with better names, then document them explicitly. The less general, the better.

3. Do not break a sentence into two.

The function split (seems) useless outside of divide_n_conquer. Ideally split would belong inside of the body of divide_n_conquer. This cannot happen without refactoring the code because of the recursive calls, i.e., split would be redefined at every function call. A pythonic solution to this problem is to mark the function split as a helper function, by renaming it _split. See more info here.

Alternatively, split can be defined inside of divide_n_conquer, provided you define another helper function divide_n_conquer_recurse, for example. The function would then look something like:

def divide_n_conquer(xpoints): # Same signature as brute_force. See 1.

    def split(xpoints, ypoints, sep):
        pass

    def divide_n_conquer_recurse(...conditions):
        if base_condition: # n <=3 ?
            return brute_force(xpoints)
        else:
            if some_condition:  # l_sep < r_sep ?
                updated_conditions = split(...)
                return divide_n_conquer_recurse(updated_conditions)
            else:
                other_conditions = split(...)
                return divide_n_conquer_recurse(other_conditions)

    # parse xpoints into xpoints and ypoints.
    ...
    return divide_n_conquer_recurse(...initial_conditions)

Small disclaimer: Paragraph names inspired by The Elements Of Style.

\$\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.