Circular Array Shift

[dakotad8218]

Did some searching but couldn't find anything helpful. Trying to write a helper function for a project that basically verifies if two arrays are in the same circular order (i.e. 1,2,3,4 would be the same as 4, 1, 2, 3 but not 3, 2, 1, 4). I'm trying to write it so that it'll basically turn 1,2,3,4 into 4,1,2,3 so I can check that they're identical in a loop and keep doing this until I've exhausted the length of the array. For some reason, however, I get 4, 2, 3, 4 as output when parsing 1,2,3,4.

I tried using

a[i] = a[i - 1];

But that just replaces the entire array with the 0 value.
Let me know if anyone can help.

  /** Shifts all elements one position upwards and 
 * moves final element to 0 index
 * @param int a[] (array to modify)
 * @param int size (size of array)
*/

void shift(int a[], int size)
{
    int i;
    int last = a[size - 1];
    
    for(i = size - 1; i > size; i--)
    {
        a[i] = a[i - 1];      
        
        
    }
    a[0] = last;
    
}

[dakotad8218]

Oh, wait, I think I figured it out myself. Can anyone verify this is correct? Seems to compile correctly in visual studio and provides the desired output (4, 1, 2, 3) from (1, 2, 3, 4).

/** Shifts all elements one position upwards and 
 * moves final element to 0 index
 * @param int a[] (array to modify)
 * @param int size (size of array)
*/

void shift(int a[], int size)
{
    int i;
    int j = size - 1;
    int last = a[j];
    
    for(i = 0; i < size; i++)
    {
        a[j] = a[j-1];
        j--;
        
        
    }
    a[0] = last;
    
}

[Duthomhas]

That works. You can also use the Standard Library rotate algorithm:
http://www.cplusplus.com/reference/algorithm/rotate/

#include <algorithm> 

std::rotate( a, a + size - 1, a + size )  // == shift( a, size )  

That said, actually rotating an array some N times is going to get really inefficient, really fast. If all you want is to check for two arrays being circularly equal, you can avoid a lot of it even with a very naïve algorithm:

#include <iostream>

template <typename T>
bool is_circular_equal_helper( const T* a1, const T* a2, int size, int offset )
{
  // Look for mismatches with wraparound on a2[]
  for (int n = 1; n < size; n++) // starting with 1 because we already know that a1[0] == a2[0+offset]
    if (a1[n] != a2[(n+offset)%size])
      return false;
  // No mismatches means a1 == a2 with offset
  return true;
}

template <typename T>
bool is_circular_equal( const T* a1, const T* a2, int size )
{
  // Empty arrays are circularly equal
  if (size == 0) return true;
  
  // Find each instance of a1[0] in a2[]
  for (int n = 0; n < size; n++)
    if (a1[0] == a2[n])
    {
      // Compare arrays
      if (is_circular_equal_helper( a1, a2, size, n ))
        return true;
    }
  // No circular matches
  return false;
}

Here is something to help play with it:

#include <ciso646>
#include <sstream>
#include <string>
#include <vector>

std::vector<int> read_vector( const std::string& prompt )
{
  std::cout << prompt;

  std::string s;
  getline( std::cin, s );
  std::istringstream ss( s );

  std::vector<int> xs;
  int x;
  while (ss >> x) xs.push_back( x );
  return xs;
}

int main()
{
  auto a1 = read_vector( "first array?  " );
  auto a2 = read_vector( "second array? " );
  
  if ((a1.size() == a2.size()) and
      is_circular_equal( a1.data(), a2.data(), a1.size() ))
    std::cout << "The arrays can be rotated to be equal.\n";
  else
    std::cout << "The arrays are unequal.\n";
}

Hope this helps.

[dakotad8218]

Oh, fun, new issues.

There seems to be a problem with my really simple boolean return function that checks to see if the elements in two arrays are in the same order and in the same position.

/**Determines if the elements of two arrays are in the exact same order
 * @param int a[] (first array)
 * @param int b[] (second array)
 * @param int size (size of array)
*/
bool exact_order(int a[], int b[], int size)
{
    bool result = false;

    for(int i = 0; i < size; i++)
    {
        if(a[i] == b[i])
        {
            result = true;
        }
    }
  
    return result;
    
}

I tested it using something like this. With these element values in a[] and b[], it outputs "Exact Same Order"

int main()
{
    const int SIZE = 4;
    int a[] = {1, 2, 3, 4};
    int b[] = {3, 2, 4, 1};

    
    if(exact_order(a, b, SIZE))
    {
        cout << endl << "Exact Same Order";
    }
    else
    {
        cout << endl << "Not same order";
    }
    
}

Just when I got the tricky part figured out, the simple one comes back to bite me!

[dakotad8218]

Jeez, figured it out for myself again. Aren't you guys glad you get a play-by-play of my mental struggles?

bool exact_order(int a[], int b[], int size)
{
    bool result = true;

    for(int i = 0; i < size; i++)
    {
        if(a[i] != b[i])
        {
            result = false;
        }
    }
  
    return result;
    
}

Figured out that even one element was identical, it would return true, even if the others were not. Switched it around to assume true until conditional proved otherwise and it works like a charm.

[Duthomhas]

When my brain is being that stupid I take a break.

Go get a good hamburger or something and sit outside for a while and enjoy it.

^{_{Social distancing!}}

[dakotad8218]

Yeah, I wish I could, I just have a ton of homework that's due by midnight and C++ isn't exactly my strong suit lol. It's taken me like 5 hours just to come up with this, and this is just one of the 6 problems I have to figure out. Next is a 2 player tic-tac toe game.

#include <iostream>

using namespace std;



/** Prints all elements of an array with comma separators
 * @param int a[] (array to be printed)
 * @param int size (size of array to be printed)
*/

void print_array(const int a[], const int size)
{
    for(int i = 0; i < size; i++)
    {
        if(i > 0)
        {
            cout << ", ";
        }
        cout << a[i];
    }
}

/** Shifts all elements one position upwards and 
 * moves final element to 0 index
 * @param int a[] (array to modify)
 * @param int size (size of array)
*/

void shift(int a[], int size)
{
    int i;
    int j = size - 1;
    int last = a[j];
    
    for(i = 0; i < size; i++)
    {
        a[j] = a[j-1];
        j--;
    }
    a[0] = last;
    
}

/**Determines if the elements of two arrays are in the exact same order
 * @param int a[] (first array)
 * @param int b[] (second array)
 * @param int size (size of array)
*/
bool exact_order(int a[], int b[], int size)
{
    bool result = true;

    for(int i = 0; i < size; i++)
    {
        if(a[i] != b[i])
        {
            result = false;
        }
    }
  
    return result;
    
}

/**Determines if elements in 2 arrays are both in the same circular order
 * @param int a[] (first array)
 * @param int b[] (second array)
 * @return result (true/false)
*/

bool circular(int a[], int b[], int size)
{
    bool result = false;

    if(exact_order(a, b, size))
    {
        result = true;
    } 
    else 
    {
        for(int i = 0; i < size; i++)
        {
            shift(b, size);
            if(exact_order(a, b, size))
            {
                result = true;
            }
        }
        
    }
    
    
    return result;
}

int main()
{
    const int SIZE = 4;
    int a[] = {1, 2, 3, 4};
    int b[] = {2, 3, 4, 1};

    
    if(circular(a, b, SIZE))
    {
        cout << "Circular Order!";
    }
    else 
    {
        cout << "Not Circular Order!";
    }
    
}