lösung_blatt6.clj

(ns muster.core)
(set! *print-length* 25)

;; Aufgabe 1
(def nat (iterate inc 0))
(def even-nat (filter even? nat))
(def primes (remove
             (fn [a] (some #(= 0 (mod a %)) (range 2 (/ 2 a))))
             (iterate inc 2)))
(def partial-sum (reductions + nat))

;; Aufgabe 2
(defn min-path
  ([triangle] (min-path 0 triangle))
  ([pos [cur-row & rest-rows :as t]]
     (if t
       (let [cur-value (cur-row pos)
             left-subtree (min-path pos rest-rows)
             right-subtree (min-path (inc pos) rest-rows)]
         (+ cur-value
            (min left-subtree right-subtree)
            ))
       0)))

;; Aufgabe 3
(defn levenshtein [[h1 & t1 :as s1] [h2 & t2 :as s2]]
  (let [l1 (count s1)
        l2 (count s2)]
    (cond
     (= s1 s2) 0
     (= 0 l1) l2
     (= 0 l2) l1
     :else (min
            (let [lsr (levenshtein t1 t2)]
              (if (= h1 h2) lsr (inc lsr)))
            (inc (levenshtein t1 s2))
            (inc (levenshtein s1 t2))))))

(defn step [cs]
  (mapcat
   (fn [[[h :as p] xs]]
     (if (seq xs)
       (remove nil?
               (for [x xs]
                 (when (= 1 (levenshtein x h))
                   [(cons x p) (disj xs x)])))
       
       [[p xs]]))
   cs))

(defn init [cs]
  (for [c cs] [[c] (disj cs c)]))

(defn chains [cs]
  (map first (reduce (fn [a _b] (step a)) (init cs) (range (count cs)))))

(defn chain [cs]
  (first (chains cs)))