Knight Moves Problem in Java

In this text, i represent a solution for Knight Moves Problem in java. The problem is defined as follows:

Pictured here is a keypad:

We want to find all sequences of length n that can be keyed into the keypad in the following manner:

• The initial keypress can be any of the keys.
• Each subsequent keypress must be a knight move from the previous keypress. 
• There can be at most 2 vowels in the sequence.
• Run your solution for n = 1 to 32

A knight move is made in one of the following ways:

• Move two steps horizontally and one step vertically.
• Move two steps vertically and one step horizontally.
• There is no wrapping allowed on a knight move.

Here are some examples of knight moves:

Given a value for n, the program should write the number of valid n-key sequences on a single line to standard out.

Knight Moves Solution

package com.denizstij.km;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import com.denizstij.km.Keyboard.Key;
/**
 * 
 * @author Deniz Turan, http://denizstij.blogspot.co.uk denizstij AT gmail.com
 * 
 */
public class KnightMoveMain {
 private final int maxVowelCount;
 
 public KnightMoveMain(int maxVowelCount){
  this.maxVowelCount=maxVowelCount;
 }
 
 public long findNumberOfSequence(int lenOfSequence) {
  if (lenOfSequence<=0){   
   return 1;// number of empty set is 1
  }
  Map <PathInfoBean, Long> pathInfoMap= new LinkedHashMap<PathInfoBean, Long>();
  for (Key key : Keyboard.INSTANCE.getKeySet()) {   
   PathInfoBean pathinfo= new PathInfoBean(key, key.isVowel()?1:0);
   pathInfoMap.put(pathinfo, 1L);
  }
  
  long numberOfPaths = findNumberOfSequence1(pathInfoMap,1,lenOfSequence);
  return numberOfPaths;
 }
 
 private long findNumberOfSequence1(Map <PathInfoBean, Long> pathInfoMap ,int sequenceLen, int lenOfSequence) {

  if (sequenceLen>=lenOfSequence){
   long numberOfPaths=0;
   for (Long pathCount : pathInfoMap.values()) {   
    numberOfPaths+=pathCount;
   }      
   return numberOfPaths;
  }   
   
  Map <PathInfoBean, Long> pathInfoMapNew= new LinkedHashMap<PathInfoBean, Long>();
  for (Entry<PathInfoBean, Long> pathInfoBeanEntry : pathInfoMap.entrySet()) {
   PathInfoBean pathInfoBean = pathInfoBeanEntry.getKey();

   Long pathCount = pathInfoBeanEntry.getValue();
   Set<key> possibleMoveSet =pathInfoBeanEntry.getKey().getKey().getKnightMoves();
     
   for (Key key : possibleMoveSet) {
    int vowelCount=pathInfoBean.getVowelCount();
    if (key.isVowel()){
     if (vowelCount>=maxVowelCount){
      continue;
     } 
     vowelCount++;
    }
    PathInfoBean newPathInfoBean = new PathInfoBean(key,vowelCount);  
    Long currentPath = pathInfoMapNew.get(newPathInfoBean);
    if (currentPath==null)  // first time 
     pathInfoMapNew.put(newPathInfoBean,pathCount);
    else {
     // we have already, so just lets aggregate both branch
     pathInfoMapNew.put(newPathInfoBean,currentPath+pathCount);
    }
   }   
  }
  return findNumberOfSequence1(pathInfoMapNew,sequenceLen+1,lenOfSequence);
 }  
 
 public static void main(String[] args) {  
  KnightMoveMain km= new KnightMoveMain(2);
  long now = System.currentTimeMillis();
  for (int n=0;n<=32;n++) {
   long numberOfPaths = km.findNumberOfSequence(n);
   System.out.println(n+"==>"+numberOfPaths);   
  }
  long elapsedTime = System.currentTimeMillis()-now;
  System.out.println("Total Elapsed Time (msec):"+elapsedTime);
 }
}

//###############################################################
//###############################################################
//###############################################################

package com.denizstij.km;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
/**
 * 
 * @author Deniz Turan, http://denizstij.blogspot.co.uk denizstij AT gmail.com
 * 
 */
public class Keyboard{

 final private  Set <key> KEYSET= new LinkedHashSet<key>();    
 final public static Key A= new Key('A', true);
 final public static Key B= new Key('B', false);
 final public static Key C= new Key('C', false);
 final public static Key D= new Key('D', false);
 final public static Key E= new Key('E', true);
 final public static Key F= new Key('F', false);
 final public static Key G= new Key('G', false);
 final public static Key H= new Key('H', false);
 final public static Key I= new Key('I', true);
 final public static Key J= new Key('J', false);
 final public static Key K= new Key('K', false);
 final public static Key L= new Key('L', false);
 final public static Key M= new Key('M', false);
 final public static Key N= new Key('N', false);
 final public static Key O= new Key('O', true);
 final public static Key _1= new Key('1', false);
 final public static Key _2= new Key('2', false);
 final public static Key _3= new Key('3', false);

