CODEWITHSUNDEEP
python
user1411837
user1411837

Reputation: 1564

Python - Finding the number of squares by connected coordinates

If I have a list of lists as below , 

[[1, 2], [3, 4], [1, 5], [2, 6], [4, 8], [5, 6], [6, 7],
 [7, 8], [6, 10], [7, 11], [8, 12], [10, 11],
 [10, 14], [12, 16], [14, 15], [15, 16]]

And another list as below : 

([[1, 2], [2, 3], [3, 4], [1, 5], [4, 8],
     [6, 7], [5, 9], [6, 10], [7, 11], [8, 12],
     [9, 13], [10, 11], [12, 16], [13, 14], [14, 15], [15, 16]]

The above 2 lists can be visualized as in the image, where each point is represented by a list . enter image description here

I want to write a program in python which detects the number of squares formed by the connecting points .

I know there is a graph traversal where every visited node can be tracked as we traverse through the graph . But in this case , there is no direction mentioned .

I am not asking for a complete solution here nor is the case that i have not researched enough . Any advice on how to approach this problem would really help as i am just not able to get a start to this .

THanks in advance .

Upvotes: 2

Views: 1221

Answers (1)

huwenchao
huwenchao

Reputation: 44

Given the length of side, in this case it is 3, the squares inside is limited and can be described as list of sides just like your input.

In your case, there are 9 (1*1) squares, 4 (2*2) squares, and 1 (3*3) squares inside. The first (1*1) square can be described as {(1,2), (1,5), (2,6), (5,6)}. I use tuple instead of list here, because tuple can be element of set in python, while list can not. If we transform the input like this, we get the graph as 

{(1, 2), (3, 4), (1, 5), (2, 6), (4, 8), (5, 6), (6, 7),
 (7, 8), (6, 10), (7, 11), (8, 12), (10, 11),
 (10, 14), (12, 16), (14, 15), (15, 16)}

The first square {(1,2), (1,5), (2,6), (5,6)} is subset of the graph set (we can use the python function issubset to check), then we can say it is in the graph. Use the same way to check whether all the 14 squares are in the graph, you get the number.

If the side length is big, like 100, you can use a loop to get all possible squares inside. 

for point in all_points:
    for side_length in range(1, N):
        if the_square_is_valid:
            gen_the_side_set

As tiboas_k commented, the algorithm complexity is high. I just came up with a new solution.

First transform the input to 

{(1, 2), (3, 4), (1, 5), (2, 6), (4, 8), (5, 6), (6, 7),
 (7, 8), (6, 10), (7, 11), (8, 12), (10, 11),
 (10, 14), (12, 16), (14, 15), (15, 16)}

as above. Then get all possible top left nodes, it is the set of first element of the side pair. 

 {1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15}

for every possible top left nodes, check whether square of length 1, 2 ... n with this node as top left node exists in the input graph. It can be optimized, for length k, if the top side or left side is missing, then you don't need to check k+1 to n.

In this algorithm, we don't need to generate all possible squares, just check all possible squares in the input graph, and as soon as we find one side missing, we can return false, don't have to check all sides. It should be faster.

Upvotes: 2

Related Questions