Programming Praxis - Ullman’s Puzzle

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.

About these ads

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