Skip to content

Latest commit

 

History

History
159 lines (134 loc) · 4.87 KB

readme_q2_dont-get-volunteered.md

File metadata and controls

159 lines (134 loc) · 4.87 KB

Don't Get Volunteered

Question Summarized

Create a function named solution(src, dest)
to calculate the minimum number of moves a **Knight** - in a game of Chess -
must make to travel from one square to another on a chessboard? 

The squares are numbered from 0 to 63, like a standard chessboard. 
Knight moves two squares in any direction immediately followed by one square perpendicular to that direction, 
or vice versa, in an "L" shape).

Shown in the appendix

Solution Summarized

  • Textbook BFS / Knight's Tour Problem

Expected Values

-- Python cases --
Input:
solution.solution(19, 36)
Output:
    1

Input:
solution.solution(0, 1)
Output:
    3

Knight's Tour Solution

solution-1_19-to-36-in-1.png

solution-2_0-to-1-in-3.png

Keywords

Solution

Initial thoughts

  • Interesting question to animate. However, let's just get it done (7 days left though, I can afford to have fun)
  • Good ol brute force? Dynamic programming? or greedy?
    • Challenge is to guarantee the minimum number of moves? I think BFS can guarantee that.
    • BFS smart brute force
  • Python 3.11.6 should be backwards compatible with 2.7 for this question. Based on previous experience.
    • Can be optimized by using @mnemonic decorator
      • However, support was dropped for 2.7 since it's deprecated amost 4 years ago in 2020

Revised thoughts

  • after my soln... todo

Appendix

Raw Question

  • levels/q1/raw/q1_readme.txt.html
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 ordering the bunnies around at the same time, after all!
In order to make sure that everyone 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 solution(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|
-------------------------

Languages
=========

To provide a Python solution, edit solution.py
To provide a Java solution, edit Solution.java

Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Python cases --
Input:
solution.solution(19, 36)
Output:
    1

Input:
solution.solution(0, 1)
Output:
    3

-- Java cases --
Input:
Solution.solution(19, 36)
Output:
    1

Input:
Solution.solution(0, 1)
Output:
    3

Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

Verify file

  • returns a json
{
    "output": "<span class=\"term-green\">All test cases passed.</span> Use <span class=\"term-yellow\">submit solution.py</span> to submit your solution",
    "score": 100
}

Interesting

  • python 2.7 didnt have types. i.e.
def some_function(x:int, y:int):
    print(x,y)

image