-
-
Save gigamonkey/6249d85021bc8bf54eb4 to your computer and use it in GitHub Desktop.
-- Problem statement: | |
-- 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. | |
data Item = Plus | Minus | Num Int deriving (Show) | |
hundreds = filter ((100 ==) . eval) $ map combineAdjacent $ combos [1..9] | |
-- Generate all combos of digits 1-9 with +, -, or nothing in between. | |
combos :: [Int] -> [[Item]] | |
combos [n] = [ [Num n] ] | |
combos (n:ns) = [ (Num n : x) ++ rest | x <- [[Plus], [Minus], []], rest <- combos ns ] | |
-- Combine adjacent digits into a single number. | |
combineAdjacent :: [Item] -> [Item] | |
combineAdjacent (Num n : Num m : rest) = combineAdjacent (Num (n * 10 + m) : rest) | |
combineAdjacent (Num n : op : rest) = Num n : op : combineAdjacent rest | |
combineAdjacent x = x | |
-- Now eval the resulting thing as a left-associative expression. | |
eval :: [Item] -> Int | |
eval (Num n : Plus : Num m : rest) = eval (Num (n + m) : rest) | |
eval (Num n : Minus : Num m : rest) = eval (Num (n - m) : rest) | |
eval [ Num n ] = n | |
display xs = foldl (++) "" (map d xs) where | |
d Plus = " + " | |
d Minus = " - " | |
d (Num n) = show n | |
main = mapM_ (putStrLn . display) hundreds |
-- For further grins: here's a Haskell version of something like his solution. | |
hitTarget :: Int -> [Int] -> [[Int]] | |
hitTarget 0 [] = [[]] | |
hitTarget _ [] = [] | |
hitTarget target (d:ds) = plus ++ minus ++ combined where | |
plus = [ d:x | x <- hitTarget (target - d) ds ] | |
minus = [ -d:x | x <- hitTarget (target + d) ds ] | |
combined = if null ds then [] else hitTarget target ((d * 10 + head ds) : tail ds) | |
display :: [Int] -> String | |
display (n:ns) = foldl (++) (show n) (map withSign ns) where | |
withSign n | n > 0 = " + " ++ show n | |
withSign n | n < 0 = " - " ++ show (abs n) | |
hundreds = filter ((>0) . head) $ hitTarget 100 [1..9] | |
main = mapM_ (putStrLn . display) hundreds |
I like the concatMap (I thought there was something like that but I couldn't find it) and the fusion. But that do expression doesn't produce the right thing at all.
Gabriel, here's what I came up with which is not at all like your do expression but was inspired by trying to figure out what you were getting at. This replaces combos [1..9]
.
expressions :: [[Item]]
expressions = foldl cross [[]] (map withOp [1..9]) where
withOp n = [ Num n : x | x <- if n == 9 then [[]] else [[Plus],[Minus],[]] ]
cross xs ys = [ x ++ y | x <- xs, y <- ys ]
Actually, I think my filter
fusion is totally incorrect, so ignore that one.
Also, I think I managed to fix the items
one:
import Control.Monad (forM)
data Item = Num Int | Plus | Minus deriving (Show)
items :: [[Item]]
items = do
-- Example `groups` value: [[Num 1, Plus], [Num 2], ... [Num 8, Minus]]
groups <- forM [1..8] (\n -> do
xs <- [[Plus], [Minus], []]
return (Num n:xs) )
return (concat groups ++ [Num 9])
forM
is basically "foreach" in Haskell, except it works with arbitrary monads and collects the results in a list. Here I'm just saying "generate 8 groups", except that the result of each group is allowed to vary using the list monad. Then concatenate those groups and tack on Num 9
at the end.
I think you can simplify the generation of the list of items:
Also you can simplify
display
a little bit:Also, you can simplify
hundreds
a little bit by fusing thefilter
andmap
(stream fusion!)