Solution to http://www.4clojure.com/problem/127

love-triangle.clj

(use 'clojure.test)

(defn transpose [m]
  (apply map vector m))

(defn window1d
  "Computes all triples of consecutives elements"
  [padding acoll]
  (partition 3 1 [padding] (cons padding acoll)))

(defn window2d
  "Computes all 3x3 windows of elements"
  [padding bitmap]
  (let [padding-line  (repeat (repeat 3 padding))
        horiz-windows (map #(window1d padding %) bitmap)
        vert-windows  (window1d padding-line horiz-windows)]
    (map transpose vert-windows)))

(defn erode
  "Morphological erosion operator. http://en.wikipedia.org/wiki/Erosion_(morphology)"
  [i bitmap]
  (letfn [(matches? [window]
            (every? identity (map #(or (not %1) %2)
                         (flatten i)
                         (flatten window))))]
    (map #(map matches? %) (window2d false bitmap))))

(defn blank-bitmap? [bitmap]
  (every? not (flatten bitmap)))

(defn max-order
  "Returns the order of the biggest estructural element in the bitmap"
  [i bitmap]
  (letfn [(erode-iter [n n-erosion]
            (let [n1-erosion (erode i n-erosion)]
              (if (or (blank-bitmap? n-erosion) (= n1-erosion n-erosion)) n
                  (recur (inc n) n1-erosion))))]
    (erode-iter 0 bitmap)))

(defn max-size
  "Returns the area of the biggest structural element in the bitmap"
  [bitmap]
  (let [f false, t true,
        area3 #(/ (* (inc %) %) 2),
        area4 #(* % %),
        forms [[[[f f f] [f t t] [f t f]] area3]
               [[[f f f] [t t f] [f t f]] area3]
               [[[f t f] [t t f] [f f f]] area3]
               [[[f t f] [f t t] [f f f]] area3]
               [[[f f f] [f t f] [t t t]] area4]
               [[[t f f] [t t f] [t f f]] area4]
               [[[t t t] [f t f] [f f f]] area4]
               [[[f f t] [f t t] [f f t]] area4]]]
    (apply max
      (map (fn [[i area]] (area (max-order i bitmap))) forms))))

(defn pad-to [pad size aseq]
  (take size (concat aseq (repeat pad))))

(defn unpack
  "Unpacks a binary encoded bitmap"
  [bitmap]
  (let [decode-line (fn [line] (reverse (map #(= % \1) (Integer/toString line 2))))
        pad-line (fn [cols line] (pad-to false cols line))
        lines (map decode-line bitmap)
        columns (apply max (map count lines))]
    (map #(pad-line columns %) lines)))

(defn love-triangle [coded-bitmap]
  "Solution to http://www.4clojure.com/problem/127"
  (let [bitmap (unpack coded-bitmap)
        size (max-size bitmap)]
    (if (>= size 3) size nil)))

; Tests

(deftest window1d-test
  (is (= [[:pad 1 2] [1 2 3] [2 3 :pad]]
        (window1d :pad (range 1 4)))))

(deftest window2d-test
  (is (= [[[[0 0 0] [0 1 0] [0 0 0]]]]
        (window2d 0 [[1]])))
  (is (= [[[[0 0 0] [0 1 2] [0 0 0]] [[0 0 0] [1 2 0] [0 0 0]]]]
        (window2d 0 [[1 2]])))
  (is (= [[[[0 0 0] [0 1 0] [0 2 0]]]
          [[[0 1 0] [0 2 0] [0 0 0]]]]
        (window2d 0 [[1]
                     [2]])))
  (is (= [[[[0 0 0] [0 1 2] [0 3 4]] [[0 0 0] [1 2 0] [3 4 0]]]
          [[[0 1 2] [0 3 4] [0 0 0]] [[1 2 0] [3 4 0] [0 0 0]]]]
        (window2d 0 [[1 2]
                     [3 4]])))
  )

(deftest erode-test
  (is (= [[false false false]
          [false true false]
          [false false false]]
         (erode [[true true true]
                 [true true true]
                 [true true true]]
                [[true true true]
                 [true true true]
                 [true true true]])))
  (is (= [[true true false]
          [true true false]
          [false false false]]
        (erode [[false false false]
                [false true true]
                [false true false]]
          [[true true true]
           [true true true]
           [true true false]]))))

(deftest max-order-test
   (is (= 3
         (max-order [[false false false]
                     [false true true]
                     [false true false]]
           [[true true true]
            [true true true]
            [true true true]]))))

(deftest max-size-test
  (is (= 6
        (max-size [[true true true]
                   [true true true]
                   [true true true]]))))

(deftest unpack-test
  (is (= [[true false false false false]
          [true true false false false]
          [true true true false false]
          [true true true true false]
          [true true true true true]]
        (unpack [1 3 7 15 31]))))

(deftest love-triangle-test
  (is (= 10 (love-triangle [15 15 15 15 15])))
  (is (= 15 (love-triangle [1 3 7 15 31])))
  (is (= 3 (love-triangle [3 3])))
  (is (= 4 (love-triangle [7 3])))
  (is (= 6 (love-triangle [17 22 6 14 22])))
  (is (= 9 (love-triangle [18 7 14 14 6 3])))
  (is (= nil (love-triangle [21 10 21 10])))
  (is (= nil (love-triangle [0 31 0 31 0]))))

(run-tests)