Friday, December 26, 2014

IsHomomorphism

Problem:

TopCoder Problem Statement - IsHomomorphism
Single Round Match 161 Round 1 - Division I, Level One

Overview:

Test if two functions, given as tables, provide the same results for a set of values.

Java Source:
01: import java.util.ArrayList;
02: import java.util.List;
03: 
04: public class IsHomomorphism {
05:  
06:  public String[] numBad(String[] source, String[] target, int[] mapping) {
07: 
08:   List results = new ArrayList<>();
09: 
10:   for (int a = 0; a < source.length; a++)  {
11:    for (int b = 0; b < source.length; b++)  {
12: 
13:     /*
14:     * Testing:
15:     * mappings(a@b) = mappings(a)~mappings(b)
16:     * for all values of a and b.
17:     */
18: 
19:     /*
20:     * For the '@' operator, the first value given is the index into
21:     * the source array, and the second value gives the character
22:     * we're interested in.
23:     */
24:     int leftSide = mapping[source[a].charAt(b) - '0'];
25: 
26:     // Same for the '~' operator, except use the target array
27:     int rightSide = target[mapping[a]].charAt(mapping[b]) - '0';
28: 
29:     // If the sides are not equal, add the pair to the results list.
30:     if (leftSide != rightSide) {
31:      results.add("(" + a + "," + b + ")");
32:     }
33:    }
34:   }
35: 
36:   // Convert the List to an array and return it.
37:   String[] ret = new String[results.size()];
38:   for (int i = 0; i < ret.length; i++)  {
39:    ret[i] = results.get(i);
40:   }
41: 
42:   return ret;
43:  }
44: }
Notes:

The source and target tables map two inputs to a result. The result of a@b is source[a].charAt(b). Likewise, the result of a~b is target[a].charAt(b). Since the value in the table is a char, we need to subtract '0' to get it's int value.

We need to determine is if:

mapping(a@b) = mapping(a)~mapping(b)

which can be coded as:

mapping[source[a].charAt(b) - '0'] == target[mapping[a]].charAt(mapping[b]) - '0'

Now, just test that for all values of a and b. For any combination that fails the test, we'll add it to a List. Once complete, we convert the List to an array, and return it.

Since we loop through a in the outer loop, and then b in the inner loop, entries will be added to the results List in exactly the order we need. There is no need to sort them to match the expected output.

No comments:

Post a Comment