Stokastik

Machine Learning, AI and Programming

LeetCode : Cutoff Trees for Golf

Problem Statement

Solution :

My solution in Python for this problem is not accepted as of yet due to "Time Limit Exceeded". There is no trick that reduces the worst case time complexity for this problem. The straightforward approach is to first sort the tree heights smallest to largest (ignoring the tree heights with height < 1) and then for each successive pair (A, B) of sorted tree heights, do a BFS from A to B and compute the minimum length path required to travel from A to B. The overall minimum path length to traverse each tree in order of their heights is the sum of the successive path lengths.

Sorting the tree heights requires O(M*N*(logM + log N)) time complexity and for each successive sorted tree height, doing a BFS requires O(M*N) time complexity. Since there are O(M*N) number of successive tree heights, total time complexity is :

O(M*N*(logM + log N)) + O(M^2*N^2) = O(M^2*N^2)

The solution in python :

import collections
import time

class Solution(object):
    def check_insert(self, x, y, start_x, start_y, end_x, end_y, queue, depth, forest, visited):
        if start_x <= x <= end_x and start_y <= y <= end_y and (x, y) not in visited and forest[x][y]:
            visited.add((x, y))
            queue.append((x, y, depth))

    def bfs_search(self, forest, start, end):
        if start == end:
            return 0

        queue = collections.deque([(start[0], start[1], 0)])
        visited = set([(start[0], start[1])])

        while len(queue) > 0:
            x, y, depth = queue.popleft()

            if (x, y) == end:
                return depth

            self.check_insert(x - 1, y, 0, 0, len(forest) - 1, len(forest[0]) - 1, queue, depth + 1, forest, visited)
            self.check_insert(x + 1, y, 0, 0, len(forest) - 1, len(forest[0]) - 1, queue, depth + 1, forest, visited)
            self.check_insert(x, y - 1, 0, 0, len(forest) - 1, len(forest[0]) - 1, queue, depth + 1, forest, visited)
            self.check_insert(x, y + 1, 0, 0, len(forest) - 1, len(forest[0]) - 1, queue, depth + 1, forest, visited)

        return -1

    def cutOffTree(self, forest):
        start = time.time()
        print len(forest), len(forest[0])

        tree_heights = []

        for row in range(len(forest)):
            for col in range(len(forest[0])):
                tree_heights.append((forest[row][col], row, col))

        tree_heights = sorted(tree_heights, key = lambda k: k[0])

        tree_heights = [(0, 0)] + [(x, y) for (v, x, y) in tree_heights if v > 1]

        num_steps = 0

        for idx in range(1, len(tree_heights)):
            p, q = (tree_heights[idx - 1][0], tree_heights[idx - 1][1]), (tree_heights[idx][0], tree_heights[idx][1])

            n = self.bfs_search_fast(forest, p, q)

            if n == -1:
                return -1

            num_steps += n

        print time.time() - start

        return num_steps

The time taken for an example matrix of size 49x36, is around 11 seconds.

The same logic when written in compiled programming languages like C++ or Java, runs within a second and has high acceptance rate as compared to the one written in Python. One thing is for sure that my solution is not accepted is not due to less than efficient logic but primarily due to Python's slow speed of execution.

Can we do better than this ? Obviously we cannot do better than the worst case time complexity for this problem, but probably using some heuristics and other observations we can reduce the time taken to find the solution. The slowness of Python has given us the opportunity to explore faster alternatives than plain BFS.

One possible time reduction technique, is to use the information about the relative position of successive tree heights (in sorted order) in the matrix. For example, consider the successive tree heights (A, B), if B is located towards right and down w.r.t. A in the matrix, then probably we can reach from A to B by doing BFS only along the right and down direction. But it is not guaranteed that we will reach B from A since there might be obstacles that block all such paths. In that case we need to do BFS along all possible directions (not only right and down).

A and B could be positioned anywhere in the matrix, but there could be at-most 4 possible arrangements as shown below.

[['A' 'x' 'x' 'x']
 ['x' 'x' 'x' 'x']
 ['x' 'x' 'x' 'x']
 ['x' 'x' 'x' 'B']]

Similarly for three other possible scenarios :

[['x' 'x' 'x' 'A']
 ['x' 'x' 'x' 'x']
 ['x' 'x' 'x' 'x']
 ['B' 'x' 'x' 'x']]
