Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Loading…

Issue in eval answer for problem 131, Sum Some Set Subsets #238

Open
life0fun opened this Issue · 0 comments

1 participant

@life0fun

The following code is tested to return the correct value in both clojure 1.2 and 1.4.
However, it failed the first test case when running at the site.
Any idea why ?

(fn subsetsum [ & sets ]
  (letfn [
          ;; all the trouble to make the recursive function see its own memoized bindings
          (subsetsum-ycombinator []  
                                 (let [dp (fn [mem-dp itemsvec idx sumval]
                                            (let [dp (fn [itemsvec idx sumval]  
                                                       ;; redef dp, so pass down memoized dp
                                                       (mem-dp mem-dp itemsvec idx sumval))]
                                              (if (= idx 0)
                                                (if (= sumval (nth itemsvec idx))  ;; bottom, ret true if found, false if not.
                                                  true
                                                  false)
                                                ;; not bottom, first check direct hit before incl/excl recursion.
                                                (if (>= idx (count itemsvec))
                                                  false    ;; idx out of bound
                                                  (let [curval (nth itemsvec idx)]
                                                    ;;(prn "recursion " idx curval sumval)
                                                    (if (= sumval curval)
                                                      true
                                                      (if (> sumval curval)  ;; incl only when val > curval                     
                                                        (or (dp itemsvec (dec idx) (- sumval curval))
                                                            (dp itemsvec (dec idx) sumval))
                                                        (dp itemsvec (dec idx) sumval))))))))
                                       mem-dp (memoize dp)]
                                   (partial mem-dp mem-dp)))

          (has-subsetsum-yb [itemsvec sumval]  ;; whether this set has subset sum to sumval
                         ((subsetsum-ycombinator) itemsvec (dec (count itemsvec)) sumval))
          (max-value [ sets ]
                     (apply max (map #(apply + %) (map (fn [e] (map #(Math/abs %) e)) sets))))
          (all-true [vs]  ;; split vec into two sublist, whether eqs first one, then count
                    (let [hd (first vs)]
                      (and (= hd true) (every? #(= % hd) vs))))]
      (loop [v (- 0 100)]   ;; hard code for test reason
        (if (> v 100)
          false
          (if (all-true (for [s sets] (has-subsetsum-yb (vec s) v)))
            true
            (recur (inc v)))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.