5
\$\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\$
  • 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 '20 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 '20 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 '20 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 '20 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 '20 at 5:12
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\$
  • \$\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 '20 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\$ – Sᴀᴍ Onᴇᴌᴀ Jul 28 '20 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 '20 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 '20 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 '20 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, privacy policy and cookie policy

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