Chat-GPT's Solution To A Unique Hashset Key For Each Shape (Regardless of Reflection & Rotation)

[miranamer]

Solution

import numpy as np

def normalize_shape(shape):
    # Convert the shape to a binary numpy array
    binary_shape = np.array(shape, dtype=bool)

    # Generate canonical representations for rotations and reflections
    canonical_representations = []
    normalized_shape = binary_shape

    for _ in range(4):
        normalized_shape = np.rot90(normalized_shape)
        canonical_representations.append(normalized_shape)

    normalized_shape = np.fliplr(binary_shape)
    for _ in range(4):
        normalized_shape = np.rot90(normalized_shape)
        canonical_representations.append(normalized_shape)

    # Find the lexicographically smallest representation
    canonical_representations.sort(key=lambda x: tuple(x.flatten()))
    return canonical_representations[0]

def calculate_distance_signature(shape):
    # Convert the shape to a binary numpy array
    binary_shape = np.array(shape, dtype=bool)

    # Calculate the centroid (center of mass)
    rows, cols = np.nonzero(binary_shape)
    centroid = np.mean(rows), np.mean(cols)

    # Calculate the distances from each boundary point to the centroid
    distances = set()
    for r, c in zip(rows, cols):
        distance = np.sqrt((r - centroid[0])**2 + (c - centroid[1])**2)
        distances.add(distance)

    # Sort the distances for a consistent hash key
    sorted_distances = tuple(sorted(distances))

    return sorted_distances

def is_shape_stored(shape, hashmap):
    # Get the normalized representation of the shape
    normalized_shape = normalize_shape(shape)

    # Get the distance signature for the normalized shape
    distance_signature = calculate_distance_signature(normalized_shape)

    # Check if the distance signature is already stored
    if distance_signature in hashmap:
        return True

    # If the distance signature is not in the hashmap, store it
    hashmap.add(distance_signature)
    return False

stored_shapes = set()

# Test cases
m = [[1, 1, 0],
     [0, 1, 0],
     [0, 1, 0]]

n = [[0, 0, 0],
     [0, 0, 1],
     [1, 1, 1]]

print(is_shape_stored(m, stored_shapes))  # Output: True
print(is_shape_stored(n, stored_shapes))  # Output: True

Explanation

Problem Statement:
The problem is to determine if two 2D shapes are the same, regardless of rotation and reflection.

Solution Approach:
To achieve this, we need to find a way to convert each shape into a unique hash key such that equivalent shapes will produce the same hash key. This unique hash key allows us to perform quick lookups to check if a shape has already been encountered.

Step 1: Normalize Shapes
To handle rotations and reflections, we need to normalize the shapes into their canonical representations. We achieve this by generating all possible rotations and reflections of the shape and choosing the lexicographically smallest representation among them.

Step 2: Calculate Distance Signature
The next step is to compute the distance signature of the normalized shape. The distance signature represents the shape as a set of distances from each boundary point to the centroid (center of mass) of the shape. By using distances, we can capture the overall shape geometry and its invariance under rotation and reflection.

Step 3: Calculate Centroid and Distances
The centroid of a shape is computed as the average of the row and column indices of all the True elements (boundary points) in the shape. This gives us the center point around which we calculate the distances.

For each boundary point (row, col) in the shape, we calculate the Euclidean distance from that point to the centroid. These distances are collected in a set to eliminate duplicates.

Step 4: Sort Distances
To ensure a consistent hash key, we sort the distances obtained in Step 3. This is important because the distances can be in different orders for different shapes, but equivalent shapes should have the same distances when sorted.

Step 5: Using Hashsets for O(1) Lookup
We use a Python set (hashset) data structure to store the calculated distance signatures. Checking for the existence of a distance signature in the set has an average-case time complexity of O(1). This allows us to quickly determine if a shape has been encountered before.

Step 6: Check for Shape Existence
In the is_shape_stored function, we take a shape as input. First, we normalize the shape to get its canonical representation. Then, we calculate the distance signature of the normalized shape.

Step 7: Check for Existence in Hashset
We check if the calculated distance signature is already present in the hashset. If it is, this means the shape has been encountered before and is equivalent to a previously seen shape. Hence, we return True. Otherwise, we add the distance signature to the hashset and return False.

Conclusion:
The solution uses the normalized shape's distance signature as a unique hash key to perform shape existence checks in a hashset. This approach allows us to quickly determine if two shapes are the same regardless of their rotation or reflection. While the time complexity of calculating the distance signature is O(N) (N being the number of non-zero elements in the shape), the overall average-case time complexity of the solution remains O(1) due to the use of hashset for quick lookups.