7
\$\begingroup\$

The task

Given an integer array, move all elements that are equal to 0 to the left while maintaining the order of other elements in the array. Let's look at the following integer array.

After moving all zero elements to the left, the array should look like this. We need to maintain the order of non-zero elements.

0 0 0 1 10 20 59 63 88

My approach, I used TDD and hoped my solution would become just as good as the sample solution.

test('contains no element', () => {
  expect(moveZeroToLeft([])).toStrictEqual(undefined);
});

test('contains only a 0 element', () => {
  expect(moveZeroToLeft([0])).toStrictEqual([0]);
});

test('contains only a non 0 element', () => {
  expect(moveZeroToLeft([1])).toStrictEqual([1]);
});

test('contains more than one element with a 0', () => {
  expect(moveZeroToLeft([1, 0])).toStrictEqual([0, 1]);
});

test('contains more than one element without 0', () => {
  expect(moveZeroToLeft([1, 3])).toStrictEqual([1, 3]);
});

test('contains more than one element with a 0 somewhere in the middle', () => {
  expect(moveZeroToLeft([1, 0, 3])).toStrictEqual([0, 1, 3]);
});

test('contains random number of zeros and non-zero elements', () => {
  expect(moveZeroToLeft([1, 0, 3, 0, 0, 44, 1, 0, 2])).toStrictEqual([0, 0, 0, 0, 1, 3, 44, 1, 2]);
});

My solution

function moveZeroToLeft(arr) {
  if (arr.length < 2) {
    return arr;
  }
  if (arr.some(x => x === 0)) {
    let zeroCounter = 0;
    const res = arr.filter(el => {
      if (el !== 0) {
        return true;
      }
      zeroCounter++;
    });
    const leadingZeros = Array(zeroCounter).fill(0);
    return leadingZeros.concat(res);
  }
  return arr;
}

But the sample solution is much more elegant than mine:

let move_zeros_to_left = function(A) {
  if (A.length < 1) {
    return;
  }

  let lengthA = A.length;
  let write_index = lengthA - 1;
  let read_index = lengthA - 1;

  while (read_index >= 0) {
    if (A[read_index] != 0) {
      A[write_index] = A[read_index];
      write_index--;
    }

    read_index--;
  }

  while (write_index >= 0) {
    A[write_index] = 0;
    write_index--;
  }
};

How could I have come to the sample solution with a TDD approach?

\$\endgroup\$
  • 1
    \$\begingroup\$ ...And you're already off to a bad start: your first test case expects the wrong result! moveZeroToLeft([]) should result in [], not undefined. If your test is incorrect in the first place, TDD would be a hindrance to you instead. \$\endgroup\$ – Voile Nov 25 '19 at 8:03
  • \$\begingroup\$ Ah, just forgot to update the code in the question. My first impulse was indeed to return an empty array. But the sample solution returned undefined, therefore I changed the test case but forgot to update the question here \$\endgroup\$ – thadeuszlay Nov 25 '19 at 8:15
  • \$\begingroup\$ The code returns a new array, the task is to modify the existing array. It seems the tests and implementation are wrong. \$\endgroup\$ – konijn Nov 25 '19 at 10:52
  • 1
    \$\begingroup\$ It's been said in the answers but it is worth saying on it's own: the sample solution is awful, awful, awful. The only lines I don't have problems with are the blank lines and most of the ones with only "}". \$\endgroup\$ – Odalrick Nov 25 '19 at 13:59
  • \$\begingroup\$ @konijn where does it say that the function should return the existing array? \$\endgroup\$ – thadeuszlay Nov 30 '19 at 23:32
8
\$\begingroup\$

TDD is not for finding "elegant" solutions, but for finding working solutions that cover all edge cases. Without edge cases, solutions are often too naive and in the end won't work.

You missed some edge cases; the task states: "order of other elements in the array" (that are integer). How about Infinity and -Infinity? Are they numbers? :) isNaN(Infinity)?

Another thing is, that beauty lies in the eye of the beholder. For me elegant code, is code, that is easy to grasp and not overly complex. Whenever a problem can be solved in such a generic way, that edge case do not need any special handling this is good code. :)

Speaking of which - your problem is clearly about transforming an array - with JavaScript you have a good set of Array.fns() at you disposal and fat arrow functions. Thus I'd intuitively never use loops, but only array functions.

The original problem sounds very constructed to me - I guess some stupid code interview stuff. I guess it is about thinking of how to find zeros in an array and move them around.

However the solution is quite trivial if you are thinking outside the box (which you are!), that with the elements being numbers, the solution is not about moving around zeros (and thus maintain their reference, if it where not zeros but objects), but in filtering and reconstructing them.

const move_zeros_to_left = function(unsortedArray) {
  const numberOfZeros = unsortedArray.filter(item => item === 0).length;
  const nonZeroArray = unsortedArray.filter(item => item !== 0);
  return [...Array.from({length: numberOfZeros}).fill(0), ...nonZeroArray];
}

