Last active
October 7, 2016 22:55
-
-
Save mrmx/08db9b21c41645a42f28f393629ed2bc to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.Collections; | |
| import java.util.LinkedList; | |
| import java.util.List; | |
| /** | |
| * Compute the minimum knight movements from (0,0) -> (A,B) | |
| * | |
| * @author mrmx | |
| */ | |
| public class KnightRider { | |
| public static void main(String[] args) { | |
| for (int i = 1; i <= 10; i++) { | |
| for (int j = 1; j <= 10; j++) { | |
| System.out.println("##########################################"); | |
| System.out.println("Moves:(" + i + "," + j + "):"); | |
| System.out.println(solution(i, j)); | |
| } | |
| } | |
| //System.out.println("Solution:" + solution(4, 5)); | |
| } | |
| private static int solution(int A, int B) { | |
| Knight k = new Knight(); | |
| if (k.dist(A, B) >= 100000000d) { | |
| return -2; | |
| } | |
| return move(k, A, B, 0); | |
| } | |
| private static int move(Knight k, int A, int B, int moves) { | |
| if (k.goal(A, B)) { | |
| return moves; | |
| } | |
| if (k.dist(A, B) < 8 && moves > 8) { | |
| return moves; | |
| } | |
| List<Knight> movements = k.getMovements(A, B); | |
| moves++; | |
| //System.out.println("Best:" + movements + " moves " + moves); | |
| List<Integer> best = new LinkedList<>(); | |
| for (Knight path : movements) { | |
| if (path.goal(A, B)) { | |
| return moves; | |
| } | |
| best.add(move(path, A, B, moves)); | |
| } | |
| Collections.sort(best); | |
| return best.get(0); | |
| } | |
| final static class Knight { | |
| int x, y; | |
| public Knight() { | |
| this(0, 0); | |
| } | |
| public Knight(int x, int y) { | |
| this.x = x; | |
| this.y = y; | |
| } | |
| int dist(int a, int b) { | |
| return (int) Math.hypot(a - x, b - y); | |
| } | |
| boolean goal(int a, int b) { | |
| return x == a && y == b; | |
| } | |
| List<Knight> getMovements(int a, int b) { | |
| List<Knight> movements = getMovements(); | |
| Collections.sort(movements, (Knight o1, Knight o2) -> o1.dist(a, b) - o2.dist(a, b)); | |
| return movements.size() > 3 ? movements.subList(0, 3) : movements.subList(0, 2); | |
| } | |
| List<Knight> getMovements() { | |
| List<Knight> moves = new LinkedList<>(); | |
| moves.add(new Knight(x + 2, y + 1)); | |
| moves.add(new Knight(x + 1, y + 2)); | |
| if (y - 1 >= 0) { | |
| moves.add(new Knight(x + 2, y - 1)); | |
| if (x - 2 >= 0) { | |
| moves.add(new Knight(x - 2, y - 1)); | |
| moves.add(new Knight(x - 2, y + 1)); | |
| } | |
| } | |
| if (y - 2 >= 0) { | |
| moves.add(new Knight(x + 1, y - 2)); | |
| if (x - 1 >= 0) { | |
| moves.add(new Knight(x - 1, y - 2)); | |
| } | |
| } | |
| if (x - 1 >= 0) { | |
| moves.add(new Knight(x - 1, y + 2)); | |
| } | |
| return moves; | |
| } | |
| @Override | |
| public String toString() { | |
| return "(" + x + "," + y + ")"; | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment