Solution to the newest Reaktor FastTrack. Mathematically elegant, code-wise maybe not so :)

outrun.clj

; A solution to the latest http://reaktor.fi/careers/fast_track/
;
; Calculates recursively the maximum path function
; S(i,j) = W(i,j) + max { S(i-1, j-1), S(i-1, j) }
;
; Solution to the problem is just finding
; M = max { S(N, i) }, 1 <= i <= N (using 1-based indexing)
;
; then prints out the solution from the given node as an HTML table.
 
(ns outrun.core
  (:require [clojure.string :as s]))
 
;; Parses the file as a vector-of-vectors
;; returns [seed tree]
(defn- convert-line [line] (map #(Integer/parseInt %) (s/split line #"\s")))
(defn parse-tree [resource]
    (let [contents (slurp resource)
          lines (s/split contents #"\n")
          seed (first (take 1 lines))
          levels (drop 1 lines)]
        [seed (map convert-line levels)]))
 
;; Calculates the maximum number of likes to the given entry in the matrix
;; Recurses upwards in the tree
(def S
  (memoize (fn [m i j]
    (if (and (<= 0 i (dec (count m))) 
             (<= 0 j (dec (count (nth m i)))))
        (let [current (nth (nth m i) j)
              left (S m (dec i) (dec j))
              right (S m (dec i) j)]
          (+ current (max left right)))
      0))))
 
;; This finds the maximum number of likes from the given height.
;; To find the maximum likes in the leaf, use (count tree) as the parameter
(defn find-max-likes [tree n]
  (if (> n 0)
    (reduce
     (fn [a b]
       (if (> (second b) (second a)) b a))
      (map (fn [a b] [b (S tree (dec n) a)]) (range n) (range n)))
    [0 (nth tree 0)]))
 
;; Print the route as HTML table
(defn highlight-route-from [stream tree i j]
  (if-not (and (= i 0) (= j 0))
    (let [height (count tree)
          row (nth tree i)
          current (nth row j)
          left  (S tree (dec i) (dec j))
          right (S tree (dec i) j)
          col-span (- height i)]
    (cond
       (>= left right) (highlight-route-from stream tree (dec i) (dec j))
       :else (highlight-route-from stream tree (dec i) j))
 
    (.write stream "<tr>")
    (doseq [n (range (inc i))]
        (.write stream "<td") 
        (when (= n j)
          (.write stream " class=\"selected\""))
        (when (= n 0)
          (.write stream (str " colspan=\"" col-span "\"")))
        (.write stream ">")
        (.write stream (.toString (nth row n)))
        ; To see the S-value, uncomment this and comment previous line
        ; (.write stream (.toString (S tree n i)))
        (.write stream "</td><td></td>"))
    (.write stream "</tr>")
    nil)
    (.write stream (str "<tr><td colspan=\""  (- (count tree) i) "\" class=\"selected\">" (.toString (nth (nth tree 0) 0)) "</td></tr>"))))
 
; To construct solutions from the web page, just uncomment this and
; comment the fixed resource
; (let [resource "http://reaktor-code-tree.herokuapp.com/"
(let 
      [resource "/Users/maharj/Downloads/tree.txt"
      [seed tree] (parse-tree resource)
      ; Use the web page version for sanity test
      ; [seed tree] ["# seed: from web page" [[22 0 0 0] [14 81 0 0] [81 46 34 0] [83 59 94 9]]]
      [like-index max-likes] (find-max-likes tree (count tree))]
  (with-open [s (java.io.FileWriter. "/tmp/outrun-tree.html")]
    (.write s "<style>td { text-align: center; } tr :first-child { text-align: right; } h1,h2 { text-align: center !important; } td.selected { font-weight: bold; }</style>")
    (.write s "<table>")
    (.write s (str "<tr><td colspan=\"198\"><h1>" (.toString seed) "</h1>"))
    (.write s (str "<h2>likes: " (.toString max-likes) "</h2></td></tr>"))
    (highlight-route-from s tree (dec (count tree)) like-index)
    (.write s "</table>") s))