Sorting largest amounts to fit total delay

Question

have following array of objects, where amount represent the value of transaction and delay time in ms:

const transactionsDemo =
  [
    { amount: 100, delay: 1000 },
    { amount: 50, delay: 100 },
    { amount: 80, delay: 300 },
    { amount: 200, delay: 800 },
    { amount: 20, delay: 50 },
    { amount: 40, delay: 100 },
  ];

and I want to arrange them into chunks to have largest sum of amounts but to fit under 1000ms. So final arranged array will look like this:

const transactionResult = 
[
  [
    { amount: 200, delay: 800 },
    { amount: 50, delay: 100 },
    { amount: 40, delay: 100 }, 
  ], // amount 290, totalDelay 0
  [
    { amount: 80, delay: 300 },
    { amount: 20, delay: 50 },
  ], // amount 100, totalDelay 350
  [
    { amount: 100, delay: 1000 },
  ], // amount 100, totalDelay 1000
]

Had an idea to calculate amount per MS (by doing amount / delay) and to sort it like this, but its not fully correct since here for example 200 is most valuable amount and this should be in first array, and to add others on top of it. But doing it like this I am getting this in first array:

 [ 
    { amount: 50, delay: 100, valuePerMs: 0.5 },
    { amount: 20, delay: 50, valuePerMs: 0.4 },
    { amount: 40, delay: 100, valuePerMs: 0.4 },
    { amount: 80, delay: 300, valuePerMs: 0.26666666666666666 }
 ] // amount 190, totalDelay 550

any idea how this can be done?

Thanks in advance

Answer 1

@osaro The idea here is the same as Sorting algorithm returning incorrect answer which was wrongly closed yesterday.

I won't give code, but I'll explain it in detail. The idea is to calculate an optimal fringe with dynamic programming. Meaning after each transaction, a list of possible groupings such that for each one, no element with the same or better delay can produce a better amount (in case of ties, pick an arbitrary one).

Each grouping can be represented as [amount, delay, [i, [j, [k, ...[undefined]...]]]] where the first two are how good it is, and the last is a linked list of which elements you chose.

Here is how that works in this case.

We start with

  fringe = [[0, 0, undefined]]

representing we can get to an amount of 0 with 0 delay by picking nothing.

The first transaction is { amount: 100, delay: 1000 }. We get a fringe for picking that transaction of:

secondFringe = [[100, 1000, [0, undefined]]];

Merge them and our fringe works out to be:

fringe = [[0, 0, undefined], [100, 1000, [0, undefined]]]

The second transaction gives us

secondFringe = [[50, 100, [1, undefined]]]

We leave off the sum of the first 2 because they exceeded the limit of 1000 ms. And merged we get:

fringe = [[0, 0, undefined], [50, 100, [1, undefined]], [100, 1000, [0, undefined]]]

The third gets us:

secondFringe = [[80, 300, [2, undefined]], [130, 400, [2, [1, undefined]]]]

And merged we get:

fringe = [[0, 0, undefined], [50, 100, [1, undefined]], [80, 300, [2, undefined]], [130, 400, [2, [1, undefined]]]]

Note that we lost [100, 1000, [0, undefined]] because its amount of 100 is not as good as 130 that we can reach with a shorter delay.

After processing them, the last element of fringe will be:

[290, 1000, [5, [3, [1, undefined]]]]

And now you can find which transactions were used from [5, [3, [1, undefined]]], namely you extract out [5, 3, 1] and then reverse it to get [1, 3, 5].

Now that you know the indexes of your first group, you can split the transactions into your first group and the rest. Do the same procedure with the rest. Stop when either you've got everything in groups, or you make no progress because some element's individual delay is too big. (You can tell that because you get an empty group.)

---

And I added an implementation.

