patternjavaModerate
Knight moves in Chess game
Viewed 0 times
chessgameknightmoves
Problem
I am trying to learn Java by doing some (easy) ACM ICPC problems. The problem consist to check if the knight in a chess game can move from a point
```
package dalia;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
public class Dalia {
static int[] moves = { -1, 2, -1, -2, 1, 2, 1, -2, -2, 1, -2, -1, 2, 1, 2, -1 };
public static void main(String[] args) throws IOException {
File fin = new File("./dalia.in");
knight(fin);
}
private static void knight(File fin) throws IOException {
try (BufferedReader br = new BufferedReader(new FileReader(fin))) {
String line;
// Read the number of cases.
int numberOfCases = Integer.parseInt(br.readLine());
int[] cord = new int[5];
String[] parts;
int i = 0;
// Solve each case
while ((line = br.readLine()) != null && i < numberOfCases) {
// Split the line to array of integer
parts = line.split(" ");
for (int j = 0; j < 5; j++) {
cord[j] = Integer.parseInt(parts[j]);
}
// Print case number
i++;
System.out.print("Case " + i + ": ");
// Check if the knight can move
if (validMove(cord[0], cord[1], cord[2], cord[3], cord[4]))
System.out.println("YES");
else
System.out.println("NO");
}
br.close();
}
}
private static boolean validMove(int n, int r1, int c1, int r2, int c2) {
// Return True if the knight can move from (r1, c1) to (r2, c2) in one
// move
for (int i = 0; i < moves.length; i = i + 2) {
if (r1 == r2 + moves[i] && c1 == c2 + moves[i + 1] && stillInTheBoard(n, r2, moves[i])
&& stillInTheBoard(n, c2, moves[i + 1]))
return true;
}
return false;
}
private static boolean stillInTheBoard(int n, int x1, int x2) {
// Check if the knight still in the board after making the move
A(r1, c1) to B(r2, c2) with one move only.```
package dalia;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
public class Dalia {
static int[] moves = { -1, 2, -1, -2, 1, 2, 1, -2, -2, 1, -2, -1, 2, 1, 2, -1 };
public static void main(String[] args) throws IOException {
File fin = new File("./dalia.in");
knight(fin);
}
private static void knight(File fin) throws IOException {
try (BufferedReader br = new BufferedReader(new FileReader(fin))) {
String line;
// Read the number of cases.
int numberOfCases = Integer.parseInt(br.readLine());
int[] cord = new int[5];
String[] parts;
int i = 0;
// Solve each case
while ((line = br.readLine()) != null && i < numberOfCases) {
// Split the line to array of integer
parts = line.split(" ");
for (int j = 0; j < 5; j++) {
cord[j] = Integer.parseInt(parts[j]);
}
// Print case number
i++;
System.out.print("Case " + i + ": ");
// Check if the knight can move
if (validMove(cord[0], cord[1], cord[2], cord[3], cord[4]))
System.out.println("YES");
else
System.out.println("NO");
}
br.close();
}
}
private static boolean validMove(int n, int r1, int c1, int r2, int c2) {
// Return True if the knight can move from (r1, c1) to (r2, c2) in one
// move
for (int i = 0; i < moves.length; i = i + 2) {
if (r1 == r2 + moves[i] && c1 == c2 + moves[i + 1] && stillInTheBoard(n, r2, moves[i])
&& stillInTheBoard(n, c2, moves[i + 1]))
return true;
}
return false;
}
private static boolean stillInTheBoard(int n, int x1, int x2) {
// Check if the knight still in the board after making the move
Solution
I feel @spyr03's answer is great (+1 it), but I would like to extend it a but further in a number of ways.
Algorithm
The suggestion that you can validate the move by checking one axis moves 2, and the other moves 1, is an interesting, but not ambitious enough solution. A knight moves in a right-angled pattern, with 2 steps on one side, and 1 on the other.
Pythagoras indicates that the square on the hypoteneuse is the same as the sum of the other two squares.
Putting those together, there is a really neat trick....
You can avoid the conditional checks on 1 or 2 steps, and you can also remove the
Try-With-Resources
I really like that you have used a try-with-resources to open the buffered reader (though again, @spyr03's suggestion to use a Scanner is a good one.
My special point here, though, is that one of the main reasons that try-with-resources was introduced, is to ensure the resources are always closed in a sane order.
There is no need to explicitly close the buffered reader at all... the try block is designed to do that for you.
Algorithm
The suggestion that you can validate the move by checking one axis moves 2, and the other moves 1, is an interesting, but not ambitious enough solution. A knight moves in a right-angled pattern, with 2 steps on one side, and 1 on the other.
Pythagoras indicates that the square on the hypoteneuse is the same as the sum of the other two squares.
Putting those together, there is a really neat trick....
public boolean isValid(int r1, int c1, int r2, int c2) {
// use pythagoras to ensure that a move makes a right-angled
// triangle move with sides of 1 and 2. 1-squared + 2 squared is 5.
int deltaR = r2 - r1;
int deltaC = c2 - c1;
return 5 == deltaR * deltaR + deltaC * deltaC;
}You can avoid the conditional checks on 1 or 2 steps, and you can also remove the
Math.abs() calls because the square of negative numbers are always positive.Try-With-Resources
I really like that you have used a try-with-resources to open the buffered reader (though again, @spyr03's suggestion to use a Scanner is a good one.
My special point here, though, is that one of the main reasons that try-with-resources was introduced, is to ensure the resources are always closed in a sane order.
There is no need to explicitly close the buffered reader at all... the try block is designed to do that for you.
Code Snippets
public boolean isValid(int r1, int c1, int r2, int c2) {
// use pythagoras to ensure that a move makes a right-angled
// triangle move with sides of 1 and 2. 1-squared + 2 squared is 5.
int deltaR = r2 - r1;
int deltaC = c2 - c1;
return 5 == deltaR * deltaR + deltaC * deltaC;
}Context
StackExchange Code Review Q#105748, answer score: 11
Revisions (0)
No revisions yet.