Solution la plus efficace pour USACO: Triangles - Python

Oct 05 2020

J'essaye de résoudre ce problème avec Python 3.8. Dans mon code, j'ai utilisé 3 boucles for imbriquées pour vérifier chaque point et stocker la plus grande zone avec chaque ensemble de points. Ce programme fonctionne bien, mais c'est \$ O(n^3) \$complexité temporelle, et je me demande s'il existe des solutions plus élégantes / efficaces. Existe-t-il un algorithme plus efficace qui ne passe pas par chaque point ou est-ce nécessaire?

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

Le fichier d'entrée triangles.in:

Synopsis du problème: étant donné un ensemble de \$ n \$points distincts \$ (X_1, Y_1) \$à \$ (X_n, Y_n) \$, trouvez l'aire du plus grand triangle multipliée par 2, étant donné que le triangle est un triangle rectangle (une des lignes du triangle parallèle à l'axe x et une autre parallèle à l'axe y).

Réponses

5 superbrain Oct 05 2020 at 18:43

Une amélioration évidente est de ne pas diviser les cordes et de convertir les parties en int plusieurs fois . Faites-le une fois, au début:

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)

Et il peut être résolu en O (n). Pour chaque «coin» comme vous l'appelez, vous passez par toutes les paires de points. Au lieu de cela, recherchez simplement le point le plus éloigné sur la même coordonnée y et le point le plus éloigné sur la même coordonnée x. Cela peut être précalculé 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)

Notez que j'ai également fait la sortie un peu différemment. Pas besoin de closetoi. Obtenir le dossier fermé pour vous est un peu la raison pour laquelle vous avez utilisé withen premier lieu, vous vous souvenez? Et je préfère printplutôt que write, car je n'ai pas à convertir en chaîne à ce moment-là et à faire confiance aux fins de ligne de manière appropriée pour la plate-forme (peut-être pas un problème ici, car la sortie n'est qu'une ligne et apparemment, ils ne se soucient pas de savoir comment ça se termine).

PS Ces fichus ... ils n'arrêtaient pas de dire que ma solution avait échoué en raison d'une "erreur d'exécution ou d'une limite de mémoire dépassée" et il m'a fallu un certain temps pour comprendre: au lieu de cela, tuple(map(...))j'avais utilisé mon préféré [*map(...)]. Mais ils utilisent inexplicablement Python 3.4 et cela n'existait pas à l'époque. Mais cela devrait être une erreur de syntaxe . Grrrr ....

3 SylvainD Oct 05 2020 at 20:37

Ce sera assez similaire à la bonne réponse de la superbe pluie.

Écrire des fonctions

Les fonctions d'écriture vous aideront à écrire du code plus facile à maintenir. De plus, pour les défis algorithmiques, cela vous aidera à vous concentrer sur l'algorithme lui-même au lieu de traiter les entrées / sorties.

Rédiger des tests

Une fois que vous avez une fonction, il est plus facile d'écrire des tests. (Vous pouvez également écrire les tests avant la fonction). Cela aidera à tester différentes implémentations, à les tester, à les comparer (à la fois en exactitude et en performances)

Conseils d'optimisations

Calculez le moins possible, arrêtez le plus tôt possible.

Ici, cela pourrait signifier vérifier lx == cxdès que vous le pouvez et abs(ly-cy)ne calculer qu'une fois par 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

Précalculez autant que possible

Au lieu d'avoir à parcourir tous les points pour trouver les points sur la même ligne ou les mêmes colonnes que le point considéré, nous pourrions effectuer un pré-calcul pour pouvoir trouver rapidement tous les points de la même ligne (ou colonne) que le point courant.

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

Calculez le moins possible (encore une fois)

Pour un point donné, nous n'avons pas à considérer tous les autres points de la même ligne et tous les autres points de la même colonne. Nous pouvons simplement considérer celui qui est le plus éloigné verticalement ou horizontalement.