1

A pattern of the integers 2,1,4 is irregularly repeated in an array of 5000 elements, with rest of the elements in the array being 0. But 2 is always followed by 1, and 1 is always followed by 4, then 2 again and so on...

For example:-

0 0 0 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1 0 0 0 4 0 0 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 4 0 0 0 0 0......and so on.

I want to check if this 2-1-4 pattern is repeated in the array, irrespective of the number of 0's between the elements.

If this pattern, however irregular, is repeated, then I have a correct array. Else I have missed some elements.

How can I go about this ??

Edit:- This be done without traversing the array multiple times with simple C language code.

9
  • 6
    C OR C++ The best answer will differ considerably based on which language it is, so choose one or the other, since they are quite different. Commented Feb 15, 2016 at 10:59
  • 2
    Sound like a job for a state machine. Which begs the question: Is an array that contains only zeros considered to be matching the pattern?
    – user3185968
    Commented Feb 15, 2016 at 11:01
  • 3
    That's counter productive, and makes for a lesser quality question (which is already too broad for SO, even if you do settle for one language). Commented Feb 15, 2016 at 11:08
  • @EOF:- Nope, an array containing only zeroes means absolutely no data is received, and hence deemed incorrect. Commented Feb 15, 2016 at 11:08
  • 1
    @Abhishek: In that case, make the state machine's initial state nonaccepting.
    – user3185968
    Commented Feb 15, 2016 at 11:10

5 Answers 5

3

Your data is in a vector of integers. The solution could be something like (C++11):

std::vector<int> data;
//fill your data here
data.erase(std::remove(data.begin(), data.end(), 0), data.end());
auto is_ok=true;
for(auto it=data.begin();it!=data.end();it=std::advance(it,3)){
    if(*it!=2 && *(std::next(it))!=1 && *(std::advance(it,2))!=4){
        is_ok=false;   
        break;
    }
    if(std::next(it)==data.end() || std::advance(it,2)==data.end()){
          //This is a special case that you should do it by yourself depending on the requirement 
          break;
    }
}
4
  • I'm pretty sure it can be made prettier with some more uses of stuff from algorithm. A repeated use of std::mismatch may make this clearer. Commented Feb 15, 2016 at 11:16
  • 2
    @StoryTeller Feel free to propose an edit or to enhance on it and post it as new answer Commented Feb 15, 2016 at 11:17
  • I'm viewing this through the SE mobile app, won't be doing any editing or answering like this :) Commented Feb 15, 2016 at 11:18
  • This is going to be outrageously slow compared with a simple loop that checks integer values... Consider using C instead.
    – Lundin
    Commented Feb 15, 2016 at 12:50
3

I would go for a function which finds the first mis-matching element; if it finds no mismatch, an end-of-input pointer is returned.

In C:

int *mismatch(int *arr, size_t len)
{
    int expected = 2;
    int *end = arr + len;
    for (; arr < end; ++arr) {
        if (*arr != 0 && *arr != expected) {
            return arr;
        }

        switch (*arr) {
            case 2: expected = 1; break;
            case 1: expected = 4; break;
            case 4: expected = 2; break;
            default: break;
        }
    }
    return arr;
}

A more C++'esque version would not use raw pointers but some iterator type, i.e.. It would also use a range (i.e. an end iterator) instead of a length:

template <typename Iterator>
Iterator mismatch(Iterator begin, Iterator end)
{
    typename Iterator::value_type expected = 2;
    for (; begin != end; ++begin) {
        if (*begin != 0 && *begin != expected) {
            return begin;
        }

        // dito
    }
}

You should also consider what to do with empty sequences (i.e. length zero) or all-zero sequences. Or incomplete sequences (e.g. just 2).

12
  • why a template function though!? Seems a bit excessive. Commented Feb 15, 2016 at 11:27
  • 1
    @Lundin The first snippet would be somewhat inefficient if the sequence of numbers was actually stored as e.g. a std::list or maybe even a custom data structure. The fact that C++ permits efficiently abstracting over types is actually quite useful: note that plain raw iterators are valid random-access-iterators, so the second version would be equivalent to the first in C++ when given plain int* values. Since the OP didn't specify any context, it's not possible to make any assumptions about what's "excessive" or "efficient" or "effective". Commented Feb 15, 2016 at 13:35
  • 1
    @Lundin A container which is ineffective (did you mean to write 'inefficient'?) for this particular operation may still be a good choice overall if the common operations are efficient. For instance, imagine if the input sequence commonly gets insertions/removals in the middle. The bottom line is that the C++ version will be no worse than the C version for data structures which use contiguous memory (e.g. arrays or std::vector), but -- unlike the C version -- it still permits using other containers. Commented Feb 15, 2016 at 14:02
  • 1
    @Lundin Sounds like a plan - let me know what your disassembly inspection yields. Commented Feb 15, 2016 at 14:59
  • 1
    @Lundin Thumbs up for benchmarking! However, it seems that you rather profiled the performance of std::vector than the performance of the function template I sketched. My original claim was that the template is equivalent to the C code when given plain int* pointers. I.e. the code generated is no worse than what the C definition does (but the template permits being used with other containers). Commented Feb 15, 2016 at 18:06
