# 840. Magic Squares In Grid
"""
a 3 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9
such that each row, column, and both diagonals all have the same sum. given a
row x col 'grid' of integers, how many 3 x 3 contiguous magic square subgrids
are there? note, while a magic square can only contain numbers from 1 to 9,
'grid' may contain numbers up to 15.
"""
class Solution(object):
def numMagicSquaresInside(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def isMagic(i, j):
s = "".join(
str(grid[i + x / 3][j + x % 3]) for x in [0, 1, 2, 5, 8, 7, 6, 3]
)
return grid[i][j] % 2 == 0 and (
s in "43816729" * 2 or s in "43816729"[::-1] * 2
)
return sum(
isMagic(i, j)
for i in range(len(grid) - 2)
for j in range(len(grid[0]) - 2)
if grid[i + 1][j + 1] == 5
)
if __name__ == "__main__":
obj = Solution()
print(obj.numMagicSquaresInside(grid=[[4, 3, 8, 4], [9, 5, 1, 9], [2, 7, 6, 2]]))
print(obj.numMagicSquaresInside(grid=[[8]]))
