Ullman’s Puzzle

December 7, 2010

We begin with a function that generates random puzzles of length n:

(define (puzzle n)
    (define (r x) (/ (floor (* x 1000)) 10.))
    (let loop ((n n) (xs '()))
      (if (zero? n) xs
        (loop (- n 1) (cons (r (rand)) xs)))))

Then the solution is easy: sort the list, sum the first k elements, and compare to t:

(define (solve xs t k) (< (sum (take k (sort < xs))) t))

We use take, sum, sort, and rand from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/i7HUvdFb.

About these ads

Pages: 1 2

21 Responses to “Ullman’s Puzzle”

  1. My Haskell solution (see http://bonsaicode.wordpress.com/2010/12/07/programming-praxis-ullman%E2%80%99s-puzzle/ for a version with comments):

    import Data.List
    
    ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool
    ullman t k = any (\s -> length s == k && sum s < t) . subsequences
    
    ullman2 :: (Ord a, Num a) => a -> Int -> [a] -> Bool
    ullman2 t k = (< t) . sum . take k . sort
    
  2. Graham said

    My O(n log n) solution is similar to the one given. I did keep one quick check in that’s not
    strictly necessary, though: if k times the first (smallest) element is bigger than t, then we
    needn’t bother adding things up. This is a remnant from when I first started working on the
    problem. I was trying to find things that would reduce the amount of work needed in
    O(n log n) time or less before I came upon the final answer. Since it’s a quick check for small
    first values, I’ve kept it in.

    def ullman(L, t, k):
        L.sort()
        if k * L[0] > t:
            return False
        elif sum(L[:k]) < t:
            return True
        else:
            return False
    
  3. Lautaro Pecile said
    import itertools
    def ullmans_puzzle(lst, t, k):
        for sublist in itertools.combinations(lst, k):
            if sum(sublist) < t:
                return True
        return False
    
  4. My Ocaml commented solution: http://www.gleocadie.net/?p=444&lang=en

    let powerset s =
      let fu x l = List.map (fun y -> x::y) l in
      let rec powerset' = function
      | [] -> [[]]
      | h::t -> let pt = powerset' t in
                pt @ (fu h pt)
    in
      powerset' s
    ;;
    
    let sum = fold_left (+.) 0.;;
     
    let ullmann s t k =
      exists (fun x -> length x == k && t > sum x) (powerset s);;
    
  5. F. Carr said
    import heapq
    def ullman(xs, t, k):
        return sum(heapq.nsmallest(k, xs) <= t)
    

    This is O(n lg(k)) instead of O(n lg(n)).

  6. Veer said

    Here’s my try , not sure if it is right way to do
    Also have not checked if it is correct (will do that later).

    (define (solve nums t k)
    (let ([p-num (/ t k)])
    (let ([l1 (filter (lambda (n) (= n p-num)) nums)])
    (if (empty? l1)
    #f
    (let ([len (length l1)])
    (if (>= len k)
    (take l1 k)
    (let ([new-k (- k len)])
    (let ([solved (solve l2 (- t (apply + l1)) new-k)])
    (if solved
    (append l1 solved )
    #f)))))))))

  7. Veer said

    oops formatting

    (define (solve nums t k)  
      (let ([p-num (/ t k)])
        (let ([l1 (filter (lambda (n) (< n p-num)) nums)]
              [l2 (filter (lambda (n) (>= n p-num)) nums)])
          (if (empty? l1)
              #f
              (let ([len (length l1)])
                (if (>= len k)
                    (take l1 k)
                    (let ([new-k (- k len)])
                      (let ([solved (solve l2 (- t (apply + l1)) new-k)])
                        (if solved
                            (append l1 solved )
                            #f)))))))))
    
  8. Veer said

    hmm , i guess mine is in quadratic , not good :)

  9. keramida said

    A slightly un-optimized and simplistic Python version:

    {{{
    def ullman(numbers, threshold, k):
    count = 0
    for x in numbers:
    count += 1
    if (k – 1) < count and count <= len(numbers):
    b = count – k # subsequence start
    e = count # subsequence end
    if sum(numbers[b:e]) < threshold:
    return True
    return False
    }}}

  10. keramida said

    Formatting fail…

    def ullman(numbers, threshold, k):
      count = 0
      for x in numbers:
        count += 1
        if (k - 1) < count and count <= len(numbers):
          b = count - k
          e = count
          values = numbers[b:e]
          if sum(values) < threshold:
            return True
      return False
    
  11. Keramida:
    sorry but your code does not return true for this case:

    myTab2 = [1.1, 1.2, 10.1, 1.3]
    print ullman(myTab2, 9.0, 3)
    

    You only select the k-subsets of contiguous elements of the set, which are not all k-subsets of the original set.

  12. Lautaro Pecile said

    An improved version of my previous post. Thanks to F. Carr for the inspiration.

    def ullman (lst, t, k):
        return sum(sorted(lst)[:k]) < t
    
  13. Khanh Nguyen said

    In F#.

    let ullman_puzzle (xs:float list) (t: float) (k: int) =
        let sum_k_smallest = List.sort xs |> Seq.ofList |> Seq.take k |> Seq.sum
        sum_k_smallest < t
    
    let xs = [8.1; 55.1; 91.2; 74.6; 73.0; 85.9; 73.9; 81.4; 87.1; 49.3; 88.8; 5.7; 26.3; 7.1; 58.2; 31.7; 5.8; 76.9; 16.5; 8.1; 48.3; 6.8; 92.4; 83.0; 19.6]
    
    ullman_puzzle xs 98.2 3
    
  14. keramida said

    Gregory LEOCADIE, you’re right. I didn’t realize that we were looking for non-contiguous subsets too.

  15. ;) just call me Greg ;)

  16. George said
    (Define (ullman numbers t k)
      (define (insert-descending item seq)
        (if (or (null? seq) (> item (car seq)))
            (cons item seq)
            (cons (car seq)
                  (insert-descending item (cdr seq)))))
      (define (inner state remaining)
        (if (< (apply + state) t)
            #t
            (if (null? remaining)
                #f
                (inner (cdr (insert-descending (car remaining) state))
                       (cdr remaining)))))
      (inner (sort > (take k numbers))
             (drop k numbers)))
    

    I’m not really sure about the complexity of this, but I think it’s O(n k). Also I’m not sure about the take & drop from the standard prelude—my leading & without were O(k) but assumed n > k.

  17. Alan said

    The J solution (and algorithm) is pretty simple: sort the data set, and test if the sum of the K first items sum is less than T.

    NB. Three inputs:
    NB. DATA – the data set of numbers (in the example, 25 real numbers)
    NB. K – the grouping factor (in the example, 3)
    NB. LIMIT – the sum limit (in the example, 98.2
    up =: dyad def 0
    NB. LIMIT K up DATA
    ({.x)>+/({:x){.(/:{])y
    )
    NB. Returns 1 for true and 0 for false
    testdata =. (25?1000)%1+25?100
    testdata
    35.8148 1.26667 3.93814 51.8571 3.73034 24.7838 3.74324 4.6 58.1667 5.63291 12.425 12.8333 4.64789 49.125 17.8261 10.1528 14.4167 6.32 11.2436 218 26.5294 4.64211 4.35366 26.9524 4.79104
    <./testdata NB. mininum
    1.26667
    >./testdata NB. maximum
    218
    (+/ % #)testdata NB. average
    24.7117

    98.2 3 up testdata
    1
    10 3 up testdata
    1
    5 3 up testdata
    0
    3{.(/:{])testdata NB. 3 smallest numbers
    1.26667 3.73034 3.74324

  18. Jeff said

    Just getting used to Q :)


    / data
    n:18.1 55.1 91.2 74.6 73.0 85.9 73.9 81.4 87.1 49.3 88.8 5.7 26.3 7.1 58.2 31.7 5.8 76.9 16.5 8.1 48.3 6.8 92.4 83.0 19.6
    t:98.2
    k:3

    / func
    df:{y>+/[asc[x][til z]]}
    df[n;t;k]

  19. david said

    Another J solution.

    ullman=: 3 : 0
    ‘t k list’ =. y
    list =. /:~ list NB. ascending sort
    set =. k {. list NB. first k items
    U =. t > +/set NB. test
    U ; U#set NB. result; empty set if false
    )

    ullman 12.3; 4; 145.3 3 4 4 5 655 _3 6
    +-+——–+
    |1|_3 3 4 4|
    +-+——–+

    ullman 2.3; 4; 145.3 3 4 4 5 655 _3 6
    +-++
    |0||
    +-++

  20. Matt said

    I got asked a variant of this question in a phone interview for Google. I basically used the sorting solution above, but my interviewer told me there’s a better solution. Instead, if you use a data structure like a BST or a heap, size-bounded at k elements, and replacing the largest element when you find something smaller than it, you can reduce the complexity from O(n log n) to O(n log k). In the worst case scenario, where k = n, the complexity will become O(n log n), but otherwise it will be quicker. Thanks for the coding puzzles, and keep up the good work!

  21. the ‘better’ solution will not even get the first line coded by the time {t > +/ k take sort V} gets coded. One could use the remaining time to find an idiomatic shortcut to k take sort V, which is what Matt described with the data structure solution, like:

    t > +/ k take_sort V

    Note, that kind of optimization not being obvious with an algoloid language.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 611 other followers

%d bloggers like this: