Last active
August 29, 2015 14:20
-
-
Save shoooe/92068db275bfc11ac9d7 to your computer and use it in GitHub Desktop.
Solution to the fifth problem found here: https://goo.gl/eEyf9x, because it took longer than it should have.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-- Write a program that outputs all possibilities to put + or - or nothing | |
-- between the numbers 1, 2, ..., 9 (in this order) such that the result is | |
-- always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100. | |
import Control.Monad (replicateM) | |
ints :: [String] | |
ints = map (\i -> [i]) ['1'..'9'] | |
inbetweens :: [[String]] | |
inbetweens = replicateM 8 [" + ", " - ", ""] | |
alternate :: [a] -> [a] -> [a] | |
alternate [] r = r | |
alternate (x:xs) r = x : alternate r xs | |
allStrings :: [String] | |
allStrings = map (concat . alternate ints) inbetweens | |
splitBy :: (a -> Bool) -> [a] -> [[a]] | |
splitBy _ [] = [] | |
splitBy c ls = | |
let (l, r) = span (not . c) ls | |
in l : (splitBy c . drop 1 $ r) | |
opOf :: String -> (Int -> Int -> Int) | |
opOf "+" = (+) | |
opOf "-" = (-) | |
opOf _ = error "Unrecognized OP code" | |
evalTokens :: Int -> [String] -> Int | |
evalTokens acc [] = acc | |
evalTokens _ [_] = error "Invalid tokens" | |
evalTokens acc (op:b:r) = evalTokens ((opOf op) acc (read b)) r | |
evalString :: String -> Int | |
evalString str = | |
let (h:tokens) = (splitBy (==' ') str) in | |
evalTokens (read h) tokens | |
solution :: [String] | |
solution = map fst | |
. filter ((==100) . snd) | |
. map (\s -> (s, evalString s)) | |
$ allStrings | |
main :: IO () | |
main = mapM_ putStrLn solution |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment