Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
422 PurelyFunctional.tv Newsletter

Knight move

Write a function that takes a chess position as a tuple (such as [:A 4]). If there were a knight there, where would it be able to move? Have the function return a collection of all possible moves for that knight. Assume there are no other pieces on the board. Be sure the knight doesn't leave the board.

Knight Move diagram

Examples

(knight-move [:D 3]) ;=> [[:B 2] [:C 1] [:B 4] [:C 5] [:E 5] [:F 4] [:E 1] [:F 2]]
(knight-move [:A 1]) ;=> [[:B 3] [:C 2]]

Thanks to this site for the problem idea, where it is rated Hard in JavaScript. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

@steffan-westcott
Copy link

steffan-westcott commented Apr 23, 2021

Here's my answer to the extra challenge of finding all shortest paths:

(defn extend-path [path]
  (map #(conj path %) (knight-move (peek path))))

(defn shortest-paths [src dest]
  (loop [reached #{src} paths [[src]]]
    (if (reached dest)
      (filter #(= dest (peek %)) paths)
      (let [paths' (remove (comp reached peek) (mapcat extend-path paths))]
        (recur (into reached (map peek paths')) paths')))))

@vmpj
Copy link

vmpj commented Apr 23, 2021

(def file2int {:A 1 :B 2 :C 3 :D 4 :E 5 :F 6 :G 7 :H 8})
(def int2file (clojure.set/map-invert file2int))

(defn valid-move? [move]
  (every? #(and (> % 0) (< % 9)) move))

(defn friendly-format [[f r]] [(int2file f) r])

(defn knight-move [[file rank]]
  (let [f (file2int file) r rank]
    (as-> '(2 2 -2 -2 1 -1 1 -1) l
          (map #(vector (+ f %1) (+ r %2)) l (reverse l))
          (filter valid-move? l)
          (map friendly-format l))))

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