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
Tags: 147, bonsai, code, Haskell, kata, praxis, programming, puzzle
