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 = [1];
arr[100] = 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?

someArray.findIndex((x,i,arr) => x === undefined && !(i in arr)) >= 0

Object.keys(someArray).length < someArray.length

someArray.filter(_ => true).length < someArray.length

— Axel Rauschmayer (@rauschma) June 19, 2018

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 myWeekly 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!

Our next step will take advantage of a property of numbers in JavaScript. When converting numbers to booleans, 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 :pensive:.

So there you have it. 27 characters to identify sparse arrays. I’d love to hear from you if you can do better. Hit me up on Twitter or byemail.

Recommend

Connect "Fore!": Code Golf in Javascript

Code-Golf

GitHub - uber/sbnet: Sparse Blocks Networks

Introduction to Code-Golf in Clojure

Code Golf

PowerShell 10 Year Anniversary Code Golf Winners

Code a Spectrum-style Crazy Golf game | Wireframe #54

Sparse vs Dense Arrays in JavaScript

Code.golf – Solve problems in the least number of characters

What are sparse arrays in javascript?

About Joyk