Combos.java

package crossnum;

/**
 * Combos can tell how many combinations of a specified number of digits sums
 * to a particular total. Only the digits one to nine are allowed.
 *
 * Combos implements an optimisation whereby the number of combinations is
 * retrieved from a cache. Combos has to be initialised with the maximum number
 * of digits, and maximum total, that it can handle.
 *
 * @author dub_nerd
 *
 */
public class Combos {

    /**
     * The cache from which numbers of combinations are retrieved. The
     * dimensions of the cache are max digits x max total.
     */
    private final int cache[][];

    /**
     * Construct the Combos cache.
     * @param maxDigits maximum number of digits to be handled.
     * @param maxTotal maximum total sum that can be requested.
     */
    public Combos(int maxDigits, int maxTotal) {

        cache = new int[maxDigits][];

        /**
         * We populate the cache by creating a Base9 number of each
         * possible number of digits, incrementing it until it overflows
         * and counting the number of times its digits sum a given value
         * within the specified limits.
         */
        for (int digits = 1; digits <= maxDigits; digits++) {
            cache[digits - 1] = new int[maxTotal];
            DigitCombo d = new Base9(digits);
            while (!d.isOverflow()) {
                int tot = d.summedDigits();
                if (tot < maxTotal) {
                    cache[digits - 1][tot]++;
                }
                d.increment();
            }
        }

    }

    /**
     * Gets the number of combinations of digits from 0-9 that sum to a given
     * total.
     *
     * @param digits
     *            the number of digits to be summed.
     * @param total
     *            the total to which the digits must sum.
     * @return the number of combinations that sum to the total.
     */
    int getNumberCombos(int digits, int total) {
        return cache[digits - 1][total];
    }

}