const task = [
    { x: 1, y: 20 },
    { x: 2, y: 30 },
    { x: 1, y: 50 },
    { x: 2, y: 20 },
    { x: 1, y: 10 },
    { x: 9, y: 40 },
    { x: 1, y: 30 },
    { x: 3, y: 5 }
];

there are two conditions:

• grouping limit can be max z
• sums of y can be max t

For example z=2 and t=60(I am passing these values as parameters to a function), the result should be:

let result = [
    [{ x: 1, y: 20 },{ x: 2, y: 30 }],
    [{ x: 1, y: 50 }],
    [{ x: 2, y: 20 },{ x: 1, y: 10 }],
    [{ x: 9, y: 40 }],
    [{ x: 1, y: 30 },{ x: 3, y: 5 }]
];

I have managed to implement with for loop but i am curious about possible functional solutions. Any help would be appriciated.

const task = [
    { x: 1, y: 20 },
    { x: 2, y: 30 },
    { x: 1, y: 50 },
    { x: 2, y: 20 },
    { x: 1, y: 10 },
    { x: 9, y: 40 },
    { x: 1, y: 30 },
    { x: 3, y: 5 }
];

there are two conditions:

• grouping limit can be max z
• sums of y can be max t

For example z=2 and t=60(I am passing these values as parameters to a function), the result should be:

let result = [
    [{ x: 1, y: 20 },{ x: 2, y: 30 }],
    [{ x: 1, y: 50 }],
    [{ x: 2, y: 20 },{ x: 1, y: 10 }],
    [{ x: 9, y: 40 }],
    [{ x: 1, y: 30 },{ x: 3, y: 5 }]
];

I have managed to implement with for loop but i am curious about possible functional solutions. Any help would be appriciated.

• javascript
• arrays

• You want the items to stay in the original order? – trincot Commented Feb 1, 2018 at 21:48
• @trincot, yes, the order is important. – serkan Commented Feb 1, 2018 at 21:49
• What do you mean by functional ? Paradigms are not very well defined... – Jonas Wilms Commented Feb 1, 2018 at 21:58
• @NenadVracar, It was typo, updated, Thanks – serkan Commented Feb 1, 2018 at 22:29
• 1 Then why are those two objects in last array with y sum of 70? – Nenad Vracar Commented Feb 1, 2018 at 22:31

7 Answers 7

A slightly more functional approach would include some very simple pure helpers. Let's start with a function ySum that returns the sum of all y properties within given argument group:

const ySum = (group) => group.reduce((sum, { y: currY }) => sum + currY, 0);

Next, let's define a function that takes a task and a group and tells us whether the given task would fit in the also given group:

Update from ments This function always returns true for empty groups to prevent the empty array problem when y > 60 for a certain task

const taskFitsInGroup = (task, group) => {

    if (group.length === 0) {
        return true;
    }

    return (group.length < 2) && (ySum(group) + task.y <= 60);
};

Note: you can of course extract the constants 2 and 60 to variables / arguments.

Array.prototype.reduce is a perfect candidate for the data transformation you require. The following line should do what you require, after addTask is implemented:

const result = tasks.reduce(addTask, [[]]);

Only thing left to do is create the addTask function that we give to reduce above. Using the helper functions we already created, this is actually pretty straightforward:

const addTask = (accumulation, task) => {

    const lastGroup = accumulation[accumulation.length - 1];

    if (taskFitsInGroup(task, lastGroup)) {
        lastGroup.push(task);
    } else {
        accumulation.push([task]);
    }

    return accumulation;
};

Working Example:

const tasks = [
    { x: 1, y: 80 },
    { x: 2, y: 30 },
    { x: 1, y: 50 },
    { x: 2, y: 20 },
    { x: 1, y: 10 },
    { x: 9, y: 40 },
    { x: 1, y: 30 },
    { x: 3, y: 5 },
];

const ySum = (group) => group.reduce((sum, { y: currY }) => sum + currY, 0);


const taskFitsInGroup = (task, group) => {

    if (group.length === 0) {
        return true;
    }

    return (group.length < 2) && (ySum(group) + task.y <= 60);
};


const addTask = (accumulation, task) => {

    const lastGroup = accumulation[accumulation.length - 1];

    if (taskFitsInGroup(task, lastGroup)) {
        lastGroup.push(task);
    } else {
        accumulation.push([task]);
    }

    return accumulation;
};

const result = tasks.reduce(addTask, [[]]);
console.log(result);

Here is another functional ES6 solution:

function chunk(task, z, t) {
    return task.reduce( ({sum, arr, i}, {y}, j) => 
        (j > i && sum + y > t) || j - i >= z
            ? {sum: y, arr: [...arr, arr[arr.length-1].splice(j-i)], i: j}
            : {sum: sum + y, arr, i}
    , {sum: 0, arr: [task.slice()], i: 0}).arr;
}

const task = [{x:1,y:20}, {x:2,y:30}, {x:1,y:50}, {x:2,y:20},{x:1,y:10},{x:9,y:40},{x:1,y:30},{x:3,y:40}];

const result = chunk(task, 2, 60);

console.log(JSON.stringify(result));

NB: Note the extra j > i condition which makes sure that every sub array in the result will have at least one element, even if the y is greater than the limit. Otherwise you could have an endless loop -- never being able to place that element with a too great y-value.

Explanation

The function starts with creating the start value of the reduce callback:

