Streaming Collatz

Challenge

The recent question The 3n + 1 algorithm for a range inspired me to investigate a Java-8 dependent streaming mechanism for solving the programming challenge:


For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j (inclusive).

The cycle length of a number is defined as the count of values in the Collatz Sequence for that number.

Input

The input is given as multiple low and high bounds in an input file, each line contains one low and high bound. The programming challenge limits the high bound to 1,000,000 but I found that I was able to handle much larger bounds. The input I used is:

-1 0
0 0
0 1
22 22
27 27
1 100
99 100
100 100
1000 1000000
1 10000000
1 10000000

Output

The output should consist of the two input values followed by the length of the longest sequence from those bounds. For example, the input sequence 22 22 should produce the output:

22 22 16

I have elected to add additional timing data to the output for my tests, but this can be removed easily....

Review Request

I am particularly interested in any ways I could be using the new Java 8 functionality more effectively, while still maintaining a high level of performance. Additionally, I am curious to know if there are faster ways to do this....

Solution

I have split the code in two classes, one which is a factory mechanism to supply an IntStream of the sequence. The second class is just the one which implements the challenge.

(The code in revision 1 is obsolete.)

The following is the Sequence factory:

```
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.IntConsumer;
import java.util.function.IntUnaryOperator;
import java.util.stream.IntStream;
import java.util.stream.StreamSupport;

/**
* A Factory class which supplies a Stream of int that follow the Collatz Conjecture
* sequence:
*
* 1 value of 1 terminates the stream
* even values are halved
* odd values a

This problem of counting lengths of Collatz sequences benefits greatly from memoization. Memoizing results for just the first 2000 seeds cuts the computation time for the 1-to-107 problem in half — and if only searching up to 106, the effect is even more dramatic.

Here's a quick-and-dirty hack that does the job; I'm sure that countCollatz() could be made more elegant. (Even with the nasty repetition, it's still shorter than writing a CollatzSequence class. A Spliterator to create a stream that you can .count() seems like overkill.)

public class CollatzWithMemo {

    private final int[] collatzCounts;

    public CollatzWithMemo(int memoizationLimit) {
        this.collatzCounts = new int[memoizationLimit];
    }

    public final int countCollatz(int n) {
        if (n = this.collatzCounts.length) {
            // Unmemoizable
            return 1 + this.countCollatz(n % 2 == 0 ? n / 2 : 3 * n + 1);
        } else if (this.collatzCounts[n] != 0) {
            // Result is already memoized
            return this.collatzCounts[n];
        } else {
            // Need to memoize new result
            return this.collatzCounts[n] = 1 + this.countCollatz(n % 2 == 0 ? n / 2 : 3 * n + 1);
        }
    }

    public final int maxCollatz(int from, int to) {
        …
    }

    public final void processChallenge(Path input, BufferedWriter output) throws IOException {
        …
    }

    public static void main(String[] args) throws IOException {
        if (args.length  1
                ? Files.newBufferedWriter(Paths.get(args[1]))
                : new BufferedWriter(new OutputStreamWriter(System.out))) {

            collatz.processChallenge(source, bw);

        }

    }

}

StackExchange Code Review Q#84669, answer score: 4