2
\$\begingroup\$

Given a list of elements, each with own width, and a max-width. I need to find how many elements can be fit inside that max-width, keeping the order of the elements.

Some examples:

  1. elements: { width: 10 }, { width: 20 }
    max-width: 30
    result count should be 2, because both elements can be fit in this max-width

  2. elements: { width: 10 }, { width: 20 }
    max-width: 5
    result count should be 0, because first element cannot be fit in this max-width

  3. elements: { width: 10 }, { width: 20 }, { width: 5 }
    max-width: 20
    result count should be 1, because adding the second element exceed the max-width.

This piece of javascript code solve it, but I feel it is not readable enough:

function getNumberOfElementsInWidth(elements, maxWidth) { 
  let accWidth = 0;
  let count = 0;
  for (let i = 0; i<elements.length; i++) {
    if (accWidth + elements[i].width <= maxWidth) {
      accWidth = accWidth + elements[i].width;
      count++;
    } else {
      break;
    }
  }
  return count;
}

function doSample() {
  const elements = [ { width: 10 }, { width: 12 }, { width: 15 } ];
  const maxWidth = 100;
  
  console.log(getNumberOfElementsInWidth(elements, maxWidth));
}

doSample();

I would appreciate your feedback on how to make the code for getNumberOfElementsInWidth function clearer.

\$\endgroup\$
  • \$\begingroup\$ How does elements: { width: 10 }, { width: 20 }, { width: 5 } give you result count 1 for max-width: 20 ? \$\endgroup\$ – Isac Apr 24 '18 at 10:36
  • \$\begingroup\$ @Isac because you can add the first item, but adding the second results in width 30, which is greater than the max-width \$\endgroup\$ – avivr Apr 24 '18 at 20:53
1
\$\begingroup\$

Code / algorithm review.

Code

  • You could have used a for...of loop rather than the standard for loop
  • You could have used return count rather than breaking out. Some will argue otherwise but I see breaks as disguised gotos and should be avoided. (In this case your algorithm is buggy so the point is mute)
  • Use the form n += num to add rather than n = n + num
  • Doubling the accWidth + elements[i].width addition. Once in the if statement and once if it passes. If you are doubling up on calculations it usually means you can simplify.
  • You have not tested the code vigorously to look for problems

Re-write

Using the points above I have written you methods. The test call gives 5 elements, to fit in a 8 units max width. You result returns the wrong count 3 the count should be 4 elements with widths 1,1,1, and 2

function countElementsToFillWidth(elements, maxWidth) {
  var accWidth = 0, count = 0;
  for (const {width} of elements) {
    accWidth += width
    if (accWidth > maxWidth) { return count } // could use break if you like
    count ++;
  }
  return count;
}





//=========================================================================
console.log("Find first # items of to fill a width of 8...")
console.log("Solution " + 
  countElementsToFillWidth(
    [{ width: 1}, {width: 2}, {width: 5}, {width: 1}, {width: 1}],
    8
  ) + " items."
);

Algorithm

UPDATE seams I miss read the question. The order of the elements must be maintained. I will leave in this second half of my answer in case anyone is interested.

This is an example of a packing problem. Find the max items to fit a finite space.

Your algorithm assumes that the items to pack are ordered from smallest to highest and thus fails to find better solutions if there are smaller items further in the list.

To fix you need to sort the elements array. This is expensive so to reduce the overhead you can first get the total size of all the items and if they all fit return the element count avoiding the need to sort.

Then if the items width is to large start at the largest and remove until the you get a length that can fit.

Improved algorithm

The following solution will find a better count. However I have not come up with a proof that it works for all cases and I feel that there may be some cases that it may fail, though can not come up with an example (proof false by contradiction).

There is also some ambiguity. Are items with 0 or negative width valid. I have let 0 width items in, but negative items are out, yet could also be valid as they are used to increase the packing size?

function getNumberOfElementsInWidth(elements, maxWidth) { 
    var totalSize = 0;
    elements = elements.filter(element => {
        if (element.width > maxWidth || element.width < 0) { return false }
        totalSize += element.width;
        return true;
    });
    if (totalSize <= maxWidth) { return elements.length }
    elements.sort((a, b) => a.width - b.width);
    count = elements.length;
    while (totalSize > maxWidth) { totalSize -= elements[--count].width   }
    return count;
}





//=========================================================================
// Single test to show correct solution

console.log("Find max items of widths 1, 2, 5, 1, 1 to fit a width of 8")
console.log("Solution " + 
  getNumberOfElementsInWidth(
    [{ width: 1}, {width: 2}, {width: 5}, {width: 1}, {width: 1}],
    8
  ) + " items"
);

Summing up.

You need to ensure that you test as many possible inputs to a function as possible. Don't cherry pick inputs (as you did with the doSample function) that you know will work. The aim of testing a function is to find out if you can break it.

\$\endgroup\$
  • \$\begingroup\$ +1, vapid points. One thing, elements.width > maxWidth && element.width < 0 - shouldn't this be or? Assuming maxWidth is positive, it would never pass. \$\endgroup\$ – Gerrit0 Apr 24 '18 at 16:39
  • \$\begingroup\$ @Gerrit0 Thanks for the heads up, breaking my own rules by not testing... :( \$\endgroup\$ – Blindman67 Apr 24 '18 at 16:45
  • \$\begingroup\$ @Blindman67 i probably didn't explain myself good enough. The matching should be in order of the elements in the array. not finding the max items that can be fitted. So in your example the answer should be 3, because after adding the first 3 items, I can't add any more without going over max-width. My third example show exactly this case. \$\endgroup\$ – avivr Apr 24 '18 at 20:57
  • \$\begingroup\$ @avivr You can then just ignore the second half of the answer. The First snippet follows your original logic, \$\endgroup\$ – Blindman67 Apr 24 '18 at 21:25
1
\$\begingroup\$

I find your code clear enough, but you could improve it a little bit, so you only do the add operation once:

function getNumberOfElementsInWidth(elements, maxWidth) {
  let accWidth = 0;
  let count = 0;
  for (let i = 0; i < elements.length; i++) {
    accWidth += elements[i].width
    if (accWidth <= maxWidth) {
      count++;
    } else {
      break;
    }
  }
  return count;
}

Further you could reverse the conditional statement:

function getNumberOfElementsInWidth(elements, maxWidth) {
  let accWidth = 0;
  let count = 0;
  for (let i = 0; i < elements.length; i++) {
    accWidth += elements[i].width
    if (accWidth > maxWidth) {
      break;
    }

    count++;
  }
  return count;
}

In a more condensed version you could make the count variable also be the index:

function getNumberOfElementsInWidth(elements, maxWidth) {
  let accWidth = 0;

  for (var count = 0; count < elements.length; count++) {
    if ((accWidth += elements[count].width) > maxWidth) {
      break;
    } 
  }
  return count;
}

Be aware that count must be declared as var count = 0 not let count = 0

\$\endgroup\$
  • 2
    \$\begingroup\$ Instead of adding to accWidth, you could subtract from maxWidth and compare it to 0. Then you don't even need accWidth anymore. \$\endgroup\$ – Kruga Apr 24 '18 at 12:27

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.