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.
