Jolly jumpers programming challenge

I have posted my solution to the jolly jumpers programming challenge(detailed here) for your review:

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the differences between successive elements take on all possible values 1 through n - 1. For instance,

1 4 2 3

is a jolly jumper, because the absolute differences are 3, 2, and 1, respectively. The definition implies that any sequence of a single integer is a jolly jumper. Write a program to determine whether each of a number of sequences is a jolly jumper.

Input

Each line of input contains an integer n < 3, 000 followed by n integers representing the sequence.

Output

For each line of input generate a line of output saying Jolly or Not jolly.

Sample Input

4 1 4 2 3
5 1 4 2 -1 6


Sample Output

 Jolly
Not jolly

//platform specific code
#ifdef WINDOWS
#include "stdafx.h"
#endif // WINDOWS

#include <iostream>
#include <vector>

using std::cout;
using std::cin;
using std::vector;

const int MAX_SEQUENCE_LENGTH = 3000;

int main()
{
bool not_jolly;
vector<int> sequence(MAX_SEQUENCE_LENGTH, 0);
vector<bool> in_sequence(MAX_SEQUENCE_LENGTH, false);
int sequence_length;
while (cin >> sequence_length) {
not_jolly = false;
std::fill(sequence.begin(), sequence.end(), 0);
std::fill(in_sequence.begin(), in_sequence.end(), false);
for (int i = 0;i < sequence_length; i++) {
cin >> sequence[i];
}

for (int i = 1;i < sequence_length; i++) {
in_sequence[abs(sequence[i] - sequence[i - 1])] = true;
}

for (int i = 1;i < sequence_length;i++) {
if (!in_sequence[i]) {
not_jolly = true;
break;
}
}

if (not_jolly == false) {
cout << "Jolly" << "\n";
} else {
cout << "Not jolly" << "\n";
}
}
}

• This code seems to be broken. You allocate in_sequence to be the same size as the maximum sequence length, but use (the absolute value of) a difference between inputs as an index into it. Consider an input of 2 0 5000. This will attempt to write to in_sequence[5000], which doesn't exist. The description says n will be less than 3000, but doesn't place that restriction on the range of the other inputs. – Jerry Coffin Nov 4 '16 at 16:02

The program already looks correct and simple enough, yet there are some thing that can be improved.

First and most important, you should have a unit test for the important part of the program. To extract this part, create a function bool is_jolly(const std::vector<int> &numbers). Then you can easily write a test that calls this function and checks whether the returned value is what you expect.

There is a bug. When the sequence of number contains two numbers whose difference is 2147483648, the abs function will return a negative value, making your program crash. The difference might also be any other number, so you need to check whether the array index is valid. For a start, you could replace array[index] with array.at(index), which throws an exception instead of crashing.

When you loop over an array, the array index should be of type std::size_t instead of it. Enable the compiler warnings, and it will complain about a comparison between signed and unsigned.

Variable names should not contain the word not. Just try to evaluate if (!not_jolly != false) in your head, or the double negation not_jolly == false. It would be easier to read if it were just if (is_jolly) { … }.

Nitpick: after a semicolon, there should be a space (see the for loops).

To use the algorithm std::fill, you have to include its header. From the top of my head, it should be <algorithm>.

When writing a line to the output, you can merge the strings, e.g. std::cout << "Jolly\n"; — the form you are currently using is perfectly fine, I'm just mentioning this as a shorter alternative.

What you did great:

• Indenting your source code consistenly, so that it is easily readable
• Importing only a few names from the std namespace
• Checking for errors when reading from std::cin (at least in one case)
• Writing short and easy to understand code