Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
How about using A* search where the position cost would be the number of moves needed to get to the solution and the expected remaining cost off ( | pos_x - dest_x | + | pos_y - dest_y | ) / 3 . Computing the memory cost and the O would be hard though...
A* seems a good solution. We normally construct a A* tree from a graph, but here we can construct it directly from the chessboard.
I did not get why the remaining cost (i.e. the heuristic) is calculated as done. I think it should be straight-line distance.
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static Scanner s=new Scanner(System.in);
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int sx,sy,dx,dy;
sx=s.nextInt();
sy=s.nextInt();
dx=s.nextInt();
dy=s.nextInt();
int mx=0,my=0;
int vertmoves,horzmoves;
vertmoves=dy-sy;
horzmoves=dx-sx;
if(Math.abs(vertmoves)>Math.abs(horzmoves))
{
if(vertmoves<0 && horzmoves>0)
{
while(horzmoves!=mx && vertmoves!=my && (dx!=sx && dy!=sy ))
{
my-=2;
my+=1;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves>0 && horzmoves>0)
{
while(horzmoves!=mx && vertmoves!=my &&(dx!=sx && dy!=sy ))
{
mx+=2;
my+=1;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves<0 && horzmoves<0)
{
while((horzmoves)!=mx && (vertmoves)!=my && (dx!=sx && dy!=sy ))
{
mx-=2;
my-=1;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves<0 && horzmoves<0)
{
while((horzmoves)!=mx && (vertmoves)!=my && (dx!=sx && dy!=sy ))
{
mx+=2;
my-=1;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
}
else if(Math.abs(vertmoves)<Math.abs(horzmoves))
{
if(vertmoves<0 && horzmoves>0)
{
while(horzmoves!=mx && (vertmoves)!=my && (dx!=sx && dy!=sy ))
{
my-=1;
mx+=2;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves>0 && horzmoves>0)
{
while((horzmoves!=mx && vertmoves!=my) && (dx!=sx && dy!=sy ))
{
my+=1;
mx+=2;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves<0 && horzmoves<0)
{
while((horzmoves)!=mx && (vertmoves)!=my && (dx!=sx && dy!=sy ))
{
my-=1;
mx-=2;
}
else if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves>0 && horzmoves<0)
{
while((horzmoves)!=mx && vertmoves!=my && (dx!=sx && dy!=sy ))
{
my+=1;
mx-=2;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
}
}
}
To get the knight from <x0,y0> to <x1,y1>, you have to find an all-integers solution to the system
c0<2,1>+c1<-2,1>+c2<-2,-1>+c3<2,-1>+c4<1,2>+c5<-1,2>+c6<1,-2>+c7<-1,-2>+<x0,y0> = <x1, y1>
(You can dump half the terms, since for example c0<2,1>+c2<-2,-1>=(c0-c2)<2,1>.)
This is basic linear algebra, will take a bit of playing around but it's doable. The shortest route would correspond to the smallest-norm solution.
Pathfinding or the brute-force traversing of the entire state-space of possible moves will also work. But solving the equation above is probably the most optimal approach? Any other opinions?
Here is my answer.
from collections import deque
def in_bounds(x, y, xb, yb):
return x <= xb and y <= yb
def movements(x, y, mov):
return [(x - 1, y - 2, mov),
(x + 1, y - 2, mov),
(x - 2, y - 1, mov),
(x + 2, y - 1, mov),
(x - 2, y + 1, mov),
(x + 2, y + 1, mov),
(x - 1, y + 2, mov),
(x + 1, y + 2, mov)]
def filter (list, xbounds, ybounds):
return [i for i in list if i[0] <= xbounds and i[1] <= ybounds and i[0] >= 0 and i[1] >= 0]
def shorter_path(x, y, xtarget, ytarget, xbounds, ybounds):
visited = dict()
queue = deque()
queue.append((x, y, 0))
while (len(queue) > 0):
current = queue.popleft()
if (current[0] == xtarget and current[1] == ytarget): return current[2]
if visited.has_key((current[0], current[1])): continue
visited[(current[0], current[1])] = True
movs = movements(current[0], current[1], current[2] + 1)
movs = filter(movs, xbounds, ybounds)
queue.extend(movs)
return -1
#Entry
print shorter_path(0, 0, 4, 4, 8, 8)
public class Solution {
class Point
{
private int x, y;
public Point()
{}
public Point(int x1, int y1)
{
this.x = x1;
this.y = y1;
}
}
class GraphNode {
private Point point;
public GraphNode(Point p)
{ this.point = p;
}
}
int[][] chessBoard;
public int knight(int N, int M, int x1, int y1, int x2, int y2) {
chessBoard = new int[N][M];
Point s = new Point(x1-1,y1-1);
int res =0;
GraphNode start = new GraphNode(s);
Queue<GraphNode> q = new LinkedList<GraphNode>();
q.add(start);
q.add(null);
while(!q.isEmpty()){
GraphNode cur = q.poll();
if(cur==null)
{
if(!q.isEmpty())
q.add(null);
res++;
}
else
{
Point p = cur.point;
if(p.x == x2-1 && p.y==y2-1)
return res;
chessBoard[p.x][p.y]=-1;
Point[] moves = PossibleJumps(p,N,M);
for(int i=0;i<moves.length;i++)
{
q.add(new GraphNode(moves[i]));
}
}
}
return -1;
}
public Point[] PossibleJumps(Point P, int N, int M)
{
ArrayList<Integer> xArray = new ArrayList<Integer>();
ArrayList<Integer> yArray = new ArrayList<Integer>();
//Point 1
if (P.x - 1 >= 0 && P.y + 2 <= M-1)
{
if (chessBoard[P.x - 1][P.y + 2] != -1)
{
xArray.add((int)(P.x - 1));
yArray.add((int)(P.y + 2));
chessBoard[P.x - 1][P.y + 2] = -1;
}
}
//Point 2
if (P.x + 1 <= N-1 && P.y + 2 <= M-1)
{
if (chessBoard[P.x + 1][P.y + 2] != -1)
{
xArray.add((int)(P.x + 1));
yArray.add((int)(P.y + 2));
chessBoard[P.x + 1][P.y + 2] = -1;
}
}
//Point 3
if (P.x + 2 <= N-1 && P.y + 1 <= M-1)
{
if (chessBoard[P.x + 2][P.y + 1] != -1)
{
xArray.add((int)(P.x + 2));
yArray.add((int)(P.y + 1));
chessBoard[P.x + 2][P.y + 1] = -1;
}
}
//Point 4
if (P.x + 2 <= N-1 && P.y - 1 >= 0)
{
if (chessBoard[P.x + 2][P.y - 1] != -1)
{
xArray.add((int)(P.x + 2));
yArray.add((int)(P.y - 1));
chessBoard[P.x + 2][P.y - 1] = -1;
}
}
//Point 5
if (P.x + 1 <= N-1 && P.y - 2 >= 0)
{
if (chessBoard[P.x + 1][P.y - 2] != -1)
{
xArray.add((int)(P.x + 1));
yArray.add((int)(P.y - 2));
chessBoard[P.x + 1][P.y - 2] = -1;
}
}
//Point 6
if (P.x - 1 >= 0 && P.y - 2 >= 0)
{
if (chessBoard[P.x - 1][P.y - 2] != -1)
{
xArray.add((int)(P.x - 1));
yArray.add((int)(P.y - 2));
chessBoard[P.x - 1][P.y - 2] = -1;
}
}
//Point 7
if (P.x - 2 >= 0 && P.y - 1 >= 0)
{
if (chessBoard[P.x - 2][P.y - 1] != -1)
{
xArray.add((int)(P.x - 2));
yArray.add((int)(P.y - 1));
chessBoard[P.x - 2][P.y - 1] = -1;
}
}
//Point 8
if (P.x - 2 >= 0 && P.y + 1 <= M-1)
{
if (chessBoard[P.x - 2][P.y + 1] != -1)
{
xArray.add((int)(P.x - 2));
yArray.add((int)(P.y + 1));
chessBoard[P.x - 2][P.y + 1] = -1;
}
}
Point[] pArray = new Point[xArray.size()];
for (int i = 0; i < pArray.length; i++)
{
pArray[i] = new Point((int)xArray.get(i), (int)yArray.get(i));
}
return pArray;
}
}
public class Solution {
class Point
{
private int x, y;
public Point()
{}
public Point(int x1, int y1)
{
this.x = x1;
this.y = y1;
}
}
class GraphNode {
private Point point;
public GraphNode(Point p)
{ this.point = p;
}
}
int[][] chessBoard;
public int knight(int N, int M, int x1, int y1, int x2, int y2) {
chessBoard = new int[N][M];
Point s = new Point(x1-1,y1-1);
int res =0;
GraphNode start = new GraphNode(s);
Queue<GraphNode> q = new LinkedList<GraphNode>();
q.add(start);
q.add(null);
while(!q.isEmpty()){
GraphNode cur = q.poll();
if(cur==null)
{
if(!q.isEmpty())
q.add(null);
res++;
}
else
{
Point p = cur.point;
if(p.x == x2-1 && p.y==y2-1)
return res;
chessBoard[p.x][p.y]=-1;
Point[] moves = PossibleJumps(p,N,M);
for(int i=0;i<moves.length;i++)
{
q.add(new GraphNode(moves[i]));
}
}
}
return -1;
}
public Point[] PossibleJumps(Point P, int N, int M)
{
ArrayList<Integer> xArray = new ArrayList<Integer>();
ArrayList<Integer> yArray = new ArrayList<Integer>();
//Point 1
if (P.x - 1 >= 0 && P.y + 2 <= M-1)
{
if (chessBoard[P.x - 1][P.y + 2] != -1)
{
xArray.add((int)(P.x - 1));
yArray.add((int)(P.y + 2));
chessBoard[P.x - 1][P.y + 2] = -1;
}
}
//Point 2
if (P.x + 1 <= N-1 && P.y + 2 <= M-1)
{
if (chessBoard[P.x + 1][P.y + 2] != -1)
{
xArray.add((int)(P.x + 1));
yArray.add((int)(P.y + 2));
chessBoard[P.x + 1][P.y + 2] = -1;
}
}
//Point 3
if (P.x + 2 <= N-1 && P.y + 1 <= M-1)
{
if (chessBoard[P.x + 2][P.y + 1] != -1)
{
xArray.add((int)(P.x + 2));
yArray.add((int)(P.y + 1));
chessBoard[P.x + 2][P.y + 1] = -1;
}
}
//Point 4
if (P.x + 2 <= N-1 && P.y - 1 >= 0)
{
if (chessBoard[P.x + 2][P.y - 1] != -1)
{
xArray.add((int)(P.x + 2));
yArray.add((int)(P.y - 1));
chessBoard[P.x + 2][P.y - 1] = -1;
}
}
//Point 5
if (P.x + 1 <= N-1 && P.y - 2 >= 0)
{
if (chessBoard[P.x + 1][P.y - 2] != -1)
{
xArray.add((int)(P.x + 1));
yArray.add((int)(P.y - 2));
chessBoard[P.x + 1][P.y - 2] = -1;
}
}
//Point 6
if (P.x - 1 >= 0 && P.y - 2 >= 0)
{
if (chessBoard[P.x - 1][P.y - 2] != -1)
{
xArray.add((int)(P.x - 1));
yArray.add((int)(P.y - 2));
chessBoard[P.x - 1][P.y - 2] = -1;
}
}
//Point 7
if (P.x - 2 >= 0 && P.y - 1 >= 0)
{
if (chessBoard[P.x - 2][P.y - 1] != -1)
{
xArray.add((int)(P.x - 2));
yArray.add((int)(P.y - 1));
chessBoard[P.x - 2][P.y - 1] = -1;
}
}
//Point 8
if (P.x - 2 >= 0 && P.y + 1 <= M-1)
{
if (chessBoard[P.x - 2][P.y + 1] != -1)
{
xArray.add((int)(P.x - 2));
yArray.add((int)(P.y + 1));
chessBoard[P.x - 2][P.y + 1] = -1;
}
}
Point[] pArray = new Point[xArray.size()];
for (int i = 0; i < pArray.length; i++)
{
pArray[i] = new Point((int)xArray.get(i), (int)yArray.get(i));
}
return pArray;
}
}
import java.util.*;
/**
* Created by ugurdonmez on 12/09/16.
*/
public class Solution {
public static void main(String [] args) {
System.out.println(knight(2,20,1,18,1,5));
}
public static int knight(int N, int M, int x1, int y1, int x2, int y2) {
Map<Integer, BoardArea> map = new HashMap<>();
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
map.put(i * M + j, new BoardArea(i,j));
}
}
int key1 = x1 * M + y1;
int key2 = x2 * M + y2;
return getKnightMinMove(map.get(x1 * M + y1), map.get(x2 * M + y2), N, M, map);
}
public static int getKnightMinMove(BoardArea pos1, BoardArea pos2, int n, int m, Map<Integer, BoardArea> map) {
PriorityQueue<QueueWrapper> queue = new PriorityQueue<>();
Set<BoardArea> visited = new HashSet<>();
queue.add(new QueueWrapper(pos1, 0));
while (!queue.isEmpty()) {
QueueWrapper queueWrapper = queue.poll();
BoardArea boardArea = queueWrapper.boardArea;
if (boardArea.equals(pos2)) {
return queueWrapper.length;
}
if (!visited.contains(boardArea)) {
// add connections
if (boardArea.x + 2 <= n) {
if (boardArea.y - 1 >= 1) {
queue.add(new QueueWrapper(map.get((boardArea.x + 2) * m + boardArea.y - 1), queueWrapper.length+1));
}
if (boardArea.y + 1 <= m) {
queue.add(new QueueWrapper(map.get((boardArea.x + 2) * m + boardArea.y + 1), queueWrapper.length+1));
}
}
if (boardArea.x + 1 <= n) {
if (boardArea.y - 2 >= 1) {
queue.add(new QueueWrapper(map.get((boardArea.x + 1) * m + boardArea.y - 2), queueWrapper.length+1));
}
if (boardArea.y + 2 <= m) {
queue.add(new QueueWrapper(map.get((boardArea.x + 1) * m + boardArea.y + 2), queueWrapper.length+1));
}
}
if (boardArea.x - 2 >= 1) {
if (boardArea.y - 1 >= 1) {
queue.add(new QueueWrapper(map.get((boardArea.x - 2) * m + boardArea.y - 1), queueWrapper.length+1));
}
if (boardArea.y + 1 <= m) {
queue.add(new QueueWrapper(map.get((boardArea.x - 2) * m + boardArea.y + 1), queueWrapper.length+1));
}
}
if (boardArea.x - 1 >= 1) {
if (boardArea.y - 2 >= 1) {
queue.add(new QueueWrapper(map.get((boardArea.x - 1) * m + boardArea.y - 2), queueWrapper.length+1));
}
if (boardArea.y + 2 <= m) {
queue.add(new QueueWrapper(map.get((boardArea.x - 1) * m + boardArea.y + 2), queueWrapper.length+1));
}
}
visited.add(boardArea);
}
}
return -1;
}
}
class BoardArea {
final int x;
final int y;
public BoardArea(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
BoardArea boardArea = (BoardArea) o;
if (x != boardArea.x) return false;
return y == boardArea.y;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
}
class QueueWrapper implements Comparable<QueueWrapper>{
final BoardArea boardArea;
final int length;
public QueueWrapper(BoardArea boardArea, int length) {
this.boardArea = boardArea;
this.length = length;
}
@Override
public int compareTo(QueueWrapper o) {
return Integer.compare(this.length, o.length);
}
}
Ok Here is the logic:
- enoughtworldisnot September 09, 20141. Create two trees one with the starting position of the knight as the root node and the other as the ending position of the knight as to root node.
2. The tree is such that for any Node N, all its children can be reached by a single move of the knight. So if N can be represented by n(x,y) then the child nodes would be n(x+1,y+2),n(x+1,y-2), n(x-1,y+2), n(x-1,y-2), n(x+2,y+1), n(x+2,y-1), n(x-2,y+1), n(x-2,y-1)
3. Now intersection of the two trees with the least number of stems will provide you the answer.
PS: all positions can ultimately be reached by the knight. The challenge is finding the shortest way.