Jolly jumpers programming challenge

Question

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";
 }
 }
}

• Jerry Coffin: 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.

Answer 1

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