%%%%%%%%%%%%
V1 = [0,8,1,0,0,0,8,6,7,8,9,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,9,1,1,3,0];
V2 = [1,0,0,0,8,6,7,8,9,1,3,0,0,8,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,9,1];
V3 = [1,0,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,0,0,8,6,7,8,9,1,3,0,0,8,9,1];
V4 = [1,0,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,0,0,8,6,7,8,9,-1,3,0,0,8,9,1]; % An additional vector that doesn't contain the pattern

12

A12BC
2BCA1

v[idx]==1 && v[idx+1]==2

v[F(idx, N)]==1 && v[F(idx+1,N)]==2

ekt_bear:

My solution (written in Matlab/Octave):

http://pastebin.com/hLs62DE9

And here is the result:



The four test vectors look like:

%%%%%%%%%%%%
V1 = [0,8,1,0,0,0,8,6,7,8,9,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,9,1,1,3,0];
V2 = [1,0,0,0,8,6,7,8,9,1,3,0,0,8,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,9,1];
V3 = [1,0,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,0,0,8,6,7,8,9,1,3,0,0,8,9,1];
V4 = [1,0,5,2,6,3,0,7,4,1,1,0,0,7,0,0,8,6,7,8,9,5,0,0,8,6,7,8,9,-1,3,0,0,8,9,1]; % An additional vector that doesn't contain the pattern

We find the location of the correct starting "1" for V1, V2 and V3 (namely, entries 34, 10, and 30), and the code returns a -1 when it cannot find the pattern in V4.

At least, I think this is the correct solution if I've understood the problem properly

 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Basically doing a modulo shift so the integer k remains within 1, n
% I'm being a bit lazy since the following code won't work for k=3n for example.
% Sufficient for solving this problem though.
%%%%%%%%%%%%%%%%%%%%%%
function shifted = shift(k, n)
    if k > n
        shifted= k-n;
    else
        shifted= k;
    end
end

Beaf:

^
My solution is similar to whoelse's, but much more efficient. He just needs a couple of optimisations to remove the need to repeat the loop.
Both of you have offered solutions which are useful, but have weaknesses; his is more robust, only because the pattern array can be a random size.

That said, I still haven't tested whoelse's entry for any gotcha's.

. . .and talking about ways of cheating and getting around the no nested loop requirement? Lol! Someone already attempted that with recursion!
In fact, I'm going to edit the article to clarify that there must be no recursion or tricks like labels and gotos.

% Getting a double loop
N=3;

for i=1:N^2 
  j = ceil(i/N);
  k = mod(i-1, N)+1;
  [j,k]
  % Call some function f(j,k) here that does whatever I wanted to do
end

for j=1:N,
  for k=1:N
    [j,k] % Same as above
  end
end

Your solution is very similar to one of mine and with less code too! So, tentatively we give it to. . . Hehe!!!
I'm gonna check your output to see that I've not missed out anything (no coding tools on this laptop).

My solution is similar to whoelse's, but much more efficient. He just needs a couple of optimisations to remove the need to repeat the loop.
Both of you have offered solutions which are useful, but have weaknesses; his is more robust, only because the pattern array can be a random size.

Are you able to do it in N steps rather than the 2N he uses? This is the only other substantial area of improvement. But I don't think it is possible to do it in N steps. . . you sort of have to double the original array one way or another (something akin to what he did.)

If you (or anyone else) can do it in N steps, I'd want to see that.

  public static int Check(int[] searchArray, int[] fullArray)
        {
            int j = 0;
            int result = -1;
            for (int i = 0; i < fullArray.Length; )
            {
                int x = i + j;
                if (x >= fullArray.Length) x -= fullArray.Length;
                if (fullArray[x] == searchArray[j])
                {
                    j++;
                }
                else
                {
                    j = 0;
                    i++;
                }
                if (j >= searchArray.Length)
                {
                    result = i;
                    break;
                }
            }

            return result;
        }

private Collection<int> foundPosCollection = new Collection<int>();

