PLEASE WRITE IN PYTHON Sample.txt: Input Input begins with a line containing an

Question

PLEASE WRITE IN PYTHON

Sample.txt:

Input

Input begins with a line containing an integer 1n64

indicating the number of test cases. The following n

lines each contain an initial location for the knight. Knight locations will be given using the common chess notation of a lowercase letter (a-h) for the file (column) followed by a number (1-8) for the rank (row). The layout of the board and rank and file labels are illustrated in the figures above.

Output

For each test case, report the number of jumps to the hiding places for the given initial location of the knight. Also report the list of hiding places using the same chess file and rank notation used in the input. If there are multiple hiding places, sort them from top to bottom and sort those in the same rank from left to right.

sample output:

In chess, the knight is one of the more interesting pieces. As illustrated below, it moves by jumping two spaces up or down and one to the left or right. Alternatively, it can jump two spaces to the left or right and one space up or down. This lets the knight cover a lot of chess board in just a few moves. No matter where the knight starts out, it can eventually reach any other space. a b Given a chess board with just one knight on it, you want to find the hiding places, the spaces that it would take the knight the most jumps to reach from its initial location. For example, it would take the knight at least two jumps to reach space as in the board above. However, it would take at least three jumps for it to reach c1. since there are other spaces that it would take the knight even more jumps to reach, neither a8 nor c1 are among the hiding places for this initial position of the knight.

Explanation / Answer

def getPosition(initialPostion):

xchar = initialPostion[0]

yint = int(initialPostion[1]);

xint = ord(xchar) - 97;

return 8- yint,xint

def isPositionPossible(x ,y):

if x>=0 and x<=7 and y>=0 and y<=7:

return True

return False

def runAllJumps(ChessBoard, x, y):

currentsteps = ChessBoard[x][y]

#For x+2,y-1

nx, ny = x+2, y-1

if isPositionPossible(nx, ny):

if currentsteps + 1 < ChessBoard[nx][ny]:

ChessBoard[nx][ny] = currentsteps + 1

runAllJumps(ChessBoard, nx, ny)

#For x+2,y+1

nx, ny = x+2, y+1

if isPositionPossible(nx, ny):

if currentsteps + 1 < ChessBoard[nx][ny]:

ChessBoard[nx][ny] = currentsteps + 1

runAllJumps(ChessBoard, nx, ny)

#For x-2,y-1

nx, ny = x-2, y-1

if isPositionPossible(nx, ny):

if currentsteps + 1 < ChessBoard[nx][ny]:

ChessBoard[nx][ny] = currentsteps + 1

runAllJumps(ChessBoard, nx, ny)

#For x-2,y+1

nx, ny = x-2, y+1

if isPositionPossible(nx, ny):

if currentsteps + 1 < ChessBoard[nx][ny]:

ChessBoard[nx][ny] = currentsteps + 1

runAllJumps(ChessBoard, nx, ny)

#For x+1,y+2

nx, ny = x+1, y+2

if isPositionPossible(nx, ny):

if currentsteps + 1 < ChessBoard[nx][ny]:

ChessBoard[nx][ny] = currentsteps + 1

runAllJumps(ChessBoard, nx, ny)

#For x-1,y+2

nx, ny = x-1, y+2

if isPositionPossible(nx, ny):

if currentsteps + 1 < ChessBoard[nx][ny]:

ChessBoard[nx][ny] = currentsteps + 1

runAllJumps(ChessBoard, nx, ny)

#For x+1,y-2

nx, ny = x+1, y-2

if isPositionPossible(nx, ny):

if currentsteps + 1 < ChessBoard[nx][ny]:

ChessBoard[nx][ny] = currentsteps + 1

runAllJumps(ChessBoard, nx, ny)

#For x-1,y-2

nx, ny = x-1, y-2

if isPositionPossible(nx, ny):

if currentsteps + 1 < ChessBoard[nx][ny]:

ChessBoard[nx][ny] = currentsteps + 1

runAllJumps(ChessBoard, nx, ny)

return ChessBoard

def convertToChessPostion(i, j):

position = str(chr(j+97))

position = position + str(8-i)

return position

def determineHidingPlaces(initialPostion):

# Creates a list containing 5 lists, each of 8 items, all set to 0

w, h = 8, 8;

maxsteps = 1000

ChessBoard = [[maxsteps for x in range(w)] for y in range(h)]

x, y = getPosition(initialPostion)

# set Initial position

ChessBoard[x][y] = 0;

  

# Run the horse for all possibilites of jump

ChessBoard = runAllJumps(ChessBoard, x,y)

#determine steps to reach hiding places

steps = -1;

for i in range(0,8):

for j in range(0,8):

steps = max(steps, ChessBoard[i][j])

#uncomment to debug

#print ChessBoard

#determine positions to reach hiding places

list = []

for i in range(0,8):

for j in range(0,8):

if steps == ChessBoard[i][j]:

chessPosition = convertToChessPostion(i, j)

list.append(chessPosition)

#uncomment to debug

#print ChessBoard

return steps, list

'''

Description: Controller method to get input and determine ouptut for knight hiding places problem

'''

def main():

testCases = int(raw_input())

while testCases > 0:

# get Intial position

initialPostion = raw_input()

  

#Determin knight hiding places

distance, list = determineHidingPlaces(initialPostion)

  

#print distance of hiding places

print distance,

#print hiding places

for position in list:

print position,

testCases = testCases - 1

print

'''

Program Entery point

'''

if __name__ == "__main__":

main()

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.