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

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