Posts Tagged ‘145’

Programming Praxis – 145 Puzzle

April 20, 2010

In today’s Programming Praxis exercise we have to solve a math puzzle. The provided solution is 15 lines, not counting the parser to evaluate the generated strings. Let’s see if we can bring that down a bit.

Some imports:

import Control.Applicative
import qualified Data.List.Key as K
import Text.Parsec

Generating the expressions is pretty simple. If we have at least one digit, prepend the first digit to all the possible expressions for the remaining digits with either nothing or a plus or minus sign in between. If we only have one digit, that digit is the only option.

exprs :: String -> [String]
exprs (x:y:ys) = [x:o++z | o <- ["","+","*"], z <- exprs $ y:ys]
exprs xs       = [xs]

Since we now have more control over the input string (no spaces, subtraction or division), we can make last week’s parser slightly more compact.

eval :: String -> Int
eval = either (const 0) id . parse expr "" where
    expr = chainl1 term ((+) <$ char '+')
    term = chainl1 (read <$> many1 digit) ((*) <$ char '*')

Finding the required statistics is pretty trivial. Just group the expressions by their evaluated results and find the most common one.

main :: IO ()
main = do let mf = K.maximum length . snd . K.sort snd .
                   liftA2 zip id (map eval) $ exprs ['1'..'9']
          print (snd $ head mf, length mf)
          mapM_ putStrLn $ map fst mf

Six lines, not counting the parser. Not bad.