[['B' 'x' 'x' 'x']
 ['x' 'x' 'x' 'x']
 ['x' 'x' 'x' 'x']
 ['x' 'x' 'x' 'A']]
[['x' 'x' 'x' 'B']
 ['x' 'x' 'x' 'x']
 ['x' 'x' 'x' 'x']
 ['A' 'x' 'x' 'x']]

 

 

 

My modification to the first approach, is to first check whether we can reach B from A by doing BFS utilizing the relative positions of A and B. For the first example, we will go only in the right and down direction at each step towards B. Also the path must be constrained between the row and column of B (makes sense ?). If it is not possible to reach B due to obstacles, then retry again with full BFS, i.e. the first approach. Here is my python solution for the above.

import collections
import time

class Solution(object):
    def bfs_search_fast(self, forest, start, end):
        if start == end:
            return 0

        queue = collections.deque([(start[0], start[1], 0)])
        visited = set([(start[0], start[1])])

        while len(queue) > 0:
            x, y, depth = queue.popleft()

            if (x, y) == end:
                return depth

            if end[0] >= x and end[1] >= y:
                self.check_insert(x + 1, y, 0, 0, end[0], end[1], queue, depth + 1, forest, visited)
                self.check_insert(x, y + 1, 0, 0, end[0], end[1], queue, depth + 1, forest, visited)

            elif end[0] >= x and end[1] <= y:
                self.check_insert(x + 1, y, 0, end[1], end[0], len(forest[0]) - 1, queue, depth + 1, forest, visited)
                self.check_insert(x, y - 1, 0, end[1], end[0], len(forest[0]) - 1, queue, depth + 1, forest, visited)

            elif end[0] <= x and end[1] <= y:
                self.check_insert(x - 1, y, end[0], end[1], len(forest) - 1, len(forest[0]) - 1, queue, depth + 1, forest, visited)
                self.check_insert(x, y - 1, end[0], end[1], len(forest) - 1, len(forest[0]) - 1, queue, depth + 1, forest, visited)

            else:
                self.check_insert(x - 1, y, end[0], 0, len(forest) - 1, end[1], queue, depth + 1, forest, visited)
                self.check_insert(x, y + 1, end[0], 0, len(forest) - 1, end[1], queue, depth + 1, forest, visited)

        return -1


    def check_insert(self, x, y, start_x, start_y, end_x, end_y, queue, depth, forest, visited):
        if start_x <= x <= end_x and start_y <= y <= end_y and (x, y) not in visited and forest[x][y]:
            visited.add((x, y))
            queue.append((x, y, depth))



    def bfs_search(self, forest, start, end):
        if start == end:
            return 0

        queue = collections.deque([(start[0], start[1], 0)])
        visited = set([(start[0], start[1])])

        while len(queue) > 0:
            x, y, depth = queue.popleft()

            if (x, y) == end:
                return depth

            self.check_insert(x - 1, y, 0, 0, len(forest) - 1, len(forest[0]) - 1, queue, depth + 1, forest, visited)
            self.check_insert(x + 1, y, 0, 0, len(forest) - 1, len(forest[0]) - 1, queue, depth + 1, forest, visited)
            self.check_insert(x, y - 1, 0, 0, len(forest) - 1, len(forest[0]) - 1, queue, depth + 1, forest, visited)
            self.check_insert(x, y + 1, 0, 0, len(forest) - 1, len(forest[0]) - 1, queue, depth + 1, forest, visited)

        return -1


    def cutOffTree(self, forest):
        start = time.time()
        print len(forest), len(forest[0])

        tree_heights = []

        for row in range(len(forest)):
            for col in range(len(forest[0])):
                tree_heights.append((forest[row][col], row, col))

        tree_heights = sorted(tree_heights, key = lambda k: k[0])

        tree_heights = [(0, 0)] + [(x, y) for (v, x, y) in tree_heights if v > 1]

        num_steps = 0

        for idx in range(1, len(tree_heights)):
            p, q = (tree_heights[idx - 1][0], tree_heights[idx - 1][1]), (tree_heights[idx][0], tree_heights[idx][1])

            n = self.bfs_search_fast(forest, p, q)

            if n == -1:
                n = self.bfs_search(forest, p, q)

                if n == -1:
                    return -1

            num_steps += n

        print time.time() - start

        return num_steps

