[FIXED] How to keep dividing a box inside box recursively and iteratively?

Issue

class Point:
    def __init__(self, x, y):
        self.x=x
        self.y=y
class Rect:
    def __init__(self, up, dw):
        self.up=up
        self.dw=dw
        self.next=[]
    def next_empty(self):
        return len(self.next)<=0



def inside(p1, p2, p3):
    return p3.x>=p1.x and p3.y<=p1.y and p3.x<=p2.x and p3.y>=p3.y

def create_box(root, parts):
    width=root.dw.x-root.up.x
    height=root.up.y-root.dw.y
    divx=width/parts
    divy=height/parts

    x=y=0
    for _y in range(parts):
        for _x in range(parts):
            rect=Rect(up=Point(x, y+divy), dw=Point(x+divx, y))
            root.next.append(rect)
            x+=divx
        x=0
        y+=divy
    return True

def create_tree(root, parts, n=2):
    pass
    
    

up=Point(0, 180)
dw=Point(360, 0)
root=Rect(up, dw)

#create_tree(root, 20)

The above code has two class Point and Rect. Point represents a point on a graph, Rect represents a rectangle, the 'Rect.up' attribute is top left point while 'Rect.dw' is bottom right point.

The create_box function divides the given rect object in parts*parts rectangles and saves it inside 'Rect.next' array. So first rect is up=(18, 0) dw=(18,0), second up=(18, 18) dw=(36, 0). I have a create_tree function that should creates the tree of n nodes, but I am facing some problems here. For example: First create tree will divide the root in x parts and those x parts will again get divided into x parts and similarly this process will continue until n nodes are reached. I expect the create_tree function to work in following behaviour:-

def create_tree(root, parts, n=2):
    root_arr=[root]
    # when n=1
    if n==1:
        for r in root_arr:
            create_box(r, parts)

    #when n=2
    if n==2:
        for r in root_arr:
            create_box(r, parts)
        for r in root_arr:
            for j in r.next:
                create_box(j, parts)
    # when n=3
    if n==3:
        for r in root_arr:
            create_box(r, parts)
        for r in root_arr:
            for j in r.next:
                create_box(j, parts)
        for r in root_arr:
            for j in r.next:
                for q in j.next:
                    create_box(q, parts)
# N can be any number

I am having trouble in adding such kind of loop. How should it be solved using recursion and iteration both?

Solution

Using a DFS approach, you can write a recursive function to wrap the box creation task:

def create_boxes_recursively(root, parts, levels):
    root_arr = [root]
    create_box(root, parts)
    if levels==1:
        return
    if not root.next:
        return
    for j in root.next:
        create_boxes_recursively(j, parts, levels-1)

As for iteratively, you can use a BFS approach, which keeps a track of all nodes at the next level:

def create_boxes_iteratively(root, parts, levels):
    next_nodes = [root]
    curr_level = 0
    while next_nodes and curr_level<levels:
        temp_array = []
        for node in next_nodes:
            create_box(node, parts)
            temp_array += node.next
        curr_level += 1
        next_nodes = temp_array

Answered By - Abhinav Mathur