This past weekend my wife and I spent time looking for protein-rich groceries. We were attempting to get those and additional items for a few families that wish to stay in lockdown despite the governor of Minnesota starting to relax the lockdown. The current orders went into effect last Saturday April 18, 2020 at midnight. Among the main items is that people in the state can go golfing and shooting in open ranges. Both Saturday and Sunday were sunny days. We could tell for the number of cars and people walking the dogs, jogging and just strolling that many people took advantage of the new rules.
On our side we will continue to try stay home as much as we can by limiting trips to the grocery stores and continue to use Jitsi to communicate more often with family and friends.
Today in the news it seems that many companies in the USA, Japan and 
Australia are in the process of moving their supply chains out of China. Hopefully all countries will follow suit. The cost to humanity for COVID-19 is incredibly high in lives and economies. We as humans regardless of nationalities or race should tell our governments to take the necessary steps to prevent this from happening again.
On a separate note, last week I finished an Azure course. It provided me with a full overview of most of the services offered by the Azure cloud. Will start today with the free courses on C# offered on Azure. I also signed up for a course on Python for machine learning offered by Stanford University. You can take the course for free if you just audit. I decided to take it for under $200 USD. That will give me a certificate when I satisfactorily complete the course. It should take 7 weeks to complete it. Currently I am on the first week.
I decided to take a look at a recursion problem 8.2 Robot in a Grid from the book “Cracking the Coding Interview” by Gayle Laakmann McDowell. If interested take a look at the requirements and suggested approach. I currently own a copy of version 6 of the book.
Just in case you do not have access to a copy of the book the edited requirements follow:
“Imagine a robot sitting on the upper left corner of a grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are “off limits” such that the robot cannot step on them. Design and implement an algorithm (I will use Java) to find the path for the robot from the top left to the bottom right corners.”
Microsoft Windows [Version 10.0.18363.778] (c) 2019 Microsoft Corporation. All rights reserved. # **** **** C:\Users\johnc>dir 04/16/2020 02:31 PM <DIR> . 04/16/2020 02:31 PM <DIR> .. 09/22/2019 08:00 AM <DIR> .eclipse 03/15/2020 08:38 AM 59 .gitconfig 04/07/2020 10:38 AM <DIR> .p2 04/16/2020 02:31 PM <DIR> .pylint.d 09/22/2019 08:00 AM <DIR> .tooling 03/10/2020 03:53 PM <DIR> .vscode 03/10/2020 04:43 PM <DIR> 3D Objects 03/10/2020 04:43 PM <DIR> Contacts 04/08/2020 07:59 AM <DIR> ContainsCloseNums 02/17/2020 03:52 PM <DIR> Documents 04/17/2020 09:22 AM <DIR> Downloads 09/22/2019 07:57 AM <DIR> eclipse 09/22/2019 07:59 AM <DIR> eclipse-workspace_0 03/10/2020 04:43 PM <DIR> Favorites 03/10/2020 04:44 PM <DIR> Links 03/10/2020 04:43 PM <DIR> Music 09/12/2019 04:36 PM <DIR> NCH Software Suite 04/19/2020 07:12 AM <DIR> OneDrive 03/10/2020 04:43 PM <DIR> Saved Games 03/10/2020 04:43 PM <DIR> Searches 03/10/2020 04:43 PM <DIR> Videos 04/15/2020 01:45 PM <DIR> workspace0 # **** **** C:\Users\johnc>cd workspace0 # **** **** C:\Users\johnc\workspace0>dir 04/15/2020 01:45 PM <DIR> . 04/15/2020 01:45 PM <DIR> .. 04/01/2020 08:57 AM <DIR> BST-Search 04/10/2020 11:34 AM <DIR> ComposeRanges 04/08/2020 08:04 AM <DIR> ContainsCloseNums 04/05/2020 08:32 AM <DIR> GraphBFS 04/17/2020 03:41 PM <DIR> MissingNumber 03/29/2020 08:30 AM <DIR> ORCost 03/10/2020 04:24 PM <DIR> SortOnFrequency # **** **** C:\Users\johnc\workspace0>git clone https://github.com/JohnCanessa/RobotInAGrid.git Cloning into 'RobotInAGrid'... remote: Enumerating objects: 3, done. remote: Counting objects: 100% (3/3), done. remote: Compressing objects: 100% (2/2), done. remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0 Unpacking objects: 100% (3/3), 793 bytes | 5.00 KiB/s, done. # **** **** C:\Users\johnc\workspace0>dir 04/19/2020 07:42 AM <DIR> . 04/19/2020 07:42 AM <DIR> .. 04/01/2020 08:57 AM <DIR> BST-Search 04/10/2020 11:34 AM <DIR> ComposeRanges 04/08/2020 08:04 AM <DIR> ContainsCloseNums 04/05/2020 08:32 AM <DIR> GraphBFS 04/17/2020 03:41 PM <DIR> MissingNumber 03/29/2020 08:30 AM <DIR> ORCost 04/19/2020 07:42 AM <DIR> RobotInAGrid 03/10/2020 04:24 PM <DIR> SortOnFrequency # **** **** C:\Users\johnc\workspace0>cd RobotInAGrid # **** **** C:\Users\johnc\workspace0\RobotInAGrid>dir 04/19/2020 07:42 AM <DIR> . 04/19/2020 07:42 AM <DIR> .. 04/19/2020 07:42 AM 308 README.md # **** **** C:\Users\johnc\workspace0\RobotInAGrid>type README.md # RobotInAGrid Problem from Cracking the Coding Interview solved in Java The book contains the sulutions to all problems. This code is what I came up without using the proposed solution. For additional info please take a look at the follwoing post in my blog: T.B.D. Thanks and enjoy! John
I opened a command prompt on a Windows 10 computer. Navigated to a folder and cloned a GitHub repository I created a few minutes before to hold the project at hand. As you can see I included a README.md file which I will update with the URI to this post after it in on-line in my WordPress blog.
1 3 o o o main <<< rows: 1 cols: 3 main <<< maze: o o o main <<< path: [(0,0), (0,1), (0,2)] main <<< path: [(0,0), (0,1), (0,2)] 2 3 o o o o o o main <<< rows: 2 cols: 3 main <<< maze: o o o o o o main <<< path: [(0,0), (1,0), (1,1), (1,2)] main <<< path: [(0,0), (0,1), (0,2), (1,2)] 4 5 o o o x o x o x o o o o x o o o o o o o main <<< rows: 4 cols: 5 main <<< maze: o o o x o x o x o o o o x o o o o o o o main <<< path: [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3), (3,4)] main <<< path: [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3), (3,4)] 4 5 o o o x o x o x o o o o x o o o o o x o main <<< rows: 4 cols: 5 main <<< maze: o o o x o x o x o o o o x o o o o o x o main <<< path: [] main <<< path: [] 5 5 o o o o o o o o o o o o o o o o o o o o o o o o o main <<< rows: 5 cols: 5 main <<< maze: o o o o o o o o o o o o o o o o o o o o o o o o o main <<< path: [(0,0), (1,0), (2,0), (3,0), (4,0), (4,1), (4,2), (4,3), (4,4)] main <<< path: [(0,0), (0,1), (0,2), (0,3), (0,4), (1,4), (2,4), (3,4), (4,4)] 5 5 o o x o o o o o o o x o x o x o o o o o o o x o o main <<< rows: 5 cols: 5 main <<< maze: o o x o o o o o o o x o x o x o o o o o o o x o o main <<< path: [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3), (4,3), (4,4)] main <<< path: [(0,0), (0,1), (1,1), (1,2), (1,3), (2,3), (3,3), (3,4), (4,4)]
I come up with some test cases. The idea is to have the number of rows and columns for the grid in the first line. The following lines contain a row per line. A ‘o’ indicates that the cell is empty and can be used by the robot while an ‘x’ indicates that the cell is “off limits” so the robot must avoid them.
The idea is to display the path from the top left to the bottom right if one exists. In the examples all but one has a path. There is a second path. The second path may or may not be the same but are equivalent. The first path will be generated in a bottom up approach. The second path will be generated using a top down approach. Unless I am mistaken, the book only illustrates the first approach.
Note that for testing purposes I displayed the row and column counts and the maze (or grid) followed by two equivalent paths.
/**
* Test scaffolding.
* The description does not describe the input format.
* Specifically it talks about "off limit" cells.
* Grid cells set to 'o' are open; otherwise are set to 'x' to indicate "off limit".
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read number of rows in the grid ****
String[] rc = sc.nextLine().trim().split(" ");
int rows = Integer.parseInt(rc[0]);
int cols = Integer.parseInt(rc[1]);
// ???? ????
System.out.println("main <<< rows: " + rows + " cols: " + cols);
// **** declare and initialize the maze ****
Boolean[][] maze = new Boolean[rows][];
for (int r = 0; r < rows; r++) {
maze[r] = new Boolean[cols];
}
// **** read the contents of the maze ****
for (int r = 0; r < rows; r++) {
String[] cs = sc.nextLine().trim().split(" ");
for (int c = 0; c < cols; c++) {
maze[r] = cs.equals("o") ? true : false;
}
}
// **** close scanner ****
sc.close();
// ???? display the maze ????
System.out.println("main <<< maze: ");
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
System.out.print(((maze[r] == true) ? "o": "x") + " ");
}
System.out.println();
}
// **** get the path from the top left corner to the bottom right (down up approach) ****
ArrayList<Cell> path = getPath(maze);
// **** display the path (if found) ****
if (path != null)
System.out.println("main <<< path: " + path.toString());
// **** get the path from the top left corner to the bottom right (top down approach) ****
Stack<Cell> pd = getPathTD(maze);
// **** display the path (if found) ****
if (path != null)
System.out.println("main <<< path: " + pd.toString());
}
We open a scanner to read data from the console. We start by processing the number or rows and columns. We then declare and populate the maze using the following lines. When done we close the scanner.
Just to be sure we have the proper maze, we display it.
We then generate a path from the top left corner to the bottom right corner. The first approach uses a bottom up approach. We then generate a second path (which may be identical or not). This second path uses a top – bottom approach. In both cases we display the generated paths. Both should display paths from the upper left corner to the bottom right corner.
/**
* Use to reprecent a cell in the maze.
*/
class Cell {
// **** ****
public int r;
public int c;
/**
* Constructor
*/
public Cell(int r, int c) {
this.r = r;
this.c = c;
}
/**
* Return string representation of this cell.
*/
@Override
public String toString() {
return "(" + this.r + "," + this.c + ")";
}
}
The Cell class is used to represent cells in the maze. A cell contains the associated row and column in the maze. We have a constructor and a method to generate a string for the cell.
/**
* Entry function to get the path from the end back to the start cell.
* Using bottom up approach.
*/
static ArrayList<Cell> getPath(Boolean[][] maze) {
// **** check start condition ****
if ((maze == null) || (maze.length == 0)) {
return null;
}
// **** used to hold the path ****
ArrayList<Cell> path = new ArrayList<Cell>();
// **** start recursion (from the bottom right corner) ****
if (getPath(maze, maze.length - 1, maze[0].length - 1, path) != null)
return path;
// **** path NOT found ****
return null;
}
This is the entry point for the bottom-up approach to generate the path. We perform a check and generate an array list to hold the path. The process starts from the lower right corner. If a path is found the method returns a path expressed as an array list. If the method returns false, then this method return a null value for the path.
/**
* Recursive procedure to get from s (top left corner) to e (bottom right corner).
* Using bottom up approach.
*/
static Boolean getPath(Boolean[][] maze, int row, int col, ArrayList<Cell> path) {
// **** check for cell out of bounds or not available (moving left and up only) ****
if ((col < 0) || (row < 0) || !maze[row][col]) {
return false;
}
// **** recursive call(s) ****
if (row == 0 && col == 0 || // upper left corner
getPath(maze, row, col - 1, path) || // up
getPath(maze, row - 1, col, path)) { // left
// **** add this cell to the path ****
Cell p = new Cell(row, col);
path.add(p);
// **** path found (end condition) ****
return true;
}
// **** path NOT found (keep on recursing) ****
return false;
}
This recursive method checks if it is being called with coordinates outside of the maze. Note that the check is for columns and rows less than 0. The test is all we need since this function only makes moves up and left.
The recursive calls are performed until the upper top corner is reached. At that point we add the cell to the path and return true. If the path is not found the method returns false.
/**
* Entry function to get the path from the end back to the start cell.
* Using top down approach.
*/
static Stack<Cell> getPathTD(Boolean[][] maze) {
// **** check start condition ****
if ((maze == null) || (maze.length == 0)) {
return null;
}
// **** used to hold the path ****
Stack<Cell> path = new Stack<Cell>();
// **** start recursion (from the top left corner) ****
if (getPathTD(maze, 0, 0, path) != null)
return path;
// **** path NOT found ****
return null;
}
This method performs the same check as getPath. We then initialize a stack to hold the cells in the path. We are now ready to call the recursive method starting with the top left cell.
If the recursive call returns true the path in the stack is returned; otherwise we return a null path indicating that a path was not found.
/**
* Recursive procedure to get from s (top left corner) to e (bottom right corner).
* Using top down apporoach.
*/
static Boolean getPathTD(Boolean[][] maze, int row, int col, Stack<Cell> path) {
// **** check for cell out of bounds or not available (moving right and down only) ****
if ((col > maze[0].length - 1) || (row > maze.length - 1) || !maze[row][col]) {
return false;
}
// **** add this cell to the path ****
Cell p = new Cell(row, col);
path.add(p);
// **** ****
if (row == maze.length - 1 && col == maze[0].length - 1) // lower right corner
return true;
// **** recursion ****
Boolean found = false;
// **** ****
found = getPathTD(maze, row, col + 1, path); // right
if (found)
return true;
// **** ****
found = getPathTD(maze, row + 1, col, path); // down
if (found)
return true;
// **** remove this cell from the path ****
path.pop();
// **** path NOT found (keep on recursing) ****
return false;
}
We check to make sure we are in a valid cell in the maze. Note that in this approach we only move right and down.
We allocate a cell for the current position in the maze and add it to the path.
We check if we have reached the bottom right cell. If so we return true.
Now we make a recursive call to the right cell. The returned value is checked. If we found a path we just return true.
If we get to this point in the code we make a recursive call down. If we find a path we return true.
If we did not get a true from either recursive call, the path has not been able to reach the lower right corner, so we remove from the path the current cell that was added before making the recursive calls.
The function returns false.
# **** ****
C:\Users\johnc>dir
04/16/2020 02:31 PM <DIR> .
04/16/2020 02:31 PM <DIR> ..
09/22/2019 08:00 AM <DIR> .eclipse
03/15/2020 08:38 AM 59 .gitconfig
04/07/2020 10:38 AM <DIR> .p2
04/16/2020 02:31 PM <DIR> .pylint.d
09/22/2019 08:00 AM <DIR> .tooling
03/10/2020 03:53 PM <DIR> .vscode
03/10/2020 04:43 PM <DIR> 3D Objects
03/10/2020 04:43 PM <DIR> Contacts
04/08/2020 07:59 AM <DIR> ContainsCloseNums
02/17/2020 03:52 PM <DIR> Documents
04/19/2020 07:48 AM <DIR> Downloads
09/22/2019 07:57 AM <DIR> eclipse
09/22/2019 07:59 AM <DIR> eclipse-workspace_0
03/10/2020 04:43 PM <DIR> Favorites
03/10/2020 04:44 PM <DIR> Links
03/10/2020 04:43 PM <DIR> Music
09/12/2019 04:36 PM <DIR> NCH Software Suite
04/20/2020 07:22 AM <DIR> OneDrive
03/10/2020 04:43 PM <DIR> Saved Games
03/10/2020 04:43 PM <DIR> Searches
03/10/2020 04:43 PM <DIR> Videos
04/19/2020 07:42 AM <DIR> workspace0
# **** ****
C:\Users\johnc>cd workspace0
# **** ****
C:\Users\johnc\workspace0>dir
04/19/2020 07:42 AM <DIR> .
04/19/2020 07:42 AM <DIR> ..
04/01/2020 08:57 AM <DIR> BST-Search
04/10/2020 11:34 AM <DIR> ComposeRanges
04/08/2020 08:04 AM <DIR> ContainsCloseNums
04/05/2020 08:32 AM <DIR> GraphBFS
04/17/2020 03:41 PM <DIR> MissingNumber
03/29/2020 08:30 AM <DIR> ORCost
04/19/2020 07:46 AM <DIR> RobotInAGrid
03/10/2020 04:24 PM <DIR> SortOnFrequency
# **** ****
C:\Users\johnc\workspace0>cd RobotInAGrid
# **** check that we are using th eproper GitHub repo ****
C:\Users\johnc\workspace0\RobotInAGrid>git remote -v
origin https://github.com/JohnCanessa/RobotInAGrid.git (fetch)
origin https://github.com/JohnCanessa/RobotInAGrid.git (push)
# **** ****
C:\Users\johnc\workspace0\RobotInAGrid>git status
On branch master
Your branch is up to date with 'origin/master'.
Untracked files:
(use "git add <file>..." to include in what will be committed)
Solution.java
nothing added to commit but untracked files present (use "git add" to track)
# **** ****
C:\Users\johnc\workspace0\RobotInAGrid>git add Solution.java
# **** ****
C:\Users\johnc\workspace0\RobotInAGrid>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes to be committed:
(use "git restore --staged <file>..." to unstage)
new file: Solution.java
# **** commit changes ****
C:\Users\johnc\workspace0\RobotInAGrid>git commit -m "top down and down top approaches"
[master be72aa4] top down and down top approaches
1 file changed, 213 insertions(+)
create mode 100644 Solution.java
# **** ****
C:\Users\johnc\workspace0\RobotInAGrid>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working tree clean
# **** push changes to GitHub ****
C:\Users\johnc\workspace0\RobotInAGrid>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 12 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 1.82 KiB | 1.82 MiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/RobotInAGrid.git
a980f25..be72aa4 master -> master
# **** ****
C:\Users\johnc\workspace0\RobotInAGrid>git status
On branch master
Your branch is up to date with 'origin/master'.
nothing to commit, working tree clean
# **** check the log ****
C:\Users\johnc\workspace0\RobotInAGrid>git log
commit be72aa433cf34548ce23d20b2dd7925514026b6d (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date: Mon Apr 20 14:45:12 2020 -0500
top down and down top approaches
commit a980f253e5c03b2a4bc01bcd3bb3cdabe15dc40d
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Sun Apr 19 07:41:50 2020 -0500
Create README.md
We check we are using the proper remote repository in GitHub. Commit the changes and push them to GitHub.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
One last thing, thanks to all 630 subscribers to my blog!!!
John
Twitter: @john_canessa