coder . cl

Here is another challenge called difficult, but seems to be quite easy to solve. It is a simple feasible operation search algorithm between lists of numbers, so it is not so complex to solve and took few minutes to get it working on Haskell, because Haskell provides various tools to work with algorithms. Also this solution does the extra credit, no matter if the list has up to four integers.

Today, your challenge is to create a program that will take a series of numbers (5, 3, 15), and find how those numbers can add, subtract, multiply, or divide in various ways to relate to each other. This string of numbers should result in 5 * 3 = 15, or 15 /3 = 5, or 15/5 = 3. When you are done, test your numbers with the following strings:

• 4, 2, 8
• 6, 2, 12
• 6, 2, 3
• 9, 12, 108
• 4, 16, 64

For extra credit, have the program list all possible combinations.
for even more extra credit, allow the program to deal with strings of greater than three numbers. For example, an input of (3, 5, 5, 3) would be 3 * 5 = 15, 15/5 = 3. When you are finished, test them with the following strings.

• 2, 4, 6, 3
• 1, 1, 2, 3
• 4, 4, 3, 4
• 8, 4, 3, 6
• 9, 3, 1, 7

Here is the full solution in Haskell, just to practice a little. Compile it using ghc --make prog.hs -o prog or run it using runghc prog.hs input.txt

module Main where

import Data.String.Utils
import Data.List
import Data.Maybe
import Math.Combinat.Sets
import System.Environment
import Text.Printf

data OperationResult = OperationResult {
     oper              :: Int -> [Int] -> Bool
     , msg             :: String
}

availableOperations :: [OperationResult]
availableOperations =
                    [
                    OperationResult { oper = testMatchMul,
                                      msg = "mul" },
                    OperationResult { oper = testMatchDiv,
                                      msg = "div" },
                    OperationResult { oper = testMatchSum,
                                      msg = "add" },
                    OperationResult { oper = testMatchSub,
                                      msg = "sub" }
                    ]

liftLine :: String -> [Int]
liftLine l = sort $ fmap ( read . strip ) $ split "," l

matchMessage :: String -> [Int] -> Int -> String
matchMessage s xs n = printf "%s does %s with %s"
                      s ( show n ) ( show xs )

testMatchMul :: Int -> [Int] -> Bool
testMatchMul n xs = n == foldr (*) 1 xs

testMatchDiv :: Int -> [Int] -> Bool
testMatchDiv n xs = dm == n && dr == 0
                    where (dm,dr) = divMod ( head xs ) ( last xs )

testMatchSum :: Int -> [Int] -> Bool
testMatchSum n xs = n == foldr (+) 0 xs

testMatchSub :: Int -> [Int] -> Bool
testMatchSub n xs = n == foldr (-) 0 xs

applyOperation :: [Int] -> Int -> OperationResult -> Maybe String
applyOperation xs x y = if oper y x xs
                           then Just $ matchMessage ( msg y ) xs x
                           else Nothing

matchOperation :: [OperationResult] -> [Int] -> Int -> [Maybe String]
matchOperation ops xs x = fmap (applyOperation xs x) ops

findMatch :: [Int] -> [Int] -> [String]
findMatch rs xs = fmap fromJust
                  $ filter ( /= Nothing )
                  $ join []
                  $ fmap (matchOperation availableOperations rs) xs

createCombinations :: [[Int]] -> [[Int]]
createCombinations xs = join [] $ fmap (choose 2) xs

procResults :: [String] -> IO ()
procResults = foldr ((>>) . putStrLn) (putStrLn "End!")

main :: IO ()
main = do [i] <- getArgs
          f <- readFile i
          let rows = fmap liftLine $ lines f
              comb = createCombinations rows
              oset = join [] $ nub $ join []
                     $ fmap ( x -> fmap (findMatch x) rows ) comb
              in procResults oset
                 >> print comb

Where having a sample input file with three numbers per line as follows:

4, 2, 8
6, 2, 12
6, 2, 3
9, 12, 108
4, 16, 64

Should be processed as follows:

08:21 [dmw@www:1 exercises]$ ghc --make challenge20120212.hs -o challenge20120212
[1 of 1] Compiling Main             ( challenge20120212.hs, challenge20120212.o )
Linking challenge20120212 ...
08:21 [dmw@www:1 exercises]$ ./challenge20120212 ./challenge20120212.txt
mul does 8 with [2,4]
add does 6 with [2,4]
mul does 16 with [2,8]
add does 12 with [4,8]
add does 8 with [2,6]
mul does 12 with [2,6]
mul does 6 with [2,3]
add does 9 with [3,6]
mul does 108 with [9,12]
mul does 64 with [4,16]
End!
[[2,4],[2,8],[4,8],[2,6],[2,12],[6,12],[2,3],[2,6],[3,6],[9,12],[9,108],[12,108],[4,16],[4,64],[16,64]]

Also, this program can process files with lines containing up to 4 numbers, no matter how many of them are present on the file, it will try all combinations thanks to the Math.Combinat.Sets module which is used to create the proper permutations with each line which are converted to Int lists with the liftLine function. Probably this is a kind of very basic MapReduce and non distributed implementation where you have various sets of unique permutations — or antisymmetric power of each list — and operations to check whether are executed.