Sample Input 2

  

3           (# "good" pairings <= 100,000)
A B
G L
J K
2           (# "bad" pairings <= 100,000)
D F
D G
4           (# paired groups <= 100,000)
A C G
B D F
E H I
J K L

How to store the data

What is the problem with this representation of the input data ? 

3           
A B        GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L	   GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K	   GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2           
D F	   BadPair[0][0] = "D"  BadPair[0][1] = "F"
D G	   BadPair[1][0] = "D"  BadPair[1][1] = "G"
4           
A C G      Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"
B D F	   Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"
E H I	   Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"
J K L	   Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"

How to store the data

Problem:   we need to search (a large array to finr the group of any name 

3           
A B        GoodPair[0][0] = "A" GoodPair[0][1] = "B"
G L	   GoodPair[1][0] = "G" GoodPair[1][1] = "L"
J K	   GoodPair[2][0] = "J" GoodPair[2][1] = "K"
2           
D F	   BadPair[0][0] = "D"  BadPair[0][1] = "F"
D G	   BadPair[1][0] = "D"  BadPair[1][1] = "G"
4           
A C G      Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"
B D F	   Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"
E H I	   Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"
J K L	   Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"



 Finding the group for any name (GoodPair[2][0] = "J") needs a search !

Importance of data structure

 

  • How well you can represent the information used by you program is more important than how well you can program/code !!

  • There are usually many different ways to present the same information

  • How you store the data can affect:

      • How long your program will run

      • How much information your progarm need to store

  • The inefficiency of our program arised from how we store the paired groups

  • Let's look at how to represent the paired groups in more detail

The group# --> node represention

The current representation of a paired group maps a group# to the members (names) of the group: 

4           
A C G      Grp[0][0] = "A" Grp[0][1] = "C" Grp[0][2] = "G"  <-- group 0
B D F	   Grp[1][0] = "B" Grp[1][1] = "D" Grp[1][2] = "F"  <-- group 1
E H I	   Grp[2][0] = "E" Grp[2][1] = "H" Grp[2][2] = "I"  <-- group 2
J K L	   Grp[3][0] = "J" Grp[3][1] = "K" Grp[3][2] = "L"  <-- group 3
               ^        ^               ^               ^
               |        |               |               |
            group#      +---------------+---------------+
                               members in the group

Strength:   it's efficient to find all members for a given group

Weakness:   it's inefficient to find the group for a given member name

Our program need to do the latter !!! (and never need to do the former !!)

The node --> group# represention

Alternatively, we can represent a paired group by mapping a member name to the group # like this: 

4           
A C G      Grp["A"] = 0    Grp["C"] = 0    Grp["G"] = 0     <-- group 0
B D F	   Grp["B"] = 1    Grp["D"] = 1    Grp["F"] = 1     <-- group 1
E H I	   Grp["E"] = 2    Grp["H"] = 2    Grp["I"] = 2     <-- group 2
J K L	   Grp["J"] = 3    Grp["K"] = 3    Grp["L"] = 3     <-- group 3
                ^     ^
                |     |
             member  group#
             name

Strength:   it's inefficient to find the group for a given member name

Weakness:   it's efficient to find all members for a given group

That's what we want for our program !!

The C++ map data type

 

  • The C++ map class is a storage stucture to store pairs of values: 

           (key, value)

    in a way that the pairs of values can be accessed QUICKLY using key

  • How to define a map variable: 

       #include <map>

 map<keyType,valueType> mapVarName;

The C++ map data type

 

  • How to store a (key, value) pair in a map: 

         mapVarName[ key ] = value ;

    Note:   the syntax looks like that of an array, but a map is not an array !!

  • How to retrieve the value indexed by a key in a map: 

          mapVarName[ key ]

  • I will show you a program using a map variable next

A simple program using a map variable 
#include <iostream>
#include <map>

using namespace std;

int main ()
{
   // Define a map that stores: (key:string, value:int)
   map<string,int> myMap;

   // Adding (key -> value) to map
   myMap["john"]=1;
   myMap["mary"]=2;
   myMap["jake"]=3;
   myMap["anne"]=4;

   cout << "myMap[\"john\"] = " << myMap["john"] << endl;
   cout << "myMap[\"mary\"] = " << myMap["mary"] << endl;
   cout << "myMap[\"jake\"] = " << myMap["jake"] << endl;
   cout << "myMap[\"anne\"] = " << myMap["anne"] << endl;
   cout << endl;

   myMap["john"]=99;   // Updates associated value

   cout << "myMap[\"john\"] = " << myMap["john"] << endl;
   cout << "myMap[\"mary\"] = " << myMap["mary"] << endl;
   cout << "myMap[\"jake\"] = " << myMap["jake"] << endl;
   cout << "myMap[\"anne\"] = " << myMap["anne"] << endl;
   cout << endl;

   // test if a key is in the map
   cout << "myMap.count(\"john\") = " << myMap.count("john") << endl;
   cout << "myMap.count(\"mary\") = " << myMap.count("mary") << endl;
   cout << "myMap.count(\"x\") = " << myMap.count("x") << endl;

   return 0;
}

How to store the data

Improved solution: use a map the name to an index 

3           
A B        GoodPair[0][0] =     GoodPair[0][1] =    
G L	   GoodPair[1][0] =     GoodPair[1][1] =    
J K	   GoodPair[2][0] =     GoodPair[2][1] =    
2           
D F	   BadPair[0][0] =      BadPair[0][1] =    
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 0   
Map:  (empty)

How to store the data

Processing "good" pairs:   read in a pair and assign the names to a unique index 

3           
A B        GoodPair[0][0] =     GoodPair[0][1] =    
G L	   GoodPair[1][0] =     GoodPair[1][1] =    
J K	   GoodPair[2][0] =     GoodPair[2][1] =    
2           
D F	   BadPair[0][0] =      BadPair[0][1] =    
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 2    ---> Map: A -> 0  B -> 1
Map:  (empty)

How to store the data

Processing "good" pairs:   store the name -> index assignment in a map for quick access 

3           
A B        GoodPair[0][0] =     GoodPair[0][1] =    
G L	   GoodPair[1][0] =     GoodPair[1][1] =    
J K	   GoodPair[2][0] =     GoodPair[2][1] =    
2           
D F	   BadPair[0][0] =      BadPair[0][1] =    
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 2    ---> Map: A -> 0  B -> 1
Map:  A -> 0
      B -> 1

How to store the data

Processing "good" pairs:   record the "good" pair using indexes 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] =     GoodPair[1][1] =   
J K	   GoodPair[2][0] =     GoodPair[2][1] =    
2           
D F	   BadPair[0][0] =      BadPair[0][1] =    
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 2    ---> Map: A -> 0  B -> 1
Map:  A -> 0
      B -> 1

How to store the data

Processing "good" pairs:   read the next "good" pair 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] =     GoodPair[1][1] =   
J K	   GoodPair[2][0] =     GoodPair[2][1] =    
2           
D F	   BadPair[0][0] =      BadPair[0][1] =    
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 4    ---> Map: G -> 2  L -> 3
Map:  A -> 0
      B -> 1

How to store the data

Processing "good" pairs:   store the next "good" pair 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] =     GoodPair[2][1] =    
2           
D F	   BadPair[0][0] =      BadPair[0][1] =    
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 4    ---> Map: G -> 2  L -> 3
Map:  A -> 0
      B -> 1
      G -> 2
      L -> 3

How to store the data

Processing "good" pairs:   read the next "good" pair 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] =     GoodPair[2][1] =    
2           
D F	   BadPair[0][0] =      BadPair[0][1] =    
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 6    ---> Map: J -> 4  K -> 5
Map:  A -> 0   J -> 4
      B -> 1   K -> 5
      G -> 2
      L -> 3

