Knight Hop is a Junior 5 level 7 point problem. A little bit of chess knowledge is very useful, as it requires a knight.
Functions are also extremely helpful, especially if it determines the possible next moves given a set of points.
First, create a function than takes in a coordinate. Then, it returns a list that has all the coordinates of a possible hop after the given coordinate.
Next, take in the two coordinates.
The two coordinates may be th exact same. In this case, just output 0.
Otherwise, every time you find the new possibilities, the output will incerease by 1.
Finally, output the answer.
Sample solutions:
(without comments)
def findPoints1(x, y):
nextSet = []
for i in [[x+1, y+2], [x+2, y+1], [x+2, y-1], [x+1, y-2], [x-1, y-2], [x-2, y-1], [x-2, y+1], [x-1, y+2]]:
if 1 <= i[0] <= 8 and 1 <= i[1] <= 8:
nextSet.append(i)
return nextSet
output = 0
startingX, startingY = map(int, input().split())
startingPoint = [startingX, startingY]
endingX, endingY = map(int, input().split())
endingPoint = [endingX, endingY]
nextCoordinates = []
brake = False
if startingPoint == endingPoint:
output = 0
else:
for i in range(6):
i += 1
if i == 1:
nextCoordinates = findPoints1(startingPoint[0], startingPoint[1])
output += 1
else:
for j in nextCoordinates:
try:
if nextCoordinates.index(endingPoint) > 0:
brake = True
break
except ValueError:
for t in range(len(nextCoordinates)):
nextCoordinates += (findPoints1(nextCoordinates[0][0], nextCoordinates[0][1]))
nextCoordinates[0] = ['going to be removed']
nextCoordinates.remove(['going to be removed'])
output += 1
if brake:
break
print(output)
(With comments)
"""
2022-07-01 - Canada Day
https://dmoj.ca/problem/ccc10j5
Knight Hop
This program makes a jump for some points and so on, until one of them is the final point."""
# Create a function that takes in a coordinate and outputs all the possible jumps
def find_points1(x, y):
next_set = [] # Create the list that outputs everything
# Circle-ish possibilities
for n in [[x+1, y+2], [x+2, y+1], [x+2, y-1], [x+1, y-2], [x-1, y-2], [x-2, y-1], [x-2, y+1], [x-1, y+2]]:
if 1 <= n[0] <= 8 and 1 <= n[1] <= 8:
next_set.append(n) # Add all the ones that aren't out of the 8 by 8 grid
return next_set # return the possibilities in a list
output = 0 # The final output
# The next lines add the input into coordinates, or lists with two terms.
startingX, startingY = map(int, input().split())
startingPoint = [startingX, startingY]
endingX, endingY = map(int, input().split())
endingPoint = [endingX, endingY]
# They are done. Create an empty list that is for the points as possibilities in the future,
nextCoordinates = []
# Very useful in the future. Determines when to break from future for loops.
brake = False
# There is always a possibility that the starting point is the same as the ending point.
# So, we need to consider that situation. It is the if part in the statement below:
if startingPoint == endingPoint:
output = 0 # Automatic answer
# The points aren't the same, which is what happens most of the time.
else:
for i in range(6): # It is 6 because the maximum possible moves is 6 (corner to opposite corner)
i += 1
# if the loop just started. This has to be different to avoid trying to get a position from an empty list.
if i == 1:
nextCoordinates = find_points1(startingPoint[0], startingPoint[1])
output += 1
else:
# Tests every possible coordinate
for j in nextCoordinates:
# There might be a ValueError, so we need to use Try Except:
try:
if nextCoordinates.index(endingPoint) > 0: # The ending point is in the points.
brake = True # Once this loop breaks, the outer loop will break as well
break # The smaller loop stops running.
except ValueError: # Uh-oh. ValueError from index!
for t in range(len(nextCoordinates)): # Adds the next round of possibilities, and removes a point.
nextCoordinates += (find_points1(nextCoordinates[0][0], nextCoordinates[0][1]))
nextCoordinates[0] = ['going to be removed']
nextCoordinates.remove(['going to be removed'])
output += 1
# Since there is a new round of possibilities, the final output must add 1.
if brake:
break # end if the final point is found.
print(output) # The answer
