(defn patience-insert
  "Inserts a value into the sequence where each element is a stack.
   Comparison replaces the definition of less than.
   Uses the greedy strategy."
  [comparison sequence value]
  (lazy-seq
   (if (empty? sequence) `((~value)) 
       (let [stack (first sequence)  
             top       (peek stack)]
         (if (comparison value top)
           (cons (conj stack value)  
                 (rest sequence))   
           (cons stack               
                 (patience-insert comparison
                                  (rest sequence)
                                  value)))))))

(defn patience-remove
  "Removes the value from the top of the first stack it shows up in.
   Leaves the stacks otherwise intact."
  [sequence value]
  (lazy-seq
   (if (empty? sequence) nil              
       (let [stack (first sequence)
             top       (peek stack)]
         (if (= top value)                
           (let [left-overs (pop stack)]  
             (if (empty? left-overs)      
               (rest sequence)            
               (cons left-overs           
                     (rest sequence))))   
           (cons stack                    
                 (patience-remove (rest sequence)
                                  value)))))))

(defn patience-recover
  "Builds a sorted sequence from a list of patience stacks.
   The given comparison takes the place of 'less than'"
  [comparison sequence]
  (loop [sequence sequence
         sorted         []]
    (if (empty? sequence) sorted 
        (let [smallest  (reduce #(if (comparison %1 %2) %1 %2)  
                                (map peek sequence))            
              remaining    (patience-remove sequence smallest)] 
          (recur remaining                    
                 (conj sorted smallest)))))) 

(defn patience-sort
  "Sorts the sequence by comparison.
   First builds the list of valid patience stacks.
   Then recovers the sorted list from those.
   If you don't supply a comparison, assumes less than."
  ([comparison sequence]
     (->> (reduce (comp doall 
                        (partial patience-insert comparison)) 
                  nil                                         
                  sequence)
          (patience-recover comparison)))              
  ([sequence]
     
     (patience-sort < sequence)))


(println (patience-sort [4 65 2 -31 0 99 83 782 1]))