Check a collection of prices against an associated collection of minimum prices

I would like to find a more efficient way to solve this problem. My current implementation has 3 separate loops through the data.

I'm creating an algorithm to check a collection of prices against an associated collection of minimum prices. Any price that is below the minimum must be adjusted up to meet the minimum. The sum of all upward adjustments must then be taken from the other prices in the collection that are above the minimum.

Consider the following data:

Line Price Minimum
----------------------------------
1 16 22
2 12 20
3 120 90
4 25 20


Lines 1 and 2 require an additional 14 points to meet the minimum values. I would need to take 14 from lines 3 and 4 which are greater than the minimum. Additionally I want to take the amount from 3 and 4 based on their proportions to the sum of their prices (i.e. 145).

Line % Amount
-----------------------------------------------------
3 120/145 = .8275% 14 * .8275 = 11.585
4 25/145 = .1725% 14 * .1725 = 2.415
--------- ------------
Total 1.00% 14.000


Finally I must ensure that when I reduce an above-minimum price I do not cause them to fall below their respective minimums. I have a working version of this adjustment & allocation algorithm but it's UGLY and I would really like to find a more elegant way to solve the problem.

I need a more efficient solution that reduces the number of loops through the item collection. Note: that I have used the c# and javascript tags because this algorithm will need to be implemented in both languages.

Here is the working example of my C# console test program. This is a single file, ready to go code sample.

C# Solution

Following this C# sample is a JavaScript example:

`using System;

class Program
{
[STAThread]
static void Main()
{
// Setup testing data
var linePriceInfos = new LinePriceInfo[]
{
new L

Interesting question,

I am just going to talk about the JavaScript, I know nothing about C#. Though I will point out that your JavaScript code probably has comment envy ;)

Naming

In essence you seem to raise prices to a minimum, which increases the sum of prices. Then you need to reduce the other prices proportionally so that the sum total remains the same. Your variable names with profit make sense to me, the ones refering to payment, loan.

• I would suggest to call the sum total of rate increases to match minimum price

missing

• Similarly, I would call the sum total of surplus rates ( delta between price and minimum price) surplus

Abstraction

I think you abstracted at the wrong level, it was extremely hard to follow the math because you replaced it with on-liner functions. My general rule of thumb is to avoid one-liners that you only use once. I would have created the abstraction on the collection level, something like

var model = new PricingModel(data);
model.allocate();

And keep all the logic inside allocate

Proportions

I had to bring this up, because my counter suggestion proportions differently.

If you have have to split missing over these 2 lines:

Price       Minimum
1000        990
100         10

Then your code would try to reduce 1000 far more because the price is so much higher. I would suggest that you split over the margin since the price with the highest margin can take it better. Hope that makes sense..

Counter Code

function LinePriceInfo(price, min)
{
    this.price = price;
    this.min = min;
}

var linePriceInfos =
[
    new LinePriceInfo(16,  22),
    new LinePriceInfo(12,  20),
    new LinePriceInfo(120, 90),
    new LinePriceInfo(25,  20)
];

Allocate(linePriceInfos);

function Allocate(infos)
{
    var missing = 0,  //Sum total of rate increases to match minimum price
        surplus = 0,  //Sum total of surplus rates ( delta between price and minmum price)
        info, i;

    //Analyze each line 
    for(i = 0; i < infos.length; i++)
    {
        info = infos[i];
        //Is the price too low, then fix the price and updating `missing`
        if(info.price <= info.min)
        {
            missing += (this.min - this.price);
            info.price = info.min;
        } 
        //Maintain surplus, adding 0 in case the price was too low is a non-operation
        info.bonus = info.price - info.min;
        surplus += info.bonus;
    }  

    //The missing rates have to be distributed, check whether this is possible
    var newSurplus = surplus - missing;
    if( newSurplus < 0 ){
      throw 'can\'t solve!';      
    }

    //Analyze each line and add back the newly derived surplus 
    for(i = 0; i < infos.length; i++)
    {
        info = infos[i];
        if( info.bonus ){
          info.price = info.min + info.bonus / surplus * newSurplus;
        }
    }         
}

StackExchange Code Review Q#60956, answer score: 2