dev.to staff

Posted on Jan 6, 2020

Daily Challenge #154 - Stable Arrangement

#challenge

Setup

Write a function that will take an array of unique positive integers, and two additional integers as input. With this method, try to rearrange the array so that the sum of any n consecutive values does not exceed q.

Test constraints:

2 <= n <= 6
4 <= arr length < 12
n < arr length
Every value in arr will be less than q

Example

const arr = [3,5,7,1,6,8,2,4];
const n = 3; // span length
const q = 13; // weight threshold
solver(arr,n,q); // one possible solution: [4,7,1,5,6,2,3,8]

Tests

[[3,5,7,1,6,8,2,4], 3, 13]

[[7,12,6,10,3,8,5,4,13,2,9], 4, 28]

[[9,16,11,6,15,14,19,3,12,18,7], 3, 35]

Good luck!

This challenge comes from docgunthrop on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (5)

fitsum • Jan 6 '20

const f = (ar, n, q) => {
  if (n >= ar.length)
    return `${n} is more than ${ar.length}`;

 const sorted = ar.sort((a, b) => a - b);
  do {
    sorted.pop()
  }
  while (sorted.reduce((acc, each) => acc + each) > q);
  return sorted;
}

//eg
const result = f([10, 4, 13, 11, 2], 4, 20);

Idan Arye • Jan 6 '20

You are pop()ing items from the array without push()ing them back. Shouldn't the result contain all the elements of the original array?

fitsum • Jan 6 '20

ah. good point

Cent • Jan 8 '20

JS, had to google how to use a reducer for this one since it was simpler than my original idea to add all of the values

CodePen


const solver = (arr, n, q) => {
  // console.log("Welcome to the stable arrangment, your quota is:", q)
  for(let i = 0; i < arr.length - n + 1; i++) {
    let j = 0;
    do {
      const set = arr.slice(i, i+n).reduce((acc, val) => acc + val);
      if(set > q) {
        let value = arr.shift();
        arr.push(value);
      } else {
        // console.log(arr.slice(i, i+n),set);
        break;
      }
    } while(true);
  }
  return arr;
}

Nick Holmes • Jan 8 '20

Your "shift then push" approach changes the positions of the values in the array, but not their order. Conceptually, (shift then push) * length gets you back were you started.

As the task asks you to "rearrange" the values, which I take to mean "change the order" of the values, and you are not changing the order, it would seem that this approach cannot work in the general case.

For example, in the case of

solver([3,5,7,1,6,8,2,4], 3, 13);

the return value is

[7,1,6,8,2,4,3,5]

This is clearly the input rotated 2 to the left, and the first slice [7, 1, 6] sums to 14 (when it should be <= 13).

(In the worst case, where no slice of the input sums <= q, your function will run forever).

DEV Community

Daily Challenge #154 - Stable Arrangement

Setup

Example

Tests

Top comments (5)

Read next

How to Estimate SaaS Product Development Costs

Mesmerizing Fireworks Animation - Color the Night

Check Table size in Postgresql Database

Barman vs pgbackrest