 final public static Keyboard INSTANCE= new Keyboard();

  private void init(){  
  KEYSET.add(A.setKnightMoves(H,L));
  KEYSET.add(B.setKnightMoves(I,K,M));
  KEYSET.add(C.setKnightMoves(F,J,L,N));
  KEYSET.add(D.setKnightMoves(G,M,O));
  KEYSET.add(E.setKnightMoves(H,N));
  KEYSET.add(F.setKnightMoves(C,M,_1));
  KEYSET.add(G.setKnightMoves(D,N,_2));
  KEYSET.add(H.setKnightMoves(A,E,K,O,_1,_3));
  KEYSET.add(I.setKnightMoves(B,L,_2));
  KEYSET.add(J.setKnightMoves(C,M,_3));
  KEYSET.add(K.setKnightMoves(B,H,_2));
  KEYSET.add(L.setKnightMoves(A,C,I,_3));
  KEYSET.add(M.setKnightMoves(B,D,F,J));
  KEYSET.add(N.setKnightMoves(C,E,G,_1));
  KEYSET.add(O.setKnightMoves(D,H,_2));
  KEYSET.add(_1.setKnightMoves(F,H,N));
  KEYSET.add(_2.setKnightMoves(G,I,K,O));
  KEYSET.add(_3.setKnightMoves(H,J,L));   
 }
 
 // Singleton
 private Keyboard(){
  init();
 }

public Set <key> getKeySet() {
  return KEYSET;
 }

public static class Key{
 final private char key;
 final private boolean isVowel;
 private Set<key> knightMoves;
 
 Key(char key, boolean isVowel){
  this.key=key;
  this.isVowel=isVowel;
 }

 public Key setKnightMoves(Key ...knightMoves) {
  this.knightMoves=Collections.unmodifiableSet(new HashSet<key>(Arrays.asList(knightMoves)));
  return this;
 }

 public Set<key> getKnightMoves() {
  return knightMoves;
 }

 @Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + key;
  return result;
 }

 @Override
 public boolean equals(Object obj) {
  if (this == obj)
   return true;
  if (obj == null)
   return false;
  if (getClass() != obj.getClass())
   return false;
  Key other = (Key) obj;
  if (key != other.key)
   return false;
  return true;
 }
 public char getKey() {
  return key;
 }
 
 public boolean isVowel() {
  return isVowel;
 }
 @Override
 public String toString() {
  return "Key [key=" + key + ", isVowel=" + isVowel +"]";
 }
}
}

//###############################################################
//###############################################################
//###############################################################

package com.denizstij.km;

import com.denizstij.km.Keyboard.Key;

/**
 * 
 * @author Deniz Turan, http://denizstij.blogspot.co.uk denizstij AT gmail.com
 * 
 */
public class PathInfoBean {
 final private Key key; 
 final private int vowelCount;
 
 public PathInfoBean(Key key, int vowelCount) {   
  this.key = key;
  this.vowelCount = vowelCount;
 }
 
 public Key getKey() {
  return key;
 }
 
 public int getVowelCount() {
  return vowelCount;
 }


 @Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + ((key == null) ? 0 : key.hashCode());
  result = prime * result + vowelCount;
  return result;
 }

 @Override
 public boolean equals(Object obj) {
  if (this == obj)
   return true;
  if (obj == null)
   return false;
  if (getClass() != obj.getClass())
   return false;
  PathInfoBean other = (PathInfoBean) obj;
  if (key == null) {
   if (other.key != null)
    return false;
  } else if (!key.equals(other.key))
   return false;
  if (vowelCount != other.vowelCount)
   return false;
  return true;
 }
 
 @Override
 public String toString() {
  return "PathInfoBean [key=" + key + ", vowelCount=" + vowelCount + "]\n";
 }
}

Output

1==>18
2==>60
3==>214
4==>732
5==>2486
6==>8392
7==>27912
8==>93204
9==>306288
10==>1013398
11==>3302640
12==>10842528
13==>35108325
14==>114492546
15==>368772182
16==>1195650888
17==>3833937659
18==>12367469662
19==>39505386940
20==>126863960276
21==>403894417802
22==>1291845025388
23==>4100838894764
24==>13069438426724
25==>41380854190503
26==>131455706155352
27==>415265140628246
28==>1315326269976050
29==>4146551571701468
30==>13098978945964762
31==>41218021719932582
32==>129891093550589788

Total Elapsed Time (msec):450