Generating a multiple list of combinations for a number in Java

The following is the problem I'm working on and my snippet of code. Is there a better way to implement this? I have used basic c开发者_如何学Control structures for this below.

Is it better to store the rows and columns in a map and searching through the map based on the key/value pairs?

There is a security keypad at the entrance of a building. It has 9 numbers 1 - 9 in a 3x3 matrix format.

1 2 3

4 5 6

7 8 9

The security has decided to allow one digit error for a person but that digit should be horizontal or vertical. Example: for 5 the user is allowed to enter 2, 4, 6, 8 or for 4 the user is allowed to enter 1, 5, 7. IF the security code to enter is 1478 and if the user enters 1178 he should be allowed.

The following is a snippet of code i was working on:

ArrayList<Integer> list = new ArrayList<Integer>();
int num = 9;
int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};

for(int i =0;i< arr.length;i++){
  for(int j = 0; j <arr.length;j++){
    if(num == arr[i][j]){
      row = i;
      col = j;
      break;

    }
  }
}
for(int j1 = 0; j1< 3 ; j1++){
  if(arr[row][j1] != num){
    list.add(arr[row][j1]);
  }
}
for(int i1 = 0 ; i1 <3;i1++){
  if(arr[i1][col] != num){
    list.add(arr[i1][col]);
  }
}

There are many ways to solve this, but I think it can be solved with HashMaps and HashSets more efficiently than doing several iterations.

If I were you, I would build the data model first using a hash map and a hash set. This is because hash map and hash set have fast lookup, (no iterations)

HashMap<Integer,HashSet<Integer>> values = new HashMap<Integer, HashSet<Integer>>();

//now put in the accepted values for one
HashSet<Integer> oneValues = new HashSet<Integer>();
oneValues.put(1);
oneValues.put(2);
oneValues.put(4);
values.put(1, oneValues);

//put in 2 values
......

Then when you parse your input, if you want to see if an inputed value is accepted for what the code is, just do something like

private boolean isAccepted(int input, int combinationValue)
{
  // check to see if the inputed value in the accepted values set
  return values.get(combinationValue).contains(input);
}

I would tend to want a function along the lines of isCloseTo(int a, int b) So, say, if I called isCloseTo(5, 5) it would return true. If I called isCloseTo(2, 5) it should return true, too. But if I called isCloseTo(1, 3) it would return false.

So I'd write tests like that:

assertTrue(isCloseTo(5, 5));

OK, that's really easy to get to pass:

public boolean isCloseTo(int a, int b) {return true;}

Then, maybe

assertFalse(isCloseTo(1, 3));

which fails with the above implementation, so I'd need to change it

public boolean isCloseTo(int a, int b) {return a == b;}

That's still an incomplete implementation, so we need another test

assertTrue(isCloseTo(1, 2));

Now we start to need some real substance. And I think I'll leave the rest as an exercise for the reader. Yes, I've left the tricky bits out, but this is a strategy (test-driven design) that leads you more directly to solutions than just trying to write the code. As long as you keep all the test passing, you make steady progress toward a complete solution. Good luck!

There are many different acceptable solutions here. I suppose it's easier to construct 10x10 matrix of integer to check for the errors (for example errorMatrix). First index then will mean original digit, second index - digit typed by user, and value of arr[i][j] is a number of errors for this digit pair. Initialize it that way:
errorMatrix[i][i] = 0 //no error
errorMatrix[i][j] = 1, where i and j are horizontally or vertically neighboring digits
errorMatrix[i][j] = 2, in other cases.

Then for every digit pair you will get number of errors in O(1). You stated that you will accept only one error, so the value of 2 for unmatched pairs will be enough and you can just sum up the error numbers and compare it to one.

So, how to construct this. Iterate through all of the digit pairs and find the value of error. You should better implement function CheckError that will calculate it for digit pair a and b

1. if a=b, then errorMatrix is 0;
   
2. The digits a and b are vertical neighbors if abs(a-b) = 3. So, is abs(a-b)==3 set errorMatrix[a][b] = 1;
   

3. The digits a and b are horizontal neighbors if
   

   a. (a-1)/3==(b-1)/3 - here we check that this digits are on the same line.
   b. abs(a-b)==1 - here we check that digits are in the neighboring cells.
   If (a) and (b) then error value is 1;
   

4. In other cases error value is 2.
   

It seems to me that this spec is right. However, you need to test it before using

So, if you then want to handle the changes of the keypad layout you just have to rewrite CheckError method.

Hope it helps.

Or this...

boolean matchDigit(int p, int d) {
   return (p==d) 
       || (p==d-3) 
       || (p==d+3) 
       || (d%3!=1 && p==d-1) 
       || (d%3!=0 && p==d+1);
} 

this assumes we've already assured that p and d are between 1 and 9.

For the specific keyboard in your question we can use a base 3 to solve this problem and to calculate the distances between digits/keys.

1 { 1 / 3, 1 % 3 } = {0, 1}
2 { 2 / 3, 2 % 3 } = {0, 2}
...
5 { 5 / 3, 5 % 3 } = {1, 2}
...
8 { 8 / 3, 8 % 3 } = {2, 2}

public boolean isValidCode(int code, int expexted) {
    while(code > 0)
    {
        if (!isValidDigit(code % 10, expected % 10))
            return false ;
        code /= 10 ;
        expected /= 10 ;
    }

    return (code == expected) ;
}

public boolean isValidDigit(int a, int b) {
    int dx = (a - b) / 3 ;
    int dy = (a - b) % 3 ;
    return ((Math.abs(dx) + Math.abs(dy)) == 1)
}

A more generic and robust solution will be to create a Map where you can set what other keys you accept.

Sample: allowing A, Z, P, M, N for A: place a new entry 'A'="AZPMN" in the map, validation checkd if the character is the same or if the type character is in the exceptions string.

private Map acceptedChars = new HashMap() ;

public void loadAcceptedCharacters() {
    acceptedChars.put('A', "AZPMN") ;
}

public boolean isValidKeyword(String word, String expected)
{
    if (word == null || word.matches("\\s*"))
        return false ;

    if (word.length() != expected.length())
        return false ;

    for(int idx = 0; idx < word.length(); idx++)
    {
        if (!isValidDigit(word.chatAt(idx), expected.charAt(idx)))
            return false ;
    }

    return true ;
}

public boolean isValidDigit(char chr, char expected) {
    String accepted ;
    if (chr != expected)
    {
        accepted = acceptedChars.get(chr) ;
        if (accepted == null)
            return false ;
        if (accepted.indexOf(chr) < 0) 
            return false ;
    }
    return true ;
}