Algorithm for calculating number of fitting boxes

Question

I've a client selling wine bottles. He uses boxes with space for 6 bottles, 12 bottles, 18 bottles and 21 bottles. But he only wants to accept orders which fit exactly into these boxes. There must not be any empty space inside.

E.g.

• 33 is ok: 1x21 and 2x6
• 48 is ok: 2x21 and 1x6 or 4x12
• 26 or 35 or 61 are not ok

For my first try was an straight simple way. I produce an array containing a lot of valid numbers, remove duplicates and order them.

$numbers = [];
$end = (int) $bottles/6 + 1;
for ($i=1; $i<=$end; $i++) {      
  $numbers[] = $i * 6;
  $numbers[] = $i * 21;
  $numbers[] = $i * 21 + 6;
  $numbers[] = $i * 21 + 6 + 6;
  $numbers[] = $i * 21 + 6 + 6 + 6;
}
$numbers = array_unique($numbers);
sort($numbers);

It looks like this:

Array
(
    [0] => 6
    [1] => 12
    [2] => 18
    [3] => 21
    [4] => 24
    [5] => 27
    [6] => 30
    [7] => 33
    [8] => 36
    [9] => 39
    [10] => 42
    [11] => 48
    [12] => 54
    [13] => 60
    [14] => 63
    ....

I can check against my list. ok, fine!

But I want to make a "perfekt" solution fitting for all possible numbers, e.g. I want to know if 123456 is possible. You see, that the array must be very huge for getting this :-)

I tried an equation with 2 unknowns. Why only 2? Because 18 and 12 can be divided by 6. So my approch was:

bottles = 6a + 21b

"a" and "b" must be integer values and may contain zero. "bottles" is an integer value, too. I transformed it to:

 bottles / 6 - 3,5b = a

But this doesn't help me to make a good algorithm... I think I'm on the right way, but how can I solve this quite elegant? Where are the algebra gurus? ;-)

Answer 1

I found @vivek_23's comment challenging so I figured I would give it a try.

This code will optimize the amount to the smallest number of boxes to fill the order.

It does so by first trying with 21 boxes and if the result is not %6 then it will loop backwards to if it gets a sum that is %6 and split up the rest.

// 99 is challenging since 99 can be divided on 21 to 4, but the remainder is not % 6 (15).
// However the remainder 15 + 21 = 36 which is % 6. 
// Meaning the "correct" output should be 3 x 21 + 2 x 18 = 99
$order = 99;
$b = [21 => 0, 18 => 0, 12 => 0, 6 => 0];

// number of 21 boxes possible
if($order >= 21){
    $b[21] = floor($order/21);
    $order -= $b[21]*21;
}

// if the remainder needs to be modified to be divisible on 6
while($order % 6 != 0){
    if($b[21] > 0){
        // remove one box of 21 and add the bottles back to the remainder
        $order += 21;
        $b[21]--;
    }else{
        // if we run out of 21 boxes then the order is not possible.
        echo "order not possible";
        exit;
    }
}
// split up the remainder on 18/12/6 boxes and remove empty boxes 
$b = array_filter(split_up($b, $order));

var_dump($b);

function split_up($b, $order){
    // number of 18 boxes possible
    if($order >= 18){
        $b[18] = floor($order/18);
        $order -= $b[18]*18;
    }
    // number of 12 boxes possible
    if($order >= 12){
        $b[12] = floor($order/12);
        $order -= $b[12]*12;
    }
    // number of 6 boxes possible
    if($order >= 6){
        $b[6] = floor($order/6);
        $order -= $b[6]*6;
    }
    return $b;
}

https://3v4l.org/EM9EF

Answer 2

To expand on maraca's comment, we're trying to solve the equation x = 6a + 21b over nonnegative integers. Since 6 and 21 are divisible by 3 (the greatest common divisor of 6 and 21), it is necessary that x is divisible by 3. Moreover, if x is less than 21, then it is necessary that x is divisible by 6.

Conversely, if x is divisible by 6, we can set a = x/6 and b = 0. If x is an odd multiple of 3, then x - 21 is divisible by 6; if x is at least 21, we can set a = (x - 21)/6 and b = 1. Every multiple of 3 is either odd or even (and hence divisible by 6), so this proves maraca's equivalence claim.

Answer 3

You can reduce this homework to some simpler logic with 3 valid cases:

1. Multiples of 21.
2. Multiples of 6.
3. A combination of the above.

Eg:

