|
A friend mentioned a code screen interview question he likes to ask based on
counting the number of discrete “islands” in a grid:
Given a square grid of cells, some of which are sea (0) and some of which
are land (1), implement an island counter that identifies each contiguous
area of land cells (an island) and counts the total number of such islands.
This seems like quite a fun problem to solve so I had a go at it in TypeScript.
Here’s the main part of the code that actually does the island counting:
class Grid {
cells: Cell[] = [];
countIslands(): number {
// Go through the grid.
// When we hit an unvisited land cell:
// > Mark it as visited.
// > Recursively mark each of its land neighbours as visited.
// > Increase the island count by one.
let islandCount: number = 0;
function visitNeighbours(cell: Cell): void {
let queue: Cell[] = [cell];
while (queue.length > 0) {
cell = queue.shift();
cell.visit();
cell.neighbours().forEach((cell: Cell) => {
if (cell.isUnvisitedLand()) {
queue.push(cell);
}
});
}
}
// Make sure all cells are unvisited first.
this.cells.forEach((cell: Cell) => {
cell.visited = false;
});
// Go through cells applying algorithm described above.
this.cells.forEach((cell: Cell) => {
if (cell.isUnvisitedLand()) {
visitNeighbours(cell);
islandCount++;
}
});
return islandCount;
}
}
The idea is:
- Loop through all cells.
- When you hit an unvisited land cell:
- Mark that cell as visited.
- Recursively mark of all its unvisited land neighbours in the same way.
- Increment the island count.
And that’s it.
Tests
This is shown working in these
tests with Mocha and
Chai:
describe('Count island', () => {
it(
'should be able to count a single-cell island',
() => {
const input = `
~~~
~#~
~~~
`;
const grid = Grid.fromString(input);
expect(grid.countIslands()).to.equal(1);
}
);
it(
'should be able to count zero islands',
() => {
const input = `
~~~
~~~
~~~
`;
const grid = Grid.fromString(input);
expect(grid.countIslands()).to.equal(0);
}
);
it(
'should be able to count a single-cell island on an edge',
() => {
const input = `
~~~
#~~
~~~
`;
const grid = Grid.fromString(input);
expect(grid.countIslands()).to.equal(1);
}
);
it(
'should be able to count a single-cell island in a corner',
() => {
const input = `
~~~
~~~
~~#
`;
const grid = Grid.fromString(input);
expect(grid.countIslands()).to.equal(1);
}
);
it(
'should be able to count several single-cell islands',
() => {
const input = `
012
0~#~
1~~~
2#~#
`;
const grid = Grid.fromString(input);
expect(grid.countIslands()).to.equal(3);
}
);
it(
'should be able to count a multi-cell island',
() => {
const input = `
012
0~##
1~~#
2~~#
`;
const grid = Grid.fromString(input);
expect(grid.countIslands()).to.equal(1);
}
);
it(
'should be able to count several multi-cell islands',
() => {
const input = `
012
0~~#
1#~#
2#~#
`;
const grid = Grid.fromString(input);
expect(grid.countIslands()).to.equal(2);
}
);
it(
'should be able to count several large multi-cell islands',
() => {
const input = `
0123456789
0~###~~~~~~
1~~##~~~~~~
2~~~~~~~#~~
3~~~~~###~~
4~~~~~~##~~
5~~#~~~~~#~
6~~##~~~~~~
7~~~~~~~#~~
8~~~~~~~###
9~~~~~~~###
`;
const grid = Grid.fromString(input);
expect(grid.countIslands()).to.equal(4);
}
);
});
3 dimensions
The next stage of the question is:
Now make the counter work for a 3D matrix and not just a 2D grid.
The above code for the main algorithm actually doesn’t need to change. We just
need to change how the grid assembles itself from an array of cells, and how
cells determine their neighbours.
Originally the grid assumed 2 dimensions, and checked that the length of the
input array was a square number.
class Grid {
cells: Cell[];
constructor(cells: Cell[] = []) {
if (Math.sqrt(cells.length) % 1 !== 0) {
throw new RangeError(
`Cells must be a square number; got ${cells.length}`
);
}
this.cells = cells;
// ...
}
}
That now needs to check for a cube root:
class Grid {
cells: Cell[];
dimensions: number;
constructor(cells: Cell[] = []) {
if (Math.cbrt(cells.length) % 1 !== 0) {
throw new RangeError(
`Cells must be a cubic number; got ${cells.length}`
);
}
this.cells = cells;
// ...
}
}
It might have been better to not use a single array as the underlying data
structure for the grid and actually use a multi-dimensional array of arrays,
which would allow differing side lengths. The single dimensional array does make
it easy to read in a test case grid as a string, though.
The other thing that needs to change to allow for 3 dimensions is how a cell
determines its neighbours. Currently it assumes 2 dimensions and shifts around
on those to get its neighbours:
class Cell {
grid: Grid;
x_pos: number;
y_pos: number;
neighbours(): Cell[] {
let neighbours: Cell[] = [];
let shifts: number[] = [-1, 0, 1];
for (let shift_x of shifts) {
for (let shift_y of shifts) {
// Skip this cell.
if (shift_x === 0 && shift_y === 0) {
continue;
}
let neighbour = this.grid.cell(
this.x_pos + shift_x,
this.y_pos + shift_y
);
neighbours.push(neighbour);
}
}
return neighbours;
}
}
Again that needs to change to allow 3 dimensions:
class Cell {
grid: Grid;
x_pos: number;
y_pos: number;
z_pos: number;
neighbours(): Cell[] {
let neighbours: Cell[] = [];
let shifts: number[] = [-1, 0, 1];
for (let shift_x of shifts) {
for (let shift_y of shifts) {
for (let shift_z of shifts) {
// Skip this cell.
if (shift_x === 0 && shift_y === 0 && shift_z === 0) {
continue;
}
let neighbour = this.grid.cell(
this.x_pos + shift_x,
this.y_pos + shift_y,
this.z_pos + shift_z
);
neighbours.push(neighbour);
}
}
}
return neighbours;
}
}
Those would be the main changes to get the same algorithm working with 3
dimensions.
Running tests
The TypeScript source and
tests are included in
this repo. To run them from the root of this repo:
yarn install
./node_modules/mocha/bin/mocha --reporter spec --require ts-node/register \
./static/code/2018/09/island-counting/island-counting.test.ts
View post:
Island counting algorithm in Typescript
|