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]

Re: Sequence matching exercise

Andy Green wrote:
[color=blue]
> 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?[/color]

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]

Re: Sequence matching exercise

Andy Green wrote:[color=blue]
> 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?[/color]

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.

--
Eric.Sosman@sun .com

[Thomas Matthews]

Re: Sequence matching exercise

Andy Green wrote:[color=blue]
> 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?[/color]

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]

Re: Sequence matching exercise

On 17 Jun 2004 09:59:23 -0700, andygreen@opton line.net (Andy Green)
wrote:
[color=blue]
>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:[/color]

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]

Re: Sequence matching exercise

Thomas Matthews <Thomas_Matthew sSpitsOnSpamBot s@sbcglobal.net > wrote in message news:<oMlAc.367 $7h6.311@newssv r16.news.prodig y.com>...[color=blue]
> Andy Green wrote:[color=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?[/color]
>
> 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[/color]

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]

Re: Sequence matching exercise

Thomas Matthews wrote:[color=blue]
>
> 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).[/color]

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
eunaarxra@cbobk .pbz
Use ROT13 to decode my email address.

[josh]

Re: Sequence matching exercise

Andy Green wrote:[color=blue]
> 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?[/color]

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]

Re: Sequence matching exercise


"Andy Green" <andygreen@opto nline.net> wrote in message
news:a77fc336.0 406171411.55c4f dd0@posting.goo gle.com...[color=blue]
> 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..[/color]
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]

Re: Sequence matching exercise

josh <smileyfaceswil lruletheworld@y ahoo.com.NOSPAM > wrote in message news:<vJuAc.677 58$0y.559@attbi _s03>...[color=blue]
> Andy Green wrote:[color=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?[/color]
>
> 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[/color]

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.

[Peter Ammon]

Re: Sequence matching exercise

Andy Green wrote:
[color=blue]
> 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?[/color]

I'm shocked at how many people immediately thought of a state machine
for this. It seems that classical computer science education sucks out
creativity and original thinking. (I can say that since I went through
the same grinder!)

Here's my solution. It took me about five minutes.

#include <stdio.h>
#include <string.h>

char next(void) {
int c = getchar();
if (c != 'a' && c != 'b') {
putchar('\n');
exit(0);
}
return (char)c;
}

int main(void) {
char buff[4]={0};
for (;;) {
if (! strcmp(buff, "aaa")) {
putchar('0');
buff[2]=0;
}
else if (! strcmp(buff, "aba")) {
putchar('1');
buff[2]=0;
}
else {
buff[0]=buff[1];
buff[1]=buff[2];
buff[2]=next();
}
}
return 0;
}

[Nick Austin]

Re: Sequence matching exercise

On Fri, 18 Jun 2004 12:06:15 -0700, Peter Ammon
<peter_ammon@ro cketmail.com> wrote:
[color=blue]
>Andy Green wrote:
>[color=green]
>> Emphasis is on efficiancy and speed this is the excercise:[/color][/color]
[color=blue]
>I'm shocked at how many people immediately thought of a state machine
>for this. It seems that classical computer science education sucks out
>creativity and original thinking. (I can say that since I went through
>the same grinder!)[/color]

You missed the requirement to be efficient and fast.

[...snip...][color=blue]
> if (! strcmp(buff, "aaa")) {[/color]
[...snip...][color=blue]
> else if (! strcmp(buff, "aba")) {[/color]
[...snip...][color=blue]
> buff[0]=buff[1];
> buff[1]=buff[2];[/color]

This does loads of comparisions and assignments for each character
read from the input stream. Hardly efficient or fast.

Nick.

[Andy Green]

Re: Sequence matching exercise

Peter Ammon <peter_ammon@ro cketmail.com> wrote in message news:<cavef7$8v s$1@news.apple. com>...[color=blue]
> Andy Green wrote:
>[color=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?[/color]
>
> I'm shocked at how many people immediately thought of a state machine
> for this. It seems that classical computer science education sucks out
> creativity and original thinking. (I can say that since I went through
> the same grinder!)
>
> Here's my solution. It took me about five minutes.
>
> #include <stdio.h>
> #include <string.h>
>
> char next(void) {
> int c = getchar();
> if (c != 'a' && c != 'b') {
> putchar('\n');
> exit(0);
> }
> return (char)c;
> }
>
> int main(void) {
> char buff[4]={0};
> for (;;) {
> if (! strcmp(buff, "aaa")) {
> putchar('0');
> buff[2]=0;
> }
> else if (! strcmp(buff, "aba")) {
> putchar('1');
> buff[2]=0;
> }
> else {
> buff[0]=buff[1];
> buff[1]=buff[2];
> buff[2]=next();
> }
> }
> return 0;
> }[/color]

Now that's an A++.

[Wayne Rasmussen]

Re: Sequence matching exercise



Andy Green wrote:
[color=blue]
> josh <smileyfaceswil lruletheworld@y ahoo.com.NOSPAM > wrote in message news:<vJuAc.677 58$0y.559@attbi _s03>...[color=green]
> > Andy Green wrote:[color=darkred]
> > > 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?[/color]
> >
> > 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[/color]
>
> 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.[/color]

If people are having problems "interpreti ng the question" it is the responsibility of the transmitter (i.e.
You), to insure that the proper message is getting received before blaming them. One might think if this is
the quality of the input someone might get from your department. Wonder how many competent people would walk
after seeing a question like this at an interview?

[Kevin Handy]

Re: Sequence matching exercise

Andy Green wrote:[color=blue]
> 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?[/color]


#include <stdio.h>

int state[4][4] =
{
{1, 0, 0, 0},
{2, 0, 3, 0},
{0, '0', 3, 0},
{0, '1', 0, 0}
};

int main()
{
char inch;
int st = 0;

while ((inch = fgetc(stdin)) != EOF)
{
switch(inch)
{
case 'a':
inch = 0;
break;
case 'b':
inch = 2;
break;
default:
st = 0;
continue;
}
if (state[st][inch+1])
{
printf("%c", state[st][inch+1]);
}
st = state[st][inch];
}
}