3

Walk the sequence accumulating integers from the set (1, 2, 4), and skipping all other numbers. Every time you have accumulated three numbers, check that you have a (2, 1, 4) sequence. If you do, discard the accumulated numbers, and continue; otherwise, declare the sequence invalid, and stop processing.

Upon reaching the end of the sequence check that you have no accumulated numbers. If you do, make sure that it's either a single number 2, or two numbers (2, 1). Otherwise, the sequence is invalid.

This translates in a very simple program:

bool checkValid(std::vector<int> &data) {
    int acc = 0;
    bool res = false;
    for (auto &n : data) {
        // Skip numbers other than 1, 2, 4
        if (n != 1 && n != 2 && n != 4) {
            continue;
        }
        // Do accumulation in an int
        acc = 10*acc + n;
        // If we reach the target, zero out and continue
        if (acc == 214) {
            acc = 0;
            // Now that we found 2, ... , 1, ..., 4,
            // the sequence may be considered valid,
            // unless we find an error later on.
            res = true;
            continue;
        }
        // Check if the partial accumulation is valid
        if (acc != 2 && acc != 21) {
            return false;
        }
    }
    return res;
}
10
  • 1
    Read the question again. The sequence 214 can have a padding of 0s amongst them so 20000100004 is also valid for example.
    – siphr
    Commented Feb 15, 2016 at 11:05
  • Ah, I get it. Nice one +1.
    – siphr
    Commented Feb 15, 2016 at 11:08
  • 1
    What if the array ends while you are not in an accepting state? I'd write an explicit state machine, easier to reason about.
    – user3185968
    Commented Feb 15, 2016 at 11:09
  • 2
    @EOF Of course, state machine is the first thing that comes to mind when one sees a problem like this. However, I suspect that OP may not have enough theoretical background to reason about this problem in terms of a state machine, let alone independently implementing even a small state machine. That's why I decided against swatting this particular fly with a sledgehammer, even though theoretically that would be the most efficient way. Commented Feb 15, 2016 at 11:15
  • I'm with EOF. This is a good learning example how to use state machines. Drawing it is trivial. The basic flow is Initial -> 2 -> 1 -> 4(Accepted) with obvious alternative flows to NotAccepted, a link back from 4 to 2 (when the pattern repeats itself), and formally a idempotent transition for input 0 (i.e. no state change).
    – MSalters
    Commented Feb 15, 2016 at 11:32
2

The easy way would be to read each element of the array in a loop and store the last interesting element (2, 1 or 4) in a temp variable. And when another interesting element occurs, you check is this is the one you want, you continue, else, your array is bad.

int isArrayBad(int * array, int arraySize)
{
int temp = 0;
for(int i = 0; i<arraySize; i++)
{
    if(!temp && array[i])
        temp = array[i];
    else if(array[i])
    {
        switch(temp)
        {
        case 2:
            if(array[i] != 1)
                return -1;
            break;
        case 1:
            if(array[i] != 4)
                return -1;
            break;
        case 4:
            if(array[i] != 2)
                return -1;
            break;
        }
        temp = array[i];
    }
}
return 0;
}
2
  • Yes, will try this. Please vote-up though... Commented Feb 15, 2016 at 11:15
  • Implemented this snippet and moving ahead...Thanks a lot!! Commented Feb 16, 2016 at 7:16
2

I wrote this, but IMO the better way would be to (1) filter the array by creating a new one without the zeros or unwanted values, and (2) one pass through the new array, comparing against (x, y, z) as a circular linked list.

$ g++ main.cc -o main && ./main

// main.cc
#include <stdio.h>

class Checker {
private:
  static int pattern[];
  static int* const lastElem;
  static int ignore;
  int* next;
  int* advance(int*);
public:
  Checker();
  bool isCorrect(int* const, int* const);
};

int Checker::pattern[] = {2, 1, 4};
int* const Checker::lastElem = &pattern[2];
int Checker::ignore = 0;

Checker::Checker() {
  next = &pattern[0];
}

int* Checker::advance(int* cursor) {
  if(cursor != lastElem) {
    return ++cursor;
  }
  return &pattern[0];
}

bool Checker::isCorrect(int* const begin, int* const end) {
  for(int* pArr = begin; pArr != end; ++pArr) {
    if(*pArr == ignore) {
      continue;
    }

    if(*pArr != *next) {
      return false;
    }

    next = advance(next);
  }
  return true;
}

int main(int argc, char** argv) {
  int testArr[] = {0, 0, 0, 2, 0, 1, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 4};
  Checker test;
  bool res = test.isCorrect(testArr, &testArr[sizeof(testArr)/sizeof(testArr[0])]);
  printf("Test: %s\n", res ? "passed" : "failed");
  return 0;
}

fast as hell

Not the answer you're looking for? Browse other questions tagged or ask your own question.