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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<End Of Input> would
produce the following result: 0101

Any takers?

 

[Martin Ambuhl]

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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<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]

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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<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.

 

[Thomas Matthews]

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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<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.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Nick Austin]

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]

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.learn.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]

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).

 

[josh]

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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<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(void)
{
cp = context[0] = context[1] = context[3] = 0;
}

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

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]

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]

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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<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(void)
{
cp = context[0] = context[1] = context[3] = 0;
}

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

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.

 

[Peter Ammon]

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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<End Of Input> would
produce the following result: 0101

Any takers?

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]

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!)

You missed the requirement to be efficient and fast.

[...snip...]

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

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

Nick.

 

[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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<End Of Input> would
produce the following result: 0101

Any takers?

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

Now that's an A++.

 

[Wayne Rasmussen]

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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<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(void)
{
cp = context[0] = context[1] = context[3] = 0;
}

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

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.

If people are having problems "interpreting 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]

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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<End Of Input> would
produce the following result: 0101

Any takers?

#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];
}
}

 

[Peter Ammon]

You missed the requirement to be efficient and fast.

Heh. In real world terms, the bottleneck in all the solutions I've seen
so far appears to be the use of getc() or getchar(). Using fgets()
would probably do the most to improve speed, for all of us.

[...snip...]

if (! strcmp(buff, "aaa")) {
[...snip...]

else if (! strcmp(buff, "aba")) {
[...snip...]

buff[0]=buff[1];
buff[1]=buff[2];

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

Nick.

Thanks for your thoughts. Here's my variation of the above technique,
optimized for speed (though I still input a character at a time). It
appears to be very fast in practice.

#include <stdio.h>
#include <limits.h>

typedef unsigned char uchar;

#define AAA ((unsigned)(((uchar)'a' << 2*CHAR_BIT) |\
((uchar)'a' << CHAR_BIT) |\
(uchar)'a'))

#define ABA ((unsigned)(((uchar)'a' << 2*CHAR_BIT) |\
((uchar)'b' << CHAR_BIT) |\
(uchar)'a'))

#define THREE_CHAR_MASK (((uchar)(-1) << 2*CHAR_BIT) |\
((uchar)(-1) << CHAR_BIT) |\
(uchar)(-1))

uchar next(void) {
int c = getc(stdin);
if (c==EOF) {
putchar('\n');
exit(0);
}
return (uchar)c;
}

unsigned next3(void) {
uchar a = next();
uchar b = next();
uchar c = next();
return (unsigned)((a << 2*CHAR_BIT) | (b << CHAR_BIT) | c);
}

int main(void) {
unsigned buff=0;
for (; {
if (buff==AAA) {
putchar('0');
buff=next3();
}
else if (buff==ABA) {
putchar('1');
buff=next3();
}
else buff = ((buff << CHAR_BIT) | next()) & THREE_CHAR_MASK;
}
return 0;
}

 

[Nisse Engstrom]

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<End Of Input> would produce the
following result: 100
While the following sequence aaababaaaabbababa<End Of Input> would
produce the following result: 0101

Any takers?

#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];
}
}

#include <stdio.h>
#include <stdlib.h>

int a,b;

int main (void)
{
while ((b=getchar())!=EOF) {
a = 7&(b=='a')*3985 + (b=='b')*216>>a * 3;
if (a/2&a >> 2) a = !putchar('0'+a % 2);
}
return (!!ferror(stdin)|!putchar('\n')||!!ferror(stdout))*EXIT_FAILURE;
}

 

[Blue Ocean]

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).

Each transition would have to have an action associated with it. I'm
not thinking about this too hard, so I could be getting this wrong,
but I think the transition from state 1 to 2 or 3 would have to save
the char, so that when/if the states reverted, the saved char buffer
would be read first before getchar() was called again, like K&R2's
getch() and ungetch().

 

[Blue Ocean]

If people are having problems "interpreting 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?

Since he's probably not here to defend himself any more . . . what
exactly is your point? Andy Green says _right there_ that because
people were having trouble understanding the intent, he is going to
reword it. He's not blaming anyone.

Why is it that you, like so many others in this group, are so eager to
jump on someone's back for the smallest perceived error?

 

[Gene]

Please correct me if I am wrong.
When program reads from standard in (keyboard) console is used. When program prints standard out console is used. It can not be done at the same time. So input processing started only when EOF detected.
If it is true I preffer to read hole line using InputStreamReader.
See this implementation bellow:
import java.util.*;
import java.io.*;

class ReadStandIn {

public static void main(String args[])
throws java.io.IOException {

BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
processInputStream(in);
}

public static void processInputStream(BufferedReader in){


String str = null;

try {
str = in.readLine();
}
catch (IOException e) {
e.printStackTrace();
}

System.out.println("you entered: " + str);

int count = 0;
StringBuffer sb = new StringBuffer();

char[] c = str.toCharArray();

for(int i=0; i < c.length; i++){

if(count == 0 && c == 'a'){
sb.append(c);
count++;
}
else if((count == 1 || count == 2) && (c == 'a' || c == 'b')){
sb.append(c);
count++;
}
else if(count > 0 && count < 4 && (c != 'a' && c != 'b')){
sb.delete(0,sb.length());
count = 0;
}

if(sb.toString().equals("aaa")){
System.out.print("0");
sb.delete(0,sb.length());
count = 0;
}

if(sb.toString().equals("aba")){
System.out.print("1");
sb.delete(0,sb.length());
count = 0;
}

if(sb.toString().equals("aab")){
sb.delete(0,1);
count = 2;
}
}
System.out.println("");
}
}