CODEWITHSUNDEEP
python-3.x
W Szum
W Szum

Reputation: 171

Sorting List of Connecting Coordinates in Python

I have a list of tuples with coordinates that are connected (number of tuples connected can be any):

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

How can I sort this list so that all the duplicates removed and I have the following:

[((0, 0), (0, 3)), ((1, 3), (1, 5))]

First connected coordinates:

(0, 0), (0, 1)
(0, 1), (0, 2)
(0, 2), (0, 3)

Turned to:

(0, 0), (0, 3)

Second connected coordinates:

(1, 3), (1, 4)
(1, 4), (1, 5)

Turned to:

(1, 3), (1, 5)

I have thought of enumerating through the list:

for index, item in enumerate(coordinates):
    if item[index] == item[index + 1]:
         ...

But generally have no ideas even how to solve this.

Upvotes: 0

Views: 100

Answers (1)

Patrick Artner
Patrick Artner

Reputation: 51643

Algo:

  • start with an empty list
  • add an empty list into it

Iterate over your tuples:

  • if last list in your resultlist is empty, add all elements of the current tuple to it
  • if the last element in the last list of your resultlist is identical to your current tuple first element:
    • either add your current tuples last element to it
    • or replace its last element by the current items last element
  • if not, add a new empty list to your resultlist and add all elements of the current tuple to it
  • continue iterating until done

If you opted for either above:

When done, refine your results: and add each inner list first and last elemnt to a new list and that list to your final resultlist.

Code:

data = [((0, 0), (0, 1)), ((0, 1), (0, 2)), ((0, 2), (0, 3)), 
        ((1, 3), (1, 4)), ((1, 4), (1, 5))]

result = [[]]
for connect in data:
    # empty, add all
    if not result[-1]:
        result[-1].extend(connect)
        continue
    # does not continue current streak
    if result[-1][-1] != connect[0]:
        result.append([c for c in connect])

    # does continue current streak
    else:
         # to collect all intermediate steps as well
         result[-1].append(connect[1])

         # if you do not need to build the whole thing, use this instead:
         # result[-1][-1] = connect[1] 

# simplify result
r = [ (r[0],r[-1]) for r in result]

print(result, r , sep="\n")

Output:

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

If you replace the last element of the inner list when continuing a streak, you can avoid the last refinement step but you loose the ability to see the whole connectivity in your 1st resulting list.

Upvotes: 1

Related Questions