Sequence matching exercise

[Andy Green]

Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:

The following sequence aababaaabaaa<En d Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbaba ba<End Of Input> would
produce the following result: 0101

Any takers?

[Martin Ambuhl]

Andy Green wrote:

Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:

The following sequence aababaaabaaa<En d Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbaba ba<End Of Input> would
produce the following result: 0101

Any takers?

The requirement that you monitor stdin suggests that you think
unbuffered input on a character-by-character basis is available. This
suggests that you have a specific implementation in mind and makes the
question off-topic. If, on the other hand, the challenge can be
rewritten to examine strings, wherever they came from, then this is a
simple algorithm question and is off-topic.

Perhaps you can explain what content your question has that makes it a
question about C. Or you could do your own homework.

[Eric Sosman]

Andy Green wrote:

Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:

The following sequence aababaaabaaa<En d Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbaba ba<End Of Input> would
produce the following result: 0101

Any takers?

The C language Standard has nothing to say about speed
and "efficiancy ," but I think this program will be hard to
beat:

int main(void) {
return 0;
}

You may be wondering why this program works as required, and
your professor may wonder the same thing. The answer lies in
a close reading of the homework statement:

- Output is only required *if* "aaa" or "aba" is
detected. This program detects neither (nowhere
does the homework assignment state a requirement
that anything be detected), and is thus relieved
of any responsibility to produce output.

- The program is expressly forbidden to detect
"sequences within sequences." The stream of
input characters is a sequence (note the use of
the term in the two examples), so the program is
forbidden to detect anything in its input.

- The program is required to "monitor" its input,
but the verb "monitor" is not defined by the C
language Standard, nor by the homework assignment.
Therefore we are free to define it in the manner
we find most convenient. The sixth definition
given by http://www.yourdictionary.com for the
transitive verb "monitor" is "to direct," and
the program above "directs" the input to the
highly efficient bit bucket.

- Actually, the program is not required to do anything
at all with or to the input. The homework assignment
says "The program SHOULD ..." (emphasis mine), and
"should" is merely a hint. A requirement is always
properly expressed with "shall" (and a prohibition
with "shall not"), as described in Section 4 of the
C language Standard.

I hope this helps you get the grade you deserve.

--
Er*********@sun .com

[Thomas Matthews]

Andy Green wrote:

Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:

The following sequence aababaaabaaa<En d Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbaba ba<End Of Input> would
produce the following result: 0101

Any takers?

This falls more under lexing and parsing. IMO, the natural
course of action is to create a language for this assignment.
Something like:
zero_sequence ::= a a a

one_sequance ::= a b a

Run this through a program such as lex or flex to generate
a parse table. Then write a program to support the parse
table. Keep these pieces, as you will need them to do
your next homework assignments.

Or perhaps a simple state diagram would help you:

b +---+
+------> | 4 | --+
| +---+ |
| |
+---+ a +---+ a +---+ |
O -> | 1 | ---> | 2 | ---> | 3 | |
+---+ +---+ +---+ |
^ | | |
| v v |
+---------------------------+

State 1: stay in this state until an 'a' is detected.

State 2: if an 'a' is detected, transition to state 3.
if a 'b' is detected, transition to state 4.
Otherwise transition to state 1.

State 3: if an 'a' is detected, print '0'.
Transition in all cases to state 1.

State 4: if an 'a' is detected, print '1'.
Transition in all cases to state 1.

If an EOF is detected in any state, the program should
exit (i.e. state 5).

Now, code it up.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

[Nick Austin]

On 17 Jun 2004 09:59:23 -0700, an*******@opton line.net (Andy Green)
wrote:

Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:

Use a state machine. I was able to complete the exercise with just
four states.

I created two tables to handle the 'a' and 'b' cases separately. It
would be faster to use a sparse 2 dimensional array, indexed by the
current state and the character read from the stream.

This is the code to handle detection of "aaa" in the input stream:

#include <stdio.h>

static void nothing( void );
static void print_0( void );
static void print_1( void );

