2
\$\begingroup\$

Disclaimer, I'm new to OOP, but have experience in haskell and javascript.

Essentially, the challenge was to create a program which would shift an array a given amount of times to the left and then print the result.

I've tried to make this more extendable by allowing the option to shift to the right.

My code is

#include <iostream>
#include <vector>

using namespace std;

vector<int> rotate(vector<int> myVector, int direction, int count);
vector<int> rotate(vector<int> myVector, int direction);
void print(vector<int> rotatedVector);



void print(vector<int> rotatedVector){
    for(int i = 0; i < rotatedVector.size(); i++){
        cout << rotatedVector[i] << endl;
    }
}

vector<int> rotate(vector<int> myVector, int direction, int count){

    while(count > 0){
        myVector = rotate( myVector,  direction); // should I create a new variable, or just overwrite myVector each time?
        --count;
    }

    return myVector;
}

vector<int> rotate(vector<int> myVector, int direction){

    const int length = myVector.size();

    vector<int> rotatedVector(length);

    for(int i = 0; i < myVector.size(); i++){
        rotatedVector.at(i) = myVector.at((length+i-direction)%length);
    }

    return rotatedVector;
}


int main(){

    // Array to rotate
    int arr[5] = {1,2,3,4,5};

    // Times to rotate
    const int count = 2;


    // Creating a vector object out of array
    // Should I have worked with the array given? 
    int n = sizeof(arr) / sizeof(arr[0]); 
    vector<int> myVector(arr, arr + n); 

    enum direction  {left = -1, right = 1}; // should this be global? 

    myVector = rotate(myVector, left, count);

    print(myVector);

    // Could potentially turn vector back into array? 

    return 0 ;
}

My design questions are...

  1. Is this extendable enough, how could it be made more so?

  2. Should the enums be made global?

  3. Should I have used multiple functions instead of using enums to make the rotation functions generic? (e.g a right rotation function, and a left one)

  4. Should I have kept with the array, instead of creating a vector from it?

  5. Was overloading the function necessary?

The most important thing I would like to clarify from this review, is the concept of "state" in these types of programming puzzles (done in C++/OOP)

The line which overwrites the vector is...

myVector = rotate( myVector,  direction);

Is it better form to perhaps implement something like...

myVector.rotate(direction);

and thus action on the same object each time? (and if so why)

When would I use one over the other?

In my head, I feel as though it would be best to make the vector immutable and keep creating a new one each time, but am unsure and slightly confused about which one to use.

\$\endgroup\$
  • \$\begingroup\$ Do you have to actually rotate the array, or is just printing it rotated enough? \$\endgroup\$ – Deduplicator Jul 28 '19 at 0:56
1
\$\begingroup\$

Of your questions, I think

  1. Should I have kept with the array, instead of creating a vector from it?

is the most fundamental. Changing data structures might be a code smell. In C++ Arrays are immutable and the reasons for using them often involve execution speed via static allocation at compile time and idempotency in concurrent execution.

Function Design

The encapsulation of the array as a vector avoids the quagmire of shared access in a concurrent environment. But the original array data type already solves that.

On the other hand, conversion to a vector does not preserve the performance profile of the underlying data type.

To put it another way, in the absence of knowledge about the reasons for using arrays in the part of the system that is calling rotate, working with the arrays rather than vectors is a conservative engineering choice.

Alternative design

Arrays make the problem one of pointer manipulation. One feature of the array abstraction is built in pointers.

// Pseudo code
// one indexed array
rotate(array, n){
  print(array[n+1] to array.length + 
        array[1] to array[n];
}

Context

Coming from Javascript, the use of iteration and mutation rather than pointers is not surprising because iteration works on both arrays (as defined in ECMAscript) and the node lists returned by the API's of various browsers. Because node lists can be live, array methods don't always work but iteration always will.

Validation

The code does not validate the value of n relative to the length of the array. There's a design decision about what should happen when the array and n are incompatible. Is printing a message enough? Is something more heavyweight required?

Extending the problem

Adding left rotation doesn't make the code better. So long as shifting left is not part of the specification, it only makes the code more complex. Eliminating the extension removes several of your questions and simplifies the code. Engineering wise: YAGNI.

Building the simplest thing that might work, provides more time for fundamental design practices including testing, data validation, and error handling.

Types

The code may break if tested against types other than int. As specified the problem can't assume that it won't be fed other data types. The vector could be <T> (generic). This might be a place where the Robustness principle/Postel's Law might be relevant.

Remarks

Keep in mind that it's ok to write C++ code that looks like it was written by someone without years of C++ experience. Haskell and Javscript are rarely used for problems where C++ excels. They are so very different. C++'s idioms don't translate to either very well...but it's probably good to reason about types in C++ based on Haskell experience.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

There are two basic ways to solve this type of problem. One is having to do the rotation in place, where you can't allocate additional storage for a copy of the array. This uses less memory but takes longer, since the rotations have to go by small increments (usually 1, since that is easiest to implement). The other way is to do the rotation into a copy. This has the advantage of being faster but can take additional memory. Your implementation is a hybrid of both.

Don't write using namespace std;.

You're passing all your vectors by value, which will result in copies being made. Since you're making a new vector to store the rotated vector in, you can pass them by const &. For example,

std::vector<int> rotate(const std::vector<int> &myVector, int direction);

print can take advantage of range based for loops:

void print(const vector<int> &rotatedVector) {
    for (int v: rotatedVector){
        std::cout << v << '\n';
    }
}

This also avoids using endl, since that will do a flush which can greatly slow the rate output is displayed.

Your two parameter rotate function can rotate by more than one element at a time. You can combine the two rotate functions into one, with an offset of -direction * count instead of -direction. (With appropriate code to precalculate that value and a check so that the result is not larger than -length to avoid having a negative number on the left of %.)

| improve this answer | |
\$\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.