Number of distinct islands

2023-08-29

An answer to this question on Stack Overflow.

Question

There is a leetcode question as:

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

An island is considered to be the same as another if they have the same shape, or have the same shape after rotation (90, 180, or 270 degrees only) or reflection (left/right direction or up/down direction).

Return the number of distinct islands.

I came up with a solution and it passes 508 test cases out of 510. I believe my solution should work and not sure where do i exactly miss, and was wondering if anyone can add some insights or fix my code?

following is my solution:

def numDistinctIslands2(self, grid: List[List[int]]) -> int:
    islands = []
    visited = set()
    def dfs(i, j, curr_island):  #  standard dfs to find all islands
        if (
            0 <= i < len(grid)
            and 0 <= j < len(grid[0])
            and grid[i][j] == 1
            and (i, j) not in visited
        ):
            visited.add((i, j))
            curr_island.append((i, j))
            dfs(i + 1, j, curr_island)
            dfs(i - 1, j, curr_island)
            dfs(i, j + 1, curr_island)
            dfs(i, j - 1, curr_island)
    for i in range(len(grid)):  #  loop over the entire grid
        for j in range(len(grid[0])):
            if grid[i][j] == 1 and (i, j) not in visited:
                curr_island = []
                dfs(i, j, curr_island)
                islands.append(curr_island)
    distinct_islands = set()  # keep the representative of all similar islands
    def get_distinct_islands(islands):
        for island in islands:
            island_signature_x = defaultdict(int)  #  x(row) signature of island
            island_signature_y = defaultdict(int)  #  y(col) signature of island
            for x, y in island:
                #  calculate x signature (number of "1" in each row of the island)
                island_signature_x[x] += 1
                #  calculate y signature (number of "1" in each column of the island)
                island_signature_y[y] += 1
            x_val = []
            # loop through sorted (we need to have the orders intact) signature of rows  # ex.  [1, 2, 1] is different than [1, 1, 2]
            for k, v in sorted(island_signature_x.items(), key=lambda i: i[0]):
                x_val.append(str(v))
            x_sign = ".".join(x_val)  #  string of x signature
            x_sign_r = ".".join(x_val[::-1])  # reverse string of x signature
            y_val = []
            #  loop through sorted (we need to have the orders intact) signature of columns
            for k, v in sorted(island_signature_y.items(), key=lambda i: i[0]):
                y_val.append(str(v))
            y_sign = ".".join(y_val)  #  string of y signature
            y_sign_r = ".".join(y_val[::-1])  # reverse string of y signature
            # if none of the rotations/reflections (8 possibilities) are registered then register it as a new island
            if (
                (x_sign, y_sign) not in distinct_islands
                and (x_sign, y_sign_r) not in distinct_islands
                and (x_sign_r, y_sign) not in distinct_islands
                and (x_sign_r, y_sign_r) not in distinct_islands
                and (y_sign, x_sign) not in distinct_islands
                and (y_sign, x_sign_r) not in distinct_islands
                and (y_sign_r, x_sign) not in distinct_islands
                and (y_sign_r, x_sign_r) not in distinct_islands
            ):
                distinct_islands.add((x_sign, y_sign))
    get_distinct_islands(islands)
    return len(distinct_islands)

input example as follows... my algorithm returns 68 and it says it should be 69. It's the 509th out of 510 test cases and all previous (508) test cases are passing:

