Hackbright Code Challenges

Same Line: Solution

Same Line: Solution

Problem

Same Line

Whiteboard

Harder

Challenge

Medium

Concepts

Loops, Geometry

Download

sameline-solution.zip


You could write this so that you could compare every combination of three points and see if they are on the same line. This would result in O(n ** 3) performance.

sameline.py
def sameline(pts):
    """Find segments comprising >2 points."""

    # START SOLUTION

    # The runtime of this is fixed by the combinations of points;
    # for (n choose 3); it grows as O(n ** 3)

    out = []

    for p1, p2, p3 in itertools.combinations(pts, 3):

        x1, y1 = p1
        x2, y2 = p2
        x3, y3 = p3

        # Check if these three points are on a line

        if (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2):
            out.append([p1, p2, p3])

    return out

This gets all 3-points combinations and uses a simple geometric test if they are on the same line.

A terser, functional-style version of this logic could be:

sameline.py
def sameline_functional(pts):
    """Find segments comprising >2 points."""

    # The runtime of this is fixed by the combinations of points;
    # for (n choose 3); it grows as O(n ** 3)

    return [([p1, p2, p3])
            for p1, p2, p3 in itertools.combinations(pts, 3)
            if ((p1[1] - p2[1]) * (p1[0] - p3[0]) ==
                (p1[1] - p3[1]) * (p1[0] - p2[0]))]

Better Runtime

You can do this in a much better runtime, O(n ** 2), by comparing every combination of two points, and keeping track of the discovered slope in a set. Then, if you find another combination with the same slope, you know it would be on the same point:

sameline.py
def sameline_quadratic(pts):
    """Find segments comprising >2 points."""

    # The runtime of this is fixed by the combinations of points;
    # for (n choose 2), it grows as O(n ** 2)

    # Dictionary of slope-info mapped to sets of points.
    #
    # In geometry, any line can be represented by the eqn y = mx + b;
    # we can calculate m (slope) and b (intercept) for two points and
    # keep track of those points in a dict using (m,b) for the key.

    # make slopes a dictionary where values default to being an empty set
    slopes = defaultdict(set)

    # Compare all p1,p2 combinations of points

    for p1, p2 in itertools.combinations(pts, 2):
        x1, y1 = p1
        x2, y2 = p2

        # Find slope & y-intercept, avoiding div-by-zero for vertical lines

        if x2 - x1:
            slope = float(y2 - y1) / float(x2 - x1)
            y_intercept = y1 - (slope * x1)

        else:
            slope = "vertical"
            y_intercept = x1

        # Add both points to the slopes dictionary

        slopes[slope, y_intercept].add(p1)
        slopes[slope, y_intercept].add(p2)

    return [pts for pts in slopes.values() if len(pts) > 2]

This is much preferred — if we have 500 points, an O(n ** 2) solution would check 124,750 points (that’s “500 choose 2”), whereas our O(n ** 3) solution would need to check 20,708,500 points (“500 choose 3”).