Php - Distribute a number into a range of factors (like a greedy algorithm)

JamesB
April 12, 2024
282 views
0 votes
2 Answers

I need to find the cost to ship a box, based on an array of weight rules, similar to this:

$rules = [
    '1'     => '1.2',
    '5-10'  => '6.25',
    '10-15' => '9.2',
    '15-20' => '10.9',
];

So a box that weighs 47 lbs, according to this array, would cost 10.90 + 10.90 + 6.25 = 28.05 USD to ship.

This is because 47 would consume two times the range (15-20] and one time the range (5-10]. ( denotes a > equation symbol, while ] denotes a <= equation symbol.

At first, for simplicity, I created an intermediate array (of the upper limits of each ranges rule) like this (1 doesn’t have an upper/lower limit, but that’s easy to exclude):

$tiers = [
    20,
    15,
    10,
    1,
];

And then I tried to distribute the initial weight to that array in a way similar to a factorization process. So at first I totally ignored the lower limits, and took a weight, ie. 37.75 lbs. Then, using the following code, I produced the "factorization" array of each weight tier:

print_r( distribute( 37.75 );

function distribute( $weight = 0 ) {
    $tiers = [1, 10, 15, 20];

    rsort( $tiers );

    foreach ( $tiers as $tier ) {
        $counters[$tier] = 0;
    }

    foreach ( $tiers as $tier ) {
        $quotient  = $weight / $tier;
        $floored   = floor( $quotient );
        $remaining = $weight - $floored * $tier;

        if ( $quotient >= 1 && $remaining > 1 ) {
            $counters[$tier] = $floored;
            $weight          = $remaining;
        } else if ( $tier == 1 ) {
            $counters[$tier] = ( $floored + 1 );
            $weight          = $weight - ( $floored + 1 ) * $tier;
        }
    }

    return $counters;
}

Which conveniently produced an output like this:

    Array (
        [20] => 1
        [15] => 1
        [10] => 0
        [1] => 3
    )

Then, I tried the same code with weight 38, and realized my first mistake… There is some problem with an edge case that I can’t figure out yet, that for 38 still adds a +1 to the 1-tier rule.

Then, I tried 47.75 lbs, and found the second mistake… As I said, for simplicity, I used the upper limits, which messes with the "factorization" of a weight. So, for 47.75 lbs, the above code produced an output like this:

    Array (
        [20] => 2
        [15] => 0
        [10] => 0
        [1] => 8
    )

which is totally wrong, as 1-tier can’t be consumed 8 times, since 8 (or 7.99 to be exact) falls under the (5-10] range.

All in all, unfortunately, my approach is flawed in many ways. Can someone help me please figure out the correct code to deal with this problem?

Tags: php

Answers

You can use this code to calculate those things:

     function calculate_shipping_cost($weight, $rules) {
    $cost = 0.0;

   
    uksort($rules, function($a, $b) {
        $a_val = strpos($a, '-') !== false ? intval(explode('-', $a)[1]) : intval($a);
        $b_val = strpos($b, '-') !== false ? intval(explode('-', $b)[1]) : intval($b);
        return $b_val <=> $a_val;
    });

    foreach ($rules as $range => $price) {
        $bounds = explode('-', $range);
       
        $upperLimit = isset($bounds[1]) ? intval($bounds[1]) : intval($bounds[0]);
        $lowerLimit = isset($bounds[0]) ? intval($bounds[0]) : 0;

        
        if ($weight > $upperLimit) {
            $applicableWeight = $upperLimit - $lowerLimit + ($range == '1' ? 0 : 1);
        } else if ($weight > $lowerLimit) {
            $applicableWeight = $weight - $lowerLimit;
            $cost += $applicableWeight * floatval($price);
            break; // Break the loop since we've found the tier for the remaining weight
        } else {
            $applicableWeight = 0;
        }

        
        $cost += $applicableWeight * floatval($price);
       
        $weight -= $applicableWeight;
    }

    return $cost;
}

$rules = [
    '1'     => '1.2',
    '5-10'  => '6.25',
    '10-15' => '9.2',
    '15-20' => '10.9',
];

$weight = 47;
$shipping_cost = calculate_shipping_cost($weight, $rules);
echo "The shipping cost for a box weighing $weight lbs is: $shipping_cost USD";

Your ranged expressions need to be parsed into individual values to be used in the algorithm.

Then loop over the tiers, find the highest qualifying tier, record the number of usages and reduce the weight after each tier is used.

My solution will return an array with all details — the total cost and the number of times each qualifying tier is used.

Code: (Demo)

$rules = [
    '1'     => '1.2',
    '5-10'  => '6.25',
    '10-15' => '9.2',
    '15-20' => '10.9',
];

function costFromWeight($weight, array $newRules): array {
    $result = ['cost' => 0];
    foreach ($newRules as $range => $cost) {
        if (sscanf($range, '%d-%d', $min, $consume) === 1) {
            $consume = $min;
        }
        while ($min <= $weight) {
            $result[$consume] = ($result[$consume] ?? 0) + 1;
            $result['cost'] += $cost;
            $weight -= $consume;
            if ($weight <= 0) {
                break 2;
            }
        }
    }
    return $result;
}

krsort($rules, SORT_NUMERIC);

foreach ([49, 47.75, 38, 23, 14, 4] as $weight) {
    echo "$weight :: ";
    print_r(costFromWeight($weight, $rules));
    echo "n---n";
}

Output:

49 :: Array
(
    [cost] => 28.05
    [20] => 2
    [10] => 1
)

---
47.75 :: Array
(
    [cost] => 28.05
    [20] => 2
    [10] => 1
)

---
38 :: Array
(
    [cost] => 21.8
    [20] => 2
)

---
23 :: Array
(
    [cost] => 14.5
    [20] => 1
    [1] => 3
)

---
14 :: Array
(
    [cost] => 9.2
    [15] => 1
)

---
4 :: Array
(
    [cost] => 4.8
    [1] => 4
)

Please signup or login to give your own answer.

Click here to cancel reply.

Php – Distribute a number into a range of factors (like a greedy algorithm)

Answers