3
\$\begingroup\$

I'm trying to solve this problem with Python 3.8. In my code, I used 3 nested for loops to check every single point and storing the largest area with each set of points. This program works fine, but it's \$ O(n^3) \$ time complexity, and I'm wondering if there are any more elegant/efficient solutions. Is there a more efficient algorithm that doesn't loop through every single point, or is that necessary?

My code:

with open("triangles.in", "r") as file_in:
  lines = [x.strip() for x in file_in.readlines()]
  n, points = lines[0], lines[1:]


def main(points):
  largest = 0

  for corner in points:
    cx, cy = corner.split()
    for leg in points:
      lx, ly = leg.split()
      for width in points:
        wx, wy = width.split()
        if lx == cx and wy == cy:
          area = abs(int(ly)-int(cy)) * abs(int(wx)-int(cx))
          
          if area > largest:
            largest = area

  return str(largest)

with open("triangles.out", "w+") as file_out:
  file_out.write(main(points))
  file_out.close()

The input file triangles.in:

4
0 0
0 1
1 0
1 2

Problem synopsis: Given a set of \$ n \$ distinct points \$ (X_1, Y_1) \$ to \$ (X_n, Y_n) \$, find the largest triangle's area multiplied by 2, given that the triangle is a right triangle (one of the lines of the triangle in parallel to the x-axis, and one other parallel to the y-axis).

\$\endgroup\$
0

2 Answers 2

5
\$\begingroup\$

An obvious improvement is to not split the strings and convert the parts to int over and over again. Do it once, at the start:

def main(points):
  points = [tuple(map(int, point.split())) for point in points]
  largest = 0

  for cx, cy in points:
    for lx, ly in points:
      for wx, wy in points:
        if lx == cx and wy == cy:
          area = abs(ly-cy) * abs(wx-cx)
          if area > largest:
            largest = area

  return str(largest)

And it can be solved in O(n). For every "corner" as you call it, you go through all point pairs. Instead, just look up the point furthest away on the same y-coordinate and the point furthest away on the same x-coordinate. That can be precomputed in O(n):

with open('triangles.in') as f:
    next(f)
    points = [tuple(map(int, line.split())) for line in f]

xmin, xmax, ymin, ymax = {}, {}, {}, {}
for x, y in points:
    xmin[y] = min(xmin.get(y, x), x)
    xmax[y] = max(xmax.get(y, x), x)
    ymin[x] = min(ymin.get(x, y), y)
    ymax[x] = max(ymax.get(x, y), y)

result = max(max(x - xmin[y], xmax[y] - x) * max(y - ymin[x], ymax[x] - y)
             for x, y in points)

with open('triangles.out', 'w') as f:
    print(result, file=f)

Note that I also did the output a bit differently. No need to close yourself. Getting the file closed for you kinda is the reason you used with in the first place, remember? And I prefer print over write, as I don't have to convert to string then and trust line endings to be done as appropriate for the platform (maybe not an issue here, as the output is just one line and apparently they don't care how it ends).

P.S. Those darn... they kept saying my solution failed due to "Runtime error or memory limit exceeded" and it took me a while to figure out: Instead of tuple(map(...)) I had used my preferred [*map(...)]. But they're inexplicably using Python 3.4 and it didn't exist back then. But that should be a syntax error. Grrrr....

\$\endgroup\$
2
  • \$\begingroup\$ about the file.close: yeah i'm kinda stupid LOL \$\endgroup\$ Oct 5, 2020 at 14:05
  • \$\begingroup\$ also, yeah. USACO's error messages are incredibly confusing. I don't understand why they won't update their python version. would it be that difficult? \$\endgroup\$ Oct 5, 2020 at 14:43
3
\$\begingroup\$

This will be pretty similar to superb rain's great answer.

Write functions

Writing functions will help you to write easier to maintain code. Also, for the algorithmic challenges, it will help you to focus on the algorithm itself instead of dealing with input/output.

Write tests

Once you have a function, it is easier to write tests. (You could also write the tests before the function). This will help to test various implementations, to test them, to compare them (both in correctness and in performances)

Optimisations advices

Compute as little as possible, stop as soon as possible.

Here, that could mean checking lx == cx as soon as you can and computing abs(ly-cy) only once per tuple (ly, cy).

def get_solution_naive_on_smaller_range(points):
    largest = 0
    for cx, cy in points:
        for lx, ly in points:
            if lx == cx:
                dy = abs(ly-cy)
                for wx, wy in points:
                    if wy == cy:
                        dx = abs(wx-cx)
                        area = dy * dx
                        if area > largest:
                            largest = area
    return largest

Precompute as much as possible

Instead of having to iterate through all points to find the points on the same line or columns that the point being considered, we could perform some precomputation to be able to find quickly all points in the same line (or column) that the current point.