[[0,1,0,1,0,1,1,1,1,0,1,1,1,1,0,0,0,1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,0,1,1,1,0,1,1,1,0,1,0,0,0,1,1,1,1],[0,1,1,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,0,1,1,0,1,0,0,1,1],[0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,1,1,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,1,1,1],[1,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,0,0,1,0,1,0,0,1,1,0,1,0,1,0,0],[0,0,1,0,0,1,1,1,1,1,1,1,0,0,1,0,1,1,1,0,0,0,1,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1],[1,1,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,1,0],[0,0,0,0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,1,1,1,0,0,1,0,1,1,1,1,1,0,0,0,0,1,0,1,0,1,1,1,1,1,1,0,0,1,1,1,0],[0,0,1,1,0,1,0,1,1,0,0,0,1,0,1,0,1,1,1,0,0,0,1,1,0,0,0,0,0,1,1,0,1,0,1,1,1,1,0,1,1,0,0,1,0,1,0,1,1,0],[1,1,1,0,0,1,0,1,1,0,0,1,1,1,0,1,0,1,1,0,0,1,0,0,1,1,0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,0,1,0,0,1,1,1,1,0],[1,0,0,0,1,1,0,0,1,0,0,1,0,1,1,1,1,0,0,1,1,1,1,0,0,1,1,0,1,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1],[0,1,1,1,0,0,1,1,1,0,0,0,1,1,0,1,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1],[0,1,0,0,0,1,1,0,1,0,0,0,1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,1],[1,1,0,1,1,1,0,0,1,1,0,1,0,0,0,0,0,0,0,1,0,1,1,0,1,1,0,0,1,0,0,1,0,1,1,1,0,1,0,1,0,1,1,1,0,0,1,0,0,1],[0,1,1,0,0,1,1,0,0,0,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1],[0,0,1,0,0,0,0,1,1,1,1,1,0,1,1,0,1,0,1,0,0,1,1,1,0,1,0,0,0,0,1,0,1,1,0,0,1,1,1,0,0,0,0,0,1,1,1,1,1,0],[0,0,0,1,0,0,0,1,1,0,1,0,1,1,1,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,1,1,1,0,0,1,0,1,0,1,1,0,0,1,1,1,1],[1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,1,1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,1,1,1,1,0,1,1,0,1,1,0],[1,0,0,1,1,0,0,1,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,0,0,0,1,1,1,0,1,0,1,1,0],[1,0,1,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1],[1,0,0,1,0,1,0,1,0,0,1,0,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,0,1,0,1,1,0,1,1,1,0,1,1,0,0,0,0,1,0,0,1,0,1,1],[1,1,0,0,1,1,1,0,0,0,1,0,1,0,0,0,1,1,0,1,1,1,1,1,0,1,1,1,0,0,1,0,1,1,1,1,1,0,0,0,0,1,1,0,1,1,1,1,0,0],[1,0,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,1,0,0,1,1,0,1,1,1,0,0,1,0,0,0,1],[1,1,1,0,0,1,0,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,1,0,1,0,1,0,1,0,0,1,0,1,0],[1,0,1,1,1,0,1,0,0,0,1,1,0,1,1,1,1,1,0,0,1,1,1,0,0,1,1,1,1,0,0,1,1,1,0,1,1,0,0,1,1,1,0,0,0,1,1,0,0,1],[1,0,0,1,1,0,0,1,0,0,0,1,0,0,1,1,1,1,0,0,1,1,1,0,0,0,0,1,1,0,1,1,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0],[1,1,1,0,0,1,0,1,1,0,1,0,0,1,1,1,1,1,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,1,1,1,1,0,1,1,0,1,1,0,0,0,0],[1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,0,1,1,0,0],[1,0,1,1,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,1,1,0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,0,1,1,1],[0,1,1,0,1,1,1,1,0,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,1,1,1,1,1,0,0,1,0,0,1,0,1,1,1,1,0,0,0,0,1,1,1,0,0,1],[0,0,0,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0],[0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,1,1,0,0,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,1,0,1,1,1,0,1,1,0,0],[0,0,1,1,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,0,0,0,0,0,0,1,0],[1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,1,0,0,0,1,0,0,1,1,1,1,1,0,0,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,1],[0,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,1,1,1,0,1,0,1],[1,0,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,0,1,1,1,0,1,0,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,0,1,0,1,1],[0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,0,0,1,0,1,1,1,0,0,1,0,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1,0,0],[1,0,0,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,1,1,1,1,0],[0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,0,1,0,1,1,0,1,1,1,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,1,1],[0,0,0,1,0,1,1,1,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,1,1],[0,0,1,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,0,1,0,0,0,1,1,0,1,1,1,0,0,0],[1,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,1,1,0,0,1,0,1,0,1,1,1,1,1,1,0],[0,1,1,1,0,0,1,0,0,0,0,0,1,1,0,0,1,1,0,1,0,0,0,1,0,1,0,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,0],[1,0,1,0,1,1,0,0,0,1,1,0,1,1,1,1,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1,0,1,0],[1,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1,1,1,0,1,1,0,1,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,1,0,0],[1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,1,1,0,0,0,1,0,0,0,1,0,0,1],[1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,1,1,0],[1,1,0,1,0,1,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,1,1,0,1,0,1,0,0],[1,0,0,1,0,1,0,1,0,0,0,1,1,0,0,1,0,1,0,1,0,1,0,1,1,1,0,0,1,1,1,1,1,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,0,0],[1,0,1,1,1,0,0,1,1,1,0,0,0,1,1,1,1,1,0,0,1,0,1,1,0,1,1,1,1,0,0,0,0,1,0,1,0,1,1,0,0,1,0,0,0,0,0,0,1,1]]

