1
\$\begingroup\$

Problem statement:

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely.

Each 1 marks a building which you cannot pass through.

Each 2 marks an obstacle which you cannot pass through.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

enter image description here

The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3 + 3 + 1 = 7 is minimal. So return 7.

My introduction of algorithm

I reviewed my last two practices using C# programming language, and then decided to practice again. But I learned from past experience, I spent hours to understand the breadth first search algorithm in first two practice, so I like to challenge myself to design the program using S.O.L.I.D. principles if possible this practice.

Understand breadth first search algorithm first

The algorithm is a medium level one, and I think that breadth first search and 4 direction handling related to distance increment is a challenging part. And also the idea is not easy to figure out first time, 3 categories of places, where to start for breadth first search. From every building or every empty land, what is the difference? In my practice, I chose to start from every building, and then visit empty lands if reachable, no obstacle. Each step 4 directions are considered.

Usually clockwise or anticlockwise order is used to visit neighbors, but my implementation is accidentally horizontal first, vertical afterwards. The order does not affect the distance between building and empty land.

Since in the implementation, 4 directions are visited in the order of left, right, down and up, showing in the following diagram from building (0,0) to empty land (2,4) is the route to find the empty land step by step. The distance should be 6, if it were 10, that is a bug I had at the very beginning of practice, because I increased the distance for each direction by a mistake. There are 10 empty land in the grid 3x5 in problem description, by the end of BFS search from left-top corner to bottom-right corner, all 10 empty lands are visited once, so each time is counted to distance by the mistake.

enter image description here

Breadth first search common issues

The most common issues of the algorithm are related to breadth first search, 4 of them. To avoid dead loop, only visit unvisited node, visit a node and then mark it visited; Distance calculation is related to increase distance once for every 4 directions, not one for each direction; Boundary checking of grid; Some empty lands may not be reachable because of obstacles, only visit empty land but stop on an obstacle. Asking the minimum sum of distance to all building is to put all knowledge under the test, the algorithm is really an interesting and challenging problem to practice at least once.

Interface and classes

Because there are 3 places called empty land, building, obstacles, I like to use interface IPlace, and then design a class called Place. And then I also designed the API to track distance between a building to an empty land, designed a class KeyUsingDash. Most of time the distance value is not calculated correctly, so I can easily check if it is correct by checking associated building and empty land's unique key, it is not in the algorithm requirement, but I added it to expedite problem solving and anticipate the problems in the code.

Class EmptyLandAndBuilding

I also designed the class EmptyLandAndBuilding, so every distance between a building and a empty land can be uniquely identified, but maybe Tuple<Space, Space> is a better alternative, I had some issues when I run the test case to look up function WalkFromBuildingBFS's return Dictionary object Dictionary<EmptyLandAndBuilding, int>, the key of dictionary cannot be looked up. My wish is that I should have use a string to define empty land and building pair just concatenating two key strings with a delimiter, for example, "0-0-2-4" stands for building at (0,0) and an empty land at (2,4).

Extra public API - WalkFromBuildingBFS

I made the API WalkFromBuildingBFS public and tested the API first before I tested the final result of CalculateShortestDistance.

Public API CalculateShortestDistance

Write readable code compared to my last two practice. Go over each building, conduct a breadth first search, and keep tracking of empty land visited, return distance between the building with each visited empty land. Use Dictionary object and use EmptyLandAndBuilding as key to record distances. Use LINQ to filter out empty land using local variable emptyLandVisitedCount only considering those empty lands reachable from all of building in the grid.

Community Challenge - Rainfall challenge

After the practice, I also did some quick research on related questions on this site, I am learning most from Rainfall challenge, and some of reviewes should apply to my practice of this Leetcode 317 algorithm as well.

Alternative BFS search and the idea to expedite BFS

After the practice, I continued to study some solutions on Leetcode discussion, and then I came cross the implementation to use BFS starting from every empty land instead of starting every building, and also learned the idea to expedite the BFS search by only visiting empty lands marked by previous buildings' visited ones.

