Perl Quiz, Haskell Solution: Plusified Equations
Posted: August 19th, 2009 | Author: Michel Rijnders | Filed under: Haskell, Perl Quiz of the Week | 1 Comment »The Quiz
We are given two positive integers $L and $R we need to find Plusified
expressions of both for which Eval($E_L) == Eval($E_R). So what is a plusified
expression? It is an expression where we can choose whether to add a single
"+" between any consecutive digit. So for example the number 123 has the
following plusified expression:
- 123
- 12+3
- 1+23
- 1+2+3
So if we are given 123 and 96 we can form the following plusified equation:
- 12+3 == 9+6
Your mission is to write a Perl program (or an equivalent program in any
programming language) that will find all solutions to the plusified equation
of two numbers given as input. To normalise the output we’ll rule that:
- The equations should be given one at each line.
- They will be sorted so consecutive digits will take precedence over "+"'s.
- A "+" has no surrounding spaces.
- The = sign does have a preceding and following space.
A Haskell Solution
Listing of the complete solution:
module Main where
import Data.List (iterate)
import System (getArgs)
split :: Char -> String -> [String]
split delim s =
let (s', s'') = break (== delim) s
in s' : case s'' of
delim : _ -> split delim (tail s'')
otherwise -> []
plusify :: String -> [String]
plusify "" = [""]
plusify (c : "") = [c : ""]
plusify (c : cs) = concatMap (\cs' -> [c : cs', c : '+' : cs']) (plusify cs)
combis :: String -> String -> [(String, String)]
combis x y =
[(l, r) | l <- plusify x, r <- plusify y, sum' l == sum' r]
where sum' = sum . map (\s -> read s :: Int) . split '+'
main :: IO ()
main = do
args <- getArgs
mapM_ (putStrLn . \(l, r) -> l ++ " = " ++ r) (combis (args!!0) (args!!1))
return ()
import Data.List (iterate)
import System (getArgs)
split :: Char -> String -> [String]
split delim s =
let (s', s'') = break (== delim) s
in s' : case s'' of
delim : _ -> split delim (tail s'')
otherwise -> []
plusify :: String -> [String]
plusify "" = [""]
plusify (c : "") = [c : ""]
plusify (c : cs) = concatMap (\cs' -> [c : cs', c : '+' : cs']) (plusify cs)
combis :: String -> String -> [(String, String)]
combis x y =
[(l, r) | l <- plusify x, r <- plusify y, sum' l == sum' r]
where sum' = sum . map (\s -> read s :: Int) . split '+'
main :: IO ()
main = do
args <- getArgs
mapM_ (putStrLn . \(l, r) -> l ++ " = " ++ r) (combis (args!!0) (args!!1))
return ()
[...] For problem definition see: The Haskell solution. [...]