private void PatternSearch(int[] patternArray, int[] searchArray)
    {
        int foundPos = -1;
        int foundPosExtendedMode = -1;
        int currSearchElementPos = 0;//current index of searchArray being tested
        int currExtendedModeSearchElementPos = 0;//current index of searchArray being tested in extended mode
        int maxExtendedCycles = 0;
        int patternArrayLength = patternArray.Length;
        bool isLoopInExtendedMode = false;

        for (int i = 0; i < searchArray.Length; i++)
        {
            if (patternArray[0] == searchArray[i])
            {
                //get the number of elements by which our pattern must spill over the upper bound of the
                //array we are searching for a match to be found.
                int spillover = ((i + patternArrayLength) - searchArray.Length);
                if (spillover > 0)
                {
                    foundPosExtendedMode = i;
                    isLoopInExtendedMode = true;
                }
                else
                {
                    isLoopInExtendedMode = false;
                    currExtendedModeSearchElementPos = 0;
                }

                foundPos = i;
                currSearchElementPos++;
                continue;
            }

            //perform overlapping mode specific search
            if (isLoopInExtendedMode)
            {
                currExtendedModeSearchElementPos++;//set index of next element to be tested
                if (i == (searchArray.Length - 1))
                {
                    //get number of elements left to match
                    maxExtendedCycles = (patternArrayLength - 1) - currExtendedModeSearchElementPos;
                    i = -1;//reset the loop and start over (we use -1, cos i is going to be incremented in the loop declaration
                    continue;
                }

                if (currExtendedModeSearchElementPos == (patternArrayLength - 1))
                {
                    foundPosCollection.Add(foundPosExtendedMode);//add to found positions
                }
                if (i == (maxExtendedCycles - 1))
                {
                    //reset and break
                    foundPos = -1;
                    currSearchElementPos = 0;//current index of searchArray being tested
                    currExtendedModeSearchElementPos = 0;//current index of searchArray being tested in extended mode
                    maxExtendedCycles = 0;
                    patternArrayLength = patternArray.Length;
                    isLoopInExtendedMode = false;
                    break;
                }
            }

            //perform regular specific search
            if (currSearchElementPos > 0)
            {
                if (patternArray[currSearchElementPos] == searchArray[i])
                {
                    if (i + 1 == searchArray.Length)
                    {
                    }
                    //report a find if we have successfully tested to the last element
                    if (currSearchElementPos == (patternArrayLength - 1))
                    {
                        foundPosCollection.Add(foundPos);//add to found positions
                        currSearchElementPos = 0;
                        continue;//you can break here, if you are sure there's only a single occurrence of the pattern
                    }

                    currSearchElementPos++;
                }
                else
                {
                    //set to zero if there is no match
                    foundPos = -1;
                    currSearchElementPos = 0;
                }
            }
        }
    }

ekt_bear:

Are you able to do it in N steps rather than the 2N he uses? This is the only other substantial area of improvement. But I don't think it is possible to do it in N steps. . . you sort of have to double the original array one way or another (something akin to what he did.)

If you (or anyone else) can do it in N steps, I'd want to see that.

ekt_bear:

You could always manufacture a nested loop from a single one, just using the ceil function and the modulo function:

% Getting a double loop
N=3;

for i=1:N^2 
  j = ceil(i/N);
  k = mod(i-1, N)+1;
  [j,k]
  % Call some function f(j,k) here that does whatever I wanted to do
end

for j=1:N,
  for k=1:N
    [j,k] % Same as above
  end
end

 public static int Check(int[] searchArray, int[] fullArray)
       {
           int j = 0;
           int result = -1;
           for (int i = 0; i < fullArray.Length; )
           {
               int x = i + j;
               if (x >= fullArray.Length) x -= fullArray.Length;
               if (fullArray[x] == searchArray[j])
               {
                   j++;
               }
               else
               {
                   j = 0;
                   i++;
               }
               if (j >= searchArray.Length)
               {
                   result = i;
                   break;
               }
           }

           return result;
       }

whoelse:

Not yet giving it to me?

Thought making it a lil bit clearer wouldn't be a bad idea.

Funny, just as i was about trying it out, I got an even better response from someone else I showed the question.

  public static int Check(int[] searchArray, int[] fullArray)
        {
            int j = 0;
            int result = -1;
            for (int i = 0; i < fullArray.Length; )
            {
                int x = i + j;
                if (x >= fullArray.Length) x -= fullArray.Length;
                if (fullArray[x] == searchArray[j])
                {
                    j++;
                }
                else
                {
                    j = 0;
                    i++;
                }
                if (j >= searchArray.Length)
                {
                    result = i;
                    break;
                }
            }

            return result;
        }

BTW Beaf, a very cool thread for the programming section. The fact that peeps post in different languages might just encourage some of us to pick up another language.

ekt_bear:

. . . . in hindsight it is obvious. N iterations (rather than 2N or NM), short and simple.

Beaf:

^
Wow! Nice terse solution!
The solution is to see the array as a wheel that can be turned in one revolution or more by resetting the loops current index.
The above solution is basically what I've got, though I'm more verbose. I believe my solution will work for multiple occurences of the pattern in a single array as well (not tested tho), and random pattern and search array sizes. Here goes (feel free to burst my bubble ):

private Collection<int> foundPosCollection = new Collection<int>();

