「Triangle Minimal Path」──來做題吧！

一. 語言鼓吹篇

很多人不喜歡Clojure，也有很多人喜歡Clojure。

還有不少人原來不喜歡Clojure，後面卻鬼使神差一般喜歡上了它──說的就是我！

Clojure的括弧會讓人眼花，Clojure的代碼──或者說Lisp的代碼，很詭異。

但，重劍無鋒。那一劍風情，絕對匹敵──一劍西來，天外飛仙。

二. 題目描述

今天上手的是4clojure上的一道題「Triangle Minimal Path」，乘著興緻走起！周末了，碼農們也可以用你喜愛的語言來練練手。

此題難度係數為「Hard」。題目描述如下：

編寫一個函數，計算經過三角形相關點的最短路徑值。該三角形用Vector表示（如下圖所示）。路徑由頂點開始，經過與當前經過點相鄰的下層節點，直到最底層。

剛開始看到這道題目的時候，腦袋裡就想能否找到Clojure內置函數來解決，希望取個巧，但終究沒找到「一針見血」的特效藥（也許有吧，但我不知道）。後來，就還是安安靜靜地找規律吧。

先把圖例的第一題展開：

user=> (reduce #(into %1 %2) ([1] [2 4] [5 1 4] [2 3 4 5]))n[1 2 4 5 1 4 2 3 4 5]n

再對著圖找規律：

比如其中一條路徑[1 2 5 2] ，相鄰間隔（offset）為1、2、3......依次遞增。哈哈哈哈哈！∪ω∪......Σ(( つ??ω??)つ

四. 代碼！

代碼才是重劍的劍氣與劍招。

第一步，找出所有的通路路徑。

又可以開心地整遞歸了......=』①。①』=

;; 找出所有路徑n(defn find-all-pathn [original-vec target-vec idx offset] ;; 初始時，idx（當前位置） = 0, offset（下一個滿足條件項距離當前idx的位移） = 0n (let [target-vec (conj target-vec (original-vec idx))n offset (inc offset)n idx (+ idx offset)]n (if (>= idx (- (count original-vec) 1))n (conj [] target-vec)n (lazy-seqn (concat [] (find-all-path original-vec target-vec idx offset) ;; 遍歷左節點n (find-all-path original-vec target-vec (inc idx) offset)))))) ;; 遍歷右節點n

其實，這時候，已經可以初步地找出滿足條件的某條路徑了：

;; 以下可獲取單個滿足條件的Vectorn(reduce #(if (< (reduce + %1) (reduce + %2)) %1 %2) (find-all-path [1 2 4 5 1 4 2 3 4 5] [] 0 0))n

顯示如下：

[1 2 1 3]n

但我們希望能找到所有滿足條件的路徑，因此，還得繼續......

第二步，獲取滿足條件的所有Vector。

;; 以下獲取滿足條件的所有Vectorn(defn get-minimal-pathn [s]n (let [min-value (apply min (map #(reduce + %) s))]n (for [item s :when (= (reduce + item) min-value)] item)))n

第三步，整一個總體的調用函數吧。

;; 總調用函數n(defn triangle-minimal-pathn [original-vec]n (let [original-vec (reduce #(into %1 %2) original-vec)]n (get-minimal-path (find-all-path original-vec [] 0 0))))n

好咧！代碼總算完成了。

第四步，來測試我們的函數吧！

user=> (triangle-minimal-path ([1] [2 4] [5 1 4] [2 3 4 5]))n([1 2 1 3])nuser=> (triangle-minimal-path ([3] [2 4] [1 9 3] [9 9 2 4] [4 6 6 7 8] [5 7 3 5 1 4]))n([3 4 3 2 7 1])nuser=> (triangle-minimal-path ([1] [2 0] [0 2 2]))n([1 2 0] [1 0 2] [1 0 2])nuser=>n

OK！我們可以注意到最後一行測試代碼，其多條路徑的總數都是最小值，如下圖所示。

user=> (apply min (map #(reduce + %) (find-all-path (reduce #(into %1 %2) ([1] [2 4] [5 1 4] [2 3 4 5])) [] 0 0)))n7nuser=> (apply min (map #(reduce + %) (find-all-path (reduce #(into %1 %2) ([3] [2 4] [1 9 3] [9 9 2 4] [4 6 6 7 8] [5 7 3 5 1 4])) [] 0 0)))n20nuser=> (apply min (map #(reduce + %) (find-all-path (reduce #(into %1 %2) ([1] [2 0] [0 2 2])) [] 0 0)))n3nuser=>n

五. 結束

有點意猶未盡了，最近又要重新拾起Ruby和RoR，是不是也用Ruby寫個實現呢？（＾＿?）......