A bacteria called streptosquarus comes in very peculiar shapes. The streptosquarus is flat with no perceived thickness. (It is essentially two-dimensional.) It is composed of an integer number of unit squares.
In addition, all the squares in the streptosquarus must be touching at least one other square of the bacteria along edges.
Write a program that takes a positive integer from the user and returns the number of possible different streptosquarus shapes of that size. Notice that there is only one streptosquarus of sizes one and two, but there are two of size three, five of size four, and 12 of size five.
모든 가능한 스트렙토스쿼러스의 형태를 생성하고, 회전과 대칭에 의한 중복을 제거하여 유일한 형태의 수를 계산해야 합니다. 회전과 대칭을 확인하는 로직을 추가하여 중복을 제거하는 것이 핵심입니다.
이 알고리즘은 크기가 커질수록 매우 느려질 수 있으므로, 크기가 5를 초과하는 경우에는 실행 시간을 고려해야 합니다.
from collections import deque
def generate_streptosquarus(n):
if n == 1:
return 1
# All possible moves from a square
moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]
# Generate all possible shapes by adding a square to each exposed edge
def generate_shapes(current_shape):
new_shapes = set()
for x, y in current_shape:
for dx, dy in moves:
new_pos = (x + dx, y + dy)
if new_pos not in current_shape:
new_shape = current_shape | {new_pos}
new_shapes.add(frozenset(new_shape))
return new_shapes
# Normalize shapes by rotating and flipping to remove duplicates
def normalize(shape):
# Convert frozenset to a sorted list of tuples to allow rotations and flips
shape = sorted(shape)
def rotate(shape):
return sorted((y, -x) for x, y in shape)
def flip(shape):
return sorted((-x, y) for x, y in shape)
# Generate all unique rotations and flips of the shape
unique_transforms = {tuple(shape)}
for _ in range(3): # Rotate three more times
shape = rotate(shape)
unique_transforms.add(tuple(shape))
# Flip the shape and get all its rotations
shape = flip(shape)
unique_transforms.add(tuple(shape))
for _ in range(3): # Rotate three more times
shape = rotate(shape)
unique_transforms.add(tuple(shape))
# Normalize to ensure all shapes start from (0, 0)
def normalize_shape(transform):
min_x = min(x for x, y in transform)
min_y = min(y for x, y in transform)
return tuple((x - min_x, y - min_y) for x, y in transform)
normalized_shapes = set(normalize_shape(transform) for transform in unique_transforms)
return min(normalized_shapes) # Return the smallest normalized shape
# Use a set to store all unique shapes
unique_shapes = set()
# Starting queue with a single square
queue = deque([frozenset([(0, 0)])])
while queue:
shape = queue.popleft()
if len(shape) == n:
norm_shape = normalize(shape)
unique_shapes.add(norm_shape)
else:
for new_shape in generate_shapes(shape):
queue.append(new_shape)
return len(unique_shapes)
# Example usage
def main():
print("Enter a positive integer or 'q' to quit.")
while True:
user_input = input("Enter a integer number or 'q' to quit: ")
if user_input.lower() == 'q':
print("Program has ended.")
break
try:
n = int(user_input)
if n < 1:
print("Warning: Please enter a positive integer.")
elif n > 6:
print("Warning: Calculations for numbers greater than 6 may be slow.")
result = generate_streptosquarus(n)
print(f"Number of possible shapes for a streptosquarus of size {n}: {result}")
except ValueError:
print("Warning: Please enter a valid integer or 'q' to quit.")
if __name__ == "__main__":
main()