1 
{-
   2 
 
   3 
Pearl 6: Making a century
   4 
 
   5 
Problem:
   6 
Given the digits 1..9, list all the ways the operations + and x can be inserted into 
   7 
the sequence so as to make the total sum 100.
   8 
For example:
   9 
100 = 12 + 34 + 5x6 +7 + 8 + 9
  10 
100 = 1 + 2x3 + 4 + 5 + 67 + 8 + 9
  11 
 
  12 
No parthneses, normal order of operations.
  13 
 
  14 
Solution:
  15 
This is a brute-force problem, but the goal of the pearl is to establish some
  16 
general formulation of 'Brute-Force' search, and improve on it with 'little'
  17 
assumptions.
  18 
 
  19 
Two main things for brute-force methods:
  20 
1. Generating the 'values' while generating the 'candidates', can produce savings (Especially
  21 
if generations of candidates can be 'sequential'). 
  22 
2. Reduce 'good' critertia to 'ok', it can help trim the generation of all sequences.
  23 
 
  24 
-}
  25 
 
  26 
-- You CAN skip all the general formulation description and go to ======
  27 
 
  28 
-- General formulation:
  29 
-- candidates    :: Data -> [Candidate]
  30 
-- value        :: Candidate -> Value
  31 
-- good         :: Value -> Bool
  32 
 
  33 
-- Brute force search over all candidates
  34 
-- solutions     :: Data -> [Candidate]
  35 
-- solutions    =  filter (good.value).candidates    
  36 
 
  37 
-- Now, using a few assumptions we can modify thigns:
  38 
 
  39 
-- Assumption 1: This will allow us to fuse operations.
  40 
--
  41 
-- Data is a list of values, [Datum], and candidates takes the form
  42 
-- candidates :: [Datum] -> [Candidate]
  43 
-- candidates =  foldr extend []
  44 
-- where
  45 
-- extend :: Datum -> [Candidate] -> [Candidate]
  46 
--
  47 
--
  48 
-- Assumption 2: This will allow us to extend search only as needed.
  49 
-- 
  50 
--      2.a There is a predicate 'ok', such that every good value is necesserialy 'ok'
  51 
--      2.b candidates with 'ok' values are the extension of candidates with 'ok' value.
  52 
--
  53 
-- Assumption 3: This will save us computing 'value' of candidate
  54 
--
  55 
--   map value.extend x = modify x.map value
  56 
--  The values of an extended set can be computed from the values of which the extension was
  57 
--  built from.
  58 
--
  59 
--  We then introduce a few operations on 'fork', 'cross', and relates these
  60 
-- to zip and unzip.
  61 
--   fork (f,g) x          =  (f x, g x)
  62 
--   cross (f,g) (x,y)     = (f x, g y)
  63 
--
  64 
-- and we get:
  65 
 
  66 
-- solutions     ::     Data -> [Candidate]
  67 
-- solutions     =     map fst.filter (good.snd).foldr expand []
  68 
 
  69 
-- expand x     =     filter (ok.snd).zip.cross (extend x, modify x).unzip
  70 
 
  71 
module P6 where
  72 
 
  73 
import Data.List (intercalate)
  74 
 
  75 
-- ================================================
  76 
 
  77 
 
  78 
 
  79 
-- So all the above was general design-framework.
  80 
-- now, to the specific problem (creating 100)
  81 
 
  82 
-- Expression     = sum of terms
  83 
-- Term         = products of factors
  84 
-- Factor         = sequence of digits
  85 
 
  86 
                            -- Candidate solution are expressions built from + and x
  87 
                            -- Remember: No parnthesis etc, and simple prioity.
  88 
type Expression    = [Term]    -- Each expression is the sum of Terms
  89 
type Term         = [Factor]    -- Each term is the product of factors
  90 
type Factor     = [Digit]    -- Each factor is list of digits
  91 
type Digit         = Int    
  92 
 
  93 
 
  94 
-- Just computing the value:
  95 
valExpr        ::    Expression -> Int
  96 
valExpr         =    sum.map valTerm 
  97 
valTerm      = product.map valFact 
  98 
valFact      = foldl (\n d -> 10*n+d)  0
  99 
 
 100 
 
 101 
good     ::     Int -> Bool
 102 
good v     =     (v==100)
 103 
 
 104 
ok        ::    Int -> Bool
 105 
ok v     =     (v<=100)
 106 
 
 107 
-- Creating all possible expressions
 108 
-- They mention there is a function 'partitions', but never spell it out.
 109 
-- so here it is, even though we will NOT use it!
 110 
partitions :: [Digit] -> [[[Digit]]]
 111 
partitions [] = [[]]
 112 
partitions (x:xs) = [[x]:p | p <- partitions xs]                -- x is a prt of it's own
 113 
                 ++ [(x:ys):yss | (ys:yss) <- partitions xs]    -- x is with the next ones
 114 
 
 115 
-- A difffernet way
 116 
expressions xs = foldr extend [] xs
 117 
 
 118 
extend                     ::    Digit -> [Expression] -> [Expression]
 119 
extend x []             =    [[[[x]]]]
 120 
extend x es             =    concatMap (glue x) es
 121 
 
 122 
-- glue: Each new digit can be added in one of 3-different ways to the expression:
 123 
-- as a digit; as factor (multiplication); or as a term ==> 3 options.
 124 
-- BTW, this shows the number of possible expressions is 3^(n-1) 
 125 
glue                     ::    Digit -> Expression -> [Expression]
 126 
glue x ((xs:xss):xsss)    =     [((x:xs):xss):xsss,       -- digit
 127 
                             ([x]:xs:xss):xsss,        -- factor
 128 
                             [[x]]:(xs:xss):xsss]    -- term
 129 
 
 130 
 
 131 
-- Main
 132 
 
 133 
main = do
 134 
    -- putStr "Testing partitions: "
 135 
    -- print $ partitions [1..4]
 136 
 
 137 
    putStrLn "Brute force : " 
 138 
    let res = filter (good.valExpr) $ expressions [1..9]
 139 
    --print res 
 140 
    prettyPrint res
 141 
 
 142 
 
 143 
-- pretty
 144 
prettyPrint es         =     putStr $ unlines $ map printExpression es 
 145 
 
 146 
printExpression     ::  Expression -> String
 147 
printExpression e     =     "100 = " ++ 
 148 
                        ( intercalate  " + " $ map printTerm e)
 149 
 
 150 
printTerm t         =      intercalate  "*" $ map printFactor t
 151 
printFactor f         =      concat $ map show f