Skip to content

Instantly share code, notes, and snippets.

@dave-maldonado
Created November 16, 2012 20:04
Show Gist options
  • Save dave-maldonado/4090410 to your computer and use it in GitHub Desktop.
Save dave-maldonado/4090410 to your computer and use it in GitHub Desktop.
Programming Challenges (Skiena) - first problem "3n+1 problem"
class myStuff implements Runnable{
/* Collatz conjecture problem: Skiena's Programming Challenges textbook:
* This program accepts two ints representing a range of ints from the robo-judge.
* For each int in the range it peforms the HOTPO operation to produce a hailstone sequence.
* outputs (prints) the first and second ints inputted and the largest hailstone sequence.
* produced from the range
*/
public void run(){
String input;
int i, j, accum, cycleLen, maxCycleLen;
while ((input = Main.ReadLn(255)) != null) {
StringTokenizer tokens = new StringTokenizer(input); // tokenize input string
i = Integer.parseInt(tokens.nextToken()); // first int from input
j = Integer.parseInt(tokens.nextToken()); // second int from input
cycleLen = 1; // cycle length of current Collatz sequence
maxCycleLen = 0; // maximum cycle length of Collatz sequence from integer i thru j
int min, max; // for reordering inputs if i > j
// assign min and max to i and j
if (i > j) {
min = j;
max = i;
}
else {
min = i;
max = j;
}
// init and fill array with i thru j values
accum = min; // accumulator for filling array
int[] arr = new int[max - min + 1];
for (int k = 0; k < arr.length; k++) {
arr[k] = accum++;
}
// peform logic on each element in array
for (int k : arr) {
cycleLen = 1; // it's 1 rather than 0 to account for the beginning value
while (k != 1) {
if (k % 2 == 0)
k /= 2;
else
k = k * 3 + 1;
cycleLen += 1;
}
if (cycleLen > maxCycleLen)
maxCycleLen = cycleLen;
}
// print largest hailstone sequence from integer i thru j
System.out.println(i + " " + j + " " + maxCycleLen);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment