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.
Solution
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.