So, please help me to think better as a designer, use this simple algorithm compared to community challenge ones, show me how to design interface, class, access level, and apply knowledge of SOLID if possible etc.

Because Leetcode 317 is not a public algorithm, there is no public online judge to run through the code. My work is tested on my test cases, the sample test case provided in the problem statement. The code is also available on the link for easy to read because total lines of code is 405: https://gist.github.com/jianminchen/68a31f9d20dab1658286fbfec7e4fcdb

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode317_ShortestDistanceFromAllBuildings
{
    /*
    * Leetcode 317:
    * You want to build a house on an empty land which reaches all 
    * buildings in the shortest amount of distance. You can only
    * move up, down, left and right. You are given a 2D grid of 
    * values 0, 1 or 2, where:
       Each 0 marks an empty land which you can pass by freely.
       Each 1 marks a building which you cannot pass through.
       Each 2 marks an obstacle which you cannot pass through.
       For example, given three buildings at (0,0), (0,4), (2,2), 
       and an obstacle at (0,2):
     * 
       1 - 0 - 2 - 0 - 1
       |   |   |   |   |
       0 - 0 - 0 - 0 - 0
       |   |   |   |   |
       0 - 0 - 1 - 0 - 0
    * 
    * The point (1,2) is an ideal empty land to build a house, as the 
    * total travel distance of 3+3+1=7 is minimal, so return 7.
    * 
    * 
    * 
    * Analysis from the above blog:
    * Note:
       There will be at least one building. If it is not possible to 
       build such house according to the above rules, return -1.
    * 
       Understand the problem:
       Use breadth first search to visit all emtpy lands if possible 
       starting from each building, track the statistics.
    * 
    *  Search from each building and calculate the distance to the building. 
    *  Find all empty lands which can be reachable started from any
    *  building first, then find minimum distance. 
    *    
    *  
    */
    public interface IPlace
    {
        string GetKey(int row, int col);
        int[]  DecryptKey(string s); 
    }

    class WalkTrackingNode : IPlace
    {
        public string Key { get; set; }
        public int Distance { get; set; }

        public WalkTrackingNode(string s, int value = 0)
        {
            Key = s;
            Distance = value;
        }

        // interface methods
        public string GetKey(int row, int col)
        {
            return KeyUsingDash.Encrypt(row, col);
        }

        public int[] DecryptKey(string s)
        {
            return KeyUsingDash.Decrypt(s);
        }

        public Tuple<int, int> DecryptKeyTuple(string s)
        {
            return KeyUsingDash.DecryptToTuple(s);
        }        
    }

    /*
     * Design to help track distance between building and empty lande
     * Each building has a key generated by row, col's value, like "0-0"
     * "0-0" can be decrypted to a node in jagged array two indexes, row, column.
     */
    public static class KeyUsingDash
    {
        public static string Encrypt(int row, int col)
        {
            return row + "-" + col;
        }

        public static int[] Decrypt(string s)
        {
            return Array.ConvertAll(s.Split('-'), int.Parse);
        }

        public static Tuple<int, int> DecryptToTuple(string s)
        {
            if (s == null || s.Length < 2)
            {
                return new Tuple<int, int>(-1, -1);
            }

            int[] data = Array.ConvertAll(s.Split('-'), int.Parse);
            return new Tuple<int, int>(data[0], data[1]);
        }        
    }

    class EmptyLandAndBuilding
    {
        public string BuildingKey { get; set; }

        public string LandKey { get; set; }

        public EmptyLandAndBuilding(Place building, Place land)
        {
            BuildingKey = building.key;
            LandKey = land.key;
        }
    }

    class Place : IPlace
    {
        public string key { get; set; }

        public string GetKey(int row, int col)
        {
            return KeyUsingDash.Encrypt(row, col); 
        }

        public int[] DecryptKey(string s)
        {
            return KeyUsingDash.Decrypt(s); 
        }

        public Tuple<int,int> DecryptKeyTuple(string s)
        {
            return KeyUsingDash.DecryptToTuple(s);
        }

        public Place(int row, int col)
        {
            key = row + "-" + col;
        }

        public static bool IsSamePlace(Tuple<int, int> land1, Tuple<int, int> land2)
        {
            return land1.Item1 == land2.Item1 && land1.Item2 == land2.Item2;
        }

        /*
         * 0 - empty land
         * 1 - building
         * 2 - obstacle
         */
        public static IList<Place> GetAllBuildings(int[][] grid)
        {
            var buildings = new List<Place>();
            int rows = grid.Length;
            int cols = grid[0].Length;

            for (int row = 0; row < rows; row++)
            {
                for (int col = 0; col < cols; col++)
                {
                    if (grid[row][col] == 1)
                    {
                        buildings.Add(new Place(row, col));
                    }
                }
            }

            return buildings;
        }
    }  

    class Solution
    {
        private static readonly int EMTPYLAND = 0;       

        /*
         * Find an emtpy land to have the shortest distance to all the buildings.
         * 
         * Solve the problem in the following steps:
         * 1. Enumerate all buildings, from each building walk 4 directions to reach all
         * empty lands using breadth first search. Count the visited for each empty land. 
         * 2. Find those empty lands which can be reached by all buildings, calculate the 
         * minimum sum of distance.            
         *
         */
        public int CalculateShortestDistance(int[][] grid, int rows, int cols)
        {
            var buildings = Place.GetAllBuildings(grid);
            var emptyLandVisitedCount = new Dictionary<Tuple<int, int>, int>();
            var walksFromEachBuilding    = new List<Dictionary<EmptyLandAndBuilding, int>>();

            foreach (Place building in buildings)
            {
                walksFromEachBuilding.Add(WalkFromBuildingBFS(building, grid, emptyLandVisitedCount));
            }

            // step 2: caluclate the minimum distance
            int minimumDistance = Int16.MaxValue;
            foreach (var chosen in emptyLandVisitedCount.Where(x => x.Value == buildings.Count))
            {
                var emtpyLand = chosen.Key;
                int sumDistance = 0;
                foreach (var walk in walksFromEachBuilding)
                {
                    foreach (var buildingAndLand in walk)
                    {
                        var distanceKey = buildingAndLand.Key;
                        var value       = buildingAndLand.Value;

                        if (Place.IsSamePlace(emtpyLand, KeyUsingDash.DecryptToTuple(distanceKey.LandKey)))
                        {
                            sumDistance += value;
                        }
                    }
                }

                minimumDistance = (sumDistance < minimumDistance) ? sumDistance : minimumDistance;
            }

            return minimumDistance == Int16.MaxValue ? -1 : minimumDistance;
        }      

        /*
         * @building - start a walk from building, using BFS
         * @grid - places including empty land, building, obstacle. n x m size 
         * @emptyLandReached - record visited count for each empty land, 
         *  add a new record for a new visit, increment value 1 if the value is existed 
         * 
         * return Dictionary<EmptyLandAndBuilding, int>
         * distance from building to emtpy land, 
         * Add this enhanced API, test how good I can write BFS algorithm, dealing with multiple
         * directions. Easy to troubleshoot errors through development. 
         * Building's key value is recorded, and empty land's key value is also recorded,
         * both are stored in the key object.          
         * distance is the integer value. 
         */
        public new Dictionary<EmptyLandAndBuilding, int> WalkFromBuildingBFS(
            Place building,
            int[][] grid,
            Dictionary<Tuple<int, int>, int> emptyLandReached
            )
        {
            var distanceData = new Dictionary<EmptyLandAndBuilding, int>();
            int rows = grid.Length;
            int cols = grid[0].Length;

            var visited = new bool[rows, cols];

            var queue = new Queue<WalkTrackingNode>();

            // add first node into the queue 
            queue.Enqueue(new WalkTrackingNode(building.key, 0));

            // BFS - visit all nodes in the grid
            while (queue.Count > 0)
            {
                WalkTrackingNode node = queue.Dequeue();

                int distance = node.Distance;

                int[] data = KeyUsingDash.Decrypt(node.Key);

                int row = data[0];
                int col = data[1];

                // four directions - left, right, down, up 
                int[][] directions = {new int[2]{-1,  0},     
                                      new int[2]{ 1,  0},    
                                      new int[2]{ 0, -1},    
                                      new int[2]{ 0,  1}      
                                     };

                // increment distance once for all directions, should not be put in
                // direction loop. Fix the bug in my first writing, remove out of for loop. 
                distance++;  

                for (int i = 0; i < directions.Length; i++)
                {
                    int nextRow = row + directions[i][0];
                    int nextCol = col + directions[i][1];

                    if (boundaryCheck(nextRow, nextCol, rows, cols) &&
                        !visited[nextRow, nextCol] &&
                        grid[nextRow][nextCol] == EMTPYLAND)
                    {
                        var keyObject = new Tuple<int, int>(nextRow, nextCol);
                        if (emptyLandReached.ContainsKey(keyObject))
                        {
                            emptyLandReached[keyObject]++;
                        }
                        else
                        {
                            emptyLandReached.Add(keyObject, 1);
                        }

                        var emptyLand = new Place(nextRow, nextCol);
                        distanceData.Add(new EmptyLandAndBuilding(building, emptyLand), distance);

                        visited[nextRow, nextCol] = true;

                        queue.Enqueue(new WalkTrackingNode(KeyUsingDash.Encrypt(nextRow, nextCol), distance));
                    }
                }
            }

            return distanceData;
        }        

        private bool boundaryCheck(int row, int col, int rows, int cols)
        {
            return row >= 0 && row < rows && col >= 0 && col < cols;
        }

        /*   
         * Test case: 
         * 
             1 - 0 - 2 - 0 - 1
             |   |   |   |   |
             0 - 0 - 0 - 0 - 0
             |   |   |   |   |
             0 - 0 - 1 - 0 - 0
         * 
         The point (1,2) is an ideal empty land to build a house, 
         as the total travel distance of 3+3+1=7 is minimal. So return 7.
         * 
         * Ref: jagged array initilization lookup
         * https://msdn.microsoft.com/en-us/library/2s05feca.aspx

         */
        static void Main(string[] args)
        {
            RunTestcaseOnWalk();
            RunSampleTestcase();
        }

        /*
         * It is worth time to test API first: 
         * WalkFromBuildingBFS
         * And choose two points to verify the distance is correct. 
         * BFS is tested, all directions are tested as well.
         * After that, the shortest distance from all buildings will be much easy 
         * to be tested. 
         */
        public static void RunTestcaseOnWalk()
        {
            int[][] grid = new int[3][] { 
                 new int[]{ 1, 0, 2, 0, 1 }, 
                 new int[]{ 0, 0, 0, 0, 0 },
                 new int[]{ 0, 0, 1, 0, 0 } 
            };

            Solution solution = new Solution();
            var building = new Place(0, 0);

            var emptyLandStatistics = new Dictionary<Tuple<int, int>, int>();

            var distanceData = solution.WalkFromBuildingBFS(
                building,
                grid,
                emptyLandStatistics
            );

            // distanceData to count the minimum steps from building top-left corner to 
            // emtpy land bottom-right corner is 6
            // one of shortest routes (6 steps):
            // 1
            // 0 0 0 0 0
            //         0
            // another one of shortest routes (6 steps):
            // 1 0
            //   0 0 0 0
            //         0
            {
                var pair = new EmptyLandAndBuilding(new Place(0, 0), new Place(2, 4));
                // manually verify the value
                //Debug.Assert(distanceData[pair] == 6);
            }

            // 0
            // 0 0 1
            {
                var pair = new EmptyLandAndBuilding(new Place(2, 2), new Place(1, 0));
                // manually verify the value
                //Debug.Assert(distanceData[pair] == 3);
            }
        }

        public static void RunSampleTestcase()
        {
            int[][] grid = new int[3][] { 
                 new int[]{ 1, 0, 2, 0, 1 }, 
                 new int[]{ 0, 0, 0, 0, 0 },
                 new int[]{ 0, 0, 1, 0, 0 } 
            };

            Solution solution = new Solution();

            int result = solution.CalculateShortestDistance(grid, 3, 5);

            Debug.Assert(result == 7);
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.