Minimising the triangle

Question

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 < bestFound; a++) {
            long beg = System.nanoTime();
            for (int b = 1; co[1] * b < bestFound; b++) {

                for (int c = 1; co[2] * c < bestFound; c++) {
                    for (int d = 1; co[3] * d < bestFound; d++) {
                        //for (int e = 1; co[4] * e < bestFound; e++) {
                            //for (int f = 1; co[5] * f < bestFound; f++) {

                                x = new int[] { a, b, c, d,/* e, f */};
                                res = solve(x);

                                if (res != -1 && res < bestFound) {
                                    System.out.print(Arrays.toString(x));
                                    System.out.println(":\t" + res);
                                    bestFound = res;
                                    best = x;
                                }
                            //}
                        //}
                    }
                }
            }
            System.out.println((System.nanoTime() - beg) / 1000000 + "ms");
        }

        System.out.println("The best result possible is:");
        System.out.println(bestFound);
        System.out.println(Arrays.toString(best));

    }

    public int solve(int[] in) {
        Set<Integer> 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
        // ie pascal's triangle with outermost values ignored

        for (int i = 1; i < size; i++) {
            for (int j = 0; j < size - i; j++) {
                int a = arr[i - 1][j] + arr[i - 1][j + 1];
                if (data.contains(a))
                    return -1;
                data.add(a);
                arr[i][j] = a;
            }
        }

        // return final value, our result if no duplicates occur during the
        // process
        return arr[size - 1][0];
    }
}

Answer 1

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.

Answer 2

General Comments

Firstly, congratulations on solving the problem. I don't know if it was an exercise in curiosity on your behalf or a piece of coursework, but from my perspective being able to solve this kind of interesting question is a superb benefit of being a programmer.

Secondly, writing good code for almost anyone takes experience and persistence, so don't take criticisms too hard.

The two worst aspects of the program are (imo) the following:

1. Do not use cutesy names for your classes. Whether or not you are an idiot people will treat you like one (unless they also do it) because most people who do it are indeed idiots.
2. If you are having to change your code to run it when you really want to just change a parameter then there is something very wrong. Fix your code to run with a parameter. I'm talking here about the commented out loops that you need to uncomment merely to solve the same problem with a different base size.

A minor style issue, that's easy to bear in mind, is that it's nicer and easier to calculate time unit conversions like this:

TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - beg)

Algorithm Comments

On my laptop it takes 152 seconds to calculate the 5 element base using your code.

There are a couple of easy performance improvements you can make to the code without overhauling the algorithm completely.

1. Any time you need to keep track of a reasonably limited countable set of items, it's much faster to do it using a BitSet. This took the running time for your 5 element base down to 53s. This is not due to collisions in the HashSet slowing it, just the overhead of using the HashSet.
2. You can actually use a BitSet in the solveAll method to only even look at unselected numbers,

Like this:

BitSet bitSet = new BitSet();
for (int a = 1; co[0] * a < bestFound; a++) {
    long beg = System.nanoTime();
    bitSet.set(a);
    for (int b = 2; !bitSet.get(b) && co[1] * b < bestFound; b++) {
        bitSet.set(b);
        for (int c = 3; !bitSet.get(c) && co[2] * c < bestFound; c++) {
            bitSet.set(c);
            for (int d = 4; !bitSet.get(d) && co[3] * d < bestFound; d++) {
                bitSet.set(d);
                for (int e = 5; !bitSet.get(e) && co[4] * e < bestFound; e++) {
                    bitSet.set(e);
                    // ...
                    bitSet.clear(e);
                }
                bitSet.clear(d);
            }
            bitSet.clear(c);
        }
        bitSet.clear(b);
    }
    bitSet.clear(a);
}

This takes your running time down to 2.5 secs for the 5 element base. Not bad ;-)

However you can get it faster if you

Change the Algorithm

Firstly, for simplicity, represent the triangle as a simple array. You can do this by saying the item at the top is position 0, the next row is at positions 1 and 2, the next at 3,4,5 etc etc.

Then, instead of starting at the bottom and calculating up, we can start at the top and calculate down. So you can start at the top of the triangle with a minimum value then try to populate it downwards. If you cannot calculate all the way down, then you increase the minimum value and try again. An advantage of this is that other than the left hand edge of the triangle, there is no choice to be made. And for each of these entries on the left, they must be on or above the value for the minimum of a triangle with the height of that row, and also below the value of the parent minus the minimum. This puts quite a bound on the range of values to check.

To get a sensible minimum value, the easiest is to just recursively downwards create triangles, until we get to triangles of size 1 which has a hardcoded minimum of one. Then we calculate the minimum of triangle of size two using as a starting point 2*1+1 (ie 3), then process to get the real minimum, lets call this x. We then repeat the process using x, to give an initial minimum of 2*x+1 for the triangle one step up (ie 4) etc etc. The reason to choose 2*x+1 is that if the minimum is x, then its adjacent number is at least x+1 to avoid a repeated number, meaning that the initial minimum of the parent element must be 2*x+1.

Anyway putting it all together makes a big difference. The 5 element base is calculated in 6ms :-)

I've included my code below, there's no comments (but it follow the algorithm explained above) and it's just to illustrate the algorithm rather than seek any code review (in particular it's fine to do work in a constructor when you are just writing a class to solve a particular problem, and recursion of constructors makes the code more simple. Imo.)

import java.util.*;
import java.util.concurrent.TimeUnit;

public class MinimumTriangle {
    final static Map<Integer, Integer> minsForHeight = new HashMap<Integer, Integer>(){{
        put(0, 0);
        put(1, 1);
    }};

    int[] values;
    int depth;

    public MinimumTriangle(int depth) {
        this.depth = depth;
        this.values = new int[depth * (depth + 1) / 2];
        if (depth == 1) {
            values[0] = 1;
        } else if (depth != 0) {
            new MinimumTriangle(depth-1);
            rowReduce(0, new BitSet());
            minsForHeight.put(depth, values[0]);
        }
    }

    private boolean rowReduce(int row, final BitSet usedNumbers) {
        if (row == depth) return true;
        int minForHeight = minsForHeight.get(depth-row-1)*2+1;
        int startPos = row * (row + 1) / 2;
        int parentStartPos = startPos - row;
        int maxForHeightWithParent = row > 0 ? values[parentStartPos] - minForHeight : 0;
        for (int i = minForHeight; row == 0 || i <= maxForHeightWithParent; i++) {
            if (usedNumbers.get(i)) continue;
            final BitSet localUsedNumbers = (BitSet) usedNumbers.clone();
            if (populateRow(i, row, startPos, localUsedNumbers, minForHeight)) {
                if (rowReduce(row + 1, localUsedNumbers)) return true;
            }
        }
        return false;
    }

    private boolean populateRow(int i, int row, int startPos, final BitSet usedNumbers, int minForHeight) {
        int rowLength = row + 1;
        final BitSet bitSet = (BitSet) usedNumbers.clone();
        if (!setAndCheck(startPos, i, bitSet, minForHeight)) return false;
        for (int j = 1; j < rowLength; j++) {
            if (!setAndCheck(startPos+j, values[startPos + j - row - 1] - values[startPos + j - 1], bitSet, minForHeight)) return false;
        }
        usedNumbers.or(bitSet);
        return true;
    }

    private boolean setAndCheck(int pos, int val, final BitSet localUsedNumbers, int minForHeight) {
        if (val >= minForHeight && !localUsedNumbers.get(val)) {
            localUsedNumbers.set(val);
            values[pos] = val;
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        for(int i=0; i<8; i++) time(i);
    }

    public static void time(int level) {
        long l = System.nanoTime();
        System.out.println(new MinimumTriangle(level));
        System.out.println(TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - l)+ "ms");
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        int numbersToPrint = values.length;
        for (int row = 1; numbersToPrint>0; row++) {
            for (int j=0; j<row; j++) {
                if (j != 0) sb.append(",");
                sb.append(values[values.length-(numbersToPrint--)]);
            }
            if (numbersToPrint !=0) sb.append("\n");
        }
        return sb.toString();
    }
}

Just run the main method, it will output all the triangles up to base of 7 (the base of 7 takes approx 400ms). I have not verified the results, so there may be errors, but the lower triangles seem to match your output as well.