Paths in python

Question

Consider a rectangular grid.

I want a short and elegant way of generating a straight path from [x0,y0] to [x1,y1], where either x0=x1 or y0 = y1.

For example, on input [1,3], [3,3] the output [[1,3],[2,3],[3,3] should be generated. Likewise if the input is [3,3], [1,3].

I have tried [[i,j] for i in range(self.origin[0],self.end[0]+1) for j in range(self.origin[1], self.end[1]+1)], but it only works for the case where the input is ordered.

• TemporalWolf: Make life easy on yourself and break up the problem, there is no reason to iterate over both x and y when only one is changing

Answer 1

Your question states that the solution from x -> y should be the same as the solution y -> x, i.e. we're only interested in defining the points on the path, not in any ordering of those points. If that's true, then simply find out which path has the smaller x (or y) and designate that as the origin.

origin = (3,3)
dest = (1,3)
origin, dest = sorted([origin, dest])
path = {(i,j) for i in range(origin[0], dest[0]+1) for j in range(origin[1], dest[1]+1)}
# note that this is now a set comprehension, since it doesn't make any sense
# to use a list of unique hashable items whose order is irrelevant

of course, this solves any obstructionless 2-D pathfinding. If you know that only one direction is changing, then only look in that direction.

origin, dest = sorted((origin, dest))
if origin[0] == dest[0]: # y is changing
 path = {(origin[0], j) for j in range(origin[1], dest[1]+1)}
else: # x is changing
 path = {(i, origin[1]) for i in range(origin[0], dest[0]+1)}

Answer 2

Add the step argument to your range, deriving the sign of the start & end difference:

x_dir = copysign(1, self.end[0] - self.origin[0])
... for i in range(self.origin[0], self.end[0]+1, x_dir) ...

Do likewise for the y direction.

• Jsevillamol: I was hoping for something less verbose
• Adam Smith: how do you get less verbose than this?
• Adam Smith: @Jsevillamol certainly you could do this as a one-liner, but it would be MORE verbose not less. [(i, j) for i in range(self.origin[0], self.end[0]+1, math.copysign(1, self.end[0] - self.origin[0])) for j in range(self.origin[1], self.end[1]+1, math.copysigh(1, self.end[1] - self.origin[1]))]
• Prune: That depends on your metric of verbose. You could certainly first determine which variable is changing, and then deal only with the other. See @AdamSmith's answer for a lexically simple switch of order. It may execute a tad slower, but readability would dictate what you want to use.
• Adam Smith: Also I just noticed I typo'd copysigh in my ugly-as-sin one-liner. That's strangely fitting.