{sum: 0, arr: [task.slice()], i: 0}

The arr property represents the result so far, which is the original array with all its elements bined together. The slice is necessary to make sure we have a copy of the array and don't mutate the original one.

The sum property will keep track of the sum in the last chunk up until the current index of the reduce loop.

The i property tells at which the index in the original array we made the last split into a new chunk.

The reduce callback has these parameters:

• {sum, arr, i}: this is the destructured representation of the object described above. The reduce callback will always return an object with these three properties, so they will serve again in the next iteration as arguments of the callback.
• {y}: again destructuring to extract the y value of the current element in the task array.
• j: the current index in the task array

Then the short expression syntax is used for the arrow function (=>): there is no statement block following it, just an expression, which is the return value of the callback.

This expression uses the ternary operator which decides whether the current element can stay in the current chunck, in which case only the sum needs to be updated, while the arr and i properties can remain the same. The short ES6 object notation is used to express that the arr property will get the arr value. Same for i:

: {sum: sum + y, arr, i}

The other case is when a new chunk must be split of:

? {sum: y, arr: [...arr, arr[arr.length-1].splice(j-i)], i: j}

Here the splice method is used to remove all elements from the current last chunk after the i-j first elements there. The deleted elements are put back in a new array, as the last, new element of it. The rest is reproduced with ...arr. I have to admit that this is not purely functional, since the last subarray of arr is being mutated with splice. But writing the same with slice would require more code.

The condition to decide which of the two actions to take, reflect the conditions you specified: y > t and j - i >= z. I already explained why I added j > i to the first condition.

You could use a helper array for the actual group and sum the property y together with the y property of the actual object

group.reduce((s, { y }) => s + y, o.y)
^^^^^                                  array
              ^                        accumulator for sum
                 ^^^^^                 destructuring to get y property
                           ^^^^^       build sum and return value
                                  ^^^  start accumulator with actual y prop

for checking against the given value.

function group(array, z, t) {
    var result = [];
    array.reduce(function (group, o, i) {
        var sum = group.reduce((s, { y }) => s + y, o.y);
        if (i && sum <= t && group.length < z) {
            group.push(o);
        } else {
            result.push(group = [o]);
        }
        return group;
    }, []);
    return result;
}

var task = [{ x: 1, y: 20 }, { x: 2, y: 30 }, { x: 1, y: 50 }, { x: 2, y: 20 }, { x: 1, y: 10 }, { x: 9, y: 40 }, { x: 1, y: 30 }, { x: 3, y: 5 }],
    result = group(task, 2, 60);
    
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Here's one potential solution using .reduce:

var task = [{x:1,y:20}, {x:2,y:30}, {x:1,y:50}, {x:2,y:20},{x:1,y:10},{x:9,y:40},{x:1,y:30},{x:3,y:40}];

// grouping limit can be max z
// sums of y can be max t

// the result should be:
// [[{x:1,y:20}, {x:2,y:30}],[{x:1,y:50}], [{x:2,y:20},{x:1,y:10}],[{x:9,y:40}],[{x:1,y:30},{x:3,y:5}]];

function sumY(arr) {
    return arr.reduce((sum, item) => sum + item.y, 0);
}

function group(maxSize, maxSum, arr) {
    return arr.reduce((groups, item) => {
        const last = groups[groups.length - 1];
        (!last || last.length >= maxSize || sumY(last) + item.y > maxSum)
            ? groups.push([item])
            : last.push(item); 
        return groups;
    }, []);
}

console.log(group(2, 60, task));

const group = (arr, z, t, result = [[]], count = 0, y = 0) => 
  (arr.reduce((acc, curr) => (
    count++, y += curr.y,
    count > z || y >= t 
      ? (count = 0, y = curr.y, result[result.push([curr]) - 1])
      :  (acc.push(curr), acc)
  ), result[0]), result);

Thats a purely functional approach. Call it with group(task, 2, 60). However i would still prefer the good old for loop:

 const result = [];
 let group = [], z = 2, t = 60, count = 0, y = 0;

for(const task of tasks){
  if(count++ >= z || (y += task.y) >= t){
    count = 0;
    y = task.y;
    result.push(group);
    group = [];
  }
  group.push(task);
}
if(group.length) result.push(group);

You could use reduce() method and use one variable for current array number and one for current y sum value.

const task = [{x:1,y:20}, {x:2,y:30}, {x:1,y:50}, {x:2,y:20},{x:1,y:10},{x:9,y:40},{x:1,y:30},{x:3,y:40}];

const group = (data, z, t) => {
  let n = 0, tTemp = 0;
  return data.reduce(function(r, e) {
    if ((r[n] && r[n].length >= z) || (tTemp + e.y) > t) n += 1, tTemp = e.y;
    else tTemp += e.y;
    r[n] = (r[n] || []).concat(e)
    return r;
  }, [])
}

const result = group(task, 2, 60)
console.log(result)

const task = [{x:1,y:20}, {x:2,y:30}, {x:1,y:50}, {x:2,y:20},{x:1,y:10},{x:9,y:40},{x:1,y:30},{x:3,y:40}],
z = 2, t = 60;

const group = task =>
  task.reduce((a, e) => (
    !!a.length && a[a.length - 1].length < z &&
    a[a.length - 1].reduce((s, {y}) => s + y, e.y) <= t ?
    a[a.length - 1].push(e) : a.push([e])
  ) && a, [])

console.log(JSON.stringify(group(task)))