In today’s Programming Praxis exercise, our task is to write a solution to Ullman’s puzzle, which is to check whether there exists a subsequence of exactly length k of a series of real numbers that sums up to less than a given t. Let’s get started, shall we?

A quick import:

import Data.List

Today’s exercise is a short one. My first attempt was basically converting the problem statement into Haskell syntax:

ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool
ullman t k = any (\s -> length s == k && sum s < t) . subsequences

The Scheme solution uses a more efficient algorithm, so for the sake of completeness we’ll translate that into Haskell as well. This one runs in O(n log n) rather than O(n!) and it’s shorter to boot.

ullman2 :: (Ord a, Num a) => a -> Int -> [a] -> Bool
ullman2 t k = (< t) . sum . take k . sort

Some tests to see if everything is working properly:

main :: IO ()
main = do let xs = [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]
let ys = [3, 4, 3]
print $ ullman 98.2 3 xs
print $ ullman2 98.2 3 xs
print . not $ ullman 5 2 ys
print . not $ ullman2 5 2 ys

Looks like it is.

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, Haskell, kata, praxis, programming, puzzle, ullman

This entry was posted on December 7, 2010 at 10:34 am and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply