June 19th 2018
Code Golf: Sparse Arrays
Today on Twitter, Axel Rauschmayer posted a fun little coding challenge:
Code golf: check if an Array has holes. I’ll reply with two ideas of mine in a few minutes.— Axel Rauschmayer (@rauschma) June 19, 2018
For context, code golf is a type of challenge where participants attempt to find the shortest possible way to express a program. Arrays that have holes, or sparse arrays, refer to arrays that don’t have values at every index between their maximum and minimum values. You can define a sparse array like this:
let arr = ; arr = 2 // arr.length is 100
or like this
let arr = [1,,2]; // arr.length is 3
This is different from
let arr = [1, undefined, 2], because the index keys are not defined. If this is difficult to understand, you can picture arrays as simple objects, with access to the
Array.Prototype methods and a special
length property that is aware of numeric keys. The important thing is not whether a value is defined for a specific index, but whether a key was ever explicitly set. Axel’s suggested solutions take advantage of that distinction:
// Does someArray have holes?— Axel Rauschmayer (@rauschma) June 19, 2018
someArray.findIndex((x,i,arr) => x === undefined && !(i in arr)) >= 0
Object.keys(someArray).length < someArray.length
someArray.filter(_ => true).length < someArray.length
I’m going to standardize these into a function syntax for the purpose of comparison. I’m only going to consider one liners, so we’ll define a simple arrow function
isSparse, and compare the length of the function bodies.
// Solution 1 let isSparse = someArray => someArray.findIndex((x,i,arr) => x === undefined && !(i in arr)) >= 0 // Solution 1 condensed (49 characters) let isSparse = a => a.findIndex((x,i,b)=>x===undefined&&!(i in b))>=0 // Solution 2 let isSparse = someArray => Object.keys(someArray).length < someArray.length // Solution 2 condensed (30 characters) let isSparse = a => Object.keys(a).length<a.length // Solution 3 let isSparse = someArray => someArray.filter(_ => true).length < someArray.length // Solution 3 condensed (33 characters) let isSparse = a => a.filter(_=>true).length<a.length
Axel’s solutions all rely on the fact that sparse items don’t have keys, and that Object.keys and Array.prototype methods therefore don’t iterate over them. That’s a good insight and a good foundation for getting even more concise. We can use a few tricks to do that.
Let’s start with his second solution, which was the shortest and clearest in practice and modify it a bit
// We're comparing the length of the list of keys to the array length let isSparse = a => Object.keys(a).length<a.length //But we can use reduce to do this instead (28 characters) let isSparse = a => a.reduce(x=>x-1,a.length)==0
So our first step is to use
reduce to save 2 characters. If you haven’t seen
reduce before, I recommend checking out this great explainer by Sarah Drasner that I linked to in my Weekly Links post last week. Essentially though, reduce is a generic method for iterating through an array to produce a new value. It takes a function and an initial value, and uses the items of the array to iteratively transform the initial value. In this case, I’m just decrementing the value for each defined item in the array, starting at length and seeing if it equals 0. Which ends up being shorter than taking the length of the keys array. But we can still do better!
0 is considered falsy, while every other number is considered truthy. Since we want our function to produce a boolean, we can take advantage of this property, and write our function like this.
// Boolean version (27 characters) let isSparse = a => !!a.reduce(x=>x-1,a.length)
That seems like a bit of a local maximum. But getting to this point made me realize that we weren’t actually saving anything by using the boolean version over a comparison, since we can increment instead and end up at the same length.
// Counting up to length (27 characters) let isSparse = a => a.reduce(x=>x+1,0)<a.length
Doing it this way though, we can actually save 2 more characters, because if reduce doesn’t have an initial value, it just uses the unmodified first element in an array as its initial value, and goes from there:
// Final (broken) Version (25 characters) // UPDATE: This doesn't work let isSparse = a => a.reduce(x=>x+1)<a.length
Update: This last solution only works in situations where the array starts with
1. So 27 is the best generic solution I can find at this point. Thanks to Axel for correcting me. Code golf is hard 😔.