Problem Description

You are provided with two strings, coordinate1 and coordinate2, that represent the coordinates of squares on an 8 x 8 chessboard. The task is to determine if these two squares have the same color. The chessboard squares follow the standard pattern where alternating squares are colored differently, creating a checkered layout. The coordinates are always given with the column letter followed by the row number.

Intuition

To determine if two chessboard squares have the same color, consider how the colors alternate:

• Each square is identified by a letter (column) and a number (row).
• Chessboard columns are represented by letters 'a' to 'h', and rows are numbered from '1' to '8'.
• The pattern alternates such that:
  • Squares in columns 'a', 'c', 'e', 'g' are black on odd-numbered rows (1, 3, 5, 7) and white on even-numbered rows (2, 4, 6, 8).
  • Squares in columns 'b', 'd', 'f', 'h' are white on odd-numbered rows and black on even-numbered rows.

Using this pattern, the key insight is:

• The combined parity of the column and row, when expressed numerically, determines the color:
  • Convert the column to a number using ord(column) % 2 and the row using row % 2.
  • Calculate their sum; if the sum is even, the square is one color; if odd, the opposite color.

With this understanding, we calculate:

• Convert the column letters to numerical indices and compare the sum of indices and row numbers mod 2 for both coordinates.
• The colors match if the combined checks (column index + row) % 2 are equal for both coordinates.

Learn more about Math patterns.

Solution Approach

The solution utilizes a straightforward mathematical approach. We leverage the inherent checkered pattern of the chessboard and the properties of even and odd numbers. Here's how the solution is implemented:

1. Coordinate Transformation:

   • Convert the column from a letter to a number. This is done by using the ASCII value of the character: ord(coordinate[0]). This gives us a numerical representation of the column.
   • For example, ord('a') results in 97. To make 'a' correspond to a base value of 0, calculate ord(column) - ord('a'). This ensures 'a' starts at 0, 'b' at 1, and so forth.

2. Sum Calculation:

   • The row from the coordinate is already a simple integer, as it ranges from 1 to 8.
   • Calculate the parity of the coordinates by computing (column_index + row_number) % 2.

3. Comparison:

   • For both coordinates, compute the formula (ord(coordinate[0]) - ord('a') + int(coordinate[1])) % 2.
   • Compare the results for both coordinates. If they are the same, the squares are of the same color.

The solution uses this algorithm to determine the parity relationship between the two coordinates:

class Solution:
    def checkTwoChessboards(self, coordinate1: str, coordinate2: str) -> bool:
        x = ord(coordinate1[0]) - ord(coordinate2[0])
        y = int(coordinate1[1]) - int(coordinate2[1])
        return (x + y) % 2 == 0

This concise calculation lets us quickly determine if the two squares are the same color, leveraging simple arithmetic and the modular property to handle the checkered pattern efficiently.

Example Walkthrough

Let's consider two example coordinates on a chessboard: coordinate1 = 'a1' and coordinate2 = 'c1'. We will determine if these two squares have the same color using the solution approach explained.

1. Coordinate Transformation:

   • For coordinate1 = 'a1':
     • Column letter 'a' is converted to a number using ord('a') - ord('a') = 0.
     • Row number '1' is already an integer: int('1') = 1.
   • For coordinate2 = 'c1':
     • Column letter 'c' is converted to a number using ord('c') - ord('a') = 2.
     • Row number '1' is already an integer: int('1') = 1.

2. Sum Calculation:

   • Calculate the parity (even or odd sum) for each coordinate:
     • For coordinate1 = 'a1': (0 + 1) % 2 = 1.
     • For coordinate2 = 'c1': (2 + 1) % 2 = 1.

3. Comparison:

   • Since the parity for both coordinates is the same (1), this indicates that both squares are of the same color.

By following these steps, we conclude that the squares at coordinate1 = 'a1' and coordinate2 = 'c1' are the same color on the chessboard.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(1). This is because the operations performed (converting characters to their ASCII values, performing arithmetic operations, and evaluating a modulus condition) all take constant time, independent of the input size.

The space complexity of the code is O(1). This is due to the fact that the method only uses a fixed amount of extra space for the variables x and y, and does not require any additional space that grows with the input size.

Learn more about how to find time and space complexity quickly.