n length knight moves combinations on keypad

Question

find n length knight move combinations on keypad numbers from 0 - 9

unable to resolve this, getting either infinite loop or the total number of expected combinations is incorrect. Tried to dynamic programming, should it be counting possible combinations or should it added to get count. please help resolve this. thank you.

import java.io.*;
import java.util.*;

/**
 *
 * 1 2 3 
 * 4 5 6 
 * 7 8 9 
 *   0
 *
 * when start at 1 : move L shape like knight on chess board
 * make 3-digit numbers, like this : 161, 167, 160, 181, and 183
 * total combis is: 5
 */
public class KeyPadKnight {
  public static void main(String[] args) {
    Map<Integer, List<Integer>> keyPadMap = new HashMap<>();
    keyPadMap.put(1, Arrays.asList(6, 8));
    keyPadMap.put(2, Arrays.asList(7, 9));
    keyPadMap.put(3, Arrays.asList(4, 8));
    keyPadMap.put(4, Arrays.asList(3, 9, 0));
    keyPadMap.put(6, Arrays.asList(1, 7, 0));
    keyPadMap.put(7, Arrays.asList(2, 6));
    keyPadMap.put(8, Arrays.asList(1, 3));
    keyPadMap.put(9, Arrays.asList(2, 4));
    keyPadMap.put(0, Arrays.asList(4, 6));

    int start = 1;

    int length = 3;

    int count = getCountCombi(keyPadMap, length, start);
    System.out.println("Total combi: " + count);

  }


  public static int getCountCombi(Map<Integer, List<Integer>> map, int length, Integer key) {

    int count = 0;

    count = findCombinations(key, map, length, count);

    return count;
  }

  public static int findCombinations(Integer val, Map<Integer, List<Integer>> map, int length,
      int counter) {

    if (length == 0) {
      return counter;
    }

    if (map.containsKey(val)) {
      for (Integer next : map.get(val)) {
        counter += map.get(next).size();
        findCombinations(next, map, length - 1, counter);
      }
    }
    return counter;
  }

}

seeing as the code you posted will not compile, I doubt it gives you an infinite loop — Stultuske, Jan 25 '19 at 08:30
I am still getting familiarized with the editor, I missed the braces while pasting it here. The code is now compiling. I am still not able to resolve my mistake. — cald00dvin, Jan 25 '19 at 17:10

score 0 · Answer 1 · answered Jan 25 '19 at 20:40

You have several mistakes in your code, which are as follow:

1. mistake

if (map.containsKey(val)) {
   [...]
}

This will always be true, you don't need this check. However, this is only a minor mistake.

2. mistake

 for (Integer next : map.get(val)) {
   counter += map.get(next).size();       // <-- this line
   findCombinations(next, map, length - 1, counter);
 }

Even if using the counter variable like you do would work (it does not), you will count the intermediate positions of a single "N step" on the counter variable, which makes it much bigger than it should be. So on each "level" you are sum up the number of possible moves, but in reality you are interested only in exactly "N step" long moves/sequences.

3. mistake

 for (Integer next : map.get(val)) {
   counter += map.get(next).size();       
   findCombinations(next, map, length - 1, counter); // <-- this line
 }

The main problem is that you think the counter variable is changed back from your recursive method call to your previous location where you called your recursive call. However, this is not the case. Additionally, you are not using the return value of that method call at all. In fact, your method call as it is right now has no effect at all and you could remove it. This would show you why your code return wrong results.

To make it work properly you have to save the return value of that recursive method call in a variable and use it somehow in your calculation. In pseudo code, your method should be like this:

if (length < 1) {
    throw new IllegalArgumentException("length must be positive");
}
if (length == 1) {
   return number of jump positions from that location only
}
int sum = 0;
for (each possible jump location) {
    sum += recursive call from that location and length-1;
}
return sum;

n length knight moves combinations on keypad

1 Answers1

1. mistake

2. mistake

3. mistake