Island counting algorithm in Typescript
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