68 unique islands that my algorithm finds:

Answer

I see your code and I think "not enough functions".

Using small, meaningful functions is useful because it allows you to develop unit tests that help to isolate bugs and erroneous assumptions. It also helps you mentally decompose the problem so that your thinking about it is clearer.

I've rewritten your code below and written functions to accomplish several sequential steps:

Give each island a unique label
Find the bounding box of each island
Extract the bounding box from the labels grid and zero-out anything that isn't the island we're interested in
Perform all the possible transformations to the island and (for performance) hash the result of each transformation (note that these hashes might collide)
Loop through all pairs of islands to see if they share any hashed transformations. If so, one of the two is non-unique.

At each stage I can test that the functions I'm writing are working, either by handcrafting a test (in the case of labeling) or by using hypothesis to automatically generate hundreds of randomized tests for which I can check that a property holds such as:

if I flip a horizontally twice I should get the original back
if I perform a random transformation to an island it should still share a hash with the original

These tests give me confidence at each stage that I've written my code correctly so that, when I finally run it, it just does the right thing. And that's enabled by having modular code with small functions.

import random
from dataclasses import dataclass
from typing import Dict, Final, List, Set, Tuple
from hypothesis import given
from hypothesis import strategies as st
# Constant for the ocean between islands
OCEAN: Final[int] = 0
@dataclass
class BoundingBox:
    """Bounding box dataclass"""
    xmin: int
    xmax: int
    ymin: int
    ymax: int
    def expand(self, x: int, y: int) -> None:
        self.xmin = min(self.xmin, x)
        self.xmax = max(self.xmax, x)
        self.ymin = min(self.ymin, y)
        self.ymax = max(self.ymax, y)
def get_island_labels(grid: List[List[int]]) -> List[List[int]]:
    """
    Convert 0-1 grid of island locations to a grid of labels
    where each island is assigned a unique number
    """
    height = len(grid)
    width = len(grid[0])
    labels = [[OCEAN for x in range(width)] for y in range(height)]
    # Find all contiguous parts of the island using DFS
    def _dfs_labeler(x: int, y: int, label: int, visited: Set[Tuple[int, int]]) -> bool:
        if not 0 <= x < width:
            return False
        if not 0 <= y < height:
            return False
        if grid[y][x] == OCEAN:
            return False
        if (x, y) in visited:
            return False
        visited.add((x, y))
        labels[y][x] = label
        _dfs_labeler(x + 1, y, label, visited)
        _dfs_labeler(x - 1, y, label, visited)
        _dfs_labeler(x, y + 1, label, visited)
        _dfs_labeler(x, y - 1, label, visited)
        return True
    current_label = 1
    for y in range(len(grid)):
        for x in range(len(grid[0])):
            if labels[y][x] != OCEAN:
                continue
            if _dfs_labeler(x, y, current_label, set()):
                current_label += 1
    return labels
def get_island_bounding_boxes(labels: List[List[int]]) -> Dict[int, BoundingBox]:
    """Convert a labels array into a {Label: BoundingBox} dictionary"""
    islands: Dict[int, BoundingBox] = {}
    for y in range(len(labels)):
        for x in range(len(labels[0])):
            if labels[y][x] == OCEAN:
                continue
            if labels[y][x] not in islands:
                islands[labels[y][x]] = BoundingBox(x, x, y, y)
            else:
                islands[labels[y][x]].expand(x, y)
    return islands
