2
\$\begingroup\$

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";
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Jerry Coffin Nov 4 '16 at 16:02
2
\$\begingroup\$

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
\$\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.