Algorithm to make numbers from match sticks

Question

I made a program to solve this problem from the ACM.

Matchsticks are ideal tools to represent numbers. A common way to represent the ten decimal digits with matchsticks is the following:

This is identical to how numbers are displayed on an ordinary alarm clock. With a given number of matchsticks you can generate a wide range of numbers. We are wondering what the smallest and largest numbers are that can be created by using all your matchsticks.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with an integer n (2 ≤ n ≤ 100): the number of matchsticks you have. Output

Per testcase:

One line with the smallest and largest numbers you can create, separated by a single space. Both numbers should be positive and contain no leading zeroes. Sample Input

4 3 6 7 15 Sample Output

7 7 6 111 8 711 108 7111111

The problem is that it's way too slow to solve it for 100 matchsticks. The search tree is too big to bruteforce it.

Here are the results for the first 10:

2: 1 1

3: 7 7

4: 4 11

5: 2 71

6: 6 111

7: 8 711

8: 10 1111

9: 18 7111

10: 22 11111

The pattern for the maximums is easy but I don't see a shortcut for the minimums. Can someone suggest a better way to solve this problem? Here is the code I used:

    #include <iostream>
    #include <string>
    using namespace std;

    #define MAX 20 //should be 100

    //match[i] contains number of matches needed to form i
    int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    string mi[MAX+1], ma[MAX+1];
    char curr[MAX+1] = "";

    //compare numbers saved as strings
    int mycmp(string s1, string s2)
    {
        int n = (int)s1.length();
        int m = (int)s2.length();
        if (n != m)
            return n - m;
        else
            return s1.compare(s2);
    }

    //i is the current digit, used are the number of matchsticks so far
    void fill(int i, int used)
    {
        //check for smaller and bigger values
        if (mycmp(curr, mi[used]) < 0) mi[used] = curr;
        if (mycmp(curr, ma[used]) > 0) ma[used] = curr;

        //recurse further, don't start numbers with a zero
        for (int a = i ? '0' : '1'; a <= '9'; a++) {
            int next = used + match[a-'0'];
            if (next <= MAX) {
                curr[i] = a;
                curr[i+1] = '\0';
                fill(i + 1, next);
            }
        }
    }

    int main()
    {
        //initialise 
        for (int i = 0; i <= MAX; i++) {
            mi[i] = string(MAX, '9');
            ma[i] = "0";
        }

        //precalculate the values
        fill(0, 0);

        int n;
        cin >> n;

        //print those that were asked
        while (n--) {
            int num;
            cin >> num;
            cout << mi[num] << " " << ma[num] << endl;
        }

        return 0;
    }

EDIT : I ended up using the dynamic programming solution. I tried it with dp before but I was messing around with a two-dimensional state array. The solutions here are much better. Thanks!

Answer 1

You can use a dynamic programming solution.

Suppose that you have n matches, and you know how to solve the problem (minimum number) for all set of n-k matches, where k takes all the values corresponding to the number of matches that each number uses (2 for 1, 5 for 3, etc.)

The solution is then derived recursively. Supposing that you end your number with a one (in the least significant position), then the best solution is obtained by writing (best solution with n-2 matches) 1. Supposing you end it with a two, the best solution is (best solution with n-5 matches) 2. And so on ; eventually you can compare these ten numbers, and pick the best one.

So now, all you have to do is devise the best solution for all n smaller than your input, recursively.

EDIT: If you implement this algorithm in a straightforward way, you'll end up with an exponential complexity. The trick here is to notice that if your core function MinimumGivenNMatches, only takes one parameter, n. Hence you'll end up calling it with the same values a huge number of times.

To make the complexity linear, you just need to memoize (ie. remember) the solution for each n, using an auxiliary array.

Answer 2

In order to find the result :

• first find the minimal number of digits for smallest number
• then proceed from most significant digit to the least significant one.

Every digit should be chosen so that there exists a solution for remaining digits. Each digit requires between 2 and 7 matches. So you must choose the smallest Nth "top" digit that leaves the number of remaining matches between 2*(N-1) and 7*(N-1).

Do not forget that 0 has to be excluded from the search for the most significant digit of the result.

As a sidenote, one reason which makes this algorithm work is the fact that there is at least one corresponding digit for every value (of matches) between 2 and 7.

EDIT : example for 10 matches 10 matches --> 2 digits
Acceptable number of matches for top digit = between 3 and 7.
Smallest digit which requires between 3 and 7 matches -> 2 (which takes 5 matches), 0 being excluded.
Chosen first digit = 2

5 remaining matches -->
Acceptable number of matches for second (and in this case last) digit = exactly 5
Smallest digit which requires 5 matches -> 2
Chosen second digit = 2

Result = 22.

EDIT code for this problem

#include <iostream>
#include <vector>

std::vector<int> nbMatchesForDigit;

long long minNumberForMatches(unsigned int nbMatches)
{
    int nbMaxMatchesForOneDigit = 7;
    int nbMinMatchesForOneDigit = 2;
    int remainingMatches = nbMatches;
    int nbDigits = 1 + nbMatches / nbMaxMatchesForOneDigit; 
    long long result = 0;
    for (int idDigit = 0 ; idDigit < nbDigits ; ++idDigit )
    {
        int minMatchesToUse = std::max(nbMinMatchesForOneDigit, remainingMatches - nbMaxMatchesForOneDigit * (nbDigits - 1 - idDigit));
        int maxMatchesToUse = std::min(nbMaxMatchesForOneDigit, remainingMatches - nbMinMatchesForOneDigit * (nbDigits - 1 - idDigit));
        for (int digit = idDigit > 0 ? 0 : 1 ; digit <= 9 ; ++digit )
        {
            if( nbMatchesForDigit[digit] >= minMatchesToUse && 
                nbMatchesForDigit[digit] <= maxMatchesToUse )
            {
                result = result * 10 + digit;
                remainingMatches -= nbMatchesForDigit[digit];
                break;
            }
        }
    }
    return result;
}

int main()
{
    nbMatchesForDigit.push_back(6);
    nbMatchesForDigit.push_back(2);
    nbMatchesForDigit.push_back(5);
    nbMatchesForDigit.push_back(5);
    nbMatchesForDigit.push_back(4);
    nbMatchesForDigit.push_back(5);
    nbMatchesForDigit.push_back(6);
    nbMatchesForDigit.push_back(3);
    nbMatchesForDigit.push_back(7);
    nbMatchesForDigit.push_back(6);

    for( int i = 2 ; i <= 100 ; ++i )
    {
        std::cout << i << " " << minNumberForMatches(i) << std::endl;
    }
}