def mask_island(grid: List[List[int]], island: int) -> List[List[int]]:
    """Convert a grid of labels to a grid of 0-1 where 1 is the island"""
    return [
        [1 if grid[y][x] == island else 0 for x in range(len(grid[0]))]
        for y in range(len(grid))
    ]
def list2d_to_tuple2d(grid: List[List[int]]) -> List[List[int]]:
    """Convert a 2d list to a 2d tuple"""
    return tuple([tuple(row) for row in grid])
def extract_islands(
    labels: List[List[int]], islands: Dict[int, BoundingBox]
) -> Dict[int, List[List[int]]]:
    """
    Given a labels grid and a dictionary of bounding boxes, extract the
    islands into a dictionary of small grids where each grid contains only
    the island identified by the label
    """
    return {
        k: mask_island(
            [labels[y][v.xmin : v.xmax + 1] for y in range(v.ymin, v.ymax + 1)], k
        )
        for k, v in islands.items()
    }
def identity(grid: List[List[int]]) -> List[List[int]]:
    return grid
def rot90(grid: List[List[int]]) -> List[List[int]]:
    return tuple(zip(*grid[::-1]))
def rot180(grid: List[List[int]]) -> List[List[int]]:
    return rot90(rot90(grid))
def rot270(grid: List[List[int]]) -> List[List[int]]:
    return rot90(rot90(rot90(grid)))
def flip(grid: List[List[int]]) -> List[List[int]]:
    return tuple(reversed(grid))
def flop(grid: List[List[int]]) -> List[List[int]]:
    return tuple([tuple(reversed(row)) for row in grid])
# List of transformations we can do to an island
operations = [identity, rot90, rot180, rot270, flip, flop]
class TransformHasher:
    """Handy class to store hashes of the various transformations applied to a grid"""
    def __init__(self, t: List[List[int]]) -> None:
        self.t = t
        # Order independent tuple of all operations
        self.hashes = {hash(list2d_to_tuple2d(op(t))) for op in operations}
    def __eq__(self, o: "TransformHasher") -> bool:
        """Two islands are equal if they have any hashes (transformations) in common"""
        isect = self.hashes.intersection(o.hashes)
        return len(isect) != 0
def pretty_print(grid: List[List[int]]) -> None:
    """Print a grid in colours, useful for debugging"""
    # List of ansi colors
    colors = [
        "\033[31m",
        "\033[32m",
        "\033[33m",
        "\033[34m",
        "\033[35m",
        "\033[36m",
        "\033[37m",
    ]
    for row in grid:
        for x in row:
            print(
                colors[x % len(colors)] + ("X" if x != 0 else " ") + "\033[39m", end=""
            )
        print("")
    print("\n")
def count_unique_islands(grid: List[List[int]]) -> int:
    """Count the number of unique islands"""
    labels = get_island_labels(grid)
    islands = get_island_bounding_boxes(labels)
    extracted_islands = extract_islands(labels, islands)
    # Find all islands that are the same and print them in groups
    vs = list(extracted_islands.values())
    transforms = [TransformHasher(v) for v in vs]
    unique = set(range(len(transforms)))
    for i in range(len(transforms)):
        for j in range(i + 1, len(transforms)):
            # Note that the transform hashes might collide
            # Bulletproof code would check hashes and then do
            # a more expensive true equality check
            if j in unique and transforms[i] == transforms[j]:
                unique.remove(j)
    return len(unique)
