// File: beaf.h

#ifndef BEAF_PROBLEM_I
#define BEAF_PROBLEM_I

/*
 * Description: Function beaf searches [array] for the first occurence 
 *              of the sequence in [pattern].
 *
 * Param      : [array]          array to be searched.
 *            : [pattern]        array containing sequence to search for.
 *            : [ARRAY_LENGTH]   size of [array].
 *            : [PATTERN_LENGTH] size of [pattern].
 *
 * Return     : -1 if [pattern] is not in [array]
 *              else beaf returns the least non-negative index i, 
 *              (0 <=  i < ARRAY_LENGTH) where array[i + m] = pattern[m]
 *              for all 0 <= m < PATTERN_LENGTH.
 */
int 
beaf(const int* const array, 
     const int* const pattern,
     const int ARRAY_LENGTH,
     const int PATTERN_LENGTH)
{
   // size of pattern must not be greater than size of array 
   if(PATTERN_LENGTH > ARRAY_LENGTH)
      return -1;

   // the current index of [pattern] that we are trying to match
   int next = 0;

   for(int i = 0; i < ARRAY_LENGTH; ++i)
   {
      // if all has been matched, return index of first 
      // element that was matched
      if(next == PATTERN_LENGTH)
         return i - PATTERN_LENGTH;

      // move to next element in [pattern] if matching occurs
      if(array[i] == pattern[next])
         ++next;
      // matching does not occur
      else
         // start from the beginning of [pattern] if current element 
         // does not match first element of [pattern]
         next = array[i] == pattern[0] ? 1 : 0;
   }

   return -1;
}

#endif

// File: beaf.cpp
#include <iostream>
#include "beaf.h"

int 
main()
{   
   int pattern[] = {1, 3, 0, 0, 8};
   int beaf_array[3][36] = 
   {
      { 
         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
      },

      {
         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
      },

      {
         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
      }

   };

   for(int i = 0; i < 3; ++i)
   {
      int index = beaf(beaf_array[i], pattern, 36, 5);

      std::cout << "For array " << i << ":\n";
      if(index != -1)
         std::cout << "   Pattern was found at index " 
                   << index << std::endl << std::endl;
      else
         std::cout << "   Pattern was not found.\n\n";
   }

   return 0;
}

   if(PATTERN_LENGTH > ARRAY_LENGTH)
      return -1;

     if(array[i] == pattern[next])
         ++next;

Beaf:

Why do you have this piece of code?

   if(PATTERN_LENGTH > ARRAY_LENGTH)
      return -1;

PATTERN_LENGTH is the length of [pattern] array and [ARRAY_LENGTH] is the length of [array]. I have this in case someone calls the beaf function with invalid code like:

int pattern[] = {1, 2, 3, 4, 4};
int array[] ={4, 7};

int index = beaf(array, pattern, 2, 5). It simply makes certain that the latter is not greater than the former. How will the value always be false if someone sends in wrong values.

