HackerRank: Count strings (II)

April 9, 2016

Julia likes to have some adventure and just get into other people's solution, and quickly learn something in next 20 - 30 minutes.

Problem statement:


Statistics: time spent:  11:22am - 1:00pm

Here is the solution from a programmer working in Apple:

Code to study by Apple engineer


Comments after reading:

1. This problem is about DFA, NDFA, those content learning in Formal Language, how to build a compiler.

Friendly remind - great time to study formal language, first time for computer science master degree, score C in the course, and then in 2001 to prepare Ph.D. qualification example, Julia spent a lot of time to read the textbook again.
 

2. The string parsing is more complicate, '(', ')' should be treated as operator, and then, you can build up something.

3. Read the wiki webpage to quickly refresh knowledge
https://en.wikipedia.org/wiki/Deterministic_finite_automaton

4. Play with Visual studio and also the code - debug and run through the test case 20-30 minutes:
(ab)|(ba)  2
((a|b)*)  5

5. And put some diagram on the paper, take picture, post here and see if you can draw the state diagram for this machine.  ( 20 - 30 minutes)

Julia likes to read the code, and also debug the code;

Some facts:

1. she learned Formal language in 2001 to prepare Ph.D. qualification exam, but she never did spend time to work on an concrete example, debug the code to see how it is designed.

2. the code is well designed, and also beautiful code to read;

It is hard to figure out how to construct the Ndfa, but reading the code, Julia, you should figure out the design:

	/*
	Let us work out this basic test case:
	((ab)|(ba)) 2
	First char, it is '(',
	get into the switch statement for case '(',
	and then, recursive call to get the first FiniteAutomata,
	another '(', two times recursive calls, and then, 'a', 'b'
	first FiniteAutomate:
	{START: '*' -> #2;FINISH:#2: 'a' -> #3;#3: '*' -> #4;#4: 'b' -> #5;#5: '*' -> FINISH;}
	((ab) -> go to operator |,
	first, get the second operand, and then, complete the task: CombineAsOrAndFree
	*/
	private static FiniteAutomata ParsePatternIntoNdfa(StringBuilder builder, int start, out int end)
	{
	Debug.Assert(builder.Length > start);
	end = start;
	char ch = builder[end++];
	switch (ch)
	{
	case 'a':
	case 'b':
	return FiniteAutomata.CreateForSymbol(ch);
	case '(':
	FiniteAutomata first = new FiniteAutomata();
	FiniteAutomata second = new FiniteAutomata();
	FiniteAutomata result = new FiniteAutomata();
	first = ParsePatternIntoNdfa(builder, end, out end);
	ch = builder[end++];
	switch (ch)
	{
	case '|':
	second = ParsePatternIntoNdfa(builder, end, out end);
	result = FiniteAutomata.CombineAsOrAndFree(first, second);
	break;
	case '*':
	result = FiniteAutomata.StarAndFree(first);
	break;
	default:
	Debug.Assert(ch == 'a' || ch == 'b' || ch == '(');
	end--;
	second = ParsePatternIntoNdfa(builder, end, out end);
	result = FiniteAutomata.ConcatenateAndFree(first, second);
	break;
	}
	ch = builder[end++];
	Debug.Assert(ch == ')');
	return result;
	default:
	throw new Exception();
	}
	}

view raw Hackerrank_countstring_studyCode_Function.cs hosted with ❤ by GitHub