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

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 35 other followers

%d bloggers like this: