Skip to content

Instantly share code, notes, and snippets.

@aadnk
Last active January 25, 2019 04:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aadnk/52dd0048952daa40ad24739162c9638f to your computer and use it in GitHub Desktop.
Save aadnk/52dd0048952daa40ad24739162c9638f to your computer and use it in GitHub Desktop.
Trapped Knight Problem
import java.util.*;
public class SquareSpiral {
// Starting point of the spiral
private final int startX;
private final int startY;
private SquareSpiral(int startX, int startY) {
this.startX = startX;
this.startY = startY;
}
public static void main(String[] args) {
SquareSpiral spiral = new SquareSpiral(0, 0);
// Legal movements of a knight
Point[] movements = new Point[] {
new Point(-1, -2), new Point(1, -2),
new Point( -2, -1), new Point(2, -1),
new Point( -2, 1), new Point(2, 1),
new Point(-1, 2), new Point(1, 2)
};
int x = 0;
int y = 0;
List<Point> path = new ArrayList<>();
Set<Point> visited = new HashSet<>();
Point startPoint = new Point(0, 0);
path.add(startPoint);
visited.add(startPoint);
for (int i = 1; i < 50000; i++) {
//System.out.println("Step " + i + ", x: " + x+ ", y: " + y + " = " + spiral.getCellIndex(x, y));
// Now find the smallest next value
int bestScore = Integer.MAX_VALUE;
int bestIndex = -1;
for (int j = 0; j < movements.length; j++) {
Point movement = movements[j];
int x1 = movement.getX() + x;
int y1 = movement.getY() + y;
// Skip previously visited cells
if (visited.contains(new Point(x1, y1))) {
continue;
}
int currentScore = spiral.getCellIndex(x1, y1);
if (currentScore < bestScore) {
bestScore = currentScore;
bestIndex = j;
}
}
if (bestIndex < 0) {
System.out.println("Trapped in step " + i + ", x: " + x+ ", y: " + y + " = " + spiral.getCellIndex(x, y));
// Remove current point
path.remove(path.size() - 1);
// Go to previous point
Point prev = path.get(path.size() - 1);
x = prev.getX();
y = prev.getY();
i--;
} else {
x += movements[bestIndex].getX();
y += movements[bestIndex].getY();
Point nextPoint = new Point(x, y);
visited.add(nextPoint);
path.add(nextPoint);
}
}
}
private int getCellIndex(int x, int y) {
/*
Consider the following square spiral:
x -2 -1 0 1 2
y ------------------
-2 | 17 16 15 14 13
-1 | 18 05 04 03 12
0 | 19 06 01 02 11
1 | 20 07 08 09 10
2 | 21 22 23 24 25 ...
The spiral starts at point (0, 0), marked as 01. It then moves in a square around 01, starting at
02 and ending at 09. Let this be square index 1. Next, the spiral moves in another square,
starting from 10 and ending at 25. Let this be square index 2, and so on.
It is this square index we compute next:
*/
int squareIndex = Math.max(Math.abs(x - startX), Math.abs(y - startY));
// Compute the number of the cell at the top-left corner of the square. In square 1, this would be 05,
// and in square 2, this is 17, and so on.
int squareMiddleNumber = 4 * squareIndex * squareIndex + 1;
// The coordinates of the top-left corner in the square
int squareMiddleX = startX - squareIndex;
int squareMiddleY = startY - squareIndex;
// Do point (x, y) come before or after the top-left corner in the sequence
if (y >= x) {
// Point comes after in the sequence - add the value of the top-left corner to the manhattan distance
// of our current point
return squareMiddleNumber + Math.abs(squareMiddleX - x) + Math.abs(squareMiddleY - y);
} else {
// As above, only we subtract the manhattan distance
return squareMiddleNumber - Math.abs(squareMiddleX - x) - Math.abs(squareMiddleY - y);
}
}
/**
* An integer point in 2D space.
*/
public static class Point {
private final int x;
private final int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Point point = (Point) o;
return x == point.x &&
y == point.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
@Override
public String toString() {
return "Point{" +
"x=" + x +
", y=" + y +
'}';
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment