How Easy?

    A. First Edition

    This is the problem from topCoder competition and it is only a small fun for me. I know I am not good at this kind

    of competition. Anyway it is no harm to have some fun.

    B.The problem

¡¡

### Problem Statement

    ***Note:  Please keep programs under 7000 characters in length.  Thank you

    Class Name: HowEasy
    Method Name: pointVal
    Parameters: String
    Returns: int

    TopCoder has decided to automate the process of assigning problem difficulty
    levels to problems.  TopCoder developers have concluded that problem difficulty
    is related only to the Average Word Length of Words in the problem statement:

    If the Average Word Length is less than or equal to 3,  the problem is a 250
    point problem.
    If the Average Word Length is equal to 4 or 5, the problem is a 500 point
    problem.
    If the Average Word Length is greater than or equal to 6, the problem is a 1000
    point problem.

    Definitions:
    Token - a set of characters bound on either side by spaces, the beginning of
    the input String parameter or the end of the input String parameter.
    Word - a Token that contains only letters (a-z or A-Z) and may end with a
    single period. A Word must have at least one letter.
    Word Length - the number of letters in a Word. (NOTE: a period is NOT a letter)

    The following are Words :
    "ab",  "ab."

    The following are not Words :
    "ab..", "a.b", ".ab", "a.b.", "a2b.", "."

    Average Word Length - the sum of the Word Lengths of every Word in the problem
    statement divided by the number of Words in the problem statement.  The
    division is integer division. If the number of Words is 0, the Average Word
    Length is 0.

    Implement a class HowEasy, which contains a method pointVal.  The method takes
    a String as a parameter that is the problem statement and returns an int that
    is the point value of the problem (250, 500, or 1000). The problem statement
    should be processed from left to right.

    Here is the method signature (be sure your method is public):
    int pointVal(String problemStatement);

    problemStatement is a String containing between 1 and 50 letters, numbers,
    spaces, or periods.  TopCoder will ensure the input is valid.

    Examples:

    If problemStatement="This is a problem statement", the Average Word Length is
    23/5=4, so the method should return 500.
    If problemStatement="523hi.", there are no Words, so the Average Word Length is
    0, and the method should return 250.
    If problemStatement="Implement a class H5 which contains some method." the
    Average Word Length is 38/7=5 and the method should return 500.
    If problemStatement=" no9 . wor7ds he8re. hj.." the Average Word Length is 0,
    and the method should return 250.

### Definition

Class: | HowEasy
Method: | pointVal
Parameters: | string
Returns: | int
Method signature: | int pointVal(string param0)
(be sure your method is public)

¡¡

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

¡¡
C.The idea of program
¡¡
My idea is simply drawing a NFA with following states:
¡¡
StartState, WordState, PeriodState, TokenState, EndState, CountWordState, CountWordEndState
¡¡
¡¡