How to store the data

Processing "good" pairs:   store the next "good" pair 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] =      BadPair[0][1] =    
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 6    ---> Map: J -> 4  K -> 5
Map:  A -> 0   J -> 4
      B -> 1   K -> 5
      G -> 2
      L -> 3

How to store the data

Processing "bad" pairs:   same procedure - I will do it quicker.... 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] =      BadPair[0][1] =    
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 6   
Map:  A -> 0   J -> 4
      B -> 1   K -> 5
      G -> 2
      L -> 3

How to store the data

Processing "bad" pairs:   same procedure - I will do it quicker.... 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 8    ---> Map: D -> 6  F -> 7
Map:  A -> 0   J -> 4
      B -> 1   K -> 5
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing "bad" pairs:   same procedure - I will do it quicker.... 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G	   BadPair[1][0] =      BadPair[1][1] =    
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 8  (Note: D and G are found in the map !)
Map:  A -> 0   J -> 4
      B -> 1   K -> 5
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing "bad" pairs:   same procedure - I will do it quicker.... 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 2   
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 8    ---> Map: no new entry !
Map:  A -> 0   J -> 4  
      B -> 1   K -> 5
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing paired groups:   design a representation that let you find same group quickly ! 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 2   
4           
A C G     
B D F	   
E H I	   
J K L	   

