Clojure solution for http://theory.cpe.ku.ac.th/wiki/index.php/01204212/statuses

render-comments.clj

(ns comments.core
  (:require [clojure.string :as str]
            [clojure.zip :as z]))

(defn raw->comment-map [raw]
  (->> (str/split raw #"\n")
       (map #(str/trim %))
       rest
       (map #(str/split % #" "))
       (map-indexed (fn [idx x] (apply vector (str (inc idx)) x)))
       (map #(zipmap [:id :parent-id :msg] %))))

(defn make-node [id level text children]
  {:id id :level level :text text :children children})

(defn children-filter [flat-comments]
  (fn [parent-id]
    (filter (comp #(= parent-id %) :parent-id) flat-comments)))

(defn children-node-maker [find-children]
  (fn [node]
    (map (fn [{:keys [id msg]}] (make-node id (inc (:level node)) msg (find-children id))) (:children node))))

(defn format-line [{:keys [id level text]}]
  (let [spaces-count (* (dec level) 2)
        spaces (str/join "" (repeat spaces-count " "))]
    (str spaces "- " id " " text)))

(defn walk-node [zipper]
  (loop [zz zipper out []]
    (if (z/end? zz)
      out
      (recur (z/next zz) (conj out (format-line (z/node zz)))))))

(defn solve [in]
  (let [children-exist? #(seq (:children %))
        find-children (children-filter (raw->comment-map in))
        make-children (children-node-maker find-children)
        root-id "0", root-level 0, root-msg "Root"
        root-node (make-node root-id root-level root-msg (find-children root-id))]
    (doseq [line (rest (walk-node (z/zipper children-exist? make-children nil root-node)))]
      (println line))))

(solve "7
        0 hello_world
        0 this_is_another_comment
        1 first_reply
        2 good_morning_thailand
        1 second_one
        1 third_one
        5 when_it_is_ok")

คำอธิบาย

เริ่มจากการแปลง input เป็น data structure แบบนี้ ด้วยฟังก์ชัน raw->comment-map ผมเรียกผลลัพธ์ว่า flat-comments

({:id "1", :parent-id "0", :msg "hello_world"}
 {:id "2", :parent-id "0", :msg "this_is_another_comment"}
 {:id "3", :parent-id "1", :msg "first_reply"}
 {:id "4", :parent-id "2", :msg "good_morning_thailand"}
 {:id "5", :parent-id "1", :msg "second_one"}
 {:id "6", :parent-id "1", :msg "third_one"}
 {:id "7", :parent-id "5", :msg "when_it_is_ok"})

จากนั้นนำไปสร้าง zipper ตามบรรทัดที่ 41

(z/zipper children-exist? make-children nil root-node)

zipper เป็น clojure library ที่ทำให้เรา traverse data structure ได้แบบ declarative แทนที่เราจะต้องบอกว่า visit node ซ้าย,ขวา ในปกติเวลาที่ทำ depth-first search ผมแค่บอกว่า z/next ก็จะได้ node ต่อไป ไปจนกระทั่งถึง z/end? ดังเช่นที่ผมใช้ในฟังก์ชัน walk-node บรรทัดที่ 29

ส่วนประกอบของ zipper คือ

• ​Data structure ของ node ซึ่งสร้างด้วยฟังก์ชัน make-node บรรทัดที่ 13 คือ มี id, level, text และ children
• ฟังก์ชันที่รับ node มาแล้ว return ไปว่ามี children มั้ย children-exists?
• ฟังก์ชันที่รับ node มาแล้ว return children make-children
  • การสร้าง children nodes ผมไปทำการหา children ทั้งหมดของแต่ละ parent node มาก่อน โดยเลือก comment จาก flat-comments ที่ parent id ตรงกับ node id จากนั้นผมก็เอา children ไปสร้าง node find-children, make-children
  • แต่ละ child node ผมจะเพิ่ม level ขึ้น 1 จาก parent ของมัน เพื่อใช้ทำ indent ในตอน format-line ต่อไป
• ฟังก์ชันสำหรับสร้าง node (ผมไม่ได้ใช้ส่วนนี้)
• Root node ซึ่งผมให้ id = "0", level = 0

ผม loop เพื่อเรียก z/next เพื่อ walk จาก root ไปทีละ node มันจะทำ depth-first search แบบ pre-walk (visit parent ก่อน) ให้เอง (ฟังก์ชัน walk-node) ขณะที่ visit แต่ละ node ผมก็ทำการเรียกฟังก์ชัน format-line แล้วโยน node ไปให้ โดย format-line จะเปลี่ยน จาก node ให้กลายเป็นบรรทัดที่ต้องการ เช่น แบบนี้

{:id 7, :level 3, :text when_it_is_ok, :children ()} ;-> "    - 7 when_it_is_ok"

จากนั้นผมเก็บผลลัพธ์ของแต่ละการ visit node ไว้ที่ vector out เพื่อ return กลับมาเมื่อ walk ครบ และสุดท้ายในบรรทัดที่ 41 ผมตัด line ที่เกิดจาก root node ออกแล้วทำการ loop ทีละบรรทัดเพื่อ print ออกมา