Generating a multiple list of combinations for a number in Java

Question

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

Answer 1

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

Answer 2

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!

Answer 3

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.

Answer 4

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