CSES - Stars

You are given a grid, where each square is a sky square or a star square. The symbol . means a sky square and the symbol * means a star square.

Your task is to count how many different shapes of constellations there are in the grid. Two star squares belong to the same constellation if they are adjacent horizontally, vertically or diagonally.

Two constellations are considered to have a different shape even if they can be made the same with rotations and reflections. The examples in the code template illustrate this.

In a file stars.py, implement the function count_patterns, whose parameter is the description of a grid as a list of strings. The function should return the number of different constellation shapes.

def count_patterns(grid):
    # TODO

if __name__ == "__main__":
    grid = ["..*..*..",
            "**.....*",
            ".....**.",
            "...*....",
            ".**....*"]
    print(count_patterns(grid)) # 2

    grid = ["....*..*",
            "*.......",
            "......*.",
            "..*.....",
            "......*."]
    print(count_patterns(grid)) # 1

    grid = ["***.*.**",
            ".*..*..*",
            ".*.***..",
            ".......*",
            "......**"]
    print(count_patterns(grid)) # 4

    grid = ["***.***.",
            "..*...*.",
            "**..**..",
            "..*...*.",
            "**..**.."]
    print(count_patterns(grid)) # 1