def main() -> None:
    grid = [
      [0,1,0,1,0,1,1,1,1,0,1,1,1,1,0,0,0,1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,0,1,1,1,0,1,1,1,0,1,0,0,0,1,1,1,1],
      [0,1,1,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,0,1,1,0,1,0,0,1,1],
      [0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,1,1,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,1,1,1],
      [1,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,0,0,1,0,1,0,0,1,1,0,1,0,1,0,0],
      [0,0,1,0,0,1,1,1,1,1,1,1,0,0,1,0,1,1,1,0,0,0,1,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1],
      [1,1,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,1,0],
      [0,0,0,0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,1,1,1,0,0,1,0,1,1,1,1,1,0,0,0,0,1,0,1,0,1,1,1,1,1,1,0,0,1,1,1,0],
      [0,0,1,1,0,1,0,1,1,0,0,0,1,0,1,0,1,1,1,0,0,0,1,1,0,0,0,0,0,1,1,0,1,0,1,1,1,1,0,1,1,0,0,1,0,1,0,1,1,0],
      [1,1,1,0,0,1,0,1,1,0,0,1,1,1,0,1,0,1,1,0,0,1,0,0,1,1,0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,0,1,0,0,1,1,1,1,0],
      [1,0,0,0,1,1,0,0,1,0,0,1,0,1,1,1,1,0,0,1,1,1,1,0,0,1,1,0,1,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1],
      [0,1,1,1,0,0,1,1,1,0,0,0,1,1,0,1,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1],
      [0,1,0,0,0,1,1,0,1,0,0,0,1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,1],
      [1,1,0,1,1,1,0,0,1,1,0,1,0,0,0,0,0,0,0,1,0,1,1,0,1,1,0,0,1,0,0,1,0,1,1,1,0,1,0,1,0,1,1,1,0,0,1,0,0,1],
      [0,1,1,0,0,1,1,0,0,0,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1],
      [0,0,1,0,0,0,0,1,1,1,1,1,0,1,1,0,1,0,1,0,0,1,1,1,0,1,0,0,0,0,1,0,1,1,0,0,1,1,1,0,0,0,0,0,1,1,1,1,1,0],
      [0,0,0,1,0,0,0,1,1,0,1,0,1,1,1,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,1,1,1,0,0,1,0,1,0,1,1,0,0,1,1,1,1],
      [1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,1,1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,1,1,1,1,0,1,1,0,1,1,0],
      [1,0,0,1,1,0,0,1,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,0,0,0,1,1,1,0,1,0,1,1,0],
      [1,0,1,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1],
      [1,0,0,1,0,1,0,1,0,0,1,0,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,0,1,0,1,1,0,1,1,1,0,1,1,0,0,0,0,1,0,0,1,0,1,1],
      [1,1,0,0,1,1,1,0,0,0,1,0,1,0,0,0,1,1,0,1,1,1,1,1,0,1,1,1,0,0,1,0,1,1,1,1,1,0,0,0,0,1,1,0,1,1,1,1,0,0],
      [1,0,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,1,0,0,1,1,0,1,1,1,0,0,1,0,0,0,1],
      [1,1,1,0,0,1,0,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,1,0,1,0,1,0,1,0,0,1,0,1,0],
      [1,0,1,1,1,0,1,0,0,0,1,1,0,1,1,1,1,1,0,0,1,1,1,0,0,1,1,1,1,0,0,1,1,1,0,1,1,0,0,1,1,1,0,0,0,1,1,0,0,1],
      [1,0,0,1,1,0,0,1,0,0,0,1,0,0,1,1,1,1,0,0,1,1,1,0,0,0,0,1,1,0,1,1,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0],
      [1,1,1,0,0,1,0,1,1,0,1,0,0,1,1,1,1,1,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,1,1,1,1,0,1,1,0,1,1,0,0,0,0],
      [1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,0,1,1,0,0],
      [1,0,1,1,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,1,1,0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,0,1,1,1],
      [0,1,1,0,1,1,1,1,0,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,1,1,1,1,1,0,0,1,0,0,1,0,1,1,1,1,0,0,0,0,1,1,1,0,0,1],
      [0,0,0,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0],
      [0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,1,1,0,0,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,1,0,1,1,1,0,1,1,0,0],
      [0,0,1,1,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,0,0,0,0,0,0,1,0],
      [1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,1,0,0,0,1,0,0,1,1,1,1,1,0,0,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,1],
      [0,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,1,1,1,0,1,0,1],
      [1,0,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,0,1,1,1,0,1,0,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,0,1,0,1,1],
      [0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,0,0,1,0,1,1,1,0,0,1,0,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1,0,0],
      [1,0,0,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,1,1,1,1,0],
      [0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,0,1,0,1,1,0,1,1,1,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0],
      [0,0,1,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,1,1],
      [0,0,0,1,0,1,1,1,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,1,1],
      [0,0,1,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,0,1,0,0,0,1,1,0,1,1,1,0,0,0],
      [1,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,1,1,0,0,1,0,1,0,1,1,1,1,1,1,0],
      [0,1,1,1,0,0,1,0,0,0,0,0,1,1,0,0,1,1,0,1,0,0,0,1,0,1,0,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,0],
      [1,0,1,0,1,1,0,0,0,1,1,0,1,1,1,1,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1,0,1,0],
      [1,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1,1,1,0,1,1,0,1,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,1,0,0],
      [1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,1,1,0,0,0,1,0,0,0,1,0,0,1],
      [1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,1,1,0],
      [1,1,0,1,0,1,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,1,1,0,1,0,1,0,0],
      [1,0,0,1,0,1,0,1,0,0,0,1,1,0,0,1,0,1,0,1,0,1,0,1,1,1,0,0,1,1,1,1,1,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,0,0],
      [1,0,1,1,1,0,0,1,1,1,0,0,0,1,1,1,1,1,0,0,1,0,1,1,0,1,1,1,1,0,0,0,0,1,0,1,0,1,1,0,0,1,0,0,0,0,0,0,1,1]]  # fmt: skip
    print(count_unique_islands(grid))