private void PatternSearch(int[] patternArray, int[] searchArray)
    {
        int foundPos = -1;
        int foundPosExtendedMode = -1;
        int currSearchElementPos = 0;//current index of searchArray being tested
        int currExtendedModeSearchElementPos = 0;//current index of searchArray being tested in extended mode
        int maxExtendedCycles = 0;
        int patternArrayLength = patternArray.Length;
        bool isLoopInExtendedMode = false;

        for (int i = 0; i < searchArray.Length; i++)
        {
            if (patternArray[0] == searchArray[i])
            {
                //get the number of elements by which our pattern must spill over the upper bound of the
                //array we are searching for a match to be found.
                int spillover = ((i + patternArrayLength) - searchArray.Length);
                if (spillover > 0)
                {
                    foundPosExtendedMode = i;
                    isLoopInExtendedMode = true;
                }
                else
                {
                    isLoopInExtendedMode = false;
                    currExtendedModeSearchElementPos = 0;
                }

                foundPos = i;
                currSearchElementPos++;
                continue;
            }

            //perform overlapping mode specific search
            if (isLoopInExtendedMode)
            {
                currExtendedModeSearchElementPos++;//set index of next element to be tested
                if (i == (searchArray.Length - 1))
                {
                    //get number of elements left to match
                    maxExtendedCycles = (patternArrayLength - 1) - currExtendedModeSearchElementPos;
                    i = -1;//reset the loop and start over (we use -1, cos i is going to be incremented in the loop declaration
                    continue;
                }

                if (currExtendedModeSearchElementPos == (patternArrayLength - 1))
                {
                    foundPosCollection.Add(foundPosExtendedMode);//add to found positions
                }
                if (i == (maxExtendedCycles - 1))
                {
                    //reset and break
                    foundPos = -1;
                    currSearchElementPos = 0;//current index of searchArray being tested
                    currExtendedModeSearchElementPos = 0;//current index of searchArray being tested in extended mode
                    maxExtendedCycles = 0;
                    patternArrayLength = patternArray.Length;
                    isLoopInExtendedMode = false;
                    break;
                }
            }

            //perform regular specific search
            if (currSearchElementPos > 0)
            {
                if (patternArray[currSearchElementPos] == searchArray[i])
                {
                    if (i + 1 == searchArray.Length)
                    {
                    }
                    //report a find if we have successfully tested to the last element
                    if (currSearchElementPos == (patternArrayLength - 1))
                    {
                        foundPosCollection.Add(foundPos);//add to found positions
                        currSearchElementPos = 0;
                        continue;//you can break here, if you are sure there's only a single occurrence of the pattern
                    }

                    currSearchElementPos++;
                }
                else
                {
                    //set to zero if there is no match
                    foundPos = -1;
                    currSearchElementPos = 0;
                }
            }
        }
    }

Call it so:

PatternSearch(patternArray, searchArray3);
PatternSearch(patternArray, searchArray1);
PatternSearch(patternArray, searchArray2);

//Print out for console
for (int i = 0; i < foundPosCollection.Count; i++)
{
   Console.WriteLine("Found at " + foundPosCollection[i].ToString() + "
";
}
Console.ReadLine();

//Print out for web
for (int i = 0; i < foundPosCollection.Count; i++)
{
   Response.Write("Found at " + foundPosCollection[i].ToString() + "
";
}

Otuabaroku:

^^^ I think the code is clean but it is not fit for the purpose. The search function is meant to print or return the position or index of all the occurrences of the pattern in the array and not the total number of occurrences in the array.

Being the killjoy that I am tho, I went and upped the test to include several instances of the search pattern in each test array (two in each), at random positions.
The new arrays are:
0, 8, 1, 0, 0, 0, 8, 6, 7, 1, 3, 0, 0, 8, 3, 0, 7, 4, 1, 1, 0, 0, 7, 0, 0, 8, 6, 7, 8, 9, 5, 9, 1, 1, 3, 0
1, 0, 0, 0, 8, 6, 7, 8, 9, 1, 3, 0, 0, 8, 5, 2, 6, 3, 0, 7, 4, 1, 1, 0, 0, 7, 0, 0, 1, 3, 0, 0, 8, 5, 9, 1
1, 0, 5, 2, 6, 3, 0, 7, 4, 1, 1, 0, 0, 7, 0, 0, 8, 1, 3, 0, 0, 8, 0, 0, 8, 6, 7, 8, 9, 1, 3, 0, 0, 8, 9, 1

All entries failed the test. . . Except the one from here; https://www.nairaland.com/nigeria/topic-675768.32.html#msg8406195
It very correctly reported:
Found at 9
Found at 33
Found at 9
Found at 28
Found at 17
Found at 29



LOL!! I therefore shamelessly award the babe below to my humble self (strictly for the cure of a manly "itch"!