Count Distinct Islands

Problem

Count the number of distinct island shapes in a grid of 0 and 1, where two shapes are the same when one can be translated to match the other.

For each island collect its cells, normalise them by subtracting the minimum row and column, and add the resulting tuple to a set. Return the size of the set.

Hint

Sorting the normalised cells makes the shape comparison order-independent.

Test cases

case 1

in: [[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]]

expected: 1

case 2

in: [[[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]]

expected: 3

case 3

in: [[[0]]]

expected: 0

case 4

in: [[[1]]]

expected: 1

case 5

in: [[[1,0,1]]]

expected: 1

Starter codePython

def count_distinct_islands(grid):
    # Your code here
    pass

5 test cases · run your code against them in the editor