## 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.

Pages: 1 2

### 21 Responses to “Ullman’s Puzzle”

```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 > 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
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.