typedef struct
{
int new_state;
void ( *action )( void );
} TABLE;

static const TABLE table_a[] =
{
/* 0 */ { 1, nothing },
/* 1 */ { 2, nothing },
/* 2 */ { 0, print_0 },
};

static const TABLE table_b[] =
{
/* 0 */ { 0, nothing },
/* 1 */ { 0, nothing },
/* 2 */ { 0, nothing },
};

int main( void )
{
int state = 0;
int ch;

while ( ch = getc( stdin ), ch != EOF )
{
/* Do actions defined by table */

switch ( ch )
{
case 'a':
table_a[ state ].action();
state = table_a[ state ].new_state ;
break;
case 'b':
table_b[ state ].action();
state = table_b[ state ].new_state ;
break;
default:
state = 0;
}
}
printf( "\n" );

return 0;
}

static void nothing( void )
{
}

static void print_0( void )
{
printf( "0" );
}

static void print_1( void )
{
printf( "1" );
}

Nick.

[Andy Green]

Thomas Matthews <Th************ *************** *@sbcglobal.net > wrote in message news:<oM******* ********@newssv r16.news.prodig y.com>...

Andy Green wrote:

Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:

The following sequence aababaaabaaa<En d Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbaba ba<End Of Input> would
produce the following result: 0101

Any takers?

This falls more under lexing and parsing. IMO, the natural
course of action is to create a language for this assignment.
Something like:
zero_sequence ::= a a a

one_sequance ::= a b a

Run this through a program such as lex or flex to generate
a parse table. Then write a program to support the parse
table. Keep these pieces, as you will need them to do
your next homework assignments.

Or perhaps a simple state diagram would help you:

b +---+
+------> | 4 | --+
| +---+ |
| |
+---+ a +---+ a +---+ |
O -> | 1 | ---> | 2 | ---> | 3 | |
+---+ +---+ +---+ |
^ | | |
| v v |
+---------------------------+

State 1: stay in this state until an 'a' is detected.

State 2: if an 'a' is detected, transition to state 3.
if a 'b' is detected, transition to state 4.
Otherwise transition to state 1.

State 3: if an 'a' is detected, print '0'.
Transition in all cases to state 1.

State 4: if an 'a' is detected, print '1'.
Transition in all cases to state 1.

If an EOF is detected in any state, the program should
exit (i.e. state 5).

Now, code it up.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

Its not as complicted as that. It is not a homework assignment, one of
my guys submitted this as one of the questions we ask our applicants.
I'm wondering how long it should take. 15 minutes is the suggested
time. What types of answers I'd get. No credits for this one..

[Russell Hanneken]

Thomas Matthews wrote:

State 1: stay in this state until an 'a' is detected.

State 2: if an 'a' is detected, transition to state 3.
if a 'b' is detected, transition to state 4.
Otherwise transition to state 1.

State 3: if an 'a' is detected, print '0'.
Transition in all cases to state 1.

State 4: if an 'a' is detected, print '1'.
Transition in all cases to state 1.

If an EOF is detected in any state, the program should
exit (i.e. state 5).

I don't think this design would do the right thing. As I understand the
rules laid out by the original poster, a sequence like

aabaaa

Should lead to a 1 being printed (because of aba). But I think your design
would lead to a 0 being printed (aab is discarded, and then aaa causes the 0
to be printed).

--
Russell Hanneken
eu*******@cbobk .pbz
Use ROT13 to decode my email address.

[josh]

Andy Green wrote:

Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:

The following sequence aababaaabaaa<En d Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbaba ba<End Of Input> would
produce the following result: 0101

Any takers?

Well, I'd think the most straightforward implementation would be
something like:

#include <stdio.h>

char context[3];
int cp;

void clear_context(v oid)
{
cp = context[0] = context[1] = context[3] = 0;
}

char lookbehind(int distance)
{
int i = (cp - distance + 3) % 3;
return context[i];
}

