CODEWITHSUNDEEP
algorithm
Erik Hosszú
Erik Hosszú

Reputation: 65

Pattern finder algorithm

I would like to write an algorithm that is capable of detecting any pattern and determining the next element. Some examples would be 11 22 11 22 1 where the next element is 1.

But it could also be 3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1 (1x3 , 4x1, 3x3, 3x1, 3x3, 4x1) where the next element would be 3.

So it always goes like: 3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1 3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1

We do not know how long the pattern is but we know that it appears at least once in the array. We also know that there is only one pattern and 100% of it is inside the array.

It might be useful to imagine the numbers as colors and the array would be a wall with a repeating wallpaper on it. And so our task is to determine what color would the wall be if it had continued.

How should I get started?

Upvotes: 0

Views: 868

Answers (2)

MrSmith42
MrSmith42

Reputation: 10151

You could search for the longest suffix that you can find anywhere else in the string. Than simply add the character that stands behind the suffix at this other location.

Example 3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1

We can fin the following suffixes in other places of the sequence (than at the end)

1            (found at a lot of positions)   
1 1          (found at a lot of positions)  
1 1 1        (found at a lot of positions)  
1 1 1 1      (found at position 1)  
3 1 1 1 1    (found at position 0)  
3 3 1 1 1 1  (does not appear anywhere in the sequence except at  the end)

So the Longest suffix is 3 1 1 1 1 and it is followed by 3. 

3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1  
xxxxxxxxx ^

So the estimation-rule for the next character is 3 .

Upvotes: 1

Briguy37
Briguy37

Reputation: 8402

As long as the pattern always repeats throughout the array, you can just start testing patterns of ascending length from the beginning of the array to the end, moving to the next higher length upon a failure until the whole array has been checked, returning the shortest successful pattern.

Something like the following (untested) JavaScript code:

var findShortestRepeatingPattern = function(array){
  var pattern = [];

  for(var patternLength = 0; patternLength < array.length; length++){
    pattern = []
    var arrayCursor = 0;

    //Build the pattern from the start of the array
    while(arrayCursor < patternLength){
      pattern.push(array[arrayCursor++]);
    }

    //Test the pattern on the remainder of the array
    var patternMatches = true;
    while(arrayCursor < array.length){
      if(pattern[arrayCursor % patternLength] != array[arrayCursor++]){
        patternMatches = false;
        break;
      }
    }

    //Exit if the pattern matches
    if(patternMatches){
      break;
    }
  }

  return pattern;
};

Then, the next expected value should be the patternValue at index insertIndex mod patternLength.

Upvotes: 1

Related Questions