Algorithms

Chaitanya Pai wrote:

I have tried a lot to arrive at the solution.

1. [Preparation] Sort the strings representing the first ticket in each book in ascending order:
   a. zero-pad any short strings (e.g. "ABC1" should be padded to "00ABC1"
   b. sort the strings using a case-insensitive sort
   c. pad the list with a dummy ending value (e.g. "ZZZZZZ").
   d. pad the list with a dummy starting value (e.g. "000000").
2. [Eliminate low values] Use a binary search to find the location of largest value less than or equal to the target string. If the result points to the starting dummy value, then no such value exists.
3. [Eliminate high values] Use a binary search to find the location of the smallest value larger than the target string. If the result points to the ending dummy value, then no such value exists.

   IsInBetween( "A0ZWS0A" );
   IsInBetween( "A0ZWS0P" );
   IsInBetween( "A0ZWS7P" );
   IsInBetween( "A0ZWSAP" );

private static void IsInBetween( string value ) {

   string s1 = "A0ZWS0P";
   string s2 = "A0ZWS9P";

   bool isInbetween =
      value.CompareTo( s1 ) == 0 ||
      value.CompareTo( s2 ) == 0 ||
      ( value.CompareTo( s1 ) > 0 && value.CompareTo( s2 ) < 0 );

   Console.WriteLine( "Is {0} between {1} {2}? {3}", value, s1, s2, isInbetween );
}

bool isInbetween = ( value.CompareTo( s1 ) >= 0 && value.CompareTo( s2 ) <= 0 );

long long GenRadVal(char *str, int base)
{
	if (base<2 || base>36)
		return 0LL;

	long long val = 0;

	for (int i = 0; str[i]; i++)
	{
		int c = toupper(str[i]);
		if ((c < 0) || ((c > '9') && (c < 'A')) || (c > 'Z'))
			break;
		c =  c > '9' ? c - 'A' + 10 : c - '0';
		if (c >= base)
			break;
		val *= base;
		val +=  c;
	}
	return val;
}

static long Parse36(string s)
{
  long v = 0;
  foreach(char c in s)
  {
    char uc = char.ToUpper(c);
    bool isDigit = ('0' <= uc && uc <= '9');
    if (!(isDigit || ('A' <= uc && uc <= 'Z')))
      throw new FormatException();
    int d = uc - (isDigit ? '0' : ('A' - 10));
    v = v * 36 + d;
  }
  return v;
}

1. Check for base cases
2. For each attribute a
   2.1. Find the normalized information gain ratio from splitting on a
3. Let a_best be the attribute with the highest normalized information gain
4. Create a decision node that splits on a_best
5. Recur on the sublists obtained by splitting on a_best, and add those nodes as children of node