#######################
# TEST SUITE
#######################
def test_get_island_labels() -> None:
    grid = [[1, 1, 0, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 1, 1, 1]]
    assert get_island_labels(grid) == [
        [1, 1, 0, 0, 0],
        [1, 1, 1, 0, 0],
        [0, 0, 0, 2, 2],
        [0, 0, 2, 2, 2],
    ]
def test_get_islands() -> None:
    grid = [[1, 1, 0, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 1, 1, 1]]
    assert get_island_bounding_boxes(get_island_labels(grid)) == {
        1: BoundingBox(xmin=0, xmax=2, ymin=0, ymax=1),
        2: BoundingBox(xmin=2, xmax=4, ymin=2, ymax=3),
    }
def test_extract_islands() -> None:
    grid = [[1, 1, 0, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 1, 1, 1]]
    labels = get_island_labels(grid)
    islands = get_island_bounding_boxes(labels)
    assert extract_islands(labels, islands) == {
        1: [[1, 1, 0], [1, 1, 1]],
        2: [[0, 1, 1], [1, 1, 1]],
    }
@given(
    n=st.integers(min_value=1, max_value=20), m=st.integers(min_value=1, max_value=20)
)
def test_rot360(n: int, m: int) -> None:
    grid = tuple([tuple([random.randint(0, 1) for _ in range(m)]) for _ in range(n)])
    assert rot90(rot90(rot90(rot90(grid)))) == grid
@given(
    n=st.integers(min_value=1, max_value=20), m=st.integers(min_value=1, max_value=20)
)
def test_flip(n: int, m: int) -> None:
    grid = tuple([tuple([random.randint(0, 1) for _ in range(m)]) for _ in range(n)])
    assert flip(flip(grid)) == grid
@given(
    n=st.integers(min_value=1, max_value=20), m=st.integers(min_value=1, max_value=20)
)
def test_flop(n: int, m: int) -> None:
    grid = tuple([tuple([random.randint(0, 1) for _ in range(m)]) for _ in range(n)])
    assert flop(flop(grid)) == grid
@given(
    n=st.integers(min_value=1, max_value=20),
    m=st.integers(min_value=1, max_value=20),
    opi=st.integers(min_value=0, max_value=len(operations) - 1),
)
def test_hash(n: int, m: int, opi: int) -> None:
    grid = [[random.randint(0, 1) for _ in range(m)] for _ in range(n)]
    ogrid = operations[opi](grid)
    assert TransformHasher(grid) == TransformHasher(ogrid)
if __name__ == "__main__":
    main()