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