Please note that states like CountWordState and CountWordEndState are connected with StartState with Epsilon.

    ¡¡

    D.The major functions

    .

    E.Further improvement

    There is nothing special for this program except that I was given a mark of 80% and I don't know where is the bug.

    F.File listing

    #include <iostream>

    using namespace std;

    //An NFA state
    enum MyState
    {
    	StartState, WordState, PeriodState, TokenState, EndState, CountWordState,
    		CountWordEndState
    };

    //char type
    enum MyCharType
    {
    	AlphaType, PeriodType, SpaceType, OtherType, EndType
    };

    class HowEasy
    {

    private:
    	MyCharType getCharType(char ch);
    	MyState stateMachine(MyState oldState, MyCharType myCharType);
    	int countWord(int wordCounter, int lengthSum);

    public:
    	int pointVal(string param0);
    };

    //assume input is valid
    MyCharType HowEasy::getCharType(char ch)
    {
    	if (ch>='a'&&ch<='z'||ch>='A'&&ch<='Z')
    	{
    		return AlphaType;
    	}
    	if (ch==' ')
    	{
    		return SpaceType;
    	}
    	if (ch=='.')
    	{
    		return PeriodType;
    	}

    	//EndType is virtual and logical
    	/*
    	if (ch=='\0')
    	{
    		return EndType;
    	}
    	*/

    	return OtherType;
    }

    int HowEasy::countWord(int wordCounter, int lengthSum)
    {
    	int result;
    	if (wordCounter==0)
    	{
    		result= 0;
    	}
    	else
    	{
    		result= lengthSum/wordCounter;
    	}

    	if (result<=3)
    	{
    		return 250;
    	}
    	else
    	{
    		if (result==4||result==5)
    		{
    			return 500;
    		}
    		else
    		{
    			return 1000;
    		}
    	}
    }

    int HowEasy::pointVal(string param0)
    {
    	MyState myState=StartState;
    	int lengthSum=0;
    	int wordCounter=0;
    	int lengthCounter=0;
    	MyCharType myCharType;

    	char ch;
    	int strLengthPlusOne=param0.length()+1;
    	for (int i=0; i<strLengthPlusOne; i++)
    	{
    		if (i!=strLengthPlusOne-1)
    		{
    			ch=param0[i];
    			myCharType=getCharType(ch);
    		}
    		else
    		{
    			myCharType=EndType;
    		}
    		myState=stateMachine(myState, myCharType);
    		switch (myState)
    		{
    		case EndState:
    			break;
    		case CountWordState:
    			lengthSum+=lengthCounter;
    			wordCounter++;
    			lengthCounter=0;
    			//must retore state as this is NFA not DFA
    			myState=StartState;
    			break;
    		case CountWordEndState:
    			lengthSum+=lengthCounter;
    			wordCounter++;
    			break;
    		case WordState:
    			lengthCounter++;
    			break;
    		case PeriodState:

    			break;
    		default:
    			lengthCounter=0;
    			break;
    		}
    	}
    	return countWord(wordCounter, lengthSum);
    }

    MyState HowEasy::stateMachine(MyState oldState, MyCharType myCharType)
    {
    	MyState result;
    	switch (oldState)
    	{
    	case StartState:
    		switch (myCharType)
    		{
    		case AlphaType:
    			result= WordState;
    			break;

    		case SpaceType:
    			result= StartState;
    			break;
    		case EndType:
    			result= EndState;
    			break;
    		default:
    			result= TokenState;
    			break;
    		}
    		break;

    	case WordState:
    		switch (myCharType)
    		{
    		case AlphaType:
    			result= WordState;
    			break;
    		case SpaceType:
    			result= CountWordState;
    			break;

    		case EndType:
    			result= CountWordEndState;
    			break;

    		case PeriodType:
    			result= PeriodState;
    			break;

    		default:
    			result= TokenState;
    			break;
    		}
    		break;
    	case TokenState:
    		switch (myCharType)
    		{
    		case SpaceType:
    			result= StartState;
    			break;
    		case EndState:
    			result= EndState;
    			break;
    		default:
    			result= TokenState;
    			break;
    		}
    		break;
    	case PeriodState:
    		switch (myCharType)
    		{
    		case SpaceType:
    			result= CountWordState;
    			break;

    		case EndType:
    			result= CountWordEndState;
    			break;
    		default:
    			result= TokenState;
    			break;
    		}
    		break;
    	}
    	return result;
    }

    int main()
    {
    	HowEasy test;
    	cout<<test.pointVal(string(" no9 . wor7ds he8re. hj.."))<<endl;

    	return 0;
    }

    ///////////////////////////////////////////////////////////////////////////////////////

    /////////////////////////////////////////////////////////////////////

    //suppose you write code after several months, would you make the exact same choice as before?

    //The following may reveal how I am thinking after one month.

    //////////////////////////////////////////////////

    ¡¡

    //////////////////////////////////////////////////////////////////////////////////////

    //second try

    ¡¡

    #include <stdio.h>
    #include <string>
    using namespace std;
    enum State
    {
    	StartString, BeforeWord, InsideWord, NoneWord, PeriodWord, EndString, ErrorState
    };

    enum CharSet
    {
    	Alphabetic, Period, Space, Null, Others
    };

    class HowEasy
    {
    private:
    	int total;
    	int current;
    	int wordCounter;
    	State automata(CharSet ch, State state);
    	bool isAlpha(char ch);
    	CharSet whatChar(char ch);
    public:
    	int pointVal(string param);
    };

    int HowEasy::pointVal(string param)
    {
    	State state=StartString;
    	CharSet charSet;
    	int average;
    	int i=0;
    	const char* ptr=param.c_str();
    	while (state!=EndString)
    	{
    		charSet=whatChar(ptr[i]);
    		state=automata(charSet, state);
    		i++;
    	}
    	if (wordCounter!=0)
    	{
    		average=total/wordCounter;
    	}
    	else
    	{
    		average=0;
    	}
    	if (average<=3)
    	{
    		return 250;
    	}
    	if (average>=4&&average<=5)
    	{
    		return 500;
    	}
    	if (average>=6)
    	{
    		return 1000;
    	}
    	return -1;
    }

    CharSet HowEasy::whatChar(char ch)
    {
    	if (isAlpha(ch))
    	{
    		return Alphabetic;
    	}
    	if (ch==' ')
    	{
    		return Space;
    	}
    	if (ch=='.')
    	{
    		return Period;
    	}
    	if (ch=='\0')
    	{
    		return Null;
    	}
    	return Others;
    }
    bool HowEasy::isAlpha(char ch)
    {
    	return ch>='a'&&ch<='z'||ch>='A'&&ch<='Z';
    }

    State HowEasy::automata(CharSet ch, State state)
    {
    	switch (state)
    	{
    	case StartString:
    		 total=0;
    		 current=0;
    		 wordCounter=0;
    		 switch(ch)
    		 {
    		 case Alphabetic:
    		 	current++;
    		 	return InsideWord;
    		 case Space:
    		 	return BeforeWord;
    		 case Null:
    		 	return EndString;
    		 default:
    		 	return NoneWord;
    		 }
    		 break;
    	case InsideWord:
    		switch(ch)
    		{
    		case Alphabetic:
    			current++;
    			return InsideWord;
    		case Space:
    			wordCounter++;
    			total+=current;
    			current=0;
    			return BeforeWord;
    		case Period:
    			//current++;
    			return PeriodWord;
    		case Null:
    			wordCounter++;
    			total+=current;
    			current=0;
    			return EndString;
    		default:
    			current=0;
    			return NoneWord;
    		}
    		break;
    	case BeforeWord:
    		switch (ch)
    		{
    		case Alphabetic:
    			current++;
    			return InsideWord;
    		case Space:
    			return BeforeWord;
    		case Null:
    			return EndString;
    		default:
    			return NoneWord;
    		}
    		break;
    	case NoneWord:
    		switch(ch)
    		{
    		case Space:
    			return BeforeWord;
    		case Null:
    			return EndString;
    		default:
    			return NoneWord;
    		}
    		break;
    	case PeriodWord:
    		switch(ch)
    		{
    		case Space:
    			//period is not a letter
    			total+=current;
    			wordCounter++;
    			current=0;
    			return BeforeWord;
    		case Null:
    			total+=current;
    			current=0;
    			wordCounter++;
    			return EndString;
    		default:
    			current=0;
    			return NoneWord;
    		}
    	}
    	return ErrorState;
    }

¡¡

    ¡¡

    ¡¡