6
\$\begingroup\$

I need to manipulate chunks quantity until total will be as close as possible to the requirements. Decimals are ok in the quantity.

Again: I can change only quantity property.

So if the requirements are {a:500; b:1200; c:1500}, then the quantity field in the chunks array should be changed so that when I run this:

// sum all chunks
Object.keys(chunks).forEach(chunk=> {
  Object.keys(total).forEach(id=> {
    total[id] += chunks[chunk].payload[id] * chunks[chunk].quantity
  });

It returns an object as close as possible to {a:500; b:1200; c:1500}.

How do I do that efficiently?

const chunks = { // <- the chunks
  chunk1: {
    quantity: 0, // <- the quantity
    payload: { a: 19, b: 17, c: 10 } 
  },
  chunk2: {
    quantity: 0, // <- the quantity
    payload: { a: 17, b: 11, c: 15 } 
  },
  chunk3: {
    quantity: 0, // <- the quantity
    payload: { a: 7, b: 19, c: 0 } 
  },
  chunk4: {
    quantity: 0, // <- the quantity
    payload: { a: 14, b: 4, c: 19 } 
  },
  chunk5: {
    quantity: 0, // <- the quantity
    payload: { a: 3, b: 15, c: 6 } 
  },
  chunk6: {
    quantity: 0, // <- the quantity
    payload: { a: 10, b: 16, c: 3 } 
  },
  chunk7: {
    quantity: 0, // <- the quantity
    payload: { a: 2, b: 3, c: 2 } 
  },
  chunk8: {
    quantity: 0, // <- the quantity
    payload: { a: 14, b: 16, c: 11 } 
  },
  chunk9: {
    quantity: 0, // <- the quantity
    payload: { a: 7, b: 2, c: 2 } 
  },
  chunk10: {
    quantity: 0, // <- the quantity
    payload: { a: 1, b: 7, c: 17 }
  }
}

const requirements = { // <- the requirements
  a: 500,
  b: 1200,
  c: 1500
}

const total = {
  a: 0,
  b: 0,
  c: 0
}

// sum all chunks
Object.keys(chunks).forEach(chunkId => {
  Object.keys(total).forEach(propId => {
    total[propId] += chunks[chunkId].payload[propId] * chunks[chunkId].quantity
  })
})

console.log(total) // <- i need this to be as close as possible to the `requirements`.

// MY SOLUTION:
const percentages = JSON.parse(JSON.stringify(chunks))
Object.keys(percentages).forEach(chunkId => {
  let total = 0
  Object.keys(percentages[chunkId].payload).forEach(propId => {
    const perc =
      percentages[chunkId].payload[propId] / (requirements[propId] / 100)
    percentages[chunkId].payload[propId] = perc
    total += perc
  })
  Object.keys(percentages[chunkId].payload).forEach(propId => {
    percentages[chunkId].payload[propId] =
      percentages[chunkId].payload[propId] / (total / 100)
  })
})

const myTotal = {
  a: 0,
  b: 0,
  c: 0
}

Array.from(Array(10)).forEach(() => {
  Object.keys(percentages).forEach(chunkId => {
    let highestPropId
    let highestPropPercentage = 0
    Object.keys(percentages[chunkId].payload).forEach(propId => {
      const perc = percentages[chunkId].payload[propId]
      if (perc > highestPropPercentage) {
        highestPropPercentage = perc
        highestPropId = propId
      }
    })
    const remainingNum = requirements[highestPropId] - myTotal[highestPropId]
    const koe = 0.5
    const multiplier =
      (remainingNum / chunks[chunkId].payload[highestPropId]) * koe
    Object.keys(myTotal).forEach(propId => {
      myTotal[propId] += chunks[chunkId].payload[propId] * multiplier
    })
    chunks[chunkId].quantity += multiplier
  })
})

console.log('myTotal', myTotal)
/*
in the console log output you'll see this:
{
  "a": 499.98450790851257,
  "b": 1202.1742982865637,
  "c": 1499.5877967505367
}
compare it with the `requirements` object above:
const requirements = { // <- the requirements
  a: 500,
  b: 1200,
  c: 1500
}
as you see, it's almost the same. I need more efficient solution
*/

It's not accurate and quite inefficient. Any better options?

Notes, answering the first comment:

  • Second snippet contains first snippet and my solution.
  • The quantity is a property in chunks object. Find it in the very beginning of the first snippet
  • "As close as possible" means as close to requirements as mathematically possible.
  • Input is in the first code snippet. To get output, pls run the first snippet.
\$\endgroup\$
10
  • 3
    \$\begingroup\$ This is not a particularily bad question, but you might want to invest some more time to clarify the problem. Maybe explain how the first code snippet is related to the second one. Define what as close as possible mean. Define what manipulate quantity mean. Maybe show some example intput-output combinations, especialy one that would show an output that one might have not expected and explain why it should return that output rather than a different one. \$\endgroup\$
    – slepic
    Jul 25, 2020 at 8:30
  • 3
    \$\begingroup\$ Sorry, but that did not help at all. You're gonna have to invest a bit more then 2 minutes and describe the problém as if to someone who knows nothing about it. And btw if the first snippet Is part of the second, then remove the first one, Its just confusing. \$\endgroup\$
    – slepic
    Jul 25, 2020 at 12:33
  • 1
    \$\begingroup\$ I read the question twice and still have no idea what the "requirements" are, as in how they relate to the requirements object. Can't you share a way smaller example with just one requirement? \$\endgroup\$
    – GirkovArpa
    Jul 26, 2020 at 0:14
  • 2
    \$\begingroup\$ I am trying very hard to understand what this question is asking us but it is still unclear what @stkvtflw goal is with this code \$\endgroup\$
    – Peter
    Jul 27, 2020 at 16:32
  • 1
    \$\begingroup\$ When running the code as is, I get negative values for the quantity of chunk 4, 6, 7, 8 and 9. It seems rather counterintuitive to me having negative quantities - which would mean, that I have to remove something from a total, that isn't really there to begin with. Or maybe the term quantity isn't the right/original name for the value? \$\endgroup\$
    – user73941
    Jul 28, 2020 at 5:12

2 Answers 2

5
+50
\$\begingroup\$

From a short review;

  • Your code is really hard to read/parse, I would not want to maintain this

  • You have no useful comments, // <- the quantity is not useful

  • You should terminate your lines with ;,

  • I don't know if you have control over how you get the data, but getting it as an object is not helpful, this would be much easier/readable if you got a list instead

  • In fact, this code is full of functional programming on objects, if you really want to do this, you should convert your objects to lists first

  • Array(10) <- You hardcoded 10, at least go for Object.keys(chunks).length

  • koe is an unfortunate variable name, why is it 0.5? (See lack of comments)

  • In a solution driven approach, you should probably never enumerate over the keys of the payload (Object.keys(percentages[chunkId].payload).forEach), the payload could have more fields than the solution

  • This should be 1 line

    const perc =
      percentages[chunkId].payload[propId] / (requirements[propId] / 100)
    
  • I see this as a Knapsack problem, which is NP-hard, meaning that getting the perfect result will always be slow, in fact I see this as a multi-dimensional knapsack problem which is even harder than the regular knapsack problem.

From the comments, if we think of (a,b,c) as (length, width, height) and requirements as a bag of size (500, 1200, 1500). Then the question is how can we best (best as, least space wasted) fill the bag with different chunks (they all have their size defined in payload).

\$\endgroup\$
6
  • \$\begingroup\$ You describe it as a knapsack problem, implying you may have greater insight into what the poster is asking? Could you elaborate? \$\endgroup\$
    – GirkovArpa
    Jul 28, 2020 at 17:10
  • 1
    \$\begingroup\$ "You should terminate your lines with ;" I know why but others, especially the OP, likely don't - it would be good to provide an explanation, possibly with references \$\endgroup\$ Jul 28, 2020 at 23:57
  • 2
    \$\begingroup\$ @GirkovArpa added more, let me know if not sufficient. Sᴀᴍ Onᴇᴌᴀ; fair point, updated my comment with a link \$\endgroup\$
    – konijn
    Jul 29, 2020 at 10:16
  • \$\begingroup\$ Ah! I see what the OP is asking now. If there were only a couple chunks, and solution.a == 100, and chunk1.payload.a == 5 and chunk2.payload.a == 15, OP wants to know what to multiply 5 and 15 by so that when you sum them, they add up to 100. He calls this number quantity. So chunk1.quantity would be 50 if chunk2.quantity is 1/3. Because (5 * 10) + (15 * (1/3)) == 100. \$\endgroup\$
    – GirkovArpa
    Jul 29, 2020 at 16:59
  • \$\begingroup\$ But the same quantity has to work for chunk1.payload.a, chunk1.payload.b, and chunk1.payload.c. \$\endgroup\$
    – GirkovArpa
    Jul 29, 2020 at 17:02
2
\$\begingroup\$

You can replace this entire block of code with const percentages = chunks; and your results more precisely match the requirements:

// MY SOLUTION:
const percentages = JSON.parse(JSON.stringify(chunks))
Object.keys(percentages).forEach(chunkId => {
  let total = 0
  Object.keys(percentages[chunkId].payload).forEach(propId => {
    const perc =
      percentages[chunkId].payload[propId] / (requirements[propId] / 100)
    percentages[chunkId].payload[propId] = perc
    total += perc
  })
  Object.keys(percentages[chunkId].payload).forEach(propId => {
    percentages[chunkId].payload[propId] =
      percentages[chunkId].payload[propId] / (total / 100)
  })
})
myTotal { a: 500.3204153326983, b: 1200.0002333151795, c: 1499.7678177477337 }

Previously your result was:

myTotal { a: 499.98450790851257, b: 1202.1742982865637, c: 1499.5877967505367 }

For the record, I still have no idea what you're trying to do.

manipulate chunks quantity until total will be as close as possible to the requirements

Then why not just add the difference so they are equal?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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