function groupAndRest (transactions, totalDelay) {
    // fringe will be an array of:
    //    {"amount": amount, "delay": delay, "path": [index1, [index2, ...,[undefined]...]]];
    let fringe = [{"amount": 0, "delay": 0, "path": undefined}];
    for (let i = 0; i < transactions.length; i++) {
        let secondFringe = [];
        fringe.forEach((grouping) => {
            if (grouping.delay + transactions[i].delay <= totalDelay) {
                secondFringe.push({
                    "amount": grouping.amount + transactions[i].amount,
                    "delay": grouping.delay + transactions[i].delay,
                    "path": [i, grouping.path]
                });
            }
        });
        let mergedFringe = [];
        while ((0 < fringe.length) && 0 < (secondFringe.length)) {
            let chooseFringe = undefined;
            // Choose the soonest, break ties for largest amount.
            if (fringe[0].delay < secondFringe[0].delay) {
                chooseFringe = true;
            }
            else if (secondFringe[0].delay < fringe[0].delay) {
                chooseFringe = false;
            }
            else if (fringe[0].amount < secondFringe[0].amount) {
                chooseFringe = false;
            }
            else {
                chooseFringe = true;
            }

            if (chooseFringe) {
                // fringe has a better bottom eleemnt.
                while (secondFringe.length && (secondFringe[0].amount <= fringe[0].amount)) {
                    // remove from secondFringe worse solution.
                    secondFringe.shift();
                }
                mergedFringe.push(fringe.shift());
            }
            else {
                // secondFringe has a better bottom eleemnt.
                while (fringe.length && (fringe[0].amount <= secondFringe[0].amount)) {
                    // remove from fringe worse solution.
                    fringe.shift();
                }
                mergedFringe.push(secondFringe.shift());
            }
        }

        // And now used the merged fringe and concat fringe, secondFringe.
        // One of those should be empty
        fringe = mergedFringe.concat(fringe).concat(secondFringe);
    }

    let path = fringe[fringe.length - 1].path;
    let inGroup = {};
    while (path) {
        inGroup[path[0]] = true;
        path = path[1];
    }

    let group = [];
    let rest = [];
    for (let i = 0; i < transactions.length; i++) {
        if (inGroup[i]) {
            group.push(transactions[i]);
        }
        else {
            rest.push(transactions[i]);
        }
    }

    return [group, rest];
}

function groupings (transactions, totalDelay) {
    let answer = [];
    let group;
    let rest;
    [group, rest] = groupAndRest(transactions, totalDelay);
    while (0 < group.length) {
        answer.push(group);
        [group, rest] = packAndRest(rest, totalDelay);
    }
    return answer;
}

const transactionsDemo =
  [
    { amount: 100, delay: 1000 },
    { amount: 50, delay: 100 },
    { amount: 80, delay: 300 },
    { amount: 200, delay: 800 },
    { amount: 20, delay: 50 },
    { amount: 40, delay: 100 },
  ];

console.log(groupings(transactionsDemo, 1000));

Answer 2

@btilly Thanks for the answer. I have a bit different implementation, but not sure if it's optimal. Results are correct tho. What do you think?

function packing(transactions) {
  const initMaxDelay = 1000;
  const initTotalAmount = 0;
  const finalArray = [{
    transactions: [],
    timeLeftMs: initMaxDelay,
    totalAmount: initTotalAmount,
  }];
  // we sort transactions by amount (largest amounts first)
  transactions.sort((a, b) => b.amount - a.amount);
  transactions.forEach(transaction => {
    // we check if there is a bin to place current transaction
    const bin = finalArray.find(t => t.timeLeftMs - transaction.delay >= 0);
    if (bin) {
      bin.transactions.push(transaction);
      bin.timeLeftMs -= transaction.delay;
      bin.totalAmount += transaction.amount;
    } else {
      if (transaction.delay <= initMaxDelay) {
        // if there is no space in current bins, we create new and place current transaction inside
        finalArray.push({
          transactions: [transaction],
          timeLeftMs: initMaxDelay - transaction.delay,
          totalAmount:  transaction.amount,
        });
      } else {
        console.log(`⚠️ transaction ${transaction} has larger delay than max and cannot be processed!`);
      }
    }
  });
  console.log(finalArray)
}