Robot on a Grid: Find a path between two corners with forbidden cells on the road
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
2
down vote
favorite
Problem statement
The problem is defined in the book as following:
8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with
r
rows andc
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 an algorithm to find a path for the robot from the top left to the bottom right.
â Cracking the Coding Interview (6th edition)
Feedback I am looking for
Here's the list of things I am interested to hear back (in order of significance):
- Design decisions and improvements (as in "better approach(es) performance- and memory-wise").
- Code readability.
- JavaScript (ES6) language idioms.
- Whatever you find important to say that does not fall into three categories mentioned above.
My approach, design, implementation, and performance description
I've solved a similar problem in the past and recalling the way I attacked it back then. To reach the bottom right cell, we need to either reach its upper neighbor and move down, or reach its left neighbor and move right. By induction, for the upper (or left) neighbor to be reached, we in turn need to first reach their upper or left neighbor and make a single move. And so on, until we find that we're at the top left position of the grid. If the "neighbor reachability moves" were recorded, replaying them in the reverse order results in the path we are after.
Graphically it can be represented like this
State I)
represents the final cell the robot needs to reach, and the arrows in neighboring cells show the direction of the move.
States II)
and III)
show how the neighbors referred in I)
can be reached.
States IV)
, V)
, VI)
, and VII)
show the same for the neighbors referred in II)
and III)
.
This picture can go on and on, but there are three (four?) more special cases:
In LI)
the upper cell is known to be unreachable (grid boundary, restricted cell, or learnt to be unreachable from the top-left cell by down/right moves). LII)
is the similar, but describes the left neighbor cell as unreachable. The current cells might only get reached from left or upper neighbor, respectively.
Finally, LIII)
is a special case which either denotes the complete "unreachability" of the cell from the top-left corner. However, it may also indicate the robot has now reached to top-left corner itself (rowIndex === 0, columnIndex === 0
).
Recursive solution
The code looks almost trivial if problem is solved recursively.
export type X = 'x'; // Forbidden cell
export type _ = ' '; // Allowed cell
export type Grid = (X | _);
export type Move = 'down' | 'right';
export function findPathRecursively(grid: Grid, rowIndex?: number, columnIndex?: number): Move | null
The obvious issues with this approach are:
- Horrible time complexity â impractically slow execution even on reasonable size grids. I haven't deeply analyzed it yet, but it's gotta be something like $ O(rc!) $, (
r
andc
are as defined in problem statement). The root cause of this is the fact the same grid cell can be visited multiple times as a part of different paths. (E.g. statesV)
andVI)
on the picture above are essentially the same, but discovered by arriving from different cells... - Quick call stack exhaustion (
StackOverflow
ðÂÂÂ) â breaking while executing.
Non-recursive solution
So, to solve the mentioned issue, I'm doing two things:
- "Linearizing" the solution (i.e. getting rig of the recursive calls by using a single loop);
- Applying memoization, which is recording the cells which are known to be unreachable from the target cell and avoiding further visits of such cells.
This is hugely improving the time complexity, which looks $ O(rc) $ to me, at the cost of $ O(rc) $ memory used for unreachable cells recording.
My main question here is whether I can further optimize the algorithm time performance AND reduce the memory usage?
Code to review
export function findPath(grid: Grid): Move | null
if (!grid
function markNoPath(hintTable: string, rowIndex: number, columnIndex: number): void
if (!hintTable[rowIndex])
hintTable[rowIndex] = ;
hintTable[rowIndex][columnIndex] = '*';
function lookUp(
grid: Grid,
hintTable: string,
rowIndex: number,
columnIndex: number,
): boolean
return rowIndex > 0 &&
(hintTable[rowIndex - 1]
function lookLeft(
grid: Grid,
hintTable: string,
rowIndex: number,
columnIndex: number,
): boolean
return columnIndex > 0 &&
(hintTable[rowIndex]
Unit tests
The tests are provided for illustration purpose only. The review is NOT necessary, but if you see a mistake, feel free to point it out.
import
findPath,
findPathRecursively,
Grid,
from '../src/cracking-the-coding-interview/8-recursion-and-dynamic-programming/8-2-robot-in-a-grid';
const nullGrid: Grid = null;
const gridWithSingleBlockedCell: Grid = [['x']];
const emptyGrid: Grid = [];
const oneByOneGrid: Grid = [[' ']];
const oneByTwoGrid: Grid = [[' ', ' ']];
const twoByOneGrid: Grid = [[' '], [' ']];
const twoByTwoGridA: Grid = [[' ', 'x'], [' ', ' ']];
const twoByTwoGridB: Grid = [[' ', ' '], ['x', ' ']];
const stairGrid: Grid = [
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', 'x', ' ', ' '],
['x', ' ', ' ', 'x', ' '],
[' ', 'x', ' ', ' ', 'x'],
[' ', ' ', 'x', ' ', ' '],
];
const wellGrid: Grid = [
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', 'x', ' '],
[' ', ' ', 'x', ' ', ' '],
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' '],
];
const cliffGrid: Grid = [
[' ', ' ', ' ', ' ', ' '],
['x', ' ', ' ', 'x', ' '],
[' ', ' ', 'x', ' ', ' '],
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' '],
];
describe(`$findPathRecursively.name & $findPath.name`, () =>
[
grid: nullGrid, expectedPath: null ,
grid: gridWithSingleBlockedCell, expectedPath: null ,
grid: emptyGrid, expectedPath: null ,
grid: oneByOneGrid, expectedPath: ,
grid: oneByTwoGrid, expectedPath: ['right'] ,
grid: twoByOneGrid, expectedPath: ['down'] ,
grid: twoByTwoGridA, expectedPath: ['down', 'right'] ,
grid: twoByTwoGridB, expectedPath: ['right', 'down'] ,
grid: stairGrid,
expectedPath: [ 'down', 'right', 'down', 'right', 'down', 'right', 'down', 'right' ],
,
grid: wellGrid,
expectedPath: [ 'down', 'down', 'down', 'down', 'right', 'right', 'right', 'right' ],
,
grid: cliffGrid,
expectedPath: [ 'right', 'right', 'right', 'right', 'down', 'down', 'down', 'down' ],
,
].forEach(( grid, expectedPath ) =>
const path = expectedPath == null ? 'null' : expectedPath.join('->');
const gridText = JSON.stringify(grid, null, 2);
it(`[Recursive] Should return "$path" for gridn$gridText`, () =>
expect(findPathRecursively(grid)).toEqual(expectedPath);
);
it(`[Non-recursive] Should return "$path" for gridn$gridText`, () =>
expect(findPath(grid)).toEqual(expectedPath);
);
);
);
recursion interview-questions dynamic-programming typescript memoization
add a comment |Â
up vote
2
down vote
favorite
Problem statement
The problem is defined in the book as following:
8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with
r
rows andc
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 an algorithm to find a path for the robot from the top left to the bottom right.
â Cracking the Coding Interview (6th edition)
Feedback I am looking for
Here's the list of things I am interested to hear back (in order of significance):
- Design decisions and improvements (as in "better approach(es) performance- and memory-wise").
- Code readability.
- JavaScript (ES6) language idioms.
- Whatever you find important to say that does not fall into three categories mentioned above.
My approach, design, implementation, and performance description
I've solved a similar problem in the past and recalling the way I attacked it back then. To reach the bottom right cell, we need to either reach its upper neighbor and move down, or reach its left neighbor and move right. By induction, for the upper (or left) neighbor to be reached, we in turn need to first reach their upper or left neighbor and make a single move. And so on, until we find that we're at the top left position of the grid. If the "neighbor reachability moves" were recorded, replaying them in the reverse order results in the path we are after.
Graphically it can be represented like this
State I)
represents the final cell the robot needs to reach, and the arrows in neighboring cells show the direction of the move.
States II)
and III)
show how the neighbors referred in I)
can be reached.
States IV)
, V)
, VI)
, and VII)
show the same for the neighbors referred in II)
and III)
.
This picture can go on and on, but there are three (four?) more special cases:
In LI)
the upper cell is known to be unreachable (grid boundary, restricted cell, or learnt to be unreachable from the top-left cell by down/right moves). LII)
is the similar, but describes the left neighbor cell as unreachable. The current cells might only get reached from left or upper neighbor, respectively.
Finally, LIII)
is a special case which either denotes the complete "unreachability" of the cell from the top-left corner. However, it may also indicate the robot has now reached to top-left corner itself (rowIndex === 0, columnIndex === 0
).
Recursive solution
The code looks almost trivial if problem is solved recursively.
export type X = 'x'; // Forbidden cell
export type _ = ' '; // Allowed cell
export type Grid = (X | _);
export type Move = 'down' | 'right';
export function findPathRecursively(grid: Grid, rowIndex?: number, columnIndex?: number): Move | null
The obvious issues with this approach are:
- Horrible time complexity â impractically slow execution even on reasonable size grids. I haven't deeply analyzed it yet, but it's gotta be something like $ O(rc!) $, (
r
andc
are as defined in problem statement). The root cause of this is the fact the same grid cell can be visited multiple times as a part of different paths. (E.g. statesV)
andVI)
on the picture above are essentially the same, but discovered by arriving from different cells... - Quick call stack exhaustion (
StackOverflow
ðÂÂÂ) â breaking while executing.
Non-recursive solution
So, to solve the mentioned issue, I'm doing two things:
- "Linearizing" the solution (i.e. getting rig of the recursive calls by using a single loop);
- Applying memoization, which is recording the cells which are known to be unreachable from the target cell and avoiding further visits of such cells.
This is hugely improving the time complexity, which looks $ O(rc) $ to me, at the cost of $ O(rc) $ memory used for unreachable cells recording.
My main question here is whether I can further optimize the algorithm time performance AND reduce the memory usage?
Code to review
export function findPath(grid: Grid): Move | null
if (!grid
function markNoPath(hintTable: string, rowIndex: number, columnIndex: number): void
if (!hintTable[rowIndex])
hintTable[rowIndex] = ;
hintTable[rowIndex][columnIndex] = '*';
function lookUp(
grid: Grid,
hintTable: string,
rowIndex: number,
columnIndex: number,
): boolean
return rowIndex > 0 &&
(hintTable[rowIndex - 1]
function lookLeft(
grid: Grid,
hintTable: string,
rowIndex: number,
columnIndex: number,
): boolean
return columnIndex > 0 &&
(hintTable[rowIndex]
Unit tests
The tests are provided for illustration purpose only. The review is NOT necessary, but if you see a mistake, feel free to point it out.
import
findPath,
findPathRecursively,
Grid,
from '../src/cracking-the-coding-interview/8-recursion-and-dynamic-programming/8-2-robot-in-a-grid';
const nullGrid: Grid = null;
const gridWithSingleBlockedCell: Grid = [['x']];
const emptyGrid: Grid = [];
const oneByOneGrid: Grid = [[' ']];
const oneByTwoGrid: Grid = [[' ', ' ']];
const twoByOneGrid: Grid = [[' '], [' ']];
const twoByTwoGridA: Grid = [[' ', 'x'], [' ', ' ']];
const twoByTwoGridB: Grid = [[' ', ' '], ['x', ' ']];
const stairGrid: Grid = [
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', 'x', ' ', ' '],
['x', ' ', ' ', 'x', ' '],
[' ', 'x', ' ', ' ', 'x'],
[' ', ' ', 'x', ' ', ' '],
];
const wellGrid: Grid = [
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', 'x', ' '],
[' ', ' ', 'x', ' ', ' '],
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' '],
];
const cliffGrid: Grid = [
[' ', ' ', ' ', ' ', ' '],
['x', ' ', ' ', 'x', ' '],
[' ', ' ', 'x', ' ', ' '],
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' '],
];
describe(`$findPathRecursively.name & $findPath.name`, () =>
[
grid: nullGrid, expectedPath: null ,
grid: gridWithSingleBlockedCell, expectedPath: null ,
grid: emptyGrid, expectedPath: null ,
grid: oneByOneGrid, expectedPath: ,
grid: oneByTwoGrid, expectedPath: ['right'] ,
grid: twoByOneGrid, expectedPath: ['down'] ,
grid: twoByTwoGridA, expectedPath: ['down', 'right'] ,
grid: twoByTwoGridB, expectedPath: ['right', 'down'] ,
grid: stairGrid,
expectedPath: [ 'down', 'right', 'down', 'right', 'down', 'right', 'down', 'right' ],
,
grid: wellGrid,
expectedPath: [ 'down', 'down', 'down', 'down', 'right', 'right', 'right', 'right' ],
,
grid: cliffGrid,
expectedPath: [ 'right', 'right', 'right', 'right', 'down', 'down', 'down', 'down' ],
,
].forEach(( grid, expectedPath ) =>
const path = expectedPath == null ? 'null' : expectedPath.join('->');
const gridText = JSON.stringify(grid, null, 2);
it(`[Recursive] Should return "$path" for gridn$gridText`, () =>
expect(findPathRecursively(grid)).toEqual(expectedPath);
);
it(`[Non-recursive] Should return "$path" for gridn$gridText`, () =>
expect(findPath(grid)).toEqual(expectedPath);
);
);
);
recursion interview-questions dynamic-programming typescript memoization
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Problem statement
The problem is defined in the book as following:
8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with
r
rows andc
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 an algorithm to find a path for the robot from the top left to the bottom right.
â Cracking the Coding Interview (6th edition)
Feedback I am looking for
Here's the list of things I am interested to hear back (in order of significance):
- Design decisions and improvements (as in "better approach(es) performance- and memory-wise").
- Code readability.
- JavaScript (ES6) language idioms.
- Whatever you find important to say that does not fall into three categories mentioned above.
My approach, design, implementation, and performance description
I've solved a similar problem in the past and recalling the way I attacked it back then. To reach the bottom right cell, we need to either reach its upper neighbor and move down, or reach its left neighbor and move right. By induction, for the upper (or left) neighbor to be reached, we in turn need to first reach their upper or left neighbor and make a single move. And so on, until we find that we're at the top left position of the grid. If the "neighbor reachability moves" were recorded, replaying them in the reverse order results in the path we are after.
Graphically it can be represented like this
State I)
represents the final cell the robot needs to reach, and the arrows in neighboring cells show the direction of the move.
States II)
and III)
show how the neighbors referred in I)
can be reached.
States IV)
, V)
, VI)
, and VII)
show the same for the neighbors referred in II)
and III)
.
This picture can go on and on, but there are three (four?) more special cases:
In LI)
the upper cell is known to be unreachable (grid boundary, restricted cell, or learnt to be unreachable from the top-left cell by down/right moves). LII)
is the similar, but describes the left neighbor cell as unreachable. The current cells might only get reached from left or upper neighbor, respectively.
Finally, LIII)
is a special case which either denotes the complete "unreachability" of the cell from the top-left corner. However, it may also indicate the robot has now reached to top-left corner itself (rowIndex === 0, columnIndex === 0
).
Recursive solution
The code looks almost trivial if problem is solved recursively.
export type X = 'x'; // Forbidden cell
export type _ = ' '; // Allowed cell
export type Grid = (X | _);
export type Move = 'down' | 'right';
export function findPathRecursively(grid: Grid, rowIndex?: number, columnIndex?: number): Move | null
The obvious issues with this approach are:
- Horrible time complexity â impractically slow execution even on reasonable size grids. I haven't deeply analyzed it yet, but it's gotta be something like $ O(rc!) $, (
r
andc
are as defined in problem statement). The root cause of this is the fact the same grid cell can be visited multiple times as a part of different paths. (E.g. statesV)
andVI)
on the picture above are essentially the same, but discovered by arriving from different cells... - Quick call stack exhaustion (
StackOverflow
ðÂÂÂ) â breaking while executing.
Non-recursive solution
So, to solve the mentioned issue, I'm doing two things:
- "Linearizing" the solution (i.e. getting rig of the recursive calls by using a single loop);
- Applying memoization, which is recording the cells which are known to be unreachable from the target cell and avoiding further visits of such cells.
This is hugely improving the time complexity, which looks $ O(rc) $ to me, at the cost of $ O(rc) $ memory used for unreachable cells recording.
My main question here is whether I can further optimize the algorithm time performance AND reduce the memory usage?
Code to review
export function findPath(grid: Grid): Move | null
if (!grid
function markNoPath(hintTable: string, rowIndex: number, columnIndex: number): void
if (!hintTable[rowIndex])
hintTable[rowIndex] = ;
hintTable[rowIndex][columnIndex] = '*';
function lookUp(
grid: Grid,
hintTable: string,
rowIndex: number,
columnIndex: number,
): boolean
return rowIndex > 0 &&
(hintTable[rowIndex - 1]
function lookLeft(
grid: Grid,
hintTable: string,
rowIndex: number,
columnIndex: number,
): boolean
return columnIndex > 0 &&
(hintTable[rowIndex]
Unit tests
The tests are provided for illustration purpose only. The review is NOT necessary, but if you see a mistake, feel free to point it out.
import
findPath,
findPathRecursively,
Grid,
from '../src/cracking-the-coding-interview/8-recursion-and-dynamic-programming/8-2-robot-in-a-grid';
const nullGrid: Grid = null;
const gridWithSingleBlockedCell: Grid = [['x']];
const emptyGrid: Grid = [];
const oneByOneGrid: Grid = [[' ']];
const oneByTwoGrid: Grid = [[' ', ' ']];
const twoByOneGrid: Grid = [[' '], [' ']];
const twoByTwoGridA: Grid = [[' ', 'x'], [' ', ' ']];
const twoByTwoGridB: Grid = [[' ', ' '], ['x', ' ']];
const stairGrid: Grid = [
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', 'x', ' ', ' '],
['x', ' ', ' ', 'x', ' '],
[' ', 'x', ' ', ' ', 'x'],
[' ', ' ', 'x', ' ', ' '],
];
const wellGrid: Grid = [
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', 'x', ' '],
[' ', ' ', 'x', ' ', ' '],
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' '],
];
const cliffGrid: Grid = [
[' ', ' ', ' ', ' ', ' '],
['x', ' ', ' ', 'x', ' '],
[' ', ' ', 'x', ' ', ' '],
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' '],
];
describe(`$findPathRecursively.name & $findPath.name`, () =>
[
grid: nullGrid, expectedPath: null ,
grid: gridWithSingleBlockedCell, expectedPath: null ,
grid: emptyGrid, expectedPath: null ,
grid: oneByOneGrid, expectedPath: ,
grid: oneByTwoGrid, expectedPath: ['right'] ,
grid: twoByOneGrid, expectedPath: ['down'] ,
grid: twoByTwoGridA, expectedPath: ['down', 'right'] ,
grid: twoByTwoGridB, expectedPath: ['right', 'down'] ,
grid: stairGrid,
expectedPath: [ 'down', 'right', 'down', 'right', 'down', 'right', 'down', 'right' ],
,
grid: wellGrid,
expectedPath: [ 'down', 'down', 'down', 'down', 'right', 'right', 'right', 'right' ],
,
grid: cliffGrid,
expectedPath: [ 'right', 'right', 'right', 'right', 'down', 'down', 'down', 'down' ],
,
].forEach(( grid, expectedPath ) =>
const path = expectedPath == null ? 'null' : expectedPath.join('->');
const gridText = JSON.stringify(grid, null, 2);
it(`[Recursive] Should return "$path" for gridn$gridText`, () =>
expect(findPathRecursively(grid)).toEqual(expectedPath);
);
it(`[Non-recursive] Should return "$path" for gridn$gridText`, () =>
expect(findPath(grid)).toEqual(expectedPath);
);
);
);
recursion interview-questions dynamic-programming typescript memoization
Problem statement
The problem is defined in the book as following:
8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with
r
rows andc
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 an algorithm to find a path for the robot from the top left to the bottom right.
â Cracking the Coding Interview (6th edition)
Feedback I am looking for
Here's the list of things I am interested to hear back (in order of significance):
- Design decisions and improvements (as in "better approach(es) performance- and memory-wise").
- Code readability.
- JavaScript (ES6) language idioms.
- Whatever you find important to say that does not fall into three categories mentioned above.
My approach, design, implementation, and performance description
I've solved a similar problem in the past and recalling the way I attacked it back then. To reach the bottom right cell, we need to either reach its upper neighbor and move down, or reach its left neighbor and move right. By induction, for the upper (or left) neighbor to be reached, we in turn need to first reach their upper or left neighbor and make a single move. And so on, until we find that we're at the top left position of the grid. If the "neighbor reachability moves" were recorded, replaying them in the reverse order results in the path we are after.
Graphically it can be represented like this
State I)
represents the final cell the robot needs to reach, and the arrows in neighboring cells show the direction of the move.
States II)
and III)
show how the neighbors referred in I)
can be reached.
States IV)
, V)
, VI)
, and VII)
show the same for the neighbors referred in II)
and III)
.
This picture can go on and on, but there are three (four?) more special cases:
In LI)
the upper cell is known to be unreachable (grid boundary, restricted cell, or learnt to be unreachable from the top-left cell by down/right moves). LII)
is the similar, but describes the left neighbor cell as unreachable. The current cells might only get reached from left or upper neighbor, respectively.
Finally, LIII)
is a special case which either denotes the complete "unreachability" of the cell from the top-left corner. However, it may also indicate the robot has now reached to top-left corner itself (rowIndex === 0, columnIndex === 0
).
Recursive solution
The code looks almost trivial if problem is solved recursively.
export type X = 'x'; // Forbidden cell
export type _ = ' '; // Allowed cell
export type Grid = (X | _);
export type Move = 'down' | 'right';
export function findPathRecursively(grid: Grid, rowIndex?: number, columnIndex?: number): Move | null
The obvious issues with this approach are:
- Horrible time complexity â impractically slow execution even on reasonable size grids. I haven't deeply analyzed it yet, but it's gotta be something like $ O(rc!) $, (
r
andc
are as defined in problem statement). The root cause of this is the fact the same grid cell can be visited multiple times as a part of different paths. (E.g. statesV)
andVI)
on the picture above are essentially the same, but discovered by arriving from different cells... - Quick call stack exhaustion (
StackOverflow
ðÂÂÂ) â breaking while executing.
Non-recursive solution
So, to solve the mentioned issue, I'm doing two things:
- "Linearizing" the solution (i.e. getting rig of the recursive calls by using a single loop);
- Applying memoization, which is recording the cells which are known to be unreachable from the target cell and avoiding further visits of such cells.
This is hugely improving the time complexity, which looks $ O(rc) $ to me, at the cost of $ O(rc) $ memory used for unreachable cells recording.
My main question here is whether I can further optimize the algorithm time performance AND reduce the memory usage?
Code to review
export function findPath(grid: Grid): Move | null
if (!grid
function markNoPath(hintTable: string, rowIndex: number, columnIndex: number): void
if (!hintTable[rowIndex])
hintTable[rowIndex] = ;
hintTable[rowIndex][columnIndex] = '*';
function lookUp(
grid: Grid,
hintTable: string,
rowIndex: number,
columnIndex: number,
): boolean
return rowIndex > 0 &&
(hintTable[rowIndex - 1]
function lookLeft(
grid: Grid,
hintTable: string,
rowIndex: number,
columnIndex: number,
): boolean
return columnIndex > 0 &&
(hintTable[rowIndex]
Unit tests
The tests are provided for illustration purpose only. The review is NOT necessary, but if you see a mistake, feel free to point it out.
import
findPath,
findPathRecursively,
Grid,
from '../src/cracking-the-coding-interview/8-recursion-and-dynamic-programming/8-2-robot-in-a-grid';
const nullGrid: Grid = null;
const gridWithSingleBlockedCell: Grid = [['x']];
const emptyGrid: Grid = [];
const oneByOneGrid: Grid = [[' ']];
const oneByTwoGrid: Grid = [[' ', ' ']];
const twoByOneGrid: Grid = [[' '], [' ']];
const twoByTwoGridA: Grid = [[' ', 'x'], [' ', ' ']];
const twoByTwoGridB: Grid = [[' ', ' '], ['x', ' ']];
const stairGrid: Grid = [
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', 'x', ' ', ' '],
['x', ' ', ' ', 'x', ' '],
[' ', 'x', ' ', ' ', 'x'],
[' ', ' ', 'x', ' ', ' '],
];
const wellGrid: Grid = [
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', 'x', ' '],
[' ', ' ', 'x', ' ', ' '],
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' '],
];
const cliffGrid: Grid = [
[' ', ' ', ' ', ' ', ' '],
['x', ' ', ' ', 'x', ' '],
[' ', ' ', 'x', ' ', ' '],
[' ', 'x', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' '],
];
describe(`$findPathRecursively.name & $findPath.name`, () =>
[
grid: nullGrid, expectedPath: null ,
grid: gridWithSingleBlockedCell, expectedPath: null ,
grid: emptyGrid, expectedPath: null ,
grid: oneByOneGrid, expectedPath: ,
grid: oneByTwoGrid, expectedPath: ['right'] ,
grid: twoByOneGrid, expectedPath: ['down'] ,
grid: twoByTwoGridA, expectedPath: ['down', 'right'] ,
grid: twoByTwoGridB, expectedPath: ['right', 'down'] ,
grid: stairGrid,
expectedPath: [ 'down', 'right', 'down', 'right', 'down', 'right', 'down', 'right' ],
,
grid: wellGrid,
expectedPath: [ 'down', 'down', 'down', 'down', 'right', 'right', 'right', 'right' ],
,
grid: cliffGrid,
expectedPath: [ 'right', 'right', 'right', 'right', 'down', 'down', 'down', 'down' ],
,
].forEach(( grid, expectedPath ) =>
const path = expectedPath == null ? 'null' : expectedPath.join('->');
const gridText = JSON.stringify(grid, null, 2);
it(`[Recursive] Should return "$path" for gridn$gridText`, () =>
expect(findPathRecursively(grid)).toEqual(expectedPath);
);
it(`[Non-recursive] Should return "$path" for gridn$gridText`, () =>
expect(findPath(grid)).toEqual(expectedPath);
);
);
);
recursion interview-questions dynamic-programming typescript memoization
edited May 23 at 22:00
asked May 22 at 23:00
Igor Soloydenko
2,697827
2,697827
add a comment |Â
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f194979%2frobot-on-a-grid-find-a-path-between-two-corners-with-forbidden-cells-on-the-roa%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password