The total time taken for the same matrix reduces to around 3 seconds from 11 seconds (with the earlier approach).

But this time is also not good enough for the solution to be accepted. There are few other approaches discussed on the problem page (such as A* and Hadlock's algorithm) that utilizes heuristics and observations to reduce the time. I am currently looking to implement these and other heuristics.

Edit 1 :

So I learnt up and implemented the A* search algorithm. It is in-fact the generalized version of the Dijkstra'a shortest path algorithm. The idea is simple and intuitive. In simple BFS, the queue implemented is a linear queue meaning that the nodes explored at each instant of time is in the same order as they were inserted. But what if we explore the nodes in an order such that the node which is possibly more closer to our target is explored first before any other node ?

In each iteration, we pick the node whose total distance (from start to current node + an estimated distance from current to end node) is minimum. Note that we use the word "estimated" because, we do not know whether we can reach the end node from the current node due to the obstacles blocking the path. The estimated distance in this example is computed to be the Manhattan distance from the current node to the end node.

This helps us in choosing the intermediate nodes in priority to reach the end node faster.

The following code is for doing the A* search (this code replaces the one in the first experiment, i.e. the full BFS search)

class Solution(object):
    def check_insert_star(self, x, y, start_x, start_y, end_x, end_y, end, queue, depth, forest, visited, cached_g):
        if start_x <= x <= end_x and start_y <= y <= end_y and (x, y) not in visited and forest[x][y]:
            if (x, y) not in cached_g or ((x, y) in cached_g and cached_g[(x, y)] > depth):
                cached_g[(x, y)] = depth
                h = abs(x - end[0]) + abs(y - end[1])
                f = cached_g[(x, y)] + h
                heapq.heappush(queue, (f, x, y, cached_g[(x, y)]))


    def a_star(self, forest, start, end):
        if start == end:
            return 0

        queue = [(0, start[0], start[1], 0)]
        heapq.heapify(queue)

        visited = set()
        cached_g = collections.defaultdict(int)

        cached_g[(start[0], start[1])] = 0

        while len(queue) > 0:
            f, x, y, depth = heapq.heappop(queue)

            if (x, y) == end:
                return depth

            visited.add((start[0], start[1]))

            self.check_insert_star(x - 1, y, 0, 0, len(forest) - 1, len(forest[0]) - 1, end, queue, depth + 1, forest,
                                   visited, cached_g)
            self.check_insert_star(x + 1, y, 0, 0, len(forest) - 1, len(forest[0]) - 1, end, queue, depth + 1, forest,
                                   visited, cached_g)
            self.check_insert_star(x, y - 1, 0, 0, len(forest) - 1, len(forest[0]) - 1, end, queue, depth + 1, forest,
                                   visited, cached_g)
            self.check_insert_star(x, y + 1, 0, 0, len(forest) - 1, len(forest[0]) - 1, end, queue, depth + 1, forest,
                                   visited, cached_g)

        return -1

    def cutOffTree(self, forest):
        start = time.time()

        tree_heights = []

        for row in range(len(forest)):
            for col in range(len(forest[0])):
                tree_heights.append((forest[row][col], row, col))

        tree_heights = sorted(tree_heights, key = lambda k: k[0])

        tree_heights = [(0, 0)] + [(x, y) for (v, x, y) in tree_heights if v > 1]

        num_steps = 0

        for idx in range(1, len(tree_heights)):
            p, q = (tree_heights[idx - 1][0], tree_heights[idx - 1][1]), (tree_heights[idx][0], tree_heights[idx][1])

            n = self.a_star(forest, p, q)

            if n == -1:
                return -1

            num_steps += n

        print time.time() - start

        return num_steps

Note that instead of calling self.bfs_search, I am calling self.a_star inside the 'CutOffTree' method. I also replaced the 'bfs_search_fast' code with its corresponding A* version. The final code looks like :

class Solution(object):
    def check_insert_star(self, x, y, start_x, start_y, end_x, end_y, end, queue, depth, forest, visited, cached_g):
        if start_x <= x <= end_x and start_y <= y <= end_y and (x, y) not in visited and forest[x][y]:
            if (x, y) not in cached_g or ((x, y) in cached_g and cached_g[(x, y)] > depth):
                cached_g[(x, y)] = depth
                h = abs(x - end[0]) + abs(y - end[1])
                f = cached_g[(x, y)] + h
                heapq.heappush(queue, (f, x, y, cached_g[(x, y)]))


    def a_star(self, forest, start, end):
        if start == end:
            return 0

        queue = [(0, start[0], start[1], 0)]
        heapq.heapify(queue)

        visited = set()
        cached_g = collections.defaultdict(int)

        cached_g[(start[0], start[1])] = 0

        while len(queue) > 0:
            f, x, y, depth = heapq.heappop(queue)

            if (x, y) == end:
                return depth

            visited.add((start[0], start[1]))

            self.check_insert_star(x - 1, y, 0, 0, len(forest) - 1, len(forest[0]) - 1, end, queue, depth + 1, forest,
                                   visited, cached_g)
            self.check_insert_star(x + 1, y, 0, 0, len(forest) - 1, len(forest[0]) - 1, end, queue, depth + 1, forest,
                                   visited, cached_g)
            self.check_insert_star(x, y - 1, 0, 0, len(forest) - 1, len(forest[0]) - 1, end, queue, depth + 1, forest,
                                   visited, cached_g)
            self.check_insert_star(x, y + 1, 0, 0, len(forest) - 1, len(forest[0]) - 1, end, queue, depth + 1, forest,
                                   visited, cached_g)

        return -1


    def a_star_fast(self, forest, start, end):
        if start == end:
            return 0

        queue = [(0, start[0], start[1], 0)]
        heapq.heapify(queue)

        visited = set()
        cached_g = collections.defaultdict(int)

        cached_g[(start[0], start[1])] = 0

        while len(queue) > 0:
            f, x, y, depth = heapq.heappop(queue)

            if (x, y) == end:
                return depth

            visited.add((start[0], start[1]))

            if end[0] >= x and end[1] >= y:
                self.check_insert_star(x + 1, y, 0, 0, end[0], end[1], end, queue, depth + 1, forest, visited, cached_g)
                self.check_insert_star(x, y + 1, 0, 0, end[0], end[1], end, queue, depth + 1, forest, visited, cached_g)

            elif end[0] >= x and end[1] <= y:
                self.check_insert_star(x + 1, y, 0, end[1], end[0], len(forest[0]) - 1, end, queue, depth + 1, forest, visited, cached_g)
                self.check_insert_star(x, y - 1, 0, end[1], end[0], len(forest[0]) - 1, end, queue, depth + 1, forest, visited, cached_g)

            elif end[0] <= x and end[1] <= y:
                self.check_insert_star(x - 1, y, end[0], end[1], len(forest) - 1, len(forest[0]) - 1, end, queue, depth + 1, forest, visited, cached_g)
                self.check_insert_star(x, y - 1, end[0], end[1], len(forest) - 1, len(forest[0]) - 1, end, queue, depth + 1, forest, visited, cached_g)

            else:
                self.check_insert_star(x - 1, y, end[0], 0, len(forest) - 1, end[1], end, queue, depth + 1, forest, visited, cached_g)
                self.check_insert_star(x, y + 1, end[0], 0, len(forest) - 1, end[1], end, queue, depth + 1, forest, visited, cached_g)

        return -1

    def cutOffTree(self, forest):
        start = time.time()

        tree_heights = []

        for row in range(len(forest)):
            for col in range(len(forest[0])):
                tree_heights.append((forest[row][col], row, col))

        tree_heights = sorted(tree_heights, key = lambda k: k[0])

        tree_heights = [(0, 0)] + [(x, y) for (v, x, y) in tree_heights if v > 1]

        num_steps = 0

        for idx in range(1, len(tree_heights)):
            p, q = (tree_heights[idx - 1][0], tree_heights[idx - 1][1]), (tree_heights[idx][0], tree_heights[idx][1])

            n = self.a_star_fast(forest, p, q)

            if n == -1:
                n = self.a_star(forest, p, q)

                if n == -1:
                    return -1

            num_steps += n

        print time.time() - start

        return num_steps

With the same example as the earlier one, the total run time for the above code is reduced to 1.75 seconds from 3 seconds. Although the reduction is not huge, but still its a gain for us in terms of speed as well as knowledge (got to know about the A* algorithm).

Categories: PROBLEM SOLVING

Tags: , , , , , ,