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();
}
}
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
Post a Comment