-- Game of 24 implementation with the Fused Generate and Test pattern -- Sergio Antoy -- Wed Nov 28 10:37:16 PST 2001 -- updated: Mon Nov 5 11:23:45 PST 2007 -- updated: Thu Jun 29 11:23:39 PDT 2017 -- Given four 1-digit positive integers find an arithmetic expression -- that evaluates to 24 in which each digit occurs exactly once. -- A number can be divided only by its factors. -- For example, a solution of the problem [2,3,6,8] is (2+8)*3-6. -- There are 26 distinct solutions of this problem. -- Datatypes for representing an arithmetic expression of the game data Op = Add | Mul | Sub | Div data Exp = Num Int | Bin Op Exp Exp -- Convert an operation of an expression into its corresponding function dispatch Add = (+) dispatch Mul = (*) dispatch Sub = (-) dispatch Div = \x y -> if y == 0 || x `mod` y /= 0 then failed else x `div` y -- Permutations of a list permute [] = [] permute (x++[y]++z) = y : permute(x++z) -- Generate and evaluate. -- Traditionally, in a generate-and-test program, generator and -- tester are well-separated functions. Narrowing allows us to -- define a function where the two tasks are combined together. -- For each problem: generate all the expression containing the -- digits of the problem in a left-to-right traversal; simultaneously -- evaluate the expression; and return the expression's value. genEval (Num z) [z] = z genEval (Bin op x y) (u:us++v:vs) = dispatch op (genEval x (u:us)) (genEval y (v:vs)) -- Main entry point. -- Simultaneously generate and evaluate expressions and -- filter them if the value is 24. main | genEval X (permute problem) == 24 = X where X free -- A sample problem. problem = [2,3,8,6] ------------------------------------------------------------------ -- Unit testing test2 = permute problem result2 = [2,3,8,6] ? [2,3,6,8] ? [2,8,3,6] ? [2,8,6,3] ? [2,6,3,8] ? [2,6,8,3] ? [3,2,8,6] ? [3,8,2,6] ? [3,8,6,2] ? [3,2,6,8] ? [3,6,2,8] ? [3,6,8,2] ? [8,2,3,6] ? [8,3,2,6] ? [8,3,6,2] ? [8,2,6,3] ? [8,6,2,3] ? [8,6,3,2] ? [6,2,3,8] ? [6,3,2,8] ? [6,3,8,2] ? [6,2,8,3] ? [6,8,2,3] ? [6,8,3,2] test4 = main result4 = Bin Sub (Bin Mul (Bin Add (Num 2) (Num 8)) (Num 3)) (Num 6) ? Bin Sub (Bin Mul (Num 3) (Bin Add (Num 2) (Num 8))) (Num 6) ? Bin Add (Bin Mul (Num 3) (Bin Sub (Num 8) (Num 2))) (Num 6) ? Bin Sub (Bin Mul (Num 3) (Bin Add (Num 8) (Num 2))) (Num 6) ? Bin Sub (Bin Mul (Num 3) (Num 6)) (Bin Sub (Num 2) (Num 8)) ? Bin Add (Bin Sub (Bin Mul (Num 3) (Num 6)) (Num 2)) (Num 8) ? Bin Add (Bin Mul (Num 3) (Num 6)) (Bin Sub (Num 8) (Num 2)) ? Bin Sub (Bin Add (Bin Mul (Num 3) (Num 6)) (Num 8)) (Num 2) ? Bin Sub (Num 8) (Bin Sub (Num 2) (Bin Mul (Num 3) (Num 6))) ? Bin Add (Bin Sub (Num 8) (Num 2)) (Bin Mul (Num 3) (Num 6)) ? Bin Add (Bin Mul (Bin Sub (Num 8) (Num 2)) (Num 3)) (Num 6) ? Bin Sub (Bin Mul (Bin Add (Num 8) (Num 2)) (Num 3)) (Num 6) ? Bin Add (Num 8) (Bin Sub (Bin Mul (Num 3) (Num 6)) (Num 2)) ? Bin Sub (Bin Add (Num 8) (Bin Mul (Num 3) (Num 6))) (Num 2) ? Bin Sub (Num 8) (Bin Sub (Num 2) (Bin Mul (Num 6) (Num 3))) ? Bin Add (Bin Sub (Num 8) (Num 2)) (Bin Mul (Num 6) (Num 3)) ? Bin Add (Num 8) (Bin Sub (Bin Mul (Num 6) (Num 3)) (Num 2)) ? Bin Sub (Bin Add (Num 8) (Bin Mul (Num 6) (Num 3))) (Num 2) ? Bin Sub (Num 6) (Bin Mul (Num 3) (Bin Sub (Num 2) (Num 8))) ? Bin Sub (Bin Mul (Num 6) (Num 3)) (Bin Sub (Num 2) (Num 8)) ? Bin Add (Bin Sub (Bin Mul (Num 6) (Num 3)) (Num 2)) (Num 8) ? Bin Add (Num 6) (Bin Mul (Num 3) (Bin Sub (Num 8) (Num 2))) ? Bin Add (Bin Mul (Num 6) (Num 3)) (Bin Sub (Num 8) (Num 2)) ? Bin Sub (Bin Add (Bin Mul (Num 6) (Num 3)) (Num 8)) (Num 2) ? Bin Sub (Num 6) (Bin Mul (Bin Sub (Num 2) (Num 8)) (Num 3)) ? Bin Add (Num 6) (Bin Mul (Bin Sub (Num 8) (Num 2)) (Num 3))