Minimising the triangle

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.

Source

Example:

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

Here 3 occurs twice, so the triangle is invalid

The base \$n\$ can be of any size \$n > 0\$ with

solve(1) = 1, solve(2) = [1, 2] = 3, solve(3) = [2, 1, 4] = 8

I would like suggestions on how I can improve:

• The code style or best practices, so the code is easy to read.

• The algorithm/constraints, I'm pretty sure that the loops can be made tighter, so not as many numbers have to be checked, but I can't figure out what the cut off is.

• Is there a better way to implement the base size without hard-coding extra nested loops, as this doesn't seem very scalable?

```
import java.util.*;

public class spaceship {
public static void main(String[] args) {
long start = System.nanoTime();
spaceship kling = new spaceship();
kling.solveAll();
System.out.println("Took: " + (System.nanoTime() - start) / 1000000 + "ms");
}

public void solveAll() {
int len = 6;
int bestFound = 400; //definitely big enough from previous tests
int res = bestFound;
int[] best = new int[len];
int[] x = new int[len];
int[] co = new int[] { 1, 1, 1, 1, 1, 1 };

for (int a = 1; co[0] * a data = new HashSet<>();
// check input for duplicates
// could be done in loops
for (int a : in) {
if (data.contains(a))
return -1;
data.add(a);
}

int size = in.length;
int[][] arr = new int[size][size];
arr[0] = in;
// first row is the input
// every row after is the sum of the two elements below it

Style

In Java it is common practice to have class names to use PascalCase (a.k.a. UpperCamelCase). Also the name spaceship doesn't make sense to me and is confusing. Also, why is the instance called kling?

Readability

I prefer to prefix my formal parameters with a for argument, for example aInputArray. I believe it would help readability of your code.

Please prefer descriptive names. Currently I have no idea what x, co and res are.

Nested for loops

You are basically implementing a multi-byte counter. You can do something like this (not tested, but you get the idea):

boolean incr(int[] co, int max, int min, int pos){
     if(co[pos] + 1 > max){
         co[pos] = min;
         if(pos == 0)
              return false;
         return incr(co, max, min, pos - 1);
     }
     else{
         co[pos]++;
         return true;
     }
}

void solveAll(){

    int[] co = new int[len];
    while(incr(co, bestFound, 1, co.length - 1)){
       res = solve(co);
    }
}

Performance

Lets look at solve(int[] in). You're using HashSet which is fast as long as you don't get excessive collisions. Seeing as you are dealing with many numbers that are possibly small, you could be having many hash collisions. If profiling indicates this is the case, you can try a better hash function (for example multiply by a large prime number).

Here:

int[][] arr = new int[size][size];

you allocate space for the whole triangle but you only ever use the last two rows. So you only need to store two rows and alternate between them. This has the added benefit that both rows will be hot in cache all the time, avoiding cache misses as you go from line to line. It will also avoid some extra indirections in your inner most loop.

Better algorithm

The first thing we need to realize is that the problem is kind of recursive (I can't remember the proper term off the top of my head).

What I mean by that is that if a base {a,b,c} for n=3 crumbles, then the all bases {a,b,c,x} for any x will also crumble. This means that by solving the easier problem n=3 we get information about a lot of combinations for n=4 that will crumble. (1)

The second thing to realize about this problem is that if {a,b,c} crumbles, then {c,b,a} will also crumble. And if {a,b,c} doesn't crumble and has top value x then {c,b,a} will also not crumble and have the same top value x. (2)

The third thing is that for the base {a,b,c} the top value will be strictly larger than a+b+c. This is a useful stopping condition. (3)

Knowing the above, you have to unrestrainedly search for the combination of n base elements that produces the smallest top value as result. Use a greedy search for the smallest top value and terminate when all the nodes remaining fulfil (3).

The difficult part is to generate the nodes to be searched. This can be done effectively by starting with small n and then combinatorially incrementing the base elements and adding an additional base element to create triangles with n+1 base for any triangle that doesn't crumble. This exploits (1) to prune large sets of crumbling triangles from the start.

One should also take care to not generate symmetry pairs to triangles that have already been tried to exploit (2).

It is useful to store the base and right edge of the triangle in addition to a HashSet of all the values in the triangle.

I.e. for the triangle:

20
    8   12
  3   5   7 
1   2   3   4

store:

1   2   3   4 (base row)

and

4   7   12   20 (right edge, bottom -> up).

Using the right edge, we can quickly calculate any expansion of this triangle. For example:

1   2   3   4   10

is easily calculated as:

53
      20 33
        12 21
          7  14
            4  10

if we have the right edge.

I hope this helps. It's an interesting problem.

StackExchange Code Review Q#92673, answer score: 14