5
\$\begingroup\$

The task is to write a function findFraction maxDen number to find a short but good rational approximation to a decimal representation of a number — problem statement on TopCoder:

Given a fraction F = A/B, where 0 <= A < B, its quality of approximation with respect to number is calculated as follows:

  • Let S be the decimal fraction (infinite or finite) representation of F.
  • Let N be the number of digits after the decimal point in number. If number has trailing zeros, all of them are considered to be significant and are counted towards N.
  • If S is infinite or the number of digits after the decimal point in S is greater than N, only consider the first N decimals after the decimal point in S. Truncate the rest of the digits without performing any kind of rounding.
  • If the number of digits after the decimal point in S is less than N, append trailing zeroes to the right side until there are exactly N digits after the decimal point.
  • The quality of approximation is the number of digits in the longest common prefix of S and number. The longest common prefix of two numbers is the longest string which is a prefix of the decimal representations of both numbers with no extra leading zeroes. For example, "3.14" is the longest common prefix of 3.1428 and 3.1415.

[…] You are only allowed to use fractions where the denominator is less than or equal to maxDen. Find an approximation F = A/B of number such that 1 <= B <= maxDen, 0 <= A < B, and the quality of approximation is maximized. Return a String formatted "A/B has X exact digits" (quotes for clarity) where A/B is the approximation you have found and X is its quality. If there are several such approximations, choose the one with the smallest denominator among all of them. If there is still a tie, choose the one among those with the smallest numerator.

import Data.Char
import Data.List
import Data.Maybe

showResult :: (Int, Int, Int) -> String
showResult (a, b, x) = show a ++ "/" ++ show b ++ " has "
                    ++ show x ++ " exact digits"

compareDigits :: [Int] -> [Int] -> Ordering
compareDigits xs [] = EQ
compareDigits (x:xs) (y:ys) = case compare x y of
                                  EQ -> compareDigits xs ys
                                  order -> order

toDigit :: Char -> Int
toDigit c = ord c - ord '0'

preciseDivision :: Int -> Int -> [Int]
preciseDivision a b = div a' b : preciseDivision (mod a' b) b
           where a' = 10 * a

estimate :: [Int] -> Double
estimate = sum . zipWith (flip (/)) (iterate (*10) 10) .
           map fromIntegral

bestNumerator :: [Int] -> Double -> Int -> Maybe Int
bestNumerator ds p b =
    case find atLeast . map (pair ds b) $ [pivot .. ] of
        Just (a, EQ) -> Just a
        otherwise -> Nothing
    where pivot = truncate $ p * fromIntegral b
          pair ds b a = (a, compareDigits (preciseDivision a b) ds)
          atLeast (a, order) = order /= LT

bestResult :: Int -> [Int] -> Maybe (Int, Int, Int)
bestResult n ds = fromMaybe Nothing . find isJust .
                  map (toResult ds $ estimate ds) $ [1..n]
    where toResult ds p b = case bestNumerator ds p b of
                                Just a -> Just (a, b, 1 + length ds)
                                Nothing -> Nothing

findFraction' :: Int -> [Int] -> (Int, Int, Int)
findFraction' n = fromJust . last . takeWhile isJust .
                  map (bestResult n) . inits

findFraction :: Int -> String -> String
findFraction n = showResult . findFraction' n .
                 map toDigit . tail . tail

I'm most worried by bestNumerator and bestResult here. I'm using a find idiom that I invented myself, and I wonder if cleaner, more Haskelly alternatives exist.

\$\endgroup\$
5
\$\begingroup\$

Hmmm, not much ideas, only syntax:

showResult :: (Int, Int, Int) -> String
showResult (a, b, x) = concat [show a, "/", show b, " has ", show x, " exact digits"]


preciseDivision :: Int -> Int -> [Int]
preciseDivision a b = let (d,r) = divMod (10*a) b in d : preciseDivision r b 


...where toResult ds p b = fmap (\a -> (a, b, 1 + length ds)) $ bestNumerator ds p b
\$\endgroup\$
1
\$\begingroup\$

Ordering is an instance of Monoid.

import Data.Monoid

compareDigits :: [Int] -> [Int] -> Ordering
compareDigits _ [] = EQ
compareDigits (x:xs) (y:ys) = compare x y `mappend` compareDigits xs ys

toDigit is not exactly necessary; Data.Char has digitToInt, which does about the same thing. The difference is that it supports hex numbers and will fail if the character is not a valid hex digit, whereas your function assumes a decimal digit, is more efficient, but will silently give incorrect results for non-digits.

Whether you replace it or not, though, toDigit is backwards, since the function takes a digit and gives you the numeric value.

In bestNumerator's pair, you shadow the ds and b parameters. That confuses me. In bestResult, toResult also has a shadowing ds.

In general, I think many of your parameter names are too short. I realize that this is common in Haskell, but I still find it abhorrent for things that aren't abstract. For example, n instead of maxDenominator (or maxDen, as in the problem statement, but "den" is an obscure abbreviation).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.