reaktor_outrun.clj

(ns reaktor-outrun.core
  (:require [nio.core :as nio]
            [clojure.java.io :as io]
            [hiphip.int :as hh])
  (:gen-class :main true))

(set! *warn-on-reflection* true)
(set! *unchecked-math* true)

;; http://reaktor.fi/blog/fast-track-osa-kolme-koodaa-out-run-lempikielellasi/
;; Linear complexity but partition is inefficient and file needs to be read from end to start
(defn outrun-fun [pyramid]
  (->> pyramid
       reverse
       (reduce
         (fn [memo row]
           (map + row (map #(apply max %) (partition 2 1 memo)))))
       first))

;; https://gist.github.com/baabelfish/9630647
(defn outrun-2 [pyramid]
  (->> pyramid
       (reduce
         (fn [previous line]
           (mapv (fn [this i]
                   (let [left (get previous (dec i) 0)
                         right (get previous i 0)]
                     (+ this (max left right))))
                 line
                 (range))))
       (apply max)))

;; Reading file using NIO
(definline create-int [b2 b1]
  `(clojure.core/+ (clojure.core/* ~b2 10) ~b1))

;; File reading and the algorithm merged together
;; ~120sec
(defn nio-outrun [fname]
  (let [buff (nio/mmap fname)]
    (loop [skip true]
      (if skip
        (recur (not (= (int (.get buff)) 10)))))
    (loop [prev nil
           line nil
           b1 0
           b2 0]
      (if (.hasRemaining buff)
        (let [this (int (.get buff))]
          (case this
            ; \n
            10 (recur (mapv (fn [^long this ^long i]
                              (let [^long left (get prev (dec i) 0)
                                    ^long right (get prev i 0)]
                                (+ this (max left right))))
                            (cons (create-int b1 b2) line) (range))
                      nil 0 0)
            ; space
            32 (recur prev (conj line (create-int b1 b2)) 0 0)
            (recur prev line b2 (- this 48))))
        (apply max prev)))))

;; Optimized with hiphip arrays
;; NOTE: Still creating two new arrays for each line
;; ~30sec
(defn nio-outrun-hh [fname]
  (let [buff (nio/mmap fname)]
    ;; Skip comment line
    (loop [skip true]
      (if skip
        (recur (not (= (int (.get buff)) 10)))))
    (loop [prev (make-array Integer/TYPE 0)
           line (make-array Integer/TYPE 1)
           i 0
           b1 0
           b2 0]
      (if (.hasRemaining buff)
        (let [this (int (.get buff))]
          (case this
            ; \n
            10 (do
                 (hh/aset line i (create-int b1 b2))
                 (recur
                   ;; Map current line to next prev
                   (hh/amap [[j this] line]
                            (+ this (if (<= j 0)
                                      (if (>= j (hh/alength prev))
                                        0
                                        (hh/aget prev j))
                                      (if (>= j (hh/alength prev))
                                        (hh/aget prev (dec j))
                                        (max (hh/aget prev (dec j)) (hh/aget prev j))))))
                   ;; Create new line array for the next line
                   (make-array Integer/TYPE (+ 2 (hh/alength prev)))
                   0 0 0))
            ; space
            32 (do
                 (hh/aset line i (create-int b1 b2))
                 (recur prev line (inc i) 0 0))
            (recur prev line i b2 (- this 48))))
        (hh/amax prev)))))

;; To test how much of run-time is spent with I/O
;; ~7.88sec
(defn nio-last-num [fname]
  (let [buff (nio/mmap fname)]
    (loop [skip true]
      (if skip
        (recur (not (= (int (.get buff)) 10)))))
    (loop [prev nil
           b1 0
           b2 0]
      (if (.hasRemaining buff)
        (let [this (int (.get buff))]
          (case this
            ; \n
            10 (recur (create-int b1 b2) 0 0)
            ; space
            32 (recur (create-int b1 b2) 0 0)
            (recur prev b2 (- this 48))))
        prev))))

;; Main

(defmulti outrun (fn [ver fname] (keyword ver)))

(defmethod outrun :nio-outrun [_ fname]
  (nio-outrun fname))

(defmethod outrun :nio-outrun-hh [_ fname]
  (nio-outrun-hh  fname))

(defmethod outrun :nio-last-num [_ fname]
  (nio-last-num fname))

(defn -main [& [ver fname]]
  (println "Result" (outrun ver fname)))