Compile and run the code as is (save and copy the first as "beaf.h" and the second as "beaf.cpp":

This is my output on  Ubuntu 11.04 x_86_64 GNU/Linux with g++

omo_to_dun:

You said, "as a unit". Ergo, consecutively. The pattern 1,3,0,0,8 is a subsequence of the first array, but it does not exist as a single unit like you required. Rephrase your question. And also, did you compile it? I hope you are not one of those NLers who just diagnose but have nothing to back it up with. At least, I have shown you my output.

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 [none]
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
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.

If all the bad things you pointed out will happen, then show us, with proof, not words. Maybe you can't compile the code? It shouldn't be too hard, I suppose.

#ifndef BEAF_PROBLEM_I
#define BEAF_PROBLEM_I

/*
 * Description: Function beaf searches [array](with wrapping) for the 
 *              first occurence of the sequence in [pattern]. 
 *
 * Param      : [array]          array to be searched.
 *            : [pattern]        array containing sequence to search for.
 *            : [ARRAY_LENGTH]   size of [array].
 *            : [PATTERN_LENGTH] size of [pattern].
 *
 * Return     : -1 if [pattern] is not in [array]
 *              else beaf returns the least non-negative index i,
 *              (0 <=  i < ARRAY_LENGTH) where array[i + m] = pattern[m]
 *              for all 0 <= m < PATTERN_LENGTH.
 */
int
beaf(const int* const array,
     const int* const pattern,
     const int ARRAY_LENGTH,
     const int PATTERN_LENGTH)
{
   // size of pattern must not be greater than size of array
   if(PATTERN_LENGTH > ARRAY_LENGTH)
      return -1;

   // the current index of [pattern] that we are trying to match
   int next = 0;
   bool wrap = false;

   for(int i = 0; ; ++i)
   {
      // wrap at end
      if(i == ARRAY_LENGTH && !wrap)
      {
         wrap = true;
         i = 0;
      }
      else if(i == ARRAY_LENGTH && wrap)
         break;

      // if all has been matched, return index of first
      // element that was matched
      if(next == PATTERN_LENGTH && !wrap)
         return i - PATTERN_LENGTH;
      else if(next == PATTERN_LENGTH && wrap)
         return i - PATTERN_LENGTH + ARRAY_LENGTH;

      // move to next element in [pattern] if matching occurs
      if(array[i] == pattern[next])
         ++next;
      // matching does not occur
      else
         // start from the beginning of [pattern] if current element
         // does not match first element of [pattern]
         next = array[i] == pattern[0] ? 1 : 0;
   }

   return -1;
}

#endif

if(PATTERN_LENGTH > ARRAY_LENGTH)
   return -1;

omo_to_dun:

I have been in tons of programming contests and brainstorming coding sessions; one of the requirements is that problems are not to be unambiguously stated. If a programmer has to make assumptions, then your problem is not fully defined. I am happy how you are not compiling the program but simply going by your intuition. The code works only by accident? LOL. When you questioned me about this code snippet:

if(PATTERN_LENGTH > ARRAY_LENGTH)
   return -1;

It was then I knew that you didn't understand my simple code; how can a programmer say that it will always return false, given that different values could be passed to the function? Or maybe you didn't know that the variables were not declared const in function "beaf" but that they were passed in as argument. I expect more from you.

if(PATTERN_LENGTH > ARRAY_LENGTH)
   return -1;

omo_to_dun:

Oh, I see where the problem is. My function solves it for the general case. Not just yours. I was intrigued by the question, so I decided to solve it for the general case. If you look at my main code, you can set the arrays to be anything. Why did you think that I made a function? If I wanted to solve just yours, I wouldn't need a function; I'll just write a simple loop. No need to get angry. And I am not stopping anyone from submitting answers. This is a public forum. It is just not about getting answers, the learning process is very important. If you understood my code(and read my function description, you'll see that it was for the general case). And to just say that , "nah, you failed" is simply not enough. That is not how you prove that someone's code doesn't work. You have to show it! It is okay if you do not have immediate access to a compiler.

if(PATTERN_LENGTH > ARRAY_LENGTH)
   return -1;

Beaf:

Lol, dude, I don't need access to a compiler to write code, I keep wandering why you keep harping on that; after a few years of coding, you really don't need a compiler to be able to analyse code. In all honesty, I didn't read your comments as well, cos I didn't need to.

It is ironical that you talk about my ego. Even my Professors would never say something like: "I don't need access to a compiler to write code ".  I am not here to show off anything, I am only here to learn. I guess it is my fault, I should have kept it simple. You didn't even read my comments; dude, even geniuses have less egos. 

Beaf:

An example of your assumptions is that you must loop an array like it is a straight line, from beginning to end, thats why the issue of "beaf" existing in "eafhb" as a unit came up. IMHO, an array is a circle (which is why we loop it), except you specifically wish it to be something else; a circle has no beginning or end. So why should an array be visualised as having a beginning and an end, why can we not begin looping "eafhb" from the 5th element and end at the 4th? Lol, the mind is its own trap!

Beaf:

I'm not angry, ok maybe I got a bit upset at your challenging my knowledge because of the bad code below (and the potentially dangerous method signature it enables). You allow users enter arbitrary content at your own peril anyway (hackers delight):

if(PATTERN_LENGTH > ARRAY_LENGTH)
   return -1;

omo_to_dun:

It is ironical that you talk about my ego. Even my Professors would never say something like: "I don't need access to a compiler to write code ".  I am not here to show off anything, I am only here to learn. I guess it is my fault, I should have kept it simple. You didn't even read my comments; dude, even geniuses have less egos. 

omo_to_dun:

Unless otherwise stated, an array is a "contiguous portion of memory." I am glad that you said, "In My Humble Opinion". I simply felt you should have stated that the array should be treated like a "circle", not a straight line that programmers are used to. If someone asks you to print an array, I am sure you wouldn't treat it as a circle, or else you'd have an infinite loop.

omo_to_dun:

Actually, since the code does not write to either of the arrays, it does not matter if the user sends invalid input. An hacker cannot use buffer overflow or any other tricks to manipulate the address space; if the arrays are dynamically allocated, then the heap will generate a page fault, send a SEMENTATION FAULT signal and the application will terminate if the signal is not processed. Similarly if it was generated on the stack, a segmentation fault might also occur. I assume you don't write much code in C/C++, a lot of the functions in the standard library where you send in a buffer also requires you to send in the size.

omo_to_dun:


For what it's worth, this is one of the best conversations I have ever had on Nairaland. I have wasted too much time with Mrs.Chima in the romance section.

dell_net:

This code challenge is not valid in computer science. There is no how to use linear method to solve this problem as it states.

Beaf:

omo_to_dun already has the kernel (so sad to say ). The challenge is valid, but tricky.

Seun:

Why can't I use Python?

usisky:

@Beaf,

oga Beaf, maybe d problem has to do with your question. cos when i read it, i thot exactly in the same line as the first
person who replied. so u need to rephrase it better. which ever way, it looks so so easy. but why d no use of char, only int. say i must use char for a reason, why not. int takes more memory space where char would have been enough. pls rephrase. make it complete