Calculating the Days Required to Burn All Trees Using Python

Rate this post

πŸ’‘ Problem Formulation: In this article, we will address the simulation problem of computing the number of days needed to completely burn all the trees in a given forest, represented by a grid. Each cell in the grid can either contain a tree, which may or may not be on fire, or be empty. For the simulation, fire spreads from burning trees to adjacent (up, down, left, right) trees daily. Example input: a 2D grid with trees and initial fire positions. Desired output: the number of days until no trees remain.

Method 1: Breadth-First Search (BFS)

This method employs the Breadth-First Search (BFS) algorithm, which is ideal for traversing trees or graphs level by level. In the context of this problem, it means we can track the spread of fire across the forest each day by processing all burning trees simultaneously and igniting their neighbors. This continues until there are no trees left to burn. The BFS is implemented using a queue, incrementing the day counter each time the algorithm completes a level of traversal.

Here’s an example:

from collections import deque

def burn_trees_bfs(forest):
    rows, cols = len(forest), len(forest[0])
    days = 0
    queue = deque([(r, c) for r in range(rows) for c in range(cols) if forest[r][c] == 'F'])

    while queue:
        for i in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                rr, cc = r + dr, c + dc
                if 0 <= rr < rows and 0 <= cc  0 else 0

# Example forest grid where 'T' represents a tree and 'F' a tree on fire
forest = [
    ['T', 'T', 'T', 'T'],
    ['T', 'F', 'T', 'T'],
    ['T', 'T', 'T', 'T'],
    ['T', 'T', 'T', 'T']
]

print(burn_trees_bfs(forest))

Output: 3

This BFS-based function, burn_trees_bfs, defines a queue initialized with positions of all burning trees. The function then iterates until the queue is empty, popping positions and igniting neighboring trees. Days are counted accordingly. The final result is adjusted to handle cases with no initial fire by subtracting one if the fire has started; otherwise, zero is returned.

Method 2: Depth-First Search (DFS) with Iterative Approach

The DFS iterative approach delves into one path to the end before backtracking, quite like exploring to the bottom of one branch of a tree, then moving to another. For this problem, we’ll use an auxiliary stack to traverse burning trees and their adjacent cells. Although recursive DFS could be used, the iterative approach can be more memory efficient and is often easier to understand and debug.

Here’s an example:

……

Bonus One-Liner Method 5: Pythonic Functional Approach

Summary/Discussion

  • Method 1: Breadth-First Search. Effective for level-based traversal like fire spread. Linear in complexity relative to the size of the forest. Can be memory-intensive for large forests due to queue storage.
  • Method 2: Depth-First Search with Iterative Approach. Useful for exploring paths deeply without much overhead. Memory overhead is potentially less than BFS but can be slower for this problem as DFS does not process by levels.
  • Bonus One-Liner Method 5: Pythonic Functional Approach. Elegant and concise. However, it might lack clarity for those unfamiliar with functional paradigms in Python and may not be the most efficient in terms of performance for large data sets.