I have a nested list of 0s and ones such as :
L = [[1, 0, 1],
[0, 0, 0],
[0, 0, 1]]
I want to check if any ones are diagonal to each other. The nested list can come in any size, as long as the length of the sublists is equal to the length of the whole list (it's a square). So if I ran it on the above list, it would return False, because of two ones being diagonal.
My current code is:
for num, i in enumerate(List):
for count, m in enumerate(i):
key1 = True
key2 = True
key3 = True
key4 = True
num1 = num
num2 = num
num3 = num
num4 = num
count1 = count
count2 = count
count3 = count
count4 = count
if m == 1:
while key1 or key2 or key3 or key4:
#print(key1, key2, key3, key4)
try:
if List[num1 + 1][count1 + 1] == 1:
print(List[num1 + 1][count1 + 1])
return False
num1 += 1
count1 += 1
except IndexError:
key1 = False
try:
if List[num2 - 1][count2 + 1] == 1:
if num2 > 0:
print(List[num2 - 1][count2 + 1])
return False
num2 -= 1
count2 += 1
except IndexError:
key2 = False
try:
if List[num3 + 1][count3 - 1] == 1:
if count3 > 0:
print(List[num3 + 1][count3 - 1])
print(num3 + 1, count3 - 1)
return False
num3 += 1
count3 -= 1
except IndexError:
key3 = False
try:
if List[num4 - 1][count4 - 1] == 1:
if count4 > 0 and num4 > 0:
print(List[num4 - 1][count4 - 1])
return False
num4 -= 1
count4 -=1
except IndexError:
key4 = False
return True
The code scans the list for 1s, and when one is found, it looks at its four corners and searches them. It continues to search in the direction of the corner, moving one grid at a time. If another 1 is found, it returns false. Once all possible diagonal grids are searched (up to returning index error), the code moves to the next 1 that is found. Once every single 1 is searched and none of them find any diagonal is found, the code returns true.
It feels clunky and inefficient, but I'm not sure how to compact it. Is there a shorter way to do this?
You can start by thinking of a means of naming the diagonals. For example, in a 3x3 matrix the indices (x, y) go like this:
(0,0) (1,0) (2,0)
(0,1) (1,1) (2,1)
(0,2) (1,2) (2,2)
If we follow the diagonals, their indices have a simple pattern. The diagonals that run lower left to upper right are:
Diag #1 (0,0)
Diag #2 (0,1) (1,0)
Diag #3 (0,2) (1,1) (2,0)
Diag #4 (1,2) (2,1)
Diag #5 (2,2)
From upper left to lower right they are:
#1 (0,2)
#2 (0,1) (1,2)
#3 (0,0) (1,1) (2,2)
#4 (1,0) (2,1)
#5 (2,0)
Notice that in the lower left to upper right case, every cell (x, y) on the same diagonal has the same value of x + y. In the other case, every cell on the same diagonal has the same value of x - y. Obviously this will be true for any size matrix. We can use x+y and x-y to name the individual diagonals. As we step through the matrix, each time we encounter a "1" we can immediately calculate the names of the two diagonals that intersect there.
This suggests an efficient algorithm for deciding if any two "1"s are on the same diagonal. In Python we can use two sets to keep track of the "occupied" diagonals. If we encounter a "1" on an already-occupied diagonal, we return True, otherwise false. We can step through the matrix in any order provided we visit all the elements.
def has_diagonal_ones(a):
# a is a 2-dimensional square array of 0's and 1's
lower_left_upper_right = set()
upper_left_lower_right = set()
for x in range(len(a)):
for y in range(len(a)):
if a[x][y] == 0:
continue
i_lower_to_upper = x + y
i_upper_to_lower = x - y
if i_lower_to_upper in lower_left_upper_right:
return True
if i_upper_to_lower in upper_left_lower_right:
return True
lower_left_upper_right.add(i_lower_to_upper)
upper_left_lower_right.add(i_upper_to_lower)
return False
L = [[1, 0, 1],
[0, 0, 0],
[0, 0, 1]]
print(has_diagonal_ones(L))
>>> True