Covers all the edge cases and is readable. Your provided sample solution is the worst of all solution, because it neglects the fact, that JavaScript has a rich set of Array functions and thus it is neither readable nor idiomatic and I'd say thus not elegant all. :)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Can you explain what you mean by "How about Infinity and -Infinity? Are they numbers? :) isNaN(Infinity)?"? That's a bit misleading to say at least. isNaN(x) === false does not imply x is number. Well, depends what you mean by "being a number". If you mean being of js data type Number then Inf, -Inf and NaN are Numbers. If you mean mathematical sense, then nor inf nor -inf nor nan are numbers. You wont find infinity on the real number line, nor in the complex plane. And definitely not in the set of all integers. \$\endgroup\$ – slepic Nov 25 '19 at 7:00
  • 4
    \$\begingroup\$ I think doing two filters is not very elegant. You could compute nonZeroArray first and then numberOfZeros = unsortedArray.length - nonZeroArray.length. \$\endgroup\$ – Clashsoft Nov 25 '19 at 8:26
  • 1
    \$\begingroup\$ Also, isn't Array.from({length: numberOfZeros}) the same as Array(numberOfZeros)? Please correct me if there's a subtle difference \$\endgroup\$ – Clashsoft Nov 25 '19 at 8:26
  • \$\begingroup\$ @Clashsoft Or just go [...arr.filter(n => n === 0), ...arr.filter(n => n !== 0)], unless I'm missing some weird special case. If they're === 0, aren't they always, well, 0? \$\endgroup\$ – JollyJoker Nov 25 '19 at 13:42
  • 1
    \$\begingroup\$ @Clashsoft Not @ChristianUlbrich, but: From a readability standpoint Array(numberOfZeros) is ambiguous. For example, Array(a, b, c) creates an array containing a, b and c, so one could expect Array(a) to create an array containing just a - which is does unless a is an integer, in which case it creates an array of the length a instead. So using Array.from(...) like this makes it more obvious what is happening. That said: In this case I myself would prefer Array(numberOfZeros). \$\endgroup\$ – RoToRa Nov 25 '19 at 14:47
3
\$\begingroup\$

Testing elegance

Testing ignores the method and only focuses on the result. If however you add testing that includes criteria that focus on what you may call the elegant parts of the solution this can help you create better solutions.

Personally elegance is a fit, performant and lean, in that order.

  • Fit, it must pass all test.
  • Performant it must be as fast and use as little memory as possible.
  • Lean, the code must be as compact and neat as possible.

You can test all these and iterate to a more elegant solution. However the last point is subjective and this can be hard to test. Personally I measure lean as number of lines (including empty lines) and the number of tokens used.

The last to criteria are always comparative, one solution compared to another as they have no value in isolation.

The sample solution is in my book is far from elegant

  • It is overly verbose, names too long, not using shorthand styles (short circuiting and decremented operators) contains redundant length check at start.
  • Poor use of comparisons as it forces type checking for each comparison. >= should use !== 0 as its quicker.
  • Has a wasted variable. There is no need for the variable lengthA

One can rewrite the function as

function bubbleDown(arr) {
    var wIdx = arr.length, rIdx = wIdx;
    while (rIdx--) { arr[rIdx] && (arr[--wIdx] = arr[rIdx]) }
    while (wIdx--) { arr[wIdx] = 0 }
}

Slightly faster by avoiding the type checks

function bubbleDown(arr) {
    var w = arr.length, r = w;
    while (r-- !== 0) { arr[r] !== 0 && (arr[--w] = arr[r]) }
    while (w-- !== 0) { arr[w] = 0 }
}

And slower but lean. Sucks that Array.fill is so much slower than a while loop.

function bubbleDown(arr) {
    var w = arr.length, r = w;
    while (r--) { arr[r] && (arr[--w] = arr[r]) }
    arr.fill(0, 0, w);
}

The first two are up to 10% faster (last 30% slower) and easier to read and maintain (if that was important as having passed all tests it never needs to be read or changed), and all 3 are elegant.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Having performant code and having compact code are often opposed to each other. One must sort their priorities for this. Also using && just for the shortcut evaluation effect is less readable then you think IMO. And btw you say >= is less performant then !== and then you use the implicit bool conversion arr[r] as condition, which is even worse. Looks like you advocate against yourself... \$\endgroup\$ – slepic Nov 25 '19 at 7:23
  • 1
    \$\begingroup\$ Also being as fast as possible and using as little memory as possible is also often opposed to each other. You can often improve time complexity at the cost of consuming more memory. And you can often reduce memory usage at the cost of decreased speed. Again, one must sort their priorities first. \$\endgroup\$ – slepic Nov 25 '19 at 7:29
  • 1
    \$\begingroup\$ Personally, I strongly disagree with „performant and lean, in that order.“ – I much rather prefer the idiom „Make it work. Make it beautiful [i.e. manitainable]. Make it fast. In that order“ (source). The burden of badly maintainable code is often larger than the burden of an efficiency problem, (and those do not even matter most of the time). I do note that beauty, maintainability, and „neatness“/„leanness“ of code are not the same and very subjective, but I'd argue they're very correlated. \$\endgroup\$ – Lukas Juhrich Nov 25 '19 at 13:04
  • \$\begingroup\$ @Luke Two working (fit) products all things equal the faster product always has the advantage.Good coders write perfomant maintainable code from the get go. Look at the other answer, not only does it not work (it should sort in place) it is 20 times slower. Customers notice these things, they notice fans kicking in, batteries being drained, and time ticking by. Show them the same product 20 times faster and you have a sale, not only that they come back and tell there friends, they certainly don't give a hoot about the source. \$\endgroup\$ – Blindman67 Nov 25 '19 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.