NextIndex = 8  
Map:  A -> 0   J -> 4  
      B -> 1   K -> 5
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing paired groups:   store group ID in array indexed by name 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 2   
4           
A C G     Something like this:  Grp["A"] = 0  Grp["C"] = 0  Grp["G"] = 0
B D F	   
E H I	  (But C++ uses integer indexes) 
J K L	  

NextIndex = 8  
Map:  A -> 0   J -> 4   
      B -> 1   K -> 5
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing paired groups:   store group ID in array indexed by name 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 2   
4           
A C G     Something like this:  Grp["A"] = 0  Grp["C"] = 0  Grp["G"] = 0
B D F	   
E H I	  (But C++ uses integer indexes) 
J K L	  Use the map to translate: "A" => 0, "C" => int index, "G" => 2

NextIndex = 8  
Map:  A -> 0   J -> 4   
      B -> 1   K -> 5
      G -> 2   D -> 6
      L -> 3   F -> 7

Read more on the C++ map class here:  
(Demo: alienware::~cheung/OutSchool/compet-prog/DataStruct/map/)

How to store the data

Processing paired groups:   read the next group 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 2   
4           
A C G      Grp[0] =     Grp[4] =     Grp[8]  = 
B D F	   Grp[1] =     Grp[5] =     Grp[9]  = 
E H I	   Grp[2] =     Grp[6] =     Grp[10] = 
J K L	   Grp[3] =     Grp[7] =     Grp[11] = 

NextIndex = 8  
Map:  A -> 0   J -> 4   
      B -> 1   K -> 5
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing paired groups:   map the unknown names 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 2   
4     
A C G      Grp[0] =     Grp[4] =     Grp[8]  = 
B D F	   Grp[1] =     Grp[5] =     Grp[9]  = 
E H I	   Grp[2] =     Grp[6] =     Grp[10] = 
J K L	   Grp[3] =     Grp[7] =     Grp[11] =  

NextIndex = 9    ---> Map: C -> 8
Map:  A -> 0   J -> 4   C -> 8
      B -> 1   K -> 5   
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing paired groups:   store the group 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] =     Grp[8]  = 0 
B D F	   Grp[1] =     Grp[5] =     Grp[9]  = 
E H I	   Grp[2] = 0   Grp[6] =     Grp[10] = 
J K L	   Grp[3] =     Grp[7] =     Grp[11] =       

NextIndex = 9 
Map:  A -> 0   J -> 4   C -> 8
      B -> 1   K -> 5   
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing paired groups:   read the group 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] =     Grp[8]  = 0 
B D F	   Grp[1] =     Grp[5] =     Grp[9]  = 
E H I	   Grp[2] = 0   Grp[6] =     Grp[10] = 
J K L	   Grp[3] =     Grp[7] =     Grp[11] =       

NextIndex = 9    
Map:  A -> 0   J -> 4   C -> 8
      B -> 1   K -> 5   
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing paired groups:   map the unknown names 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] =     Grp[8]  = 0
B D F	   Grp[1] =     Grp[5] =     Grp[9]  = 
E H I	   Grp[2] = 0   Grp[6] =     Grp[10] = 
J K L	   Grp[3] =     Grp[7] =     Grp[11] =       

NextIndex = 9    ---> Map: no new entry !
Map:  A -> 0   J -> 4   C -> 8
      B -> 1   K -> 5   
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing paired groups:   store the group 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] =     Grp[8]  = 0
B D F	   Grp[1] = 1   Grp[5] =     Grp[9]  = 
E H I	   Grp[2] = 0   Grp[6] = 1   Grp[10] = 
J K L	   Grp[3] =     Grp[7] = 1   Grp[11] =       

