Counting Sheep (Beatrix Trotter) Javascript

Question

I am trying to solve a question on CodeWars that was part of the Google CodeJam 2016 qualification rounds. https://www.codewars.com/kata/bleatrix-trotter-the-counting-sheep/train/javascript

I believe my code accounts for all test cases, my only issue is that it cannot be submitted on codewars because it has a runtime greater than 12000 ms.

How Can I make my Code more efficient?? also is there a best practice for testing whether the loop will be infinite.

function trotter(n) {
  var tracker = [];
  var sum = [];
  var snacker = n;
  for(var i = 0; tracker.length < 10; i++){
    sum = snacker.toString().split('');
    sum.forEach(function(num) {
        if (tracker.indexOf(num) == -1) {
             tracker.push(num);
        }
    });
    snacker += n;
  }
  return tracker.length === 10 ? snacker - n : "INSOMNIA";
}

Answer 1

When performance matters and reduced readability is not an issue you should:

• Prefer for and while loops rather than built-ins like map, forEach...

• In recent (2016) versions of JavaScript, it looks like for loops, specially reverse for loops, are the most performant option.

  Also, keep in mind that you don't need to use its 3 expressions. For example, for me...:

  let found = 0;
  
  for (;found < 10;) {
  

  and

  let j = chars.length;
  
  for (;j;) {
  

  consistently returned better results than the same with the initialisation in the initialisation slot and than while loops, although in this latter case the difference was not so big.

  For more one this, see Javascript Performance: While vs For Loops

• When using foo.bar in a while's or for's expression, such as for (let i = 0; i < array.length; ++i), prefer to declare the limit condition above so that it is not evaluated each time, as that involves an object lookup:

  const totalElements = array.length;
  
  for (let i = 0; i < totalElements; ++i) { ... }
  

• Prefer pre-increment instead of post-increment. The latter will create a temporary variable storing the pre-incrementation value, which will return to you, while the former will first do the increment and then return the incremented value. No temporary variable needed.

  For more on this, see post increment vs pre increment - Javascript Optimization

  Actually, if the result is going to be the same regardless which one you use, then I would advise you to use pre-increment whenever possible.

• Avoid built-in methods that have an equivalent expression. For example, (n + '') is more performant than n.toString().

• Avoid type conversions and prefer using integers rather than floats or strings as modern JS engines tag variable types. That means that, on one hand, changing types will have a performance penalty, and, on the other hand, that using them consistently will allow the engine to do some type-specific optimisation.

  For more on this, see https://www.html5rocks.com/en/tutorials/speed/v8/

• Use bitwise operators when possible. For example, an integer division can be done with Math.floor(a /b) or with a / b | 0, which is almost twice as fast.

  For more on integer division in JavaScript, see this interesting thread: How to perform integer division and get the remainder in JavaScript?

• Prefer an object lookup (object.prop or object['prop']) rather than using Array.prototype.indexOf(...).

  See Javascript: what lookup is faster: array.indexOf vs object hash?

• Avoid using arrays and objects and related methods when there are alternatives with simpler structures or inmutable data structures.

  For example, @RobG's solution uses splice. While I'm not aware of the internal implementation, probably it is shifting the elements that come after the deleted ones to compact the array again and updating its length as well.

  With my solution, however, the length of the array is always the same and you are just changing its values from false to true, which involves much less overhead, as there's no need to reallocate space.

• Use typed arrays when possible, though I tried Uint8Array here, both assigning it true and 1, and none of them improved the times; the former actually almost doubled the time and the first one kept them more or less the same. Maybe it there was a BooleanArray it could work.

Keep in mind this is just a list of some techniques or features I think may help to speed up your example. I highly recommend you to read the external links I added as well in order to better understand how and why they work and where else they can be applied.

Moreover, in general, the lower level you keep your code, that is, you using basic data types and operations, the most performance it will be.

To prove that, below I show you a highly optimised version of this code that uses integer division (n / 10) | 0 and remainder (%).

function trotter(N) {
  if (N === 0) return 'INSOMNIA';
  
  const digits = [false, false, false, false, false, false, false, false, false, false];
    
  let n;
  let last = 0;
  let found = 0;
 
  for (;found < 10;) {
    n = last += N;
    
    for (;n;) {
      const digit = n % 10;
            
      n = (n / 10) | 0;
            
      if (!digits[digit]) {
        digits[digit] = true;
        
        ++found;
      }
    }
  }
  
  return last;
}

const numbers = [0, 2, 7, 125, 1625, 1692];
const outputs = ['INSOMNIA', 90, 70, 9000, 9750, 5076];

// CHECK IT WORKS FIRST:

numbers.map((number, index) => {
  if (trotter(number) !== outputs[index]) {
    console.log('EXPECTED = ' + outputs[index]);
    console.log('     GOT = ' + trotter(number));

    throw new Error('Incorrect value.');
  }
});


// PERF. TEST:

const ITERATIONS = 1000000;

const t0 = performance.now();

for (let i = 0; i < ITERATIONS; ++i) {
  numbers.map((number, index) => trotter(number));
}

const t1 = performance.now();

console.log(`AVG. TIME: ${ (t1 - t0) / ITERATIONS } ms. with ${ ITERATIONS } ITERATIONS`);

   AVG. TIME: 0.0033206450000000005 ms. with 1000000 ITERATIONS

     BROWSER: Google Chrome Version 59.0.3071.86 (Official Build) (64-bit)
          OS: macOS Sierra

BRAND, MODEL: MacBook Pro (Retina, 15-inch, Mid 2015)
   PROCESSOR: 2,8 GHz Intel Core i7
      MEMORY: 16 GB 1600 MHz DDR3

Below you can see my initial answer, which uses some of the other optimisations listed here, but still converts the number variable n to string and uses String.prototype.split() to get its digits.

It is almost 5 times slower then the one above!

function trotter(N) {
  if (N === 0) return 'INSOMNIA';
  
  const digits = [false, false, false, false, false, false, false, false, false, false];
  
  let n = N;
  let i = 0;
  let found = 0;
  
  for (;found < 10;) {
    // There's no need for this multiplication:

    n = N * ++i;
    
    // Type conversion + Built-in String.prototype.split(), both can
    // be avoided:

    const chars = (n + '').split('');
    
    let j = chars.length;
    
    for (;j;) {
      const digit = chars[--j];
            
      if (!digits[digit]) {
        digits[digit] = true;
        
        ++found;
      }
    }
  }
  
  return n;
}

const numbers = [0, 2, 7, 125, 1625, 1692];
const outputs = ['INSOMNIA', 90, 70, 9000, 9750, 5076];

// CHECK IT WORKS FIRST:

numbers.map((number, index) => {
  if (trotter(number) !== outputs[index]) {
    console.log('EXPECTED = ' + outputs[index]);
    console.log('     GOT = ' + trotter(number));

    throw new Error('Incorrect value.');
  }
});


// PERF. TEST:

const ITERATIONS = 1000000;

const t0 = performance.now();

for (let i = 0; i < ITERATIONS; ++i) {
  numbers.map((number, index) => trotter(number));
}

const t1 = performance.now();

console.log(`AVG. TIME: ${ (t1 - t0) / ITERATIONS } ms. with ${ ITERATIONS } ITERATIONS`);

   AVG. TIME: 0.016428575000000004 ms. with 1000000 ITERATIONS

     BROWSER: Google Chrome Version 59.0.3071.86 (Official Build) (64-bit)
          OS: macOS Sierra

BRAND, MODEL: MacBook Pro (Retina, 15-inch, Mid 2015)
   PROCESSOR: 2,8 GHz Intel Core i7
      MEMORY: 16 GB 1600 MHz DDR3

Answer 2

The following code has no special optimisations and uses all ECMA-262 ed 3 methods. It ran the full suite of tests in 339 ms.

function trotter(n){
  var nums = ['0','1','2','3','4','5','6','7','8','9'];
  var i = 1;

  // Zero creates an infinite loop, so skip it
  if (n !== 0) {

    // While there are numbers to remove, keep going
    // Limit loops to 100 just in case
    while (nums.length && i < 100) {
      // Get test number as an array of digits
      var d = ('' + (n * i)).split('');

      // For each digit, if in nums remove it
      for (var j=0, jLen=d.length; j<jLen; j++) {
        var idx = nums.indexOf(d[j]);

        if (idx > -1) nums.splice(idx, 1);
      }

      i++;
    }
  }
  // If there are numbers left, didn't get to sleep
  // Otherwise, return last number seen (put d back together and make a numer)
  return nums.length? 'INSOMNIA' : Number(d.join(''));
}

console.log('0   : ' + trotter(0));
console.log('125 : ' + trotter(125));
console.log('1625: ' + trotter(1625));

Most cases are resolved in about 10 iterations, however 125, 1250, 12500, etc. take 73 iterations, which I think is the most that any number takes.

Since Array methods may be slow, here's a string version that's about twice as fast:

function trotter(n){
  var found = '';
  if (n !== 0) {
    var i = 1;
    while (found.length < 10) {
      var d = i * n + '';
      var j = d.length;
      while (j) {
        var c = d[--j];
        var idx = found.indexOf(c);
        if (idx == -1) found += c;
      }
      i++;
    }
  }
  return found.length == 10? +d : 'INSOMNIA';
}

[0,    // Infinte loop case
 125,  // Max loop case
 1625] // just a number
 .forEach(function (n) {
  console.log(n + ' : ' + trotter(n));
});

While doing while (found.length) is not optimal, it's typically only computed about 10 times, so not really significant to move outside the condition. An alternative is to include a counter that is incremented each time a digit is added to found, but this isn't really about optimising performance as much as finding something reasonable that works and passes the (undisclosed) tests at codewars.

Answer 3

Another approach:

    function trotter(n){
      var unseen = '0123456789', last = 0;
      while (unseen != '' && last < 72*n) {
        last += n;
        var reg = new RegExp('[' + last + ']+', 'g');
        unseen = unseen.replace(reg, '');
      }
      return unseen != '' ? 'INSOMNIA' : last;
    };

    console.log('0   : ' + trotter(0));
    console.log('125 : ' + trotter(125));
    console.log('1625: ' + trotter(1625));