fork download
copy 
  1. import Data.Array.IO
  2. import Data.Char
  3. import System.IO
  4. import Control.Monad
  5. import Control.Applicative
  6.  
  7. one :: [a] -> [(a, [a])]
  8. one xs = sub xs []
  9.   where
  10.     sub [] _ = []
  11.     sub (x:xs) ac = (x, xs++ac) : (sub xs (x:ac))
  12.  
  13. two :: [a] -> [(a, a, [a])]
  14. two [] = []
  15. two [a] = []
  16. two xs = do
  17.   (x, rest) <- one xs
  18.   do
  19.     (y, rest) <- one rest
  20.     return (x, y, rest)
  21.  
  22. data Expr = Val Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr
  23. type Number = (Expr, Int)
  24.  
  25. eval :: Number -> Int
  26. eval = snd
  27.  
  28. apply :: [Number] -> [[Number]]
  29. apply xs = concat $ do
  30.   ((e, x), (f, y), rest) <- two xs
  31.   return [
  32.     (Add e f, x + y) : rest,
  33.     (Sub e f, x - y) : rest,
  34.     (Mul e f, x * y) : rest
  35.     ]
  36.  
  37. bfs :: Int -> [[Number]] -> [Number]
  38. bfs n [] = []
  39. bfs n ([x] : rest) =
  40.   (if (eval x) == n then [x] else []) ++ (bfs n rest)
  41. bfs n (xs : rest) = bfs n (rest ++ (apply xs))
  42.  
  43. instance Show Expr where
  44.   show (Val n) = show n
  45.   show (Add e f) = "(" ++ show e ++ " + " ++ show f ++ ")"
  46.   show (Sub e f) = "(" ++ show e ++ " - " ++ show f ++ ")"
  47.   show (Mul e f) = "(" ++ show e ++ " * " ++ show f ++ ")"
  48.  
  49. toVal :: Int -> Number
  50. toVal n = (Val n, n)
  51.  
  52. solve a b c d = do
  53.   let anss = bfs 10 [[toVal a, toVal b, toVal c, toVal d]]
  54.   if null anss
  55.     then print 0
  56.     else print $ fst $ head $ anss
  57.  
  58. main = do
  59.   [a,b,c,d] <- (map read . words)<$>getLine :: IO [Int]
  60.   if (minimum [a,b,c,d]) == 0
  61.     then return ()
  62.     else solve a b c d >> main
  63.  
  64.  
Success #stdin #stdout 0.06s 4780KB
comments (?)
stdin
copy 
1 1 1 1
9 9 9 9
1 2 3 4
2 3 4 5
0 0 0 0
stdout
copy 
0
0
(((1 + 2) + 3) + 4)
(5 - ((2 - 3) - 4))
https://ideone.com/Lso7nn
language:
Haskell (ghc 8.4.4)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!