14
\$\begingroup\$

Take any natural number n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3*n* + 1. Repeat the process (which has been called "Half Or Triple Plus One", or HOTPO) indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.

(Wikipedia article)

  • Any suggestions to make it more Java-8-like?
  • Please review the Javadocs and the overall readability of code+test too.

One disclaimer to add first: I know AtomicLong c = ... variable name is not ideal, the only reason why I am using a single character here is to make the code formatting look slightly better in my IDE code formatting settings. Feel free to comment on everything else.

CollatzUtils

import java.util.concurrent.atomic.AtomicLong;
import java.util.stream.LongStream;

/**
 * Utilities class for deriving number of steps using the Collatz conjecture.
 * <p>
 * Given a number <code>n</code>:
 * <ul>
 * <li>If <code>n</code> is even, repeat for value <code>n / 2</code>.</li>
 * <li>If <code>n</code> is odd, repeat for value <code>3 * n + 1</code>.</li>
 * <li>Repeat indefinitely, the conjecture is that <code>n = 1</code> eventually.</li>
 * </ul>
 */
public final class CollatzUtils {

    /**
     * Private constructor for utility class.
     */
    private CollatzUtils() {
        // intentionally blank
    }

    /**
     * Applies the Collatz conjecture on <code>value</code>, and count the steps to reach 1.
     * <p>
     * Examples:
     * <ul>
     * <li>1: 1 &#8594; 4 &#8594; 2 &#8594; 1. Therefore, the return value is 3.</li>
     * <li>2: 2 &#8594; 1. Therefore, the return value is 1.</li>
     * </ul>
     *
     * @param value the value to start from.
     * @return the number of steps to end at 1.
     * @throws IllegalArgumentException if <code>value</code> is 0 or less.
     */
    public static long stepsFor(long value) {
        if (value < 1) {
            throw new IllegalArgumentException("Input must be greater than 0.");
        }
        final AtomicLong c = new AtomicLong();
        LongStream.iterate(value, (v) -> c.incrementAndGet() > 0 && v % 2 == 0 ? v / 2 : 3 * v + 1)
                .anyMatch(v -> c.longValue() > 1 && v == 1);
        return c.decrementAndGet();
    }

}

CollatzUtilsTest

import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.equalTo;

import java.util.Arrays;
import java.util.Iterator;
import java.util.stream.LongStream;

import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

public class CollatzUtilsTest {

    static enum TestCase {
        ONE(3), TWO(1), THREE(7), FOUR(2), FIVE(5), SIX(8), SEVEN(16), EIGHT(3), NINE(19), TEN(6);

        private Long value;
        private Long expected;

        TestCase(long expected) {
            this.value = Long.valueOf(ordinal() + 1);
            this.expected = Long.valueOf(expected);
        }
    }

    @DataProvider(name = "test-cases")
    public Iterator<Object[]> getTestCases() {
        return Arrays.stream(TestCase.values())
                .map((current) -> new Object[] { current.value, current.expected }).iterator();
    }

    @DataProvider(name = "twos-test-cases")
    public Iterator<Object[]> getTwosTestCases() {
        return LongStream.range(1, 61).boxed()
                .map((v) -> new Object[] { Long.valueOf((long) Math.pow(2, v.doubleValue())), v })
                .iterator();
    }

    @Test(dataProvider = "test-cases")
    public void testCaseFor(Long value, Long expected) {
        assertThat(Long.valueOf(CollatzUtils.stepsFor(value.longValue())), equalTo(expected));
    }

    @Test(dataProvider = "twos-test-cases")
    public void testPowersOfTwo(Long value, Long expected) {
        testCaseFor(value, expected);
    }

    @Test
    public void testLargeValue() {
        testCaseFor(Long.valueOf(9780657631L), Long.valueOf(1132));
    }

    @Test(expectedExceptions = IllegalArgumentException.class)
    public void testIllegalArgumentException() {
        CollatzUtils.stepsFor(0);
    }

}
\$\endgroup\$
8
\$\begingroup\$

The urge to use Java8 features is strong, but, you need to look at the patterns of the problem, and not try to force the lambda to fit, rather, use the lambda to express the problem.

In this case, you have a stream of values that represent a Collatz sequence, but, that's not true. A Collatz sequence is terminated when the value is 1, but your initial Stream does not have a terminal condition:

