# Solving Knight's Travails Problem without using vector for position

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)

• I'm glad you found my review helpful, but, I wouldn't accept so quickly if I were you. You don't want to discourage any other answers. I also may be able to add to my answer later. I have a hell of a day in front of me and wanted to get the main things I saw addressed. I may be able to find more things when I have time though. – Carcigenicate Apr 23 '18 at 15:21

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)

• I find your code much cleaner and understadable than the one I wrote. I'm new to Functional Programming so I don't understand yet how to simplify this things. I spent a few days trying to figure how to do it in Clojure, and now, with your help, I think that maybe its even simpler than OOP Paradigm. I created a repository on GitHub with this project and I hope you don't mind that I referenced this post and your name as a helper. – Vasco Ferreira Apr 23 '18 at 20:05
• @VascoFerreira If you haven't tried it already, I recommend trying to write an implementation for Conway's Game of Life. It's my favorite simple project to do when starting a new language. It's not very difficult to create, but it contains many different aspects to it, so it forces you to learn a little of everything. I'd also recommend a good book like Clojure for the Brave and True. You might also want to look over other Clojure reviews to see what other people are doing. And ya, its fine to reference me in that project. – Carcigenicate Apr 23 '18 at 20:14