Sunday, September 2, 2012

Color Distribution sans recursion.

I did a bit of math and got rid of the recursive section.

    public int[] getPattern(int index) {
        int n = (int)Math.cbrt(index);
        index -= (n*n*n);
        int[] p = new int[3];
        Arrays.fill(p,n);
        if (index == 0) {
            return p;
        }
        index--;
        int v = index % 3;
        index = index / 3;
        if (index < n) {
            p[v] = index % n;
            return p;
        }
        index -= n;
        p[v      ] = index / n;
        p[++v % 3] = index % n;
        return p;
    }
Turns out you can calculate N without iterating the whole thing, but by rather taking the cube root or the index. Which makes sense if you consider all the previous patterns with characters from 0-(N-1)  would take N*N*N space to use up and we by definition used that up.

No comments: