Nerdatope - 1 year ago 130
Python Question

# Shorten a list of tuples by cutting out loops?

I have a function that generates a list of tuples like:

``````[(0, 0), (1, 1), (1, 2), (1,3), (2, 4), (3, 5), (4, 5)]
``````

which are used to represent a path of tiles (row, column) in a game I'm making.

The function that I use to generate these paths isn't perfect, since it often produces "loops", as shown below:

``````[(2, 0), (2, 1), (1, 2), (0, 3), (0, 4), (1, 5), (2, 5), (3, 4), (3, 3),
(3, 2), (4, 1)]
``````

The path above should instead look like:

``````[(2, 0), (2, 1), (3, 2), (4, 1)]
``````

These paths can contain any number of loops, which can be of any size and shape.

So my question is, how do I write a function in python that cuts the loopy list and returns a new, shorter list that does not have these loops.

My attempt below:

``````def Cut_Out_Loops(Path):

NewList = list(Path)
Cutting = True

a = 0
for Cords in Path:
a += 1

try:
for i in range(a + 2, len(Path)):
if (Path[i][0] == Cords[0] and abs(Path[i][1] - Cords[1]) == 1:
NewList = NewList[0:a] + NewList[i:]
Path = list(NewList)
elif Path[i][1] == Cords[1] and abs(Path[i][0] - Cords[0]) == 1:
NewList = NewList[0:a] + NewList[i:]
Path = list(NewList)
elif abs(Path[i][0] - Cords[0]) == 1 and abs(Path[i][1] - Cords[1]) == 1:
NewList = NewList[0:a] + NewList[i:]
Path = list(NewList)
elif abs(Path[i][1] - Cords[1]) == 1 and abs(Path[i][0] - Cords[0]) == 1:
NewList = NewList[0:a] + NewList[i:]
Path = list(NewList)
Cutting = False
except IndexError:
Cutting = True
``````

Although your definition of a "loop" isn't too clear, try this

``````def clean(path):
path1 = []
for (x1,y1) in path:
for (i,(x2,y2)) in enumerate(path1[:-1]):
if abs(x1-x2) <= 1 and abs(y1-y2) <= 1:
path1 = path1[:i+1]
break
path1.append((x1,y1))
return path1
``````

It definitely works for your example:

`````` >>> path = [(2, 0), (2, 1), (1, 2), (0, 3), (0, 4), (1, 5), (2, 5), (3, 4), (3, 3), (3, 2), (4, 1)]
>>> clean(path)
[(2, 0), (2, 1), (3, 2), (4, 1)]
``````

That said, it is just the most straightforward of brute force solutions. The complexity is quadratic.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download