Skip to content

Instantly share code, notes, and snippets.

@marcmo marcmo/combineNumbers.hs
Last active Dec 10, 2015

Embed
What would you like to do?
import Data.List(foldl')
data Operator = Plus | Minus | Div | Mult | None | Id Double deriving(Eq,Show)
operators = [Plus,Minus,Div,Mult,None]
higher :: Operator -> Operator -> Bool
higher None None = False
higher None _ = True
higher Div Plus = True
higher Div Minus = True
higher Mult Plus = True
higher Mult Minus = True
higher _ _ = False
apply :: Operator -> Double -> Double -> Double
apply None a b = 10*a+b
apply Mult a b = a*b
apply Div a b = a/b
apply Plus a b = a+b
apply Minus a b = a-b
eval :: [Operator] -> Double
eval xs = shunting xs [] []
where shunting [] [v] _ = v
shunting (Id n:ns) as os = shunting ns (n:as) os -- push operand
shunting [] (a:b:bs) (o:os) = shunting [] (apply o b a:bs) os
shunting (n:ns) as [] = shunting ns as [n] -- push to empty operator stack
shunting (n:ns) (a:b:bs) (o:os)
| n `higher` o = shunting ns (a:b:bs) (n:o:os)
| otherwise = shunting (n:ns) (apply o b a:bs) os
combinations :: Int -> [a] -> [[a]]
combinations n = sequence . replicate n
interleave (n:ns) cs = reverse $ foldl' (\acc (a,b) -> a:b:acc) [n] (zip ns cs)
solve n = [combo | combo <- map (interleave ids) (combinations 9 operators)
, eval combo == n]
where ids = [Id n | n <- reverse [1..10]]
main = print $ solve 2013
local ops = {"","+","-","*","/"}
function check(n,e,res)
e = e..n
if n == 1 then
if luaeval(e) == 2013 then table.insert(res,e) end
else
for i,v in ipairs(ops) do check(n-1, e..v,res) end
end
return res
end
function luaeval(e)
return assert(loadstring("return "..e))()
end
local res = check(10,"",{})
for i,v in ipairs(res) do print(v,",") end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.