Minimising the Triangle version 2

Question

I asked this question and I have made enough changes, so I think it deserves a new question.

The Problem:

A triangle needs a good foundation. Every row in the triangle is derived from the sum of the two values below it. However, there can be no repeated values, if a value shows up more than once the triangle crumbles. Find the base which minimises the value in the top of the triangle satisfying the condition of no duplicates.

Example:

      20
    8   12
 [3]   5   7
1   2  [3]  4

Here 3 occurs twice, so the triangle is considered invalid

Suggestions:

I would like ideas focused on

• Performance; base size 5 takes about 200 milliseconds on my machine, a base of 6 takes about 40 seconds, and 7 is still running after half an hour.
• Readability; how difficult is it to read the code

import java.util.*;

public class SmallestTriangle {

    static int[][] pascal = { 
        {}, 
        { 1 }, 
        { 1, 1 }, 
        { 1, 2, 1 }, 
        { 1, 3, 3, 1 },
        { 1, 4, 6, 4, 1 }, 
        { 1, 5, 10, 10, 5, 1 },
        { 1, 6, 15, 20, 15, 6, 1 }, 
        { 1, 7, 21, 35, 35, 21, 7, 1 },
        { 1, 8, 28, 56, 70, 56, 28, 8, 1 },
        { 1, 9, 36, 84, 126, 126, 84, 36, 9, 1 },
        { 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1 } 
    };

    public static void main(String[] args) {
        long start = System.nanoTime();
        SmallestTriangle solver = new SmallestTriangle();
        int baseSize = 6;
        solver.findBestTriangle(baseSize); //run

        System.out.println("Took: " + (System.nanoTime() - start) / 1000000 + "ms");
    }

    void findBestTriangle(int aBaseSize) {
        int bestFound = 1000;
        int currentResult = bestFound;
        int[] bestTriangleFound = new int[aBaseSize];
        int[] currentArray = new int[aBaseSize];

        for (int a = 0; a < aBaseSize; a++) {
            currentArray[a] = a + 1;
        }

        while (currentArray[0] < bestFound) { //run until the first number in the count is equal to the best score, needs improvement
            currentResult = checkTriangle(currentArray, bestFound);
            if (currentResult >= 0 && currentResult < bestFound) {
                bestFound = currentResult;
                bestTriangleFound = Arrays.copyOf(currentArray, currentArray.length);

                System.out.println(Arrays.toString(bestTriangleFound) + ":\t" + bestFound);
            }

            currentArray = nextTry(currentArray, bestFound);
        }

        System.out.println("The smallest result possible is: " + bestFound);
        System.out.println(Arrays.toString(bestTriangleFound));
    }

    /*  returns the next base to try, it takes the previous base, adds 1 to the end, then checks each number for overflow
            (overflow occurs if it passes the best found triangle so far)

    */
    int[] nextTry(int[] aTriangleBase, int aOverflowLimit) {
        int size = aTriangleBase.length;
        aTriangleBase[size - 1]++;
        int sum = aTriangleBase[size -1];
        for (int a = size - 1; a > 0; --a) {
            int c = pascal[size][a] * aTriangleBase[a];
            if (c >= aOverflowLimit) {
                aTriangleBase[a] = 1;
                aTriangleBase[a - 1]++;
            }
            sum += pascal[size][a-1] * aTriangleBase[a-1];
        }
        return aTriangleBase;
    }

    /** A method to check whether a base for a triangle will form a valid triangle

        @param  int[]   aTriangleBase       a potential triangle base
        @param  int     aLimit              a limit that if passed, guarentees the base is not the smallest
        @return int     -1 <= x < aLimit    if invalid, returns -1, otherwise it returns the top number in the triangle, the triangle's score
    */
    int checkTriangle(int[] aTriangleBase, int aLimit) {
        int size = aTriangleBase.length;
        boolean[] count = new boolean[aLimit];
        // check input for duplicates
        for (int i : aTriangleBase) {
            if (count[i])
                return -1;
            count[i] = true;
        }

        int[] firstRow = new int[size];
        int[] secondRow = Arrays.copyOf(aTriangleBase, size);
        boolean useFirst = true;
        int a = 0;

        for(int i = 1; i < size; ++i) {
            if(useFirst) {
                for(int j = 0; j < size-i; ++j) {
                    a = secondRow[j] + secondRow[j + 1];
                    if (a >= aLimit || count[a]) 
                        return -1;
                    count[a] = true;
                    firstRow[j] = a;
                }
                useFirst = false;
            } else {
                for(int j = 0; j < size-i; ++j) {
                    a = firstRow[j] + firstRow[j + 1];
                    if (a >= aLimit || count[a]) 
                        return -1;
                    count[a] = true;
                    secondRow[j] = a;
                }
                useFirst = true;
            }
        }
        // return final value, our result if no duplicates occur during the process
        return a;
    }
}

