Ducci Sequence - Programming challenge [Java]

There was a challenge, it went like this:

A Ducci sequence is a sequence of n-tuples of integers, sometimes known as "the Diffy game", because it is based on sequences. Given an n-tuple of integers (a_1, a_2, ... a_n) the next n-tuple in the sequence is formed by taking the absolute differences of neighboring integers. Ducci sequences are named after Enrico Ducci (1864-1940), the Italian mathematician credited with their discovery. Some Ducci sequences descend to all zeroes or a repeating sequence. An example is (1,2,1,2,1,0) -> (1,1,1,1,1,1) -> (0,0,0,0,0,0).

I did this:

import java.util.ArrayList;

public class ducci_sequence {

    public int calculate(int[] sS) {
        ArrayList<String> pS = new ArrayList<String>();
        String t = "";
        for (int i = 0; i < sS.length; i++)
            t = t + sS[i] + ",";
        System.out.println(t);
        while (true) {
            pS.add(t);
            int[] nCs = new int[sS.length];
            for (int i = 0; i < nCs.length; i++) {
                if (i == nCs.length - 1)
                    nCs[i] = sS[i] - sS[0];
                else
                    nCs[i] = sS[i] - sS[i + 1];
                if (nCs[i] < 0)
                    nCs[i] = nCs[i] * -1;
            }
            t = "";
            for (int i = 0; i < nCs.length; i++)
                t = t + nCs[i] + ",";
            sS = nCs;
            if (pS.contains(t))
                break;
            System.out.println(t);
        }
        return pS.size();
    }
}

It works like this:

We start with a sequence, stored in sS (starting sequence). We add this sequence to a list, pS (previous sequences), that will keep all of the calculated sequences. That way, whenever we calculate a new sequence, that we have already calculated before, we can detect and exit out of a possibly infinity loop. The list will also count the number of calculated sequences. 

sS has the 1st sequence, and we calculate the new sequence and store it inside the variable nCs (newly calculated sequence). This nCs is compared to all the sequences already inside pS. If it does not exist in pS yet, we add it. If it does exist inside pS, we know that we have entered an infinity loop. Now, we need to calculate a new sequence from our current nCs. So, the sequence inside nCs is moved into sS, and the loop iterates again. 

When the program reaches a loop, or the sequence calculates to something like 0, 0, 0, 0, the exit condition will be triggered. The function returns the size of the list. 



Comments

Popular posts from this blog

A* Pathfinding Algorithm Java Implementation

Additive Persistence - Programming Challenge [Java]