Solving Knight's Travails Problem without using vector for position

Question

I'm trying to implement a solution to the The Odin Project - Project 2: Knight’s Travails in Clojure (Functional Programming) based on the solution posted by benjdelt.

I would like to know your opinion about what should I change to make the code clearer and more functional (as in Functional Programming) and how should I document it.

I don't know if this code is considered functional. I am relying heavily on recursions, is this ok? If not, how can I reduce (or use any other method) to make it more functional?

Note: Instead of using a vector with position x and y "[x, y]", I chose to represent the chess board by the square index, e.g. the first square is at index 0, the second square is at index 1 ... the last square is at index 63.

(def board
 "- Not used anywhere yet, just shows how the board looks like. -"
  [(vec (range 0 8))
   (vec (range 8 16))
   (vec (range 16 24))
   (vec (range 24 32))
   (vec (range 32 40))
   (vec (range 40 48))
   (vec (range 48 56))
   (vec (range 56 64))])

(defn knight-moves
  "Get all the allowed moves of a knight at `node` position.
  Excludes all the moves that go out of the board."
  ([node]
  (let [a (- node 17)
        b (- node 15)
        c (- node 10)
        d (- node 6)
        e (+ node 6)
        f (+ node 10)
        g (+ node 15)
        h (+ node 17)
        all-neighbours [a b c d e f g h]
        possible-neighbours (vec (remove #(or (neg? %) (> % 63)) all-neighbours))]
    {:neighbours possible-neighbours :current-node node :parent-node nil}))
  ([node parent]
   (let [a (- node 17)
         b (- node 15)
         c (- node 10)
         d (- node 6)
         e (+ node 6)
         f (+ node 10)
         g (+ node 15)
         h (+ node 17)
         all-neighbours [a b c d e f g h]
         possible-neighbours (vec (remove #(or (neg? %) (> % 63)) all-neighbours))]
     {:neighbours possible-neighbours :current-node node :parent-node parent})))

;; (knight-moves 35)

(defn nodes
  "Get all the neighbours and subsequent neighbours of `starting-node`.
  Given a `node`, return a vector of maps with all the possible neighbours and
  subsequent neighbours.
  Given a `node` and a `parent`, return a vector of maps with all the possible
  nodes and subsequent neighbours and save its parent location."
  ([starting-node]
  (let [movements (knight-moves starting-node)]
    ;; For each neighbours of `starting-node`, calculate its subsequent neighbours.
    (vec (for [node (:neighbours movements)]
           (knight-moves node (knight-moves starting-node))))))
  ([starting-node parent]
   (let [movements (knight-moves starting-node)]
     (vec (for [node (:neighbours movements)]
            (knight-moves node (knight-moves starting-node parent)))))))

;; (nodes 35)

(defn backtracking
  "Return the parent location of each subsequent node in `path`."
  ([final-node] (backtracking final-node []))
  ([final-node path]
   (if (:parent-node final-node)
     (recur (:parent-node final-node) (merge path (:current-node final-node)))
     (reverse (distinct path)))))

(defn find-path
  "Given a `starting-node`, calculate the path to the `goal-node`"
  ([starting-node goal-node]
   (find-path (knight-moves starting-node) goal-node []))
  ([starting-node goal-node path]
   ;; If not yet arrived at goal
   (if-not (= (:current-node starting-node) goal-node)
     ;; Create a new node with the current-node as parent and add it to path.
     ;; Iterate through all nodes to find the path.
     (let [new-node (nodes (:current-node starting-node) starting-node)
           path (concat path new-node)]
       (recur (first path) goal-node (vec (concat (rest path) new-node))))
     ;; If path found, return the path
     (backtracking starting-node))))

;; (find-path 27 28)

(defn -main
  "I don't do a whole lot ... yet."
  [& args]
  (find-path 27 28))

(-main)
; => (27 12 18 28)

Answer 1

I'll be commenting just on the code itself, not on improvements to the algorithm. I'll also be removing your docs for brevity here.

First, I see a ton of repetitious code here. board and knight-moves contain a lot of duplicate code that can be generalized and cleaned up.

---

First, board:

(defn board [side-length]
  (->> (range (* side-length side-length)) ; Create all the numbered cells
       (partition side-length) ; Split them into rows
       (mapv vec))) ; Turn the board into a 2D vector

I turned it into a function that accepts the side length, and made it so it can handle whatever valid values you throw at it.

---

The different arity versions of knight-moves are almost identical. The only difference is that parent defaults to nil. This can be easily reduced:

(defn knight-moves
  ([node]
   (knight-moves node nil)) ; Default parent to nil

  ([node parent]
   (let [a (- node 17)
         b (- node 15)
         c (- node 10)
         d (- node 6)
         e (+ node 6)
         f (+ node 10)
         g (+ node 15)
         h (+ node 17)
         all-neighbours [a b c d e f g h]
         possible-neighbours (vec (remove #(or (neg? %) (> % 63)) all-neighbours))]
     {:neighbours possible-neighbours :current-node node :parent-node parent})))

That's still super bulky though. I bet there's a way to handle this without hardcoding all the numbers, but I can't think of it right now. A significantly more succinct version however could be:

(defn knight-moves
  ([node]
   (knight-moves node nil)) ; Default parent to nil

  ([node parent]
   (let [offsets [6 10 15 17]
         pos (map #(+ node %) offsets) ; Just map over the offsets so you aren't writing them twice.
         neg (map #(- node %) offsets)

         ; I'm reversing neg here so it matches your previous output. It seems valid without,
         ;  it just gives different answers.
         all-neighbours (vec (concat (reverse neg) pos)) ; Then stick the two together.
         possible-neighbours (vec (remove #(or (neg? %) (> % 63)) all-neighbours))]
     {:neighbours possible-neighbours :current-node node :parent-node parent})))

Note how I'm reversing neg. If I don't, the -main will return different results. The results without the call to reverse should be valid, they're just different from what you were getting before.

---

In nodes, I think you're trying too hard to use both arities of knight-moves, which is leading to duplicate code. Why not just pass nil? I'd also use mapv here instead of for. for is really only beneficial when you need to make use of it's ability to generate combinations, or make use of :when/:while:

(defn nodes
  ([starting-node]
   (nodes starting-node nil)) ; Default to nil, just like before

  ([starting-node parent]
   (let [movements (knight-moves starting-node)]
     ; You could use a full fn here instead of relying on the function macro
     ;  if you want a better identifier than %
     (mapv #(knight-moves % (knight-moves starting-node parent))
           (:neighbours movements)))))

---

I honestly couldn't find anything glaringly wrong with the rest of the code, so I left it as-is. This is the final result that I ended up with:

(ns irrelevant.knights.corrected)

(defn board
  [side-length]
  (->> (range (* side-length side-length)) ; Create all the numbered cells
       (partition side-length) ; Split them into rows
       (mapv vec))) ; Turn the board into a 2D vector

(defn knight-moves
  ([node]
   (knight-moves node nil)) ; Default parent to nil

  ([node parent]
   (let [offsets [6 10 15 17]
         pos (map #(+ node %) offsets) ; Just map over the offsets so you aren't writing them twice.
         neg (map #(- node %) offsets)

         ; I'm reversing neg here so it matches your previous output. It seems valid without,
         ;  it just gives different answers.
         all-neighbours (vec (concat (reverse neg) pos)) ; Then stick the two together.
         possible-neighbours (vec (remove #(or (neg? %) (> % 63)) all-neighbours))]
     {:neighbours possible-neighbours :current-node node :parent-node parent})))

(defn nodes
  ([starting-node]
   (nodes starting-node nil)) ; Default to nil, just like before

  ([starting-node parent]
   (let [movements (knight-moves starting-node)]
     ; You could use a full fn here instead of relying on the function macro
     ;  if you want a better identifier than %
     (mapv #(knight-moves % (knight-moves starting-node parent))
           (:neighbours movements)))))

(defn backtracking
  ([final-node] (backtracking final-node []))
  ([final-node path]
   (if (:parent-node final-node)
     (recur (:parent-node final-node) (merge path (:current-node final-node)))
     (reverse (distinct path)))))

(defn find-path
  ([starting-node goal-node]
   (find-path (knight-moves starting-node) goal-node []))
  ([starting-node goal-node path]
    ;; If not yet arrived at goal
   (if-not (= (:current-node starting-node) goal-node)
     ;; Create a new node with the current-node as parent and add it to path.
     ;; Iterate through all nodes to find the path.
     (let [new-node (nodes (:current-node starting-node) starting-node)
           path (concat path new-node)]
       (recur (first path) goal-node (vec (concat (rest path) new-node))))
     ;; If path found, return the path
     (backtracking starting-node))))

(defn -main
  "I don't do a whole lot ... yet."
  [& args]
  (find-path 27 28))

(-main)
; => (27 12 18 28)