Algorithms

Rui__Silva wrote:

Tanks ppolymorphe

Rui__Silva wrote:

After your tip i did some research and i think my solution fits more or less in Direct Acyclic Graph more than oriented graph.

Viktor Grabarchuk wrote:

I just want to find some people who might solve this task earlier.

Bastard Programmer from Hell
If you can't read my code, try converting it here[^]

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