질문제 코드에서 무엇이 잘못되었을까요? ㅜㅜ
안녕하세요, 현재 파이썬 독학을 하고 있는 사람입니다. python으로 treemap을 만들고자 하는 문제를 풀고 있는데, 답이 자꾸 나오지 않아서 무엇이 문제인지 파악하고 싶습니다! (time out 문제도 같이 발생하고 있습니다.) 문제의 로직은 아래와 같습니다. **1단계: 정렬** 여기에는 특정 방정식이 없습니다. 데이터 포인트 목록을 값의 내림차순으로 정렬하면 됩니다. (helper function 사용) 2단계: 레이아웃 초기화 방향을 결정합니다. orientation={left edge: if bounding box width ≥ bounding box height top edge: otherwise **3단계: 행 형성** For each value of k: 1) Calculate row fraction: row fraction= sum of values of first k data points / sum of all values in the list 2) Calculate individual fractions: fraction(i) = value of data point i / sum of values of first data points 3) Calculate heights and widths: height(i) =row fraction × bounding box height × fraction(i) width(i) = row fraction × bounding box width × fraction(i) 4) Calculate aspect ratios: aspect ratio(i) = max(width(i), height(i)) / min(width(i), height(i)) 5) Calculate distortion: distortion = max(aspect ratios) 각 값에 대해 : 1. 순서가 지정된 처음 k개의 데이터 포인트를 가져와 해당 값을 합산합니다. 그런 다음 전체 목록에 있는 모든 값의 합으로 나눕니다. 이 분수는 이 직사각형 행이 차지해야 하는 경계 상자 영역의 분수입니다. 2. k개의 데이터 포인트 각각에 대해 해당 값을 k개의 합으로 나눕니다. 행의 값. 이는 이 데이터 포인트의 직사각형이 차지해야 하는 행 영역의 비율입니다. 행의 직사각형은 위에서 아래로(행이 경계 상자의 왼쪽 가장자리에 있는 경우) 또는 왼쪽에서 오른쪽으로(행이 위쪽 가장자리에 있는 경우) 배치됩니다. 3. 위의 계산을 통해 행에 있는 각 직사각형의 높이와 너비를 결정할 수 있습니다. 긴 변을 짧은 변으로 나누어 각 직사각형의 종횡비를 계산합니다. 종횡비는 1보다 크거나 같은 숫자입니다. 여기서 1은 직사각형이 정사각형임을 의미하고, 종횡비가 매우 높으면 직사각형이 매우 왜곡되었음을 의미합니다. 4. 이 행의 왜곡을 행에 있는 직사각형의 최대 종횡비로 정의합니다. 5. k= 1인 경우 또는 이 행에 대한 왜곡이 이전 k에 대한 왜곡보다 작거나 같은 경우, 다음으로 넘어가세요. k의 다음 값이 없는 경우 이 행은 이미 목록의 모든 데이터 포인트를 사용하고 있으므로 프로세스를 중지하고 이 k 값을 유지합니다. (왜곡이 가장 낮습니다). 반면, 이전 k에 비해 왜곡이 더 크다면, 우리는 다음 k로 넘어가지 않을 것입니다 현재 k를 유지하지도 않음. 대신 프로세스를 중지하고 이전 k 값을 선택하십시오. (왜곡이 가장 적은 것). ** 재귀함수로 풀 것 ** 제가 만들고자 하는 function은 compute_rectangles(t, bounding_rec_width=1.0, bounding_rec_height=1.0) 이며, 제가 만들어야하는 function과 제가 만든 코드는 아래와 같습니다. (parameter 변경 불가, helper function 만들어서 풀어야함) def compute_rectangles(t, bounding_rec_width=1.0, bounding_rec_height=1.0): ''' Computes the rectangles for drawing a treemap of the provided tree. Inputs: t: (Tree) a tree bounding_rec_width, bounding_rec_height: (float) the width and height of the bounding rectangle. Returns: a list of Rectangle objects. ''' rectangles = [] # Initialize the list of rectangles stack = [(t, bounding_rec_width, bounding_rec_height)] # Initialize a stack for iterative processing while stack: current_tree, current_width, current_height = stack.pop() if not current_tree.children: # Base case: if the tree is a leaf, create a rectangle and add it to the list origin = (0.0, 0.0) # Set a default origin for the leaf node rectangles.append(Rectangle(origin, (current_width, current_height), current_tree.key)) else: # Sort the children of the tree sorted_tree_list = sorted_trees(current_tree.children) # Initialize the list of rectangles for the current tree row_layout = [] # Get the next row layout and leftover rectangle for tree in sorted_tree_list: # Calculate aspect ratio for each rectangle in the row row_sum = tree.value if not row_layout else sum(child[0].value for child in row_layout) + tree.value row_fraction = row_sum / sum(child.value for child in sorted_tree_list) width = row_fraction * current_width # Calculate width for each rectangle in the row height = row_fraction * current_height aspect_ratio = max(width, height) / min(width, height) # Check if adding the current rectangle improves the aspect ratio if not row_layout or aspect_ratio <= row_layout[-1][1]: row_layout.append((tree, aspect_ratio, width, height)) else: break # Recursively call the function for the current tree's children for child, _, child_width, child_height in row_layout: stack.append((child, child_width, child_height)) return rectangles 원하는 답은 이런 형식입니다. data_rectangles = {'birds': {'Apr': <tree.Tree object at 0x7faa9edaa3d0>, 'Aug': <tree.Tree object at 0x7faa9ed06cd0>, 'Dec': <tree.Tree...ect at 0x7faa9efd3b20>, 'Dec': <tree.Tree object at 0x7faa9f064070>, 'Feb': <tree.Tree object at 0x7faa9efce940>, ...}} key = 's1' @pytest.mark.parametrize("key", TEST_KEYS) def test_compute_rectangles_flat(data_rectangles, key): expected_recs = [{'color_code': [''], 'height': 0.5, 'label': 'B40', 'width': 0.8, ...}, {'color_code': [''], 'height': 0.5, 'label': 'C40', 'width': 0.8, ...}, {'color_code': [''], 'height': 1.0, 'label': 'D20', 'width': 0.19999999999999996, ...}] 혹은 ipython3으로 실행했을 경우, In [14]: data_flat = treemap.load_trees('data/sparrows.json') In [15]: recs = treemap.compute_rectangles(data_flat['s1']) In [16]: for r in recs: ...: print(r) ...: # x, y, width, height, label 순입니다. RECTANGLE 0.0000 0.0000 0.8000 0.5000 B40 RECTANGLE 0.0000 0.5000 0.8000 0.5000 C40 RECTANGLE 0.8000 0.0000 0.2000 1.0000 D20 In [17]: recs = treemap.compute_rectangles(data_flat['s2']) In [18]: for r in recs: ...: print(r) ...: RECTANGLE 0.0000 0.0000 0.6000 0.5000 Six (a) RECTANGLE 0.0000 0.5000 0.6000 0.5000 Six (b) RECTANGLE 0.6000 0.0000 0.4000 0.3750 Three RECTANGLE 0.6000 0.3750 0.4000 0.2500 Two RECTANGLE 0.6000 0.6250 0.2667 0.1875 One (a) RECTANGLE 0.6000 0.8125 0.2667 0.1875 One (b) RECTANGLE 0.8667 0.6250 0.1333 0.3750 One (c) In [19]: recs = treemap.compute_rectangles(data_flat['s3']) In [20]: for r in recs: ...: print(r) ...: RECTANGLE 0.0000 0.0000 0.5000 0.5000 6 RECTANGLE 0.0000 0.5000 0.5000 0.5000 6 RECTANGLE 0.5000 0.0000 0.5000 0.3333 4 RECTANGLE 0.5000 0.3333 0.5000 0.2500 3 RECTANGLE 0.5000 0.5833 0.4000 0.2083 2x RECTANGLE 0.5000 0.7917 0.4000 0.2083 2y RECTANGLE 0.9000 0.5833 0.1000 0.4167 1 # data_flat['s2']는 트리입니다. 그리고 helper functions(sorted_trees(tree_list), compute_row(bounding_rec, row_data, total_sum))과 class Rectangle는 아래와 같습니다. class Rectangle: ''' Simple class for representing rectangles. Attributes: x, y: (float) coordinates of rectangle's origin width, height: (float) the rectangle's width and height label: (str) text label for the rectangle color_code: (tuple) tuple for determining what color the rectangle should be ''' def __init__(self, origin, size, label="", color_code=("",)): ''' Constructs a new Rectangle. Inputs: origin: (pair of float) x and y coordinates of the rectangle's origin size: (pair of float) the width and height of the rectangle ''' # Validate parameters validate_tuple_param(origin, "origin") validate_tuple_param(origin, "size") assert label is not None, "Rectangle label can't be None" assert isinstance(label, str), "Rectangle label must be a string" assert color_code is not None, "Rectangle color_code can't be None" assert isinstance(color_code, tuple), \ "Rectangle color_code must be a tuple" self.x, self.y = origin self.width, self.height = size self.label = label self.color_code = color_code def __str__(self): format_string = "RECTANGLE {:.4f} {:.4f} {:.4f} {:.4f} {}" return format_string.format(self.x, self.y, self.width, self.height, self.label) def __repr__(self): return str(self) def sorted_trees(tree_list): ''' Sort a list of Tree instances by the value of their roots in descending order. Ties are broken by the key of the root, in (forward) alphabetical order. Returns a new sorted list without modifying the input list. Inputs: tree_list: list of Tree instances, each with an integer value. Returns: list of Tree instances, sorted. ''' return sorted(tree_list, key=lambda t: (-t.value, t.key)) def compute_row(bounding_rec, row_data, total_sum): ''' Lay out the given data points as rectangles in one row of a treemap. The row will be against the left or top edge of the bounding rectangle, depending on whether the rectangle is at least as wide as it is tall. Inputs: bounding_rec: (Rectangle) the bounding rectangle row_data: (list of Tree) the list of data points that should be included in this row. total_sum: (integer) the total value of all the rectangles that will eventually fill the bounding rectangle (not just those in this row). Returns: a tuple (row_layout, leftover_rec), where row_layout: list of pairs (rec, t), where rec is a Rectangle, and t is the Tree that Rectangle corresponds to, and leftover_rec: a Rectangle representing the leftover space in the bounding rectangle that was not used by this row. ''' if bounding_rec.width >= bounding_rec.height: return __compute_row_wide(bounding_rec, row_data, total_sum) else: row_layout_t, leftover_rec_t = __compute_row_wide( __transpose_rectangle(bounding_rec), row_data, total_sum) row_layout = [(__transpose_rectangle(rec), tr) for rec, tr in row_layout_t] leftover_rec = __transpose_rectangle(leftover_rec_t) return row_layout, leftover_rec def __transpose_rectangle(rec): ''' Returns a new rectangle that is the transpose of the input: The x and y attributes are switched, as are width and height. The label and color_code attributes are preserved. Input: rec: (Rectangle) Returns: (Rectangle) transpose of rec. ''' return Rectangle((rec.y, rec.x), (rec.height, rec.width), rec.label, rec.color_code) def __compute_row_wide(bounding_rec, row_data, total_sum): ''' Helper function for compute_row. Serves the same purpose as compute_row, but only when the bounding rectangle is at least as wide as it is tall. Inputs: Same as compute_row, except that bounding_rec must have a width greater than or equal to its height. Returns: Same as compute_row. ''' assert bounding_rec.width >= bounding_rec.height row_sum = sum(t.value for t in row_data) row_width = bounding_rec.width * row_sum / total_sum row_layout = [] y = bounding_rec.y for t in row_data: height = bounding_rec.height * t.value / row_sum rec = Rectangle((bounding_rec.x, y), (row_width, height)) if rec.width > 0 and rec.height > 0: row_layout.append((rec, t)) y += height leftover = Rectangle((bounding_rec.x + row_width, bounding_rec.y), (bounding_rec.width - row_width, bounding_rec.height)) return row_layout, leftover