# Minimising the Triangle version 2

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.

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;
}
}


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.

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

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

• 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 Jun 25 '15 at 19:23
• @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. Jun 25 '15 at 19:54
• @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). Jun 25 '15 at 19:57
• 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 Jun 25 '15 at 23:12
• ie 1 2 4 7 becomes 3 6 11 7 => 9 17 11 7 => 26 7 11 7 Jun 25 '15 at 23:13