function divide_order($q) {
    $result['total'] = $q;
    // find the largest multiple of 21 whose remainder is divisible by 6
    for( $i=intdiv($q,21); $i>=0; $i-- ) {
        if( ($q - $i * 21) % 6 == 0 ) {
            $result += [
                'q_21' => $i,
                'q_6' => ( $q - $i * 21 ) / 6
            ];
            break;
        }
    }
    if( count($result) == 1 ) {
        $result['err'] = true;
    }
    return $result;
}

var_dump(
    array_map('divide_order', [99, 123456])
);

Output:

array(2) {
  [0]=>
  array(3) {
    ["total"]=>
    int(99)
    ["q_21"]=>
    int(3)
    ["q_6"]=>
    int(6)
  }
  [1]=>
  array(3) {
    ["total"]=>
    int(123456)
    ["q_21"]=>
    int(5878)
    ["q_6"]=>
    int(3)
  }
}

Then you can apply some simple logic to reduce multiple boxes of 6 into boxes of 12 or 18.

Answer 4

function winePacking(int $bottles): bool {
    return ($bottles % 6 == 0 || ($bottles % 21) % 3 == 0);
}

https://3v4l.org/bTQHe

Logic Behind the code:

You're working with simple numbers, 6,12,18 can all be covered by mod 6, being that 6 goes into all 3 of those numbers. 21 we can just check a mod 21, and if it's somewhere in between then it's mod 21 mod 6.

Simple as that with those numbers.

Answer 5

What if you do something like so:

function boxes($number) {

    if($number >= 21) {

        $boxesOfTwentyOne = intval($number / 21);
        $remainderOfTwetyOne = floor($number % 21);

        if($remainderOfTwetyOne === 0.0) {

            return $boxesOfTwentyOne . ' box(es) of 21';

        }

        $boxesOfTwentyOne = $boxesOfTwentyOne - 1;

        $number >= 42 ? $textTwentyOne = $boxesOfTwentyOne . ' boxes of 21, ' : $textTwentyOne = '1 box of 21, ';

        $sixesBoxes = floor($number % 21) + 21;

        switch (true) {
            case ($sixesBoxes == 24):
                if($number >= 42) {
                    return $textTwentyOne . '1 box of 18 and 1 box of 6';
                }
                return '1 box of 18 and 1 box of 6';
            break;

            case ($sixesBoxes == 27):
                return $boxesOfTwentyOne + 1 . ' box(es) of 21 and 1 box of 6';
            break;

            case ($sixesBoxes == 30):
                if($number >= 42) {
                    return $textTwentyOne . '1 box of 18 and 1 box of 12';
                }
                return '1 box of 18 and 1 box of 12';
            break;

            case ($sixesBoxes == 33):
                return $boxesOfTwentyOne + 1 . ' box(es) of 21 and 1 box of 12';
            break;

            case ($sixesBoxes == 36):
                if($number >= 42) {
                    return $textTwentyOne . '2 boxes of 18';
                }
                return '2 boxes of 18';
            break;

            case ($sixesBoxes == 39):
                return $boxesOfTwentyOne + 1 . ' box(es) of 21 and 1 box of 18';
            break;

            default:
                return 'Not possible!';
            break;
        }

    } else {

       switch (true) {
            case ($number == 6):
                return '1 box of 6';
            break;
            case ($number == 12):
                return '1 box of 12';
            break;
            case ($number == 18):
                return '1 box of 18';
            break;
            default:
                return 'Not possible!';
            break;
        }

    }

}

EDIT: I have updated my answer, and now I think it is working properly. At least, it passed in all the tests I've made here.

Answer 6

This is actually array items summing up to a target where repetition is allowed problem.

Since in many cases multiple box configurations will come up, you may chose to use the shortest boxes sub list or may be the boxes sublist with the available boxes at hand in real life.

Sorry my PHP is rusty... the below algorithm is in JS but you may simply adapt it to PHP. Of course you may freely change your box sizes to accomodate any number of bottles. So for the given boxes and target 87 we get in total 20 different solutions like

[12,18,18,18,21], [12,12,21,21,21] ... [6,6,6,6,6,6,6,6,6,6,6,21]

function items2T([n,...ns],t){cnt++ //remove cnt in production code
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var cnt = 0, result;
console.time("combos");
result = items2T([6,12,18,21], 87)
console.timeEnd("combos");
console.log(result);
console.log(`${result.length} many unique ways to sum up to 87
and ${cnt} recursive calls are performed`);

The code is taken from a previous answer of mine.