[Feature Request] General Improvements

[thedinosoar]

Logic and Functionality Improvement Proposals:

1. Handling Rotations More Explicitly:

   • Currently, rotations are considered, but there’s no clear mechanism to handle asymmetric pieces in other possible orientations. This is fine if only 90° rotations are required, but for clarity, separate rotation logic might make the code more robust.

2. Redundant does_fit Calls:

   • In get_solution, does_fit is always called before insert. You could merge these checks into a single method to reduce duplicated code and function calls.

3. Inefficient Free Space Update (next_free):

   • The insert method iterates over the entire board to find the next free cell. This is inefficient, especially for large boards. Instead, you can maintain a sorted list of free cells or use a more efficient way to track and update the next available cell.

4. Hardcoded Board Size:

   • The board size is fixed at 56. If you want flexibility, consider passing the size as a parameter to the Board constructor.

Performance Proposals

1. Deep Copies in get_solution:

   • Creating deep copies of the board and remaining pieces (copy.deepcopy) at every recursive step can be expensive. Consider alternatives, such as undoing the placement instead of copying the entire board.

2. Recursive Depth:

   • Recursive calls may stack deeply, leading to inefficiency or stack overflow for large input sizes. Iterative solutions or limiting recursion depth could improve robustness.

3. Unused Space Optimization:

   • The algorithm doesn’t prioritize using the smallest pieces first or optimizing placements for minimal gaps. This can lead to suboptimal solutions or failure to solve even solvable configurations.

   Code

   class Board:
   def __init__(self, size=56):
       self.size = size
       self.grid = [[True] * size for _ in range(size)]
       self.next_free = (0, 0)
       self.space = size * size
   
   def does_fit(self, piece, position=None):
       x_start, y_start = self.next_free if position is None else position
       w, h = piece
   
       if x_start + w > self.size or y_start + h > self.size:
           return False
   
       for y in range(h):
           for x in range(w):
               if not self.grid[y_start + y][x_start + x]:
                   return False
   
       return True
   
   def insert(self, piece):
       x_start, y_start = self.next_free
       w, h = piece
   
       for y in range(h):
           for x in range(w):
               self.grid[y_start + y][x_start + x] = False
   
       self.update_next_free()
       self.space -= w * h
       return x_start, y_start
   
   def update_next_free(self):
       for y in range(self.size):
           for x in range(self.size):
               if self.grid[y][x]:
                   self.next_free = (x, y)
                   return
   
   def copy(self):
       copied_board = Board(self.size)
       copied_board.grid = copy.deepcopy(self.grid)
       copied_board.next_free = self.next_free
       copied_board.space = self.space
       return copied_board
   
   
   def get_solution(board, pieces, positions):
       if board.space == 0:
               return positions
   
       for piece in pieces:
               for rotated in (piece, (piece[1], piece[0])):
                       if board.does_fit(rotated):
                       new_board = board.copy()
                       new_board.insert(rotated)
   
                       solution = get_solution(new_board, [p for p in pieces if p != piece], positions + [(rotated, board.next_free)])
                       if solution:
                               return solution
   
       return None

Other Suggestions

• Better variable names
• Don't shoot anymore CEOs

[AhuiZhao]

Are you serious?

[AkhilBabuM]

If you need someone to handle your repo while you’re ‘away on vacation,’ I’ve got a surprisingly flexible schedule and a talent for not getting arrested. Just putting it out there.