def get_solution_using_dicts(points):
    largest = 0
    by_x = dict()
    by_y = dict()
    for x, y in points:
        by_x.setdefault(x, []).append(y)
        by_y.setdefault(y, []).append(x)
    for cx, cy in points:
        for ly in by_x[cx]:
            dy = abs(ly-cy)
            for wx in by_y[cy]:
                dx = abs(wx - cx)
                area = dy * dx
                if area > largest:
                    largest = area
    return largest

Compute as little as possible (again)

For a given point, we don't have to consider all other points in the same line and all the other points in the same column. We can just consider the one the furthest vertically or horizontally.

Thus, for a given point, we can quickly have the best candidates:

def get_solution_using_dicts_and_maxabs(points):
    largest = 0
    by_x = dict()
    by_y = dict()
    for x, y in points:
        by_x.setdefault(x, []).append(y)
        by_y.setdefault(y, []).append(x)
    for cx, cy in points:
        max_y_delta = max(abs(y-cy) for y in by_x[cx])
        max_x_delta = max(abs(x-cx) for x in by_y[cy])
        area = max_x_delta * max_y_delta
        if area > largest:
            largest = area
    return largest

Final code

# https://codereview.stackexchange.com/questions/250205/most-efficient-solution-for-usaco-triangles-python
# http://usaco.org/index.php?page=viewproblem2&cpid=1011

import random

def get_random_points(n, mini, maxi):
    # First generate a triangle so that there is at least one
    points = set([(5, 0), (0, 0), (0, 5)])
    # Generate remainings points
    while len(points) < n:
        a = random.randint(mini, maxi)
        b = random.randint(mini, maxi)
        points.add((a, b))
    # Shuffle
    l = list(points)
    random.shuffle(l)
    return l

def get_solution_naive(points):
    largest = 0
    for cx, cy in points:
        for lx, ly in points:
            for wx, wy in points:
                if lx == cx and wy == cy:
                    area = abs(ly-cy) * abs(wx-cx)
                    if area > largest:
                        largest = area
    return largest


def get_solution_naive_on_smaller_range(points):
    largest = 0
    for cx, cy in points:
        for lx, ly in points:
            if lx == cx:
                dy = abs(ly-cy)
                for wx, wy in points:
                    if wy == cy:
                        dx = abs(wx-cx)
                        area = dy * dx
                        if area > largest:
                            largest = area
    return largest

def get_solution_using_dicts(points):
    largest = 0
    by_x = dict()
    by_y = dict()
    for x, y in points:
        by_x.setdefault(x, []).append(y)
        by_y.setdefault(y, []).append(x)
    for cx, cy in points:
        for ly in by_x[cx]:
            dy = abs(ly-cy)
            for wx in by_y[cy]:
                dx = abs(wx - cx)
                area = dy * dx
                if area > largest:
                    largest = area
    return largest

def get_solution_using_dicts_and_maxabs(points):
    largest = 0
    by_x = dict()
    by_y = dict()
    for x, y in points:
        by_x.setdefault(x, []).append(y)
        by_y.setdefault(y, []).append(x)
    for cx, cy in points:
        max_y_delta = max(abs(y-cy) for y in by_x[cx])
        max_x_delta = max(abs(x-cx) for x in by_y[cy])
        area = max_x_delta * max_y_delta
        if area > largest:
            largest = area
    return largest


def perform_check(points, solution):
    ret = get_solution_naive(points)
    ret1 = get_solution_naive_on_smaller_range(points)
    ret2 = get_solution_using_dicts(points)
    ret3 = get_solution_using_dicts_and_maxabs(points)
    if ret != solution:
        print("ret", points, ret, solution)
    if ret1 != solution:
        print("ret1", points, ret1, solution)
    if ret2 != solution:
        print("ret2", points, ret2, solution)
    if ret3 != solution:
        print("ret3", points, ret3, solution)

# Provided test case
perform_check([(0, 0), (0, 1), (1, 0), (1, 2)], 2)

# Generated test case
perform_check([(5, 0), (-1, 1), (-5, -3), (1, -5), (5, -2), (4, 5), (-2, 5), (-2, 1), (-4, -3), (5, -4), (-4, 3), (-5, -1), (0, 0), (-2, -5), (3, 1), (3, 2), (-4, 2), (2, 3), (0, 5), (5, 5)] , 70)
```
\$\endgroup\$
3
  • \$\begingroup\$ Hmm, you don't really precompute as much as possible, and end up taking quadratic time for example for points = [(x, 0) for x in range(n)]. \$\endgroup\$ Oct 5, 2020 at 14:08
  • \$\begingroup\$ Yeah, I could not come up with the same solution as yours on my own. \$\endgroup\$
    – SylvainD
    Oct 5, 2020 at 16:32
  • 1
    \$\begingroup\$ Well, feel free to adopt :-). You could for example add for v in by_x.values(): v[:] = min(v), max(v) and the same for by_y. That would suffice to make it O(n). \$\endgroup\$ Oct 5, 2020 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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