int main(void)
{
clear_context() ;
while (!feof(stdin))
{
context[cp] = fgetc(stdin);
if (context[cp] == 'a' && lookbehind(2) == 'a')
{
if (lookbehind(1) == 'b')
{
fputc('1', stdout);
clear_context() ;
}
else if (lookbehind(1) == 'a')
{
fputc('0', stdout);
clear_context() ;
}
}
cp = (cp+1) % 3;
}
}

But I bet fgetc returns EOF at the end of file, which should be checked
instead of using feof. It doesn't really make a difference here anyway.

It might be slightly better to use a context array of size 4, so you can
do & instead of %, but your speed is really gonna be limited by the IO
anyway.

-josh

[JV]

"Andy Green" <an*******@opto nline.net> wrote in message
news:a7******** *************** ***@posting.goo gle.com...

Its not as complicted as that. It is not a homework assignment, one of
my guys submitted this as one of the questions we ask our applicants.
I'm wondering how long it should take. 15 minutes is the suggested
time. What types of answers I'd get. No credits for this one..

Depends on what level you want the answer. I would give my answer in 1
minute and it would be verbal :
"I'll would take the next three characters and compare them to two
posibilities, if match is found print the output and compare again and so
on,
else discard first character , fetch one annd compare again and so on.
If fetching fails the program would stop."
I think you are better of comparing how people perform. How fast one solves
this kind of quite trivial problem, doesn't actually tell that a person can
perform more complicated tasks efficiently. I mean I don't think it matters
wheter this one takes 1 , 5 or 15 minutes. Some people like to think first
carefully before giving the answer, others (like me) just start to give the
anser and figure out the troubles as they go:). Of course if this one takes
two hours, for get the person in question.
-Jyrki
PS. What this has to do with C-language?

[Andy Green]

josh <sm************ *************@y ahoo.com.NOSPAM > wrote in message news:<vJuAc.677 58$0y.559@attbi _s03>...

Andy Green wrote:

Emphasis is on efficiancy and speed this is the excercise:
The program should monitor a possibly infinite stream of characters
from the keyboard (standard input). If it detects the sequence "aaa"
it outputs a "0". If it detects the sequence "aba" it outputs a "1".
DO NOT detect sequences within sequences. The program should exit
cleanly when it detects an End Of Input. For example:

The following sequence aababaaabaaa<En d Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbaba ba<End Of Input> would
produce the following result: 0101

Any takers?

Well, I'd think the most straightforward implementation would be
something like:

#include <stdio.h>

char context[3];
int cp;

void clear_context(v oid)
{
cp = context[0] = context[1] = context[3] = 0;
}

char lookbehind(int distance)
{
int i = (cp - distance + 3) % 3;
return context[i];
}

int main(void)
{
clear_context() ;
while (!feof(stdin))
{
context[cp] = fgetc(stdin);
if (context[cp] == 'a' && lookbehind(2) == 'a')
{
if (lookbehind(1) == 'b')
{
fputc('1', stdout);
clear_context() ;
}
else if (lookbehind(1) == 'a')
{
fputc('0', stdout);
clear_context() ;
}
}
cp = (cp+1) % 3;
}
}

But I bet fgetc returns EOF at the end of file, which should be checked
instead of using feof. It doesn't really make a difference here anyway.

It might be slightly better to use a context array of size 4, so you can
do & instead of %, but your speed is really gonna be limited by the IO
anyway.

-josh

Thanks to all that responded!!. Sorry if I ruffled some feathers. If I
posted this to the wrong group I apologize. Josh and Nick thanks for
taking a stab at it, troopers!. getchar(), getc(stdin) would be o.k.
as well. Tom thanks for the laugh. We are not going to use this or if
we do we have to re-write it, a lot of people have trouble
interpreting the question.
We might reword it to allow the candidate to use ANY language. The guy
who came up with it says a one line shell script should do.. :). He
might be kidding me I can't tell... - Thanks again all - Andy G.