Snowfrog's blog

Accessing items in 2D Arrays

Philippe Vaillancourt -

So I've been doing a lot of code katas, puzzles and exercises lately and many of them involve dealing with multidimensional arrays, mostly 2D arrays. Often, 2D arrays will be the easiest way to represent squares or positions in a game such as chess, checkers, tic-tac-toe etc.

For instance, I recently had to use a 2D array to solve the Mine Field kata.

I continually find myself having to do this and one of the particular challenges with 2D arrays is accessing items adjacent to another item.  Here is an example of how you would do that:

array[y - 1][x] // accesses the item directly north of our reference item
array[y + 1][x + 1] // accesses the item directly south east of our refence item
array[y][x - 1] // accesses the item directly west of our reference item

The problem, in my opinion, with code like this is at least two fold:

  1. It is tedious to write.
  2. It doesn't clearly communicate intent in terms of the domain.

There is another nuisance with accessing 2D arrays using the consecutive brackets [][]  syntax. When trying to access an item at an index [y] in a 1D array where y is out of range the default behaviour of Array is to return undefined. As developers we are used to this. The problem is that when we are trying to access an item at index [y][x] in a 2D array where y is out of range, instead of getting undefined our code is going to throw a Cannot read property 'x' of undefined error. This will only happen when y is out of range but not when only x is out of range. In that case we would get undefined. To the developer, at least to this developer, whether it is y or x that is out of range, we expect that our data structure will deal with the problem in the same way.

In order to, at least partly, solve these issues I have decided to implement a generic Array2D class that I will be able to reuse in other katas. At the moment it sits in the helpers folder in my codingame repo but as I will add more functionality to it I will eventually move it into it's own repo and possibly release it on NPM. The class extends the Array class and as such has all the methods we are familiar with. Here are the extensions I have added so far:

getNorthOf(heightIndex: number, widthIndex: number): T | undefined {
    return this.get(heightIndex - 1, widthIndex)
}

getNorthEastOf(heightIndex: number, widthIndex: number): T | undefined {
    return this.get(heightIndex - 1, widthIndex + 1)
}

getEastOf(heightIndex: number, widthIndex: number): T | undefined {
    return this[heightIndex][widthIndex + 1]
}

getSouthEastOf(heightIndex: number, widthIndex: number): T | undefined {
    return this.get(heightIndex + 1, widthIndex + 1)
}

getSouthOf(heightIndex: number, widthIndex: number): T | undefined {
    return this.get(heightIndex + 1, widthIndex)
}

getSouthWestOf(heightIndex: number, widthIndex: number): T | undefined {
    return this.get(heightIndex + 1, widthIndex - 1)
}

getWestOf(heightIndex: number, widthIndex: number): T | undefined {
    return this[heightIndex][widthIndex - 1]
}

getNorthWestOf(heightIndex: number, widthIndex: number): T | undefined {
    return this.get(heightIndex - 1, widthIndex - 1)
}

get(heightIndex: number, widthIndex: number): T | undefined {
    if (!this[heightIndex]) {
        return undefined
    }
    return this[heightIndex][widthIndex]
}

And here is an example of how it can be used

const gameMap = [
  [0,0,0,3,0],
  [0,2,0,0,0],
  [0,0,1,0,0],
  [4,0,0,0,0],
]
const my2dArray = new Array2D(gameMap)

my2dArray.getNorthOf(3, 2) // -> 1

// Since Array2D extends Array, bracket syntax still works
my2dArray[3][0] // -> 4

// But be aware that you'll still have to deal with exceptions when
// trying to access y axis indices that are out of range
my2dArray[4][0] // -> Cannot read property '0' of undefined

// To avoid this and only ever get undefined if an index, whether
// on the y or x axis, is out of range you can use Array2D.get()
my2dArray.get(4, 0) // -> undefined

Here is a list of possible ideas for additional extensions:

  • Add an optional distance parameter to each getDirectionOf(heightIndex: number, widthIndex: number, distance?: number) method in order to access items not immediately adjacent to the refence item.
  • Add a getSquareAround(heightIndex: number, widthIndex: number, radius: number) method that returns a new Array2D of size (radius * 2 + 1)2 centered around heightIndex and widthIndex.
  • Add a forEach2D(callback(currentValue: T, heightIndex?: number, widthIndex?:number, array2D?), thisArg?) method that executes a provided function once for each array2D element.

Let me know what you think in the comments below and please share any ideas you may have for additional extensions to this class.