Adventure of the Cardboard boxes problem

I was looking through Prof. Ian Stewart's book "Professor Stewart's Casebook of Mathematical Mysteries" with an idea in my mind to solve the problems posed with computational brute force rather than smart thinking. For some reason the idea of brute force calculations for mathematical puzzles attract me.

On page 23 of the book he mentions the question of the cardboard boxes and in the answers section he expands more on what can be done with the question. The original question is simply asking to find 2 rectangular prism shaped boxes that have the equal volume and equal sum of the edges. As an example the box pair with sides (1, 6, 6) and (2, 2, 9) would be a solution as the volumes are 36 on both and the sum of the edges are 13 on each. It is actually the smallest 2 pair box solution to the problem as there are many more pairs with longer edges still satisfying the criteria.

The problem gets more interesting when he asks how about finding a set of 3 boxes with equal volume and sum of edges. What about a set of 5 or 6 boxes? He also mentions in the answers section that Moloy De from Kolkata India was able to find the smallest solution up to set of 6 boxes.

Here are the answers up to 6. In the following list first number is the sum of the edges, second is the volume and the third is a triplet of the edge measurements.

  • 2 Box set
    • 13 36 2-2-9
    • 13 36 1-6-6
  • 3 box set
    • 39 1200 5-10-24
    • 39 1200 4-15-20
    • 39 1200 6-8-25
  • 4 box set
    • 118 37800 15-40-63
    • 118 37800 18-30-70
    • 118 37800 21-25-72
    • 118 37800 14-50-54
  • 5 box set
    • 185 83160 12-63-110
    • 185 83160 15-44-126
    • 185 83160 18-35-132
    • 185 83160 22-28-135
    • 185 83160 11-84-90
  • 6 box set
    • 400 846720 42-70-288
    • 400 846720 36-84-280
    • 400 846720 32-98-270
    • 400 846720 28-120-252
    • 400 846720 27-128-245
    • 400 846720 24-180-196

When I tried to solve this with code, I quickly realized that, this simple problem actually pushes the limits of a 16Gb laptop when you try to calculate anything more than a set of 10 boxes with a brute force search.

Here are the smallest set of boxes for 7, 8, 9, and 10.

  • 7 box set
    • 511 1965600 72-75-364
    • 511 1965600 60-91-360
    • 511 1965600 45-130-336
    • 511 1965600 42-144-325
    • 511 1965600 40-156-315
    • 511 1965600 36-195-280
    • 511 1965600 35-216-260
  • 8 box set
    • 1022 15724800 72-390-560
    • 1022 15724800 80-312-630
    • 1022 15724800 84-288-650
    • 1022 15724800 90-260-672
    • 1022 15724800 91-256-675
    • 1022 15724800 120-182-720
    • 1022 15724800 144-150-728
    • 1022 15724800 70-432-520
  • 9 box set
    • 1287 34927200 100-539-648
    • 1287 34927200 105-462-720
    • 1287 34927200 112-405-770
    • 1287 34927200 126-336-825
    • 1287 34927200 132-315-840
    • 1287 34927200 162-245-880
    • 1287 34927200 165-240-882
    • 1287 34927200 196-200-891
    • 1287 34927200 99-588-600
  • 10 box set
    • 2574 279417600 200-1078-1296
    • 2574 279417600 210-924-1440
    • 2574 279417600 224-810-1540
    • 2574 279417600 231-768-1575
    • 2574 279417600 252-672-1650
    • 2574 279417600 264-630-1680
    • 2574 279417600 324-490-1760
    • 2574 279417600 330-480-1764
    • 2574 279417600 392-400-1782
    • 2574 279417600 198-1176-1200

The problem is worthwhile thinking about it as it seems simple enough to try but challenging to proceed further. There might even be a cryptographic benefit out of finding very large set of boxes with same property.

Below is the small cpp code I used to find the results up to a set of 10 boxes. It simply tries different edge sizes and reports when it finds matching set of boxes. I ran it up to edge lengths between 1 and 2400. There is no 11 box set satisfying the criteria up to 2400 edge length.

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;  
using vol_t = unsigned long long;  
using dim_t = uint16_t;