LongStream.iterate(value,
    (v) -> c.incrementAndGet() > 0 && v % 2 == 0 ? v / 2 : 3 * v + 1)

Your stream is infinite, and will just keep going... even when the item is 1. So you have to use a side-effect mechanism with the hack of a 'anyMatch()' short-circuit terminal condition that you tack on at the end.

You also use the Atomic Long as a crutch, to ignore the first value .... and, since it starts at 0, it will always be true. That atomic, is really hackish.

The right solution for this problem using streams would be to create a stream that is a valid Collatz sequence.... Consider a function:

public static LongStream collatzSequence(long seed) { ...}

If that function returned a complete stream that represented a single sequence, then, you could simply have the code:

public static long stepsFor(long value) {
    if (value < 1) {
        throw new IllegalArgumentException("Input must be greater than 0.");
    }
    return collatzSequence(value).count();
}

Now, that would be the right lambda to have, and, you could also do something like:

public static long stepDump(long value) {
    if (value < 1) {
        throw new IllegalArgumentException("Input must be greater than 0.");
    }
    System.out.println("The steps in " + value + " are: " + 
        Arrays.toString(collatzSequence(value).toArray()));
}

With the right stream, you can do anything you want, count, sum, etc. The Stream is self governing.

Now, the problem is that it is not easy in Java8 to create a self-terminating open-ended stream. The solution to the problem is to create your own spliterator. Consider the following code which does create a valid LongStream using an OfLong Spliterator:

private static final class CollatzSpliterator implements Spliterator.OfLong {

    private long value;

    public CollatzSpliterator(long seed) {
        this.value = seed;
    }

    @Override
    public boolean tryAdvance(LongConsumer action) {
        // always supply the value, even on termination
        action.accept(value);
        // terminal condition, the value is 1.
        if (value == 1) {
            return false; 
        }
        // non terminal, compute the next value in the sequence.
        value = value % 2 == 0 ? value / 2 : (value * 3 + 1);
        return true;
    }

    @Override
    public long estimateSize() {
        // indicate it's infinite/unknown
        return Long.MAX_VALUE;
    }

    @Override
    public int characteristics() {
        return Spliterator.ORDERED + Spliterator.IMMUTABLE;
    }

    @Override
    public OfLong trySplit() {
        // split not possible.
        return null;
    }

}

/**
 * A LongStream factory that produces a complete Collatz Sequence for a seed value.
 */    
public static final LongStream collatzSequence(long seed) {
    return StreamSupport.longStream(new CollatzSpliterator(seed), false);
}

With the above code, you have now set up a general purpose Collatz Stream that is self regulating, and can be used in any way.

The code is certainly longer than what you have, but, the result is a lot cleaner, and more versatile. Adding terminal conditions to a stream is not well covered in Java8. I would expect that subsequent versions of Java will have a stream stage similar to 'filter(...)' which will be called terminate(...) and will terminate a stream when the given condition is true. Until that arrives, we have to do it ourselves.

Update:

I tried to look around to see if there was a more Java8-ish way to specify the Collatz sequence, and figured the right way to do it was to create a generic class for streams that contain a self-modifying stream.

Given that the Collatz sequence has a well known terminal value (1), I figured that a construct like:

LongStream collatz = LongStreamUtil.inclusiveStream(seed,
         n -> n % 2 == 0 ? n / 2 : (n * 3 + 1),
         t -> t == 1);

would be the right way to do it.... in other words, create a Long stream that takes a seed value, a function that 'steps' the value, and a terminal condition (and the stream should include the terminating value in the output). This could be adapted to any system, like a long 'range' of alternate (in this case odd) numbers up to 101 ...:

LongStream incrementing = LongStreamUtil.inclusiveStream(1, n -> n + 2,  t -> t >= 101);

So, here's a general purpose utility class that produces a LongStream starting at a given value, and terminating at a given condition, and applying a stepper function each time...:

import java.util.Arrays;
import java.util.Spliterator;
import java.util.function.LongConsumer;
import java.util.function.LongPredicate;
import java.util.function.LongUnaryOperator;
import java.util.stream.LongStream;
import java.util.stream.StreamSupport;


public class TerminalLongStream {

