Categories
Code Dump

Putting operators between numbers

You might have heard of this riddle: Given the numbers 1,5,6,7 permute them and put operators between them so that the solution is 21. Let’s find a solution with Haskell:

module Main where

import Data.List

data Action = Join | Add | Sub | Times | Div
  deriving (Eq, Show)

nums = permutations [1,5,6,7]
compOps = let as = [Join, Add, Sub, Times, Div] in [[a,b,c] | a <- as, b <- as, c <- as]
permOps = nub $ concatMap permutations compOps

eval :: Action -> Double -> Double -> Double
eval Join a b = a * 10^^(floor (logBase 10 b) + 1) + b
eval Add a b = a + b
eval Sub a b = a - b
eval Times a b = a * b
eval Div a b = a / b

brackets [a,b,c,d] [p,q,r] =
  [ check [p]   $ eval p (eval q a b)  (eval r c d)
  , check [p,q] $ eval p a (eval q (eval r b c) d)
  , check [p,q] $ eval p a (eval q b (eval r c d))
  , check [p,q] $ eval p (eval q (eval r a b) c) d
  , check [p,q] $ eval p (eval q a (eval r b c)) d
  ]
  where check xs a = if all (/=Join) xs then a else 0

main = print $ filter (any (==21) . snd) $ [((n, o), brackets n o) | n <- nums, o <- permOps]

And this yields:

>> main
[(([6.0,1.0,5.0,7.0],[Div,Sub,Div]),[7.0,-0.8823529411764706,21.0,0.14285714285714285,0.8285714285714285])]
>> 6.0 / 1.0 - 5.0 / 7.0
5.285714285714286
>> (6.0 / 1.0 - 5.0) / 7.0
0.14285714285714285
>> 6.0 / (1.0 - 5.0 / 7.0)
21.0