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

### Like this:

Like Loading...

*Related*

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

This entry was posted on February 5, 2013 at 11:49 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