8
\$\begingroup\$

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 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
    return (1 <= x1 + x2 && x1 + x2 <= n);
  }

}

Example:

Input:

2
4 1 2 2 4
5 1 1 3 3

Output:

Case 1: YES
Case 2: NO

Where the first number is n, the number of block in the Chess board (in the normal Chess board n = 8).

I'm looking for a review in terms of best practices, things I should or shouldn't do, or things I should do in another way.

\$\endgroup\$
7
\$\begingroup\$

Input

Split input, output and the algorithm up, they are tangled together and it makes the code much harder to read.

Make the main modular, for example

int testCases = getInput();
int currentCase = 1;
while(currentCase <= testCases) {
    String[] in = getInput();
    String result = knight(in);
    printOutput(result);
    currentCase++;
}

Speaking of input, while a buffered reader is probably faster, I don't think the performance is worth it over the simplicity of a scanner.


Algorithm

What can we say about a knights move? It moves the piece 2 squares in a line, and then 1 square perpendicular. You have listed all the possible moves, but we can just check if one of the absolute differences is 2, and the other is 1.

row = Math.abs(r2 - r1);
col = Math.abs(c2 - c1);
return ((row == 2 && col == 1) || (row == 1 && col == 2));

This also means you only have to check if both of the input co-ordinates are valid and on the board, which can be done before the method


Conditional Operator

if (validMove(cord[0], cord[1], cord[2], cord[3], cord[4]))
    System.out.println("YES");
else
    System.out.println("NO");

This can be turned into a conditional or ternary operator

System.out.println("Case " + i + ": " + 
    (validMove(cord[0], cord[1], cord[2], cord[3], cord[4])) ? "YES" : "NO");
\$\endgroup\$
  • \$\begingroup\$ I got the following error when I try to use the ternary operator in the print function Type mismatch: cannot convert from String to boolean and there are a wrong ) after cord[4]? \$\endgroup\$ – Chaker Sep 26 '15 at 14:58
  • 1
    \$\begingroup\$ The ternary operator has lower precedence than +, so missing parentheses need to be added. \$\endgroup\$ – 200_success Sep 26 '15 at 20:19
  • \$\begingroup\$ @Chaker you need an open parens before validMove \$\endgroup\$ – Kyranstar Sep 26 '15 at 20:24
  • \$\begingroup\$ @200_success Should I fix t or not? If I do, then 3 comments are invalidated \$\endgroup\$ – spyr03 Sep 27 '15 at 13:00
  • \$\begingroup\$ Actually, comments are meant to be invalidated! Go ahead and edit your answer, then flag the invalidated comments as obsolete, since they will have served their purpose of helping you arrive at a better answer. \$\endgroup\$ – 200_success Sep 27 '15 at 15:02
10
\$\begingroup\$

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....

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.

\$\endgroup\$
  • \$\begingroup\$ your algorithm works but if i saw that code in the wild i'd have no idea what i was looking at \$\endgroup\$ – undergroundmonorail Sep 26 '15 at 15:39
  • \$\begingroup\$ @undergroundmonorail - with the 'comments' in the surrounding description I can understand. I have added comments to the actual code now and renamed the variables. Should help a lot. \$\endgroup\$ – rolfl Sep 26 '15 at 15:43
  • \$\begingroup\$ @rolfl - I don't understand why it should be better to make 2 multiplications, one addition and one comparison rather than getting 2 absolute values and doing 4 comparisons: I had thougth absolute value (very simple bitwise operation) as well as comparison needed less execution time than a multiplication (or even 2 here). Moreover, the non-pythagoras solution is much easier to read and understand, without needing comments explaining what's being done... \$\endgroup\$ – fpierrat Sep 27 '15 at 1:30
  • 3
    \$\begingroup\$ @fpierrat - I ran some benchmarks, and found that the pythagoras route is about 1/3 faster than the Math.abs for most people's testing, but, with a fully warmed up Java instance, the Math.abs starts to win out (by my calculation, after you have called the function about 400,000,000 times). The code I ran to test it, and the results I got, are here: pastebin.com/6yKk9Ji8 . That code uses the MicroBench harness I have put on GitHub here: github.com/rolfl/MicroBench - The test creates 20x20 boards, and computes each square against every other square. \$\endgroup\$ – rolfl Sep 27 '15 at 2:45
  • 1
    \$\begingroup\$ Thanks for this benchmark, you taught me testing is better than intuition for such matters :-) @Adwait Kumar: 1^2+2^2=5, so the hypothenuse^2=5 (hypothenuse=√5) \$\endgroup\$ – fpierrat Sep 27 '15 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.