NextIndex = 9   
Map:  A -> 0   J -> 4   C -> 8
      B -> 1   K -> 5   
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing paired groups:   process the next group - I will do it quicker... 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] =     Grp[8]  = 0
B D F	   Grp[1] = 1   Grp[5] =     Grp[9]  = 
E H I	   Grp[2] = 0   Grp[6] = 1   Grp[10] = 
J K L	   Grp[3] =     Grp[7] = 1   Grp[11] =       

NextIndex = 9   
Map:  A -> 0   J -> 4   C -> 8
      B -> 1   K -> 5   
      G -> 2   D -> 6
      L -> 3   F -> 7

How to store the data

Processing paired groups:   process the next group - I will do it quicker... 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] =     Grp[8]  = 0
B D F	   Grp[1] = 1   Grp[5] =     Grp[9]  = 2
E H I	   Grp[2] = 0   Grp[6] = 1   Grp[10] = 2
J K L	   Grp[3] =     Grp[7] = 1   Grp[11] = 2      

NextIndex = 9     ----> Map: E -> 9  H -> 10  I -> 11
Map:  A -> 0   J -> 4   C -> 8
      B -> 1   K -> 5   E -> 9
      G -> 2   D -> 6   H -> 10
      L -> 3   F -> 7   I -> 11

How to store the data

Processing paired groups:   process the next group - I will do it quicker... 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] =     Grp[8]  = 0
B D F	   Grp[1] = 1   Grp[5] =     Grp[9]  = 2
E H I	   Grp[2] = 0   Grp[6] = 1   Grp[10] = 2
J K L	   Grp[3] =     Grp[7] = 1   Grp[11] = 2      

NextIndex = 9    
Map:  A -> 0   J -> 4   C -> 8
      B -> 1   K -> 5   E -> 9
      G -> 2   D -> 6   H -> 10
      L -> 3   F -> 7   I -> 11

How to store the data

Processing paired groups:   process the next group - I will do it quicker... 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] = 3   Grp[8]  = 0
B D F	   Grp[1] = 1   Grp[5] = 3   Grp[9]  = 2
E H I	   Grp[2] = 0   Grp[6] = 1   Grp[10] = 2
J K L	   Grp[3] = 3   Grp[7] = 1   Grp[11] = 2      

NextIndex = 9    ----> Map: no new entry !
Map:  A -> 0   J -> 4   C -> 8
      B -> 1   K -> 5   E -> 9
      G -> 2   D -> 6   H -> 10
      L -> 3   F -> 7   I -> 11

How to store the data

Computing the score: 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] = 3   Grp[8]  = 0
B D F	   Grp[1] = 1   Grp[5] = 3   Grp[9]  = 2
E H I	   Grp[2] = 0   Grp[6] = 1   Grp[10] = 2
J K L	   Grp[3] = 3   Grp[7] = 1   Grp[11] = 2      

 for each "good" pair:
    if pair found in pair group: score++

 Do we still need to search ?

How to store the data

Computing the score: 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] = 3   Grp[8]  = 0
B D F	   Grp[1] = 1   Grp[5] = 3   Grp[9]  = 2
E H I	   Grp[2] = 0   Grp[6] = 1   Grp[10] = 2
J K L	   Grp[3] = 3   Grp[7] = 1   Grp[11] = 2      

 for each "good" pair:
    if pair found in pair group: score++

 Do we still need to search ?   A B are in different groups

How to store the data

Computing the score: 

3           
A B        GoodPair[0][0] = 0   GoodPair[0][1] = 1   
G L	   GoodPair[1][0] = 2   GoodPair[1][1] = 3  
J K	   GoodPair[2][0] = 4   GoodPair[2][1] = 5   
2           
D F	   BadPair[0][0] = 6    BadPair[0][1] = 7   
D G        BadPair[1][0] = 6    BadPair[1][1] = 8   
4      
A C G      Grp[0] = 0   Grp[4] = 3   Grp[8]  = 0
B D F	   Grp[1] = 1   Grp[5] = 3   Grp[9]  = 2
E H I	   Grp[2] = 0   Grp[6] = 1   Grp[10] = 2
J K L	   Grp[3] = 3   Grp[7] = 1   Grp[11] = 2      

 for each "good" pair:
    if pair found in pair group: score++

 Do we still need to search ?     J K are in same group !