14
\$\begingroup\$

This question was recently asked: Determining if three numbers are consecutive

It intrigued me, even though it was broken. I have the following implementation I thought would be interesting, and I am looking for reviews on readability, usability, and for any edge cases it may miss, etc.

/**
 * Determine whether three <code>int</code> values can be arranged in to an incrementing sequence.
 * 
 * @param a the first value
 * @param b the second value
 * @param c the third value
 * @return true if there is an order of the three inputs which makes them sequential
 */
public static final boolean isSequential(int a, int b, int c) {
    final int x = Math.abs(a - b);
    final int y = Math.abs(b - c);
    final int z = Math.abs(a - c);
    return x + y + z == 4 && x * y * z == 2;
}

I put this together in a unit test. Here's the full file:

import org.junit.Assert;
import org.junit.Test;

public class ThreeInARow {

    /**
     * Determine whether three <code>int</code> values can be arranged in to an incrementing sequence.
     * 
     * @param a the first value
     * @param b the second value
     * @param c the third value
     * @return true if there is an order of the three inputs which makes them sequential
     */
    public static final boolean isSequential(int a, int b, int c) {
        final int x = Math.abs(a - b);
        final int y = Math.abs(b - c);
        final int z = Math.abs(a - c);
        return x + y + z == 4 && x * y * z == 2;
    }

    private static final int[] FROM = {Integer.MIN_VALUE, Integer.MIN_VALUE + 3, -5, -4, -3, -2, -1, 
            0, 1, 2, 3, 100, Integer.MAX_VALUE - 2, Integer.MAX_VALUE};


    @Test
    public void testGoodBlocks() {

        for (int f : FROM) {
            int a = f;
            int b = a + 1;
            int c = b + 1;
            Assert.assertTrue(isSequential(a, b, c));
            Assert.assertTrue(isSequential(b, c, a));
            Assert.assertTrue(isSequential(c, a, b));
            Assert.assertTrue(isSequential(b, a, c));
            Assert.assertTrue(isSequential(a, c, b));
            Assert.assertTrue(isSequential(c, b, a));
        }

    }

    @Test
    public void testBadBlocks() {

        for (int f : FROM) {
            int a = f;
            int b = a + 1;
            int c = b + 2;
            Assert.assertFalse(isSequential(a, b, c));
            Assert.assertFalse(isSequential(b, c, a));
            Assert.assertFalse(isSequential(c, a, b));
            Assert.assertFalse(isSequential(b, a, c));
            Assert.assertFalse(isSequential(a, c, b));
            Assert.assertFalse(isSequential(c, b, a));
        }

    }

    @Test
    public void testSpecials() {
        int[][] specials = {
                {0,0,0},
                {1,0,1},
                {0,0,1}
        };
        for (int[] attempt : specials) {
            Assert.assertFalse(isSequential(attempt[0], attempt[1], attempt[2]));
        }
    }

}
\$\endgroup\$
11
\$\begingroup\$

Edge case?

I tried your function with:

Integer.MAX_VALUE
Integer.MIN_VALUE
Integer.MIN_VALUE+1

and it returned true. I don't know if wraparounds are supposed to be accepted or not, but with your function they are.

\$\endgroup\$
  • \$\begingroup\$ Good catch, but I wouldn't care. Most things break near the limits, so I guess, it's acceptable. \$\endgroup\$ – maaartinus Jun 26 '15 at 22:26
  • \$\begingroup\$ Hmmm ... I do care ;-) I added some other extreme test cases, but I did not think of wrap-around cases. I like this answer, and I think it counts... now I have to decide whether it should be solved with code, or documentation, \$\endgroup\$ – rolfl Jun 26 '15 at 22:27
  • \$\begingroup\$ Well, someone in the other question used a sort. That would give a different answer than this. So it depends on how you define consecutive. \$\endgroup\$ – JS1 Jun 26 '15 at 22:28
11
\$\begingroup\$

I don't like the idea of having to solve Diophantine equations just to be able to understand the code. I'll suggest the same solution here as I did for @cody.codes:

public static boolean isSequential(int a, int b, int c) {
    int min = Math.min(a, Math.min(b, c));
    int max = Math.max(a, Math.max(b, c));
    return max - min == 2 && a != b && a != c && b != c;
}

"The minimum and maximum differ by 2, and all three numbers are unique" is easier to understand.

\$\endgroup\$
  • \$\begingroup\$ You may want to convert min and max to long so that Integer.MAX_VALUE - Integer.MIN_VALUE (or some other select values) don't break. \$\endgroup\$ – Octavia Togami Jun 27 '15 at 0:37
  • \$\begingroup\$ @KenzieTogami I can't think of any situation where overflow would break this logic, though. \$\endgroup\$ – 200_success Jun 27 '15 at 0:45
  • \$\begingroup\$ I suppose that's true. \$\endgroup\$ – Octavia Togami Jun 27 '15 at 0:48
6
\$\begingroup\$

The expression

x + y + z == 4 && x * y * z == 2;

is a bit code-golfing. Not only are x, y, and z themselves susceptible to overflow for the wrap-around case as JS shows, but you can get unlucky with the multiplication overflowing. A search for such solutions could be a funny exercise.

To make it more funny, the addition can overflow, too.


Your expression could be replaced by

Math.min(x, y, z) == 1 && Math.max(x, y, z) == 2

if we had such three-operand functions. Using Guava, it could be replaced by

ImmutableMultiset.of(x, y, z).equals(ImmutableMultiset.of(1, 1, 2))

which would be pretty inefficient, but it'd exactly express the intention. Finally, you could count the occurrences of 1, just like I did in my answer.


Concerning tests, I'd look at all values around 0, Integer.MAX_VALUE, and maybe Integer.MAX_VALUE/3. This would require a simple surely correct method for determining the result. But given the multiplication overflow problem, such tests are still too weak.

You'd actually need a correctness proof. While the [overflow problem detected by JS] might be seen as a feature or avoided by using long, the multiplication overflow may be worse:

  • it may happen for moderately big numbers
  • it can't be prevented using long
\$\endgroup\$
4
\$\begingroup\$

Ignoring integer wraparound the second condition suffices.

The only way \$x \cdot y \cdot z = 2\$ for \$x,y,z \in \mathbb{N} \$ is if one and only one of \$\{x, y, z\}\$ is equal to \$2\$ and the rest are equal to \$1\$.

If \$\mid\> a-b \mid = 1\$ and \$\mid\> b-c \mid = 1\$ then either \$c = a\$ or \$c = a\pm 2\$.

If \$c = a \pm 2\$ then \$b\$ must be between \$a\$ and \$c\$ since it is equidistant from them both (this is 1D).

\$\endgroup\$
  • \$\begingroup\$ Nicely done, and another really good point. \$\endgroup\$ – rolfl Jun 26 '15 at 23:16
  • \$\begingroup\$ Note that this will identify {Integer.MIN_VALUE, -1, 1} ... ;-) A different edge case. \$\endgroup\$ – rolfl Jun 27 '15 at 0:12
0
\$\begingroup\$

To evade overflow in x + y + z == 4 && x * y * z == 2 (the product may exceed long), check for (x|y|z) == 3. "The other condition" may be x * y * z == 2 or x + y + z == 4 ((x^y^z) == 2 fails for {0, 1, 3}).

\$\endgroup\$

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.