Weekly Coding Challenge 2012.22 @ TW Brazil

subs_sum.clj

; Weekly Coding Challenge 22 @ ThoughtWorks Brazil
;
; For a given set, find all subsets which the sum 
; of its members is the closest smaller value to a
; given number
;

(ns tw.wcc
  (:use [clojure.contrib.combinatorics]))

(defn seq-sum [xs] (reduce + xs))

(defn smaller-pos-delta [n]
  (fn [xs] 
    (let [delta (- n (seq-sum xs))]
      (if (< delta 0) 
        (+ n (- delta)) 
        delta))))

(defn subs-sum [n s]
  (->> s
    (subsets)
    (group-by (smaller-pos-delta n))
    (first)))

; clj subs_sum.clj 29 10 8 9 11 7
(defn -main [] 
  (let [args (map read-string *command-line-args*)
        sum  (first args)
        set  (rest args) ]  
    (print (subs-sum sum set))))

(-main)

subs_sum.coffee

# subsSum -> for a given set, finds all
# subsets which the sum is closest to a 
# given value
#
# coffee> subsSum(29, [2, 8, 3, 9, 11, 6])
# [ [ 11, 9, 8 ],
#   [ 6, 11, 3, 8 ],
#   [ 6, 11, 9, 2 ],
#   [ 6, 9, 3, 8, 2 ] ]
#  

_ = require('underscore')._

subsFor = (superset, base=[]) ->
  _.tap [], (ret) ->
    _.each superset, (e, idx) ->
      combination = [e].concat(base)
      ret.splice 0, 0, combination, subsFor(superset[idx+1..], combination)...

subsSum = (val, arr) ->
  adder    = (a, b) -> a + b
  total    = (arr) -> _.reduce(arr, adder)
  indexGte = (n) -> (_, idx) -> idx >= n

  _.chain(subsFor(arr))
    .groupBy(total)
    .reject(indexGte(val))
    .last()
    .value()
  
_.extend exports, {subsSum}