Programming Praxis – The 147 Puzzle

In today’s Programming Praxis exercise, our goal is to find all combinations of five numbers whose inverses sum up to one. Let’s get started, shall we?

Since we’re working with exact fractions, the Ratio library is an obvious fit.

import Data.Ratio

We solve the problem recursively so that the algorithm will work on other amounts of numbers as well. Once we’ve chosen all but the last number, that remainder must have a numerator of one. For the rest, just try all possibilities that still leave a large enough remainder for the rest, keeping track of the previous choice to prevent duplicates (each choice must be more than or equal to the previous choice.)

puzzle :: Integer -> [[Integer]]
puzzle k = f 2 (k%1) 1 where
    f _ 1 r = if numerator r == 1 then [[denominator r]] else []
    f p n r = concat [map (x : ) $ f x (n-1) r'
                     | x <- [p..floor $ n/r], let r' = r - 1%x, r' > 0]

While writing the solution, I also came up with some variations that worked fine for k = 5, but were very slow for k = 6. To prevent this we test both of them.

main :: IO ()
main = do print . (== 147) . length $ puzzle 5
          print . (== 3462) . length $ puzzle 6
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: