4clojure problem 79

min-triangle-path.clj

; thanks to @eigenhombre i was reminded that we can only take "plinko" paths
; also props for introducing me to letfn
;
; this is what led to the insight that a vector becomes 2 possible vectors
; much like the branching universe theory, and we must mapcat those as we go !

; Key insight
; You branch in predictable way like the game of PLINKO on The Price is Right :)
; Eg at each step, the branches multiply thusly:
; ([0 0]) becomes ([0 0 0] [0 0 1])
; Essentially instead of going 'left' or 'right', appending a 0 meant you went straight
; down and a 1 meant you went over one index. It's nice how it addds so easily.
(def testcase1 '(
           [1]
          [2 4]
         [5 1 4]
        [2 3 4 5]))


; the pyramid once flushed against the y-axis (slumped against the wall)
(def testcase1 '(
        [1]
        [2 4]
        [5 1 4]
        [2 3 4 5]))

(def testcase2 '(
            [3]
           [2 4]
          [1 9 3]
         [9 9 2 4]
        [4 6 6 7 8]
       [5 7 3 5 1 4]))

;function-extraction
(defn plinko-branch [v] 
  (if (empty? v)
    []
    [(conj v (last v))
     (conj v (+ 1 (last v)))]))

;assert: [[1 23 23] [1 23 24]]
(plinko-branch [1 23])

;assert: [[0 1 1] [0 1 2]]
(plinko-branch [0 1])

;assert: [[0 0] [0 1]]
(plinko-branch [0])

;uh-uh: [] (was NPE before cond added to plinko)
(plinko-branch [])
(plinko-branch nil)

;Now, to give us all possible plinko paths for a given depth
(defn iterate-plinko-paths [depth] 
  (nth (iterate #(mapcat plinko-branch %) '([0])) (dec depth)))

;assert: ([0])
(iterate-plinko-paths 1)

;assert: ([0 0] [0 1])
(iterate-plinko-paths 2)

;assert: ([0 0 0] [0 0 1] [0 1 1] [0 1 2])
(iterate-plinko-paths 3)

;uh-uh: 
(iterate-plinko-paths 0)

;uh-uh OutOfMemoryError Java heap space 
;(iterate-plinko-paths 100)

;A little helper to go

;From each row in rows, selects the corresponding index
(defn index-from-each [rows idx]
  (map (fn [idx row] (row idx)) idx rows))

;assert (1 2 5)
(index-from-each testcase1 [0 0 0])

;assert (1 4 4)
(index-from-each  testcase1 [0 1 2])


;And now -the denoument !
(defn all-plinko-paths [row-tree]
  (map #(index-from-each row-tree %)
       (iterate-plinko-paths (count row-tree))))

;And the cherry on top
(defn minimal-plinko-path [plinko-board]
  (apply min (map #(reduce + %) (all-plinko-paths plinko-board))))

;assert 7
(minimal-plinko-path testcase1)

;assert 20
(minimal-plinko-path testcase2)

; Finally, formatted for 4clojure
(fn minimal-plinko-path [plinko-board]
  (letfn
    [(plinko-branch [v] 
      (if (empty? v)
        []
        [(conj v (last v))
         (conj v (+ 1 (last v)))]))

     (iterate-plinko-paths [depth] 
      (last
        (take depth
          (iterate #(mapcat plinko-branch %) '([0]) ))))

     (index-from-each [rows idx]
      (map (fn [idx row] (row idx)) idx rows))

     (all-plinko-paths [rows]
      (map #(index-from-each rows %)
        (iterate-plinko-paths (count rows))))]
    
    (apply min (map #(reduce + %) (all-plinko-paths plinko-board)))
    ))

; TODO - make literate programming style, or even turn asserts into real ones