5
\$\begingroup\$

Problem

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/

Algorithm

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.

Code

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[0] - u[0], w[1] - u[1])

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[0]), int(p[1])
            hedges.append((x, y))

        for _ in range(M):
            p = f.readline().split()
            x, y = int(p[0]), int(p[1])
            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[0]*point[1] - edge[1]*point[0]
                if cross == 0:
                    break
                if side == None:
                    side = cross > 0
                elif side != (cross > 0):
                    break
            else:
                if side != None:
                    dist = sqrt(edge[0]**2 + edge[1]**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.

Example input

1
4
1
1 1
4 1
4 4
1 4
2 2

Example output

10.24264068711928

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.

\$\endgroup\$
  • \$\begingroup\$ Since it's in Czech, I doubt you'll understand anything. I'll try to describe it differently - find the polygon with the smallest circumference given a list of corners and a list of points it must cointain. I will add an example of input/output to make it more clear. \$\endgroup\$ – Noxio Jun 5 '17 at 19:15
  • \$\begingroup\$ Alright, edited the post. \$\endgroup\$ – Noxio Jun 5 '17 at 19:51
2
\$\begingroup\$

I assume your algorithm is correct and will comment only coding style

I would change INF = float("inf") to INF = math.inf (also you have to import it), since you use python 3.x (I'll asume you can use newest version) inf is now in math package.

Do not put any algorithms directly to the file (I am thinking about with open("input.txt") as f: and so on...) create a function - this is a good pracice because if someone would ever wanted to load your package he wouldnt like to start algorithm right away and also it helps if it comes to testing (you cannot test file but you can test a function).

Regarding a tuple construct

def vector(u, w):
    return (w[0] - u[0], w[1] - u[1])

I would love to see namedtuple here, it is kind of named tuple but it helps other programmers to see what the object exactly is and improve readibility (you would use edge.x instead of edge[0]). It also helps IDE to intelisence it.

Regarding T = int(f.readline()):

If (and only if) you assume that input file is correct such lines are fine but if not a try-except(python's try-catch) closure would be great here. The same thing might be applied to all the parsing in your script.

Note about performance: I cannot see any real code improvements if it comes to pure pythonic way, in my opinion if you want a faster solution you should try to come up with faster algorithm (maybe some assumptions for your set that would reduce edges to check?).

\$\endgroup\$
  • \$\begingroup\$ Thanks for the comments, it's true I should have used a namedtuple there, I wanted to quickly hack the code and didn't think of using it at the time. Regarding the try-except I know for a fact that I'm the only one that's ever gonna use this code, and that the input will be properly formatted, so I really didn't want to lost time on writing try-except blocks everywhere. Is there any specific reason why I should use INF = math.inf instead of float("inf")? \$\endgroup\$ – Noxio Jun 5 '17 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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