Skip to content

Instantly share code, notes, and snippets.

@gggauravgandhi
Created June 4, 2017 08:59
Show Gist options
  • Save gggauravgandhi/f42e497813c86add9b2ae356425d12ad to your computer and use it in GitHub Desktop.
Save gggauravgandhi/f42e497813c86add9b2ae356425d12ad to your computer and use it in GitHub Desktop.
Google's Foo.bar chess Knight's Shortest Path Chess Puzzle Solution (Don't Get Volunteered!)
# Quiz : Don't Get Volunteered!
# ======================
# As a henchman on Commander Lambda's space station, you're expected to be resourceful, smart, and a quick thinker. It's not easy building a doomsday device and capturing bunnies at the same time, after all! In order to make sure that everyone working for her is sufficiently quick-witted, Commander Lambda has installed new flooring outside the henchman dormitories. It looks like a chessboard, and every morning and evening you have to solve a new movement puzzle in order to cross the floor. That would be fine if you got to be the rook or the queen, but instead, you have to be the knight. Worse, if you take too much time solving the puzzle, you get "volunteered" as a test subject for the LAMBCHOP doomsday device!
# To help yourself get to and from your bunk every day, write a function called answer(src, dest) which takes in two parameters: the source square, on which you start, and the destination square, which is where you need to land to solve the puzzle. The function should return an integer representing the smallest number of moves it will take for you to travel from the source square to the destination square using a chess knight's moves (that is, two squares in any direction immediately followed by one square perpendicular to that direction, or vice versa, in an "L" shape). Both the source and destination squares will be an integer between 0 and 63, inclusive, and are numbered like the example chessboard below:
# -------------------------
# | 0| 1| 2| 3| 4| 5| 6| 7|
# -------------------------
# | 8| 9|10|11|12|13|14|15|
# -------------------------
# |16|17|18|19|20|21|22|23|
# -------------------------
# |24|25|26|27|28|29|30|31|
# -------------------------
# |32|33|34|35|36|37|38|39|
# -------------------------
# |40|41|42|43|44|45|46|47|
# -------------------------
# |48|49|50|51|52|53|54|55|
# -------------------------
# |56|57|58|59|60|61|62|63|
# -------------------------
# Solution
# ======================
def answer(src, dest):
rawMoves = [[6,5,4,5,4,5,4,5,4,5,4,5,4,5,6],[5,4,5,4,3,4,3,4,3,4,3,4,5,4,5],[4,5,4,3,4,3,4,3,4,3,4,3,4,5,4],[5,4,3,4,3,2,3,2,3,2,3,4,3,4,5],[4,3,4,3,2,3,2,3,2,3,2,3,4,3,4],[5,4,3,2,3,4,1,2,1,4,3,2,3,4,5],[4,3,4,3,2,1,2,3,2,1,2,3,4,3,4],[5,4,3,2,3,2,3,0,3,2,3,2,3,4,5],[4,3,4,3,2,1,2,3,2,1,2,3,4,3,4],[5,4,3,2,3,4,1,2,1,4,3,2,3,4,5],[4,3,4,3,2,3,2,3,2,3,2,3,4,3,4],[5,4,3,4,3,2,3,2,3,2,3,4,3,4,5],[4,5,4,3,4,3,4,3,4,3,4,3,4,5,4],[5,4,5,4,3,4,3,4,3,4,3,4,5,4,5],[6,5,4,5,4,5,4,5,4,5,4,5,4,5,6]]
rawPlatform = [[0,1,2,3,4,5,6,7],[8,9,10,11,12,13,14,15],[16,17,18,19,20,21,22,23],[24,25,26,27,28,29,30,31],[32,33,34,35,36,37,38,39],[40,41,42,43,44,45,46,47],[48,49,50,51,52,53,54,55],[56,57,58,59,60,61,62,63]]
rawY1 = [x for x in rawPlatform if src in x][0]
rawY2 = [y for y in rawPlatform if dest in y][0]
# [7][7] is index of center spot
masterKeyX = 7 + (rawPlatform.index(rawY2) - rawPlatform.index(rawY1))
masterKeyY = 7 + (rawY2.index(dest) - rawY1.index(src))
return rawMoves[masterKeyX][masterKeyY]
@tanishkthomas
Copy link

How did you write the rawMoves? and what do they exactly mean?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment