Solución más eficiente para USACO: Triángulos - Python

Oct 05 2020

Estoy tratando de resolver este problema con Python 3.8. En mi código, usé 3 bucles for anidados para verificar cada punto y almacenar el área más grande con cada conjunto de puntos. Este programa funciona bien, pero es \$ O(n^3) \$complejidad del tiempo, y me pregunto si hay soluciones más elegantes / eficientes. ¿Existe un algoritmo más eficiente que no recorra todos los puntos o es necesario?

Mi código:

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()

El archivo de entrada triangles.in:

Sinopsis del problema: Dado un conjunto de \$ n \$puntos distintos \$ (X_1, Y_1) \$a \$ (X_n, Y_n) \$, encuentra el área del triángulo más grande multiplicado por 2, dado que el triángulo es un triángulo rectángulo (una de las líneas del triángulo en paralelo al eje x, y otra paralela al eje y).

Respuestas

5 superbrain Oct 05 2020 at 18:43

Una mejora obvia es no dividir las cuerdas y convertir las partes int una y otra vez . Hazlo una vez, al principio:

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)

Y se puede resolver en O (n). Por cada "esquina" como la llamas, pasas por todos los pares de puntos. En su lugar, busque el punto más alejado en la misma coordenada y y el punto más alejado en la misma coordenada x. Eso se puede calcular previamente en 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)

Tenga en cuenta que también hice la salida un poco diferente. No necesitas a closeti mismo. Cerrar el archivo para ti es la razón por la que usaste withen primer lugar, ¿recuerdas? Y prefiero printmás write, ya que no tengo que convertir en cadena de entonces y los finales de línea de confianza que hacerse según sea apropiado para la plataforma (tal vez no es un problema aquí, ya que la salida es una sola línea y al parecer no les importa cómo termina).

PD Esos malditos ... seguían diciendo que mi solución fallaba debido a "Error de tiempo de ejecución o límite de memoria excedido" y me tomó un tiempo darme cuenta: en lugar de tuple(map(...))usar mi preferido [*map(...)]. Pero inexplicablemente están usando Python 3.4 y no existía en ese entonces. Pero eso debería ser un error de sintaxis . Grrrr ....

3 SylvainD Oct 05 2020 at 20:37

Esto será bastante similar a la gran respuesta de superb rain.

Funciones de escritura

Las funciones de escritura le ayudarán a escribir código más fácil de mantener. Además, para los desafíos algorítmicos, le ayudará a concentrarse en el algoritmo en sí en lugar de ocuparse de la entrada / salida.

Escribir pruebas

Una vez que tiene una función, es más fácil escribir pruebas. (También puede escribir las pruebas antes de la función). Esto ayudará a probar varias implementaciones, a probarlas, a compararlas (tanto en exactitud como en rendimiento).

Consejos de optimización

Calcule lo menos posible, deténgase lo antes posible.

Aquí, eso podría significar verificar lx == cxlo antes posible y calcular abs(ly-cy)solo una vez por tupla (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

Precalcule tanto como sea posible

En lugar de tener que iterar por todos los puntos para encontrar los puntos en la misma línea o columnas que el punto que se está considerando, podríamos realizar algunos cálculos previos para poder encontrar rápidamente todos los puntos en la misma línea (o columna) que el punto actual.

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

Calcule lo menos posible (nuevamente)

Para un punto dado, no tenemos que considerar todos los demás puntos en la misma línea y todos los demás puntos en la misma columna. Podemos considerar el que está más alejado vertical u horizontalmente.