I'm trying to get into Python and get a bit familiar with it, so I found a problem online to train. The problem was to find the shortest path around some points, given a set of nodes which constitute the path and a set of points it must go around
I took the problem from here, but it's all in Czech so I don't know to what extent this will be helpful: https://kasiopea.matfyz.cz/soutez/F/
Since the providen set of edges isn't too large (<300) I iterate through all edges and check if all points are on just one side of the edge (since the shape must obviously be convex). Once I found all the edges I would run them against the Floyd Warshall algorithm to find out the shortest path length from one start node to itself.
from itertools import combinations from math import sqrt INF = float("inf") def floyd_warshall(graph): N = len(graph) dist = [[col for col in row] for row in graph] for k in range(N): for i in range(N): for j in range(N): dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]) return dist def vector(u, w): return (w - u, w - u) with open("input.txt") as f: T = int(f.readline()) for _ in range(T): N = int(f.readline()) M = int(f.readline()) hedges =  bombs =  for _ in range(N): p = f.readline().split() x, y = int(p), int(p) hedges.append((x, y)) for _ in range(M): p = f.readline().split() x, y = int(p), int(p) bombs.append((x, y)) graph = [[INF] * len(hedges) for i in range(len(hedges))] for (ui, u), (wi, w) in combinations(enumerate(hedges), 2): edge = vector(u, w) side = None for bomb in bombs: point = vector(u, bomb) cross = edge*point - edge*point if cross == 0: break if side == None: side = cross > 0 elif side != (cross > 0): break else: if side != None: dist = sqrt(edge**2 + edge**2) if side: graph[ui][wi] = dist else: graph[wi][ui] = dist solved = floyd_warshall(graph) cir = INF for i in range(len(hedges)): cir = min(solved[i][i], cir) if cir == INF: print(-1) else: print(cir)
Please don't mind the naming, the problem was presented a bit differently so I used the names for that instead.
1 4 1 1 1 4 1 4 4 1 4 2 2
I was wondering if there could be a faster solution for this problem and given the fact I'm coming from Java, if there are any things that could be more "pythonic", things I should avoid or stuff that could generally be better. Also I want to point out my solution is working, I'm just wondering if there's a better way to do it.