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()




다익스트라 알고리즘은 그래프 내의 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 다음은 자바스크립트로 다익스트라 알고리즘을 구현한 예시와 해당 코드의 설명입니다.

구현:

class PriorityQueue {
  constructor() {
    this.values = [];
  }

  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }

  dequeue() {
    return this.values.shift();
  }

  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

class WeightedGraph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(vertex1, vertex2, weight) {
    this.adjacencyList[vertex1].push({ node: vertex2, weight });
    this.adjacencyList[vertex2].push({ node: vertex1, weight });
  }

  Dijkstra(start, finish) {
    const nodes = new PriorityQueue();
    const distances = {};
    const previous = {};
    let path = [];
    let smallest;

    for (let vertex in this.adjacencyList) {
      if (vertex === start) {
        distances[vertex] = 0;
        nodes.enqueue(vertex, 0);
      } else {
        distances[vertex] = Infinity;
        nodes.enqueue(vertex, Infinity);
      }
      previous[vertex] = null;
    }

    while (nodes.values.length) {
      smallest = nodes.dequeue().val;
      if (smallest === finish) {
        while (previous[smallest]) {
          path.push(smallest);
          smallest = previous[smallest];
        }
        break;
      }

      if (smallest || distances[smallest] !== Infinity) {
        for (let neighbor in this.adjacencyList[smallest]) {
          let nextNode = this.adjacencyList[smallest][neighbor];
          let candidate = distances[smallest] + nextNode.weight;
          let nextNeighbor = nextNode.node;

          if (candidate < distances[nextNeighbor]) {
            distances[nextNeighbor] = candidate;
            previous[nextNeighbor] = smallest;
            nodes.enqueue(nextNeighbor, candidate);
          }
        }
      }
    }
    return path.concat(smallest).reverse();
  }
}

설명:

  1. PriorityQueue: 우선순위 큐를 구현한 클래스입니다. 이 큐는 다익스트라 알고리즘에서 가장 짧은 거리의 정점을 빠르게 찾기 위해 사용됩니다.
  2. WeightedGraph: 가중치가 있는 그래프를 나타내는 클래스입니다.
  3. addVertex: 그래프에 정점을 추가하는 메서드입니다.
  4. addEdge: 그래프에 간선과 그 간선의 가중치를 추가하는 메서드입니다.
  5. Dijkstra: 다익스트라 알고리즘을 구현한 메서드입니다. 시작 정점과 종료 정점을 인수로 받아서 시작 정점에서 종료 정점까지의 최단 경로를 배열로 반환합니다.

이 코드는 간선의 가중치가 양수일 때만 작동합니다. 만약 음수 가중치의 간선이 있다면, 다른 알고리즘을 사용해야 합니다.

+ Recent posts

티스토리툴바