## 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 . 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.