Instantly share code, notes, and snippets.

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