    private static class LongSpliterator implements Spliterator.OfLong {

        private final LongPredicate terminal;
        private final LongUnaryOperator operator;
        private long value;
        private boolean inclusive;

        public LongSpliterator(long seed, LongUnaryOperator operator, LongPredicate terminal, boolean inclusive) {
            this.terminal = terminal;
            this.operator = operator;
            this.value = seed;
            this.inclusive = inclusive;
        }

        @Override
        public int characteristics() {
            return Spliterator.IMMUTABLE + Spliterator.ORDERED;
        }

        @Override
        public long estimateSize() {
            return Long.MAX_VALUE;
        }

        @Override
        public java.util.Spliterator.OfLong trySplit() {
            // do not support splitting
            return null;
        }

        @Override
        public boolean tryAdvance(LongConsumer consumer) {
            if (inclusive) {
                consumer.accept(value);
                if (terminal.test(value)) {
                    return false;
                }
                value = operator.applyAsLong(value);
                return true;
            }

            if (terminal.test(value)) {
                return false;
            }

            consumer.accept(value);
            value = operator.applyAsLong(value);
            return true;
        }

    }

    public static final LongStream inclusiveStream(long init, LongUnaryOperator modifier, LongPredicate terminalvalue) {
        return StreamSupport.longStream(new LongSpliterator(init, modifier, terminalvalue, true), false);
    }

    public static final LongStream exclusiveStream(long init, LongUnaryOperator modifier, LongPredicate terminalvalue) {
        return StreamSupport.longStream(new LongSpliterator(init, modifier, terminalvalue, false), false);
    }

    public static void main(String[] args) {
        long[] data = inclusiveStream(101, n -> n % 2 == 0 ? n / 2 : (n * 3 + 1), t -> t == 1).toArray();
        System.out.println(Arrays.toString(data));
    }
}
\$\endgroup\$
  • \$\begingroup\$ Update to include more generic solution. \$\endgroup\$ – rolfl Sep 24 '14 at 21:25
  • \$\begingroup\$ Thanks for your suggestion, and confirming my suspicion that using anyMatch() may solve the problem but it's not really the right approach. Plenty more to learn for me. :) \$\endgroup\$ – h.j.k. Sep 26 '14 at 16:08
10
\$\begingroup\$

I wouldn't obfuscate to &#8594;. Google Java Style says

Never make your code less readable simply out of fear that some programs might not handle non-ASCII characters properly. If that should happen, those programs are broken and they must be fixed.

and I can only agree.


I'm rather unfamiliar with Java 8, but

    final AtomicLong c = new AtomicLong();
    LongStream.iterate(value, (v) -> c.incrementAndGet() > 0 && v % 2 == 0 ? v / 2 : 3 * v + 1)
            .anyMatch(v -> c.longValue() > 1 && v == 1);

looks pretty weird. It's not really functional, because of the side effects and it took me a while to grasp.


Using AtomicLong as a plain long holder is wrong. It's confusing (what do you need atomicity for?) and it's slow on a multicore CPU as it does quite some needles work. A plain new long[1] is way better.


While rolfl showed us, how to get the streams right, I'd argue that it should not be done at all. While functional programming is cool and this is a nice exercise, the lesson learned should be that there are problems which can be solved much simpler in a different way.

public static long stepsFor(long value) {
    checkArgument(value > 0, "Input must be greater than 0.");
    for (int i=1; ; ++i) {
        value = (value & 1) == 0 ? value >> 1 : 3*value + 1;
        if (value==1) return i;
    }
}

Untested, possibly off-by-one, but who cares... my points are:

  • use Preconditions or whatever simplifies the checks
  • always look for simpler alternatives
  • don't do the optimizations I did, as it may get unclear and error-prone ;)
\$\endgroup\$
  • \$\begingroup\$ Once again, thanks for your suggestions! AtomicLong was used merely to have a 'fluent' way of keeping a count, since only final variables may be used within the lambda. Will bear in mind the potential performance issues associated with it! \$\endgroup\$ – h.j.k. Sep 26 '14 at 16:10
  • 1
    \$\begingroup\$ @h.j.k. You're welcome. A final int[1] does the job better than AtomicLong. \$\endgroup\$ – maaartinus Sep 26 '14 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.