Answer 1

Performance; base size 5 takes about 200 milliseconds on my machine, a base of 6 takes about 40 seconds, and 7 is still running after half an hour.

I can solve size=9 in 18 seconds, but I tried a very different approach (starting from the top and trying to compute the rows below). For size=10, it took 50 minutes and I can see no chance that size=11 finishes this year.

I don't claim that starting from the top is better, maybe starting from the base could be made much more efficient when more promising candidates get tried first. Looking at the solution

1000
 489  511
 277  212  299
 175  102  110  189
 116   59   43   67  122
  77   39   20   23   44   78
  50   27   12    8   15   29   49
  32   18    9    3    5   10   19   30
  21   11    7    2    1    4    6   13   17

you can see that the smallest values are in the middle of the base. This makes sense as they contribute most to the result.

Readability; how difficult is it to read the code

Not exactly easy, but not really bad. There are quite a few strange names and strange things done. For example, nextTry both modifies it's input and returns it. This is pretty unexpected.

checkTriangle

Your javadoc should be formatted like here.

int checkTriangle(int[] aTriangleBase, int aLimit) {
    int size = aTriangleBase.length;
    boolean[] count = new boolean[aLimit];

It's only a count in a rather stretched sense. I'd suggest present or found.

    // check input for duplicates
    for (int i : aTriangleBase) {
        if (count[i])
            return -1;
        count[i] = true;
    }

Ideally, you'd need no special handling for this.

    int[] firstRow = new int[size];
    int[] secondRow = Arrays.copyOf(aTriangleBase, size);
    boolean useFirst = true;
    int a = 0;

It took me a while till I found that you're reusing the arrays. It may be a useful optimization, but you it doubled your code.

    for(int i = 1; i < size; ++i) {
        if(useFirst) {
            for(int j = 0; j < size-i; ++j) {
                a = secondRow[j] + secondRow[j + 1];
                if (a >= aLimit || count[a]) 
                    return -1;

You know, always braces. You're optimizing by aborting early on a >= limit, but this should actually never happen, except for the top element. If this happens below, then the root element will be even bigger and such a triangle is simply too bad and should have been avoided earlier.

                count[a] = true;
                firstRow[j] = a;
            }
            useFirst = false;
        } else {
            for(int j = 0; j < size-i; ++j) {
                a = firstRow[j] + firstRow[j + 1];
                if (a >= aLimit || count[a]) 
                    return -1;
                count[a] = true;
                secondRow[j] = a;
            }
            useFirst = true;

Instead of this code duplication, you could simply swap firstRow and secondRow.

        }
    }
    // return final value, our result if no duplicates occur during the process
    return a;
}

The fact that you need a comment here is a sign that the method does not do exactly one right thing. It does two things, which may be fine when optimizing heavily, but I doubt you need it.

Two methods like

boolean makesValidTriangle(int[] base)

and

int triangleSum(int base)

would be way clearer. Note that the latter can easily be implemented using the pascal triangle. Note also that with further optimization, you won't even need it as you can compute the sum incrementally.

nextTry

int[] nextTry(int[] aTriangleBase, int aOverflowLimit) {

You're using a Smalltalk naming convention which looks strange in Java. And in Smalltalk, it's not prefixing "a", but prefixing the indefinite article. Java doesn't need it and things like Triangle triangle are common.

The aOverflowLimit is misnamed, as overflow is something occurring at Integer.MAX_VALUE or alike. What's happening here, is just violating the upper bound. I always use maximum (allowed) or limit (exclusive).

    int size = aTriangleBase.length;
    aTriangleBase[size - 1]++;
    int sum = aTriangleBase[size -1];

It's a good idea to compute sum on the fly. However, without ever using it, it can only slow you down.

    for (int a = size - 1; a > 0; --a) {
        int c = pascal[size][a] * aTriangleBase[a];
        if (c >= aOverflowLimit) {
            aTriangleBase[a] = 1;
            aTriangleBase[a - 1]++;
        }

You're trying insanely big values. For size=7, the solution is 212 while the maximum value in the base is 13. Yet your first and last base entries are limited by 212 only.

        sum += pascal[size][a-1] * aTriangleBase[a-1];
    }
    return aTriangleBase;
}

I'd bet that for efficiency, the order in which the bases get generated is crucial. Also using the sum should help you to skip over bad bases.

... to be continued - maybe...