Leetcode 317: Shortest distance from all buildings (part 2)

January 19, 2016

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):

    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.

     *

Practice using C#

Julia chose this Java code implementation to study first, and then she wrote one using C#.

She spent more than 2 hours from 9pm - 11pm to practice.

Highlights of changes

1. Julia likes the idea of "express the intent", so she added a new function called getNoOfBuildings().

So,  here is the version to fix the bug.

Rewrite the fill function, make the function do one task:

public void fill(int origX, int origY, int x, int y, int curDistance, int[][] dist, int[][] reach,int[][] grid, bool[][] visited, Queue<Node> queue)

The above function is too complicated, Julia create a few bugs in the function. More than 8 arguments - too many!

Here is the version after some work on function design 

- get rid of too many arguments

- function much more easy to read, understand

- less error-prone

- function to do one task only

C# code is here.

Another version is here.

Lessons Julia learned through debugging:

1. using ref or not in C# language - does not matter

2. function design - simple, is important to review, avoid bugs

3. Queue is used for BFS, and when the node is added to queue. please also log the distance, and use it for next round. - Main bug - calculation, since each node has different distance to the building node.

More about BFS

1. BFS - how to think about the algorithm?

Tips: Try to start from simple things, like count how many building, empty lands, obstacles; then, figure out which one is meaningful to work with first.

3 choices - buildings, empty land, obstacle. Choose one and see if you can  make progress

buildings - very good. Do some simple task, put all buildings in a List data structure, easy to iterate.

empty land - kind of hard to do BFS - the question is to ask a node to all building distance sum - not sum - but the minimum of sum.

So, start from each building to do BFS

2. BFS - how to design a BFS function?

So many bugs in the first 2-3 hours coding, it takes 30 minutes to understand other people's idea and code.

Go through bugs one by one later. (To be continued)

3. Encourage herself to work on BFS algorithms in the future: 

Some facts:

1. Julia could not figure out how to handle this BFS problem on January 19, 2016, she has to read other people's solution first, and also analysis, and then, start to work on coding.

2. BFS  - Ask questions:

start from where - how many of them - what order to do BFS? order matter or not?

3. Julia could not finish the BFS algorithm writing in less than 30 minutes. A lot of bugs, confusion with BFS function design, and edge case handling.

4. Past experience on BFS

Julia is still working on BFS algorithms, and like to get more experience if possible. Here is another BFS practice she did in June 2015. More reading about Leetcode 317, click here. BFS algorithm review is here.

5. How to make BFS algorithm design experience fun, memorable?

- Have more discussion on the blog. Welcome comments.