The Xopus Challenge

Xopus.hs

-- Solution to https://twitter.com/xopus/status/88187651705946112
module Xopus where

import Data.List
import Control.Arrow

-- Prints: 
--   Sub (Mul (Num 12) (Add (Num 6) (Mul (Num 3) (Num 9)))) (Num 15)
--   Sub (Mul (Num 12) (Add (Num 6) (Mul (Num 9) (Num 3)))) (Num 15)
main :: IO ()
main = putStr
     . unlines
     . map show
     . filter (\x -> eval x == 381)
     $ solutions [3,6,9,12,15]

data Expr
  = Num Int
  | Add Expr Expr
  | Sub Expr Expr
  | Mul Expr Expr
  | Div Expr Expr
  deriving (Show, Eq)

eval :: Expr -> Int
eval x = case x of
  Num n -> n
  Add x y -> eval x + eval y
  Sub x y -> eval x - eval y
  Mul x y -> eval x * eval y
  Div x y -> case eval y of
              0 -> 0 -- cheat
              y' -> eval x `div` y'

solutions :: [Int] -> [Expr]
solutions [x] = [Num x]
solutions xs = do
  (x', xs') <- splits xs
  ys <- solutions xs'
  let x = Num x'
  [ x `Add` ys,
    x `Sub` ys,
    ys `Sub` x,
    x `Mul` ys,
    x `Div` ys,
    ys `Div` x]

splits :: [a] -> [(a, [a])]
splits [x] = [(x, [])]
splits (x : xs) = (x, xs) : map (second (x:)) (splits xs)