struct box_t{  
    dim_t x, y, z;

    box_t(dim_t x, dim_t y, dim_t z):x(x), y(y), z(z){}
    vol_t len() const {return x + y + static_cast<vol_t>(z);}
    vol_t vol() const {return x * y * static_cast<vol_t>(z);}
};


int operator<(const box_t& lhs, const box_t& rhs){  
    if (lhs.len() == rhs.len()) {
        if (lhs.vol() == rhs.vol()){
            if (lhs.x == rhs.x ){
                if(lhs.y == rhs.y){
                    return lhs.z < rhs.z;
                }else
                    return rhs.y < lhs.y;
            }else
                return lhs.x < rhs.x;
        } else
            return lhs.vol() < rhs.vol();
    } else
        return  lhs.len() < rhs.len();
}


void appendTo(stringstream& ss, const box_t& b){  
    ss << "LEN  " << b.len();
    ss << " " << b.vol();
    ss << " ";
    ss << b.x << "-" << b.y << "-" << b.z;
    ss << endl;
}

void findSmallestBoxSetThatHasEqualVolumesAndEdgeLengths  
        (const dim_t startFrom=1, const dim_t searchUpTo=100, int lookForAtLeast=1 ) noexcept{

    const dim_t minLen {startFrom};
    const dim_t maxLen {searchUpTo};
    int maxCount {lookForAtLeast};

    cout << "Starting with: " << minLen << " to "<<maxLen << " searching for smallest set of equal boxes greater than "<< maxCount << " in a set" << endl ;

    vector< box_t> boxes;
    dim_t sizeRange = maxLen-minLen;
    size_t sum {1};
    for (dim_t i=0; i<sizeRange/2; i++)
        sum += (sizeRange-2*i)*(sizeRange-2*i);
    cout << "Expected vector size: " << sum << ". Trying to allocate: " << sum*sizeof(box_t)/(1024*1024ull) << " Mb " << endl;
    boxes.reserve(sum);
    for(dim_t x=minLen; x < maxLen; ++x){
        for(dim_t y=x; y < maxLen; ++y){
            for(dim_t z=y; z < maxLen; ++z) {
                // this way of looping and construction
                // makes x, the smallest followed by y
                // and does not allow repetition of the box-dimensions
                // it is critical for rest of the code to work
                boxes.push_back(move(box_t(x, y, z)));
            }
        }
    }
    cout << "Size of of boxes tried: " << boxes.size() << " : " << sizeof(box_t)*boxes.size()/(1024*1024ull)<< " Mb" << endl;

    sort(boxes.begin(), boxes.end());
    cout << "Vector sorted, starting to process results" << endl;

    const box_t emptyBox {0, 0, 0}; //used to avoid nullptr in the first pass
    const box_t* lastBox {&emptyBox};
    bool lenVolMatches {false};
    int matchCount {1};
    stringstream ss {""};
    for (const auto& b: boxes){
        if (b.len() == lastBox->len() && b.vol() == lastBox->vol()) {
            appendTo(ss, b);
            lenVolMatches = true;
            matchCount += 1;
        }else{
            if(lenVolMatches){
                if(matchCount > maxCount) {
                    appendTo(ss,*lastBox);
                    ss << endl;
                    cout << ss.str() << flush; // output, we found the next largest set
                    maxCount = matchCount;
                }
                lenVolMatches = false;
                matchCount = 1;
                ss.str("");
                ss.clear();
            }
            lastBox = &b;
        }
    }
}


#include <boost/lexical_cast.hpp>
int main(int argc, char** argv){

    if (argc < 4){
        cout << " Usage programName startFrom goUpTo leastNumberOfBoxesInaSet" << endl;
        exit(1);
    }
    auto startFrom = boost::lexical_cast<dim_t>(argv[1]);
    auto goUpTo = boost::lexical_cast<dim_t>(argv[2]);
    auto leastNumberOfBoxes = boost::lexical_cast<dim_t>(argv[3]);
    findSmallestBoxSetThatHasEqualVolumesAndEdgeLengths(startFrom, goUpTo, leastNumberOfBoxes);

    return 0;
}
comments powered by Disqus