TopCoder Problem Statement - IsHomomorphism |

Single Round Match 161 Round 1 - Division I, Level One |

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

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: Listresults = 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: }

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