3
\$\begingroup\$

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;
    }
}
\$\endgroup\$
4
\$\begingroup\$

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...

\$\endgroup\$
  • \$\begingroup\$ Other than by trial and error, how do you know the maximum base size is 13 for size = 7? I tried using sum before, but it didn't really offer much compared to other areas, so I left it alone. The other suggestions are great, I will definitely try to pick better names and split methods up if they are doing too many things. In regards to doubling the code in checkTriangle, it saved me a factor of 3 in runtime, would that not be worth it? Code went from 2 minutes to about 40 seconds, and likewise for other base sizes \$\endgroup\$ – spyr03 Jun 25 '15 at 19:23
  • \$\begingroup\$ @spyr03 "know the maximum base size is 13 for size = 7?" - I've found the optimum and looked at the row and there was nothing bigger. I wouldn't call it "trial and error", as I'm sure it was the optimum. But yes, before finding the optimum, I couldn't know. So you should not avoid bigger values, you just should try the smaller, i.e. the more promising first. This may be hard to achieve, starting with the base row, I can find the solution for size=8 in 6 seconds, but I get out of memory for size=9. \$\endgroup\$ – maaartinus Jun 25 '15 at 19:54
  • \$\begingroup\$ @spyr03 "In regards to doubling the code in checkTriangle, it saved me a factor of 3 in runtime, would that not be worth it?" - Factor of 3 is good enough, but what was the alternative? I can't imaging that swapping the two arrays would be three times slower (but I can't exclude it either). \$\endgroup\$ – maaartinus Jun 25 '15 at 19:57
  • \$\begingroup\$ Actually I think I could go one better, and overwrite the same array, and this gives the added bonus that the side of the triangle is maintained, I can then use that to form bigger base sides with a smaller base by adding the base extending number, up from right to left, and while this triangle may not be valid, it can be used for pruning, see here: codereview.stackexchange.com/a/94302/58248 \$\endgroup\$ – spyr03 Jun 25 '15 at 23:12
  • \$\begingroup\$ ie 1 2 4 7 becomes 3 6 11 7 => 9 17 11 7 => 26 7 11 7 \$\endgroup\$ – spyr03 Jun 25 '15 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.