Programming Praxis – 145 Puzzle

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 . K.group 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.

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: