balaji R
Cover image for Bishop Path Traversal - Part 1

Bishop Path Traversal - Part 1

Balaji Ramasamy's profile pic
Balaji Ramasamy Full Stack Developer

Feb 24, 2022

typescriptcompetitive programmingrecursivetechnical interview problemreactdynamic programming

Problem Statement:

Write a program which will take starting and ending co ordinates say P1(x, y) and P2(x, y) and return the path in the form of array if a bishop has to traverse from p1 to p2 in 8x8 chessboard.

Example 1:

Input:

Starting Co ordinates:

{ x: 0, y: 1 }

Ending Co ordinates:

{ x = 3, y = 4 }
Output:
[
	{ x: 0, y: 3 },
	{ x: 1, y: 4 },
	{ x: 0, y: 5 },
];

Example 2:

Input:

Starting point:

{ x: 0, y: 3 }

Ending Point:

{ x: 2, y: 5 }
Output:
[
	{ x: 0, y: 3 },
	{ x: 1, y: 4 },
	{ x: 2, y: 5 },
];

Example 3:

Input:

Starting point:

{ x: 0, y: 3 }

Ending Point:

{ x: 0, y: 4 }
Output:
null

Approach:

In the game of chess, a Bishop can only move diagonally and there is no restriction in distance for each move.

Chess-Example-2.png

The above screenshot represents the solution mapped on a grid with start point as red, end point as green and traversed cells as yellow.

Possible moves for bishop:
  1. topLeft
  2. topRight
  3. bottomLeft
  4. bottomRight

Chess-Example-1.png

Invalid Moves:

Chess-Example-3.png

Steps:

  1. If startPoint and endPoint is on same row,
    1. If endPoint is on the right side, then move to either topRight cell or bottomRight cell,
    2. else move to topLeft or bottomLeft cell
  2. If startPoint and endPoint is on same column,
    1. If endpoint is above the startPoint, then move to either topRight or topLeft cell
    2. else move to bottomRight or bottomLeft

  3. startPoint and endPoint is on top left section, then move to topLeft .

  4. startPoint and endPoint is on top right section, then move to topRight .

  5. startPoint and endPoint is on bottom left section, then move to bottomLeft .

  6. startPoint and endPoint is on top bottom right section, then move to bottomRight.

Note:

Before diving into the solution kindly try to solve this on your own.

Solution:

This program can be solved by recursion. In this post I will be using typescript to solve this problem. First lets define our IPoint interface.

export interface IPoint {
	x: number;
	y: number;
}

So our main function would with parameters would something like this:

export const traverseBishopMove = (
	start: IPoint,
	end: IPoint,

): IPoint[] | null => { ...}

Also let's define some reusable utility functions to make it easier for us to understand and write the code.

const moveTopLeft = () => {
	console.log('tl');
	// top left
	return traverseBishopMove({ x: start.x - 1, y: start.y - 1 }, end);
};
const moveTopRight = () => {
	console.log('tr');
	// top right
	return traverseBishopMove({ x: start.x - 1, y: start.y + 1 }, end);
};
const moveBottomRight = () => {
	console.log('bl');
	// bottom right
	return traverseBishopMove({ x: start.x + 1, y: start.y + 1 }, end);
};
const moveBottomLeft = () => {
	console.log('bl');
	// bottom left
	return traverseBishopMove({ x: start.x + 1, y: start.y - 1 }, end);
};

Every recursion should cover the edge cases and breaking condition at the very earliest.

Before calling our recursive function it is better to check if the end point is with in 8x8 chess board or not.

export const traverseBishopMoveMain = (
	start: IPoint,
	end: IPoint,

): IPoint[] | null => {
	if (end.x < 0 || end.y < 0 || end.x >= 8 || end.y >= 8) {
		return null;
	}
	return traverseBishopMove(start, end);
};

In our problem the edge conditions is that if either of our start or end point is out of our 8x8 chess board. If so, then we will return null.

if (start.x < 0 || start.y < 0 || start.x >= 8 || start.y >= 8) {
	return null;
}

Now our break condition which is that if both start and end points are same, that means it is traversable so we can just return currentPoint which is our startPoint. After that we will execute our based on the step we have seen above.

Full solution:

interface IPoint {
	x: number;
	y: number;
}
const moveTopLeft = (start: IPoint, end: IPoint) => {
	console.log('tl');
	// top left
	return traverseBishopMove({ x: start.x - 1, y: start.y - 1 }, end);
};
const moveTopRight = (start: IPoint, end: IPoint) => {
	console.log('tr');
	// top right
	return traverseBishopMove({ x: start.x - 1, y: start.y + 1 }, end);
};
const moveBottomRight = (start: IPoint, end: IPoint) => {
	console.log('bl');
	// bottom right
	return traverseBishopMove({ x: start.x + 1, y: start.y + 1 }, end);
};
const moveBottomLeft = (start: IPoint, end: IPoint) => {
	console.log('bl');
	// bottom left
	return traverseBishopMove({ x: start.x + 1, y: start.y - 1 }, end);
};
const traverseBishopMove = (
	start: IPoint,
	end: IPoint,
	n: number = 8
): IPoint[] | null => {
	if (start.x < 0 || start.y < 0 || start.x >= n || start.y >= n) {
		return null;
	}
	if (start.x == end.x && start.y == end.y) {
		return [start];
	}
	let result = null;

	if (start.x == end.x) {
		console.log('same row');
		if (end.y > start.y) {
			console.log('right');
			if (end.y - start.y === 0 || (end.y - start.y - 1) % 2 === 0) {
				return null;
			}
			result = moveTopRight(start, end);
			if (result == null) {
				result = moveBottomRight(start, end);
			}
		} else {
			console.log('left');
			if (start.y - end.y === 0 || (start.y - end.y + 1) % 2 === 0) {
				return null;
			}
			result = moveTopLeft(start, end);
			if (result == null) {
				result = moveBottomLeft(start, end);
			}
		}
	} else if (start.y == end.y) {
		console.log('same column');
		if (end.x > start.x) {
			console.log('bottom');
			if (end.x - start.x === 0 || (end.x - start.x - 1) % 2 == 0) 
                                 return null;
			result = moveBottomRight(start, end);
			if (result == null) result = moveBottomLeft(start, end);
		} else {
			console.log('top');
			if ((start.x - end.x === 0 || (start.x - end.x + 1) % 2) == 0)
				return null;
			result = moveTopLeft(start, end);
			if (result == null) result = moveTopRight(start, end);
		}
	} else if (end.x > start.x && end.y > start.y) {
		result = moveBottomRight(start, end);
	} else if (end.x < start.x && end.y < start.y) {
		result = moveTopLeft(start, end);
	} else if (end.x > start.x && start.y > end.y) {
		result = moveBottomLeft(start, end);
	} else if (start.x > end.x && end.y > start.y) {
		result = moveTopRight(start, end);
	}
	if (result != null) {
		return [start, ...result];
	}
	return null;
};
console.log(traverseBishopMove({ x: 0, y: 0 }, { x: 9, y: 9 }));

In the next example, we will see how we can visualize this in a UI format using a framework such as ReactJs.

Chess-Example-4.png

Demo UI