不用矢量定位求解奈特的苦痛问题

Question

我正在尝试基于奥丁项目-项目2:骑士的苦难发布的解决方案，在Clojure (函数式编程)中实现本杰特的解决方案。

我想知道您对我应该修改什么以使代码更清晰、更实用(就像在函数式编程中那样)的看法，以及我应该如何记录它。

我不知道这段代码是否被认为是功能性的。我非常依赖递归，这样行吗？如果没有，我如何才能使reduce (或使用任何其他方法)使其更有功能？

注:我没有使用位置x和y "X，y“的向量，而是选择用平方索引表示棋盘，例如，第一个方格在索引0，第二个方格在索引1.最后一个正方形在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

我只会评论代码本身，而不是算法的改进。为了简洁起见，我还将删除您的文档。

首先，我在这里看到了大量重复的代码。board和knight-moves包含了很多重复的代码，这些代码可以被概括和清理。

首先，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

我将其转换为一个接受边长的函数，使其能够处理抛出的任何有效值。

knight-moves的不同版本几乎是相同的。唯一的区别是parent默认为nil。这一点可以很容易地减少：

(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})))

不过那还是超级笨重的。我敢打赌有一种不用硬编码所有数字的方法来处理这个问题，但我现在想不起来。然而，一个更为简洁的版本可能是：

(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})))

注意我是如何逆转neg的。如果不这样做，-main将返回不同的结果。没有调用reverse的结果应该是有效的，它们只是与您之前得到的不同而已。

在nodes中，我认为您太过努力地使用knight-moves的两个特性，这导致代码重复。为什么不直接通过nil呢？我也会在这里使用mapv而不是for。只有当您需要使用for生成组合的能力或使用: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)))))

老实说，我在代码的其余部分找不到任何明显的错误，所以我把它留在了原样上。这是我最后得到的结果：

(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)