145 Puzzle

April 20, 2010

Consider this math puzzle:

Form all the arithmetic expressions that consist of the digits one through nine, in order, with a plus-sign, a times-sign, or a null character interpolated between each pair of digits; for instance, 12+34*56+7*89 is a valid expression that evaluates to 2539. What number is the most frequent result of evaluating all possible arithmetic expressions formed as described above? How many times does it occur? What are the expressions that evaluate to that result?

Your task is to answer the three questions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

11 Responses to “145 Puzzle”

  1. [...] Praxis – 145 Puzzle By Remco Niemeijer In today’s Programming Praxis exercise we have to solve a math puzzle. The provided solution is 15 lines, not [...]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2010/04/20/programming-praxis-145-puzzle/ for a version with comments):

    import Control.Applicative
    import qualified Data.List.Key as K
    import Text.Parsec
    
    exprs :: String -> [String]
    exprs (x:y:ys) = [x:o++z | o <- ["","+","*"], z <- exprs $ y:ys]
    exprs xs       = [xs]
    
    eval :: String -> Int
    eval = either (const 0) id . parse expr "" where
        expr = chainl1 term ((+) <$ char '+')
        term = chainl1 (read <$> many1 digit) ((*) <$ char '*')
    
    main :: IO ()
    main = do let mf = K.maximum length . K.group snd . K.sort snd .
                       liftA2 zip id (map eval) $ exprs ['1'..'9']
              print (snd $ head mf, length mf)
              mapM_ putStrLn $ map fst mf
    
  3. kbob said

    From the name of the post, I expected this was the shortest solution.

    print 145
    

    But here’s a real solution using Python’s eval.

    from collections import defaultdict
    
    def z(s):
        if len(s) < 2:
            yield s
        else:
            for t in z(s[1:]):
                for i in ('+', '*', ''):
                    yield s[0] + i + t
            
    h = defaultdict(int)
    for x in z('123456789'):
        h[eval(x)] += 1
    print max(h, key=lambda n: h[n])
    
  4. F. Carr said

    You may be interested in the related “24 puzzle”, as seen on Wikipedia (http://en.wikipedia.org/wiki/24_Game) and as exhaustively enumerated (yes I am not kidding) http://home.manhattan.edu/~peter.boothe/24solutions/

  5. Mike said

    My python version:

    “product” returns all the cartesian products of its arguments,
    or if the “repeat” keyword is used, the cartesian product of
    the first argument repeated that many times.

    from collections import defaultdict
    from itertools import product
    
    expr_fmt = "1{0}2{1}3{2}4{3}5{4}6{5}7{6}8{7}9"
    output_fmt = """\
    There are {how_many} expressions that evaluate to {most_freq}.
    They are:
    	{expression_list}
    """
    
    value = defaultdict(list)
    
    for ops in product( ('','+','*'), repeat=8 ):
    	expression = expr_fmt.format( *ops )
    	value[ eval( expression ) ].append( expression )
    else:
    	most_freq = max( value, key=lambda k: len( value[k] ) )
    	how_many = len( value[ most_freq ] )
    	expression_list = '\n\t'.join( value[ most_freq ] )
    	print output_fmt.format( **locals() )
    
  6. Josh J said

    #!/usr/bin/perl
    # Answer: 0 occurs 167 times: 1*2*3*4-5*6+7+8-9 …
    use strict;
    use warnings;
    my %count;

    my @symbol = (qw(+ – * /), ”);
    foreach my $a (@symbol) {
    foreach my $b (@symbol) {
    foreach my $c (@symbol) {
    foreach my $d (@symbol) {
    foreach my $e (@symbol) {
    foreach my $f (@symbol) {
    foreach my $g (@symbol) {
    foreach my $h (@symbol) {
    my $expr = join(“”, 1, $a, 2, $b, 3, $c, 4, $d, 5, $e, 6, $f, 7, $g, 8, $h, 9);
    my $val = eval $expr;
    $count{$val}{$expr} = 1;
    }
    }}}}}}}

    my ($maxval, $maxcount, @maxexprs);
    while(my($val, $exprs) = each %count) {
    if (keys(%$exprs) > $maxcount) {
    $maxval = $val;
    $maxcount = keys %$exprs;
    @maxexprs = sort keys %$exprs;
    }
    }
    print “$maxval occurs $maxcount times: @maxexprs\n”;

  7. Josh J said

    Oops, I didn’t realize subtraction and division weren’t allowed. Just change the line to:
    my @symbol = (‘+’, ‘*’, ”);

  8. Axio said

    “Hand made” solution in Haskell, for the sake of the fun of it (I wanted to write the parser *huhu*)

    import List
    import Control.Monad.State
    import Data.Map

    data Exp = Num Int | Plus Exp Exp | Mult Exp Exp deriving Show

    {-Generate all the expressions-}
    gen [] = []
    gen [x] = [[x]]
    gen (x:xs) = let rest = gen xs in
    (List.map (\y -> x:’+':y) rest)
    ++
    (List.map (\y -> x:’*':y) rest)
    ++
    (List.map (\y -> x:y) rest)

    {-Useful tool-}
    conv :: String -> Maybe Exp
    conv [] = Nothing
    conv xs = (Just . Num . read . reverse) xs

    {-Now, the parser for our grammar!-}

    — F ::= 0 | 1 | …
    f seen = do
    l return $ conv seen
    (x:xs)->
    if (elem x “123456789”)
    then
    do
    put xs
    f (x:seen)
    else
    return $ conv seen
    — T ::= F T’
    t seen = do
    (Just exp) <- f []
    r return (Just exp)
    (Just exp’) -> return (Just (Mult exp exp’))
    — T’ ::= * T | ε
    t’ seen = do
    l return $ conv seen
    (‘*':xs)-> do
    put xs
    t seen
    otherwise -> return $ conv seen
    — E ::= T E’
    e seen = do
    (Just exp) <- t []
    r return (Just exp)
    (Just exp’) -> return (Just (Plus exp exp’))
    — E’ ::= + E | ε
    e’ seen = do
    l return $ conv seen
    (‘+':xs)-> do
    put xs
    e seen
    otherwise -> return $ conv seen

    — How to eval an Exp
    eval’ (Num n) = n
    eval’ (Plus e1 e2) = (eval’ e1) + (eval’ e2)
    eval’ (Mult e1 e2) = (eval’ e1) * (eval’ e2)
    eval x = case x of
    (Just exp) -> eval’ exp
    Nothing -> -1

    {-Well, there must be a cleaner way to do this…-}
    old tr k w =
    case Data.Map.lookup k tr of
    Just (n,v) -> (n+1,w:v)
    Nothing -> (1,[w])

    main = do
    {-All the sentences-}
    let parses = gen “123456789”
    {-Eval, build a map to store everything-}
    let list = toList $ foldl (\tr (ex,str) -> let r = eval ex in Data.Map.insert r (old tr r str) tr) empty $ List.map (\xp ->((evalState (e []) xp),xp)) parses
    {-Turn into a list to sort by number of occurences-}
    let all = (sortBy (\(_,(a,_)) (_,(b,_)) -> compare a b) list)
    {-Print everything if you want to-}
    — mapM_ print all
    {-The result-}
    let (n,(m,l)) = last all
    print $ “Number ” ++ (show n) ++ ” appears ” ++ (show m) ++ ” times, and is generated by formulas: ” ++ (show l)

  9. F. Carr said

    Another solution that does *not* “eval” or do any string-parsing. There must be a more efficient way to implement “foldls” — basically it just enumerates the depth-1 trees that have a given list of leaves — but I’m blanking on it. Any haskellers or schemers to the rescue? :)

    from collections import defaultdict
    from operator import mul
    
    def base10(x,y): return 10*x + y
    
    def foldls(xs, oper, init):
        if len(xs) == 0:
            yield []
        else:
            x = init
            for k in range(len(xs)):
                x = oper(x, xs[k])
                for tail in foldls(xs[k+1:], oper, init):
                    yield [x] + tail
    
    count = defaultdict(int)
    for numbers in foldls(range(1,9+1), base10, 0):
        for products in foldls(numbers, mul, 1):
            count[ sum(products) ] += 1
    
    print "the most common result is", max(count, key=count.get)
    
  10. slabounty said

    You can see it commented at http://steamcode.blogspot.com/2010/05/145-puzzle.html (no highlighting though :( )

    def mc(elements, level, current=[], &block)
        elements.each do | e |
            if level == 1 then
                yield current << e
            else
                mc(elements, level-1, current << e, &block)
            end
            current.pop
        end
    end
    
    digits = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
    
    results = Hash.new()
    
    mc(['*', '+', ''], 8) do | operators | 
    
        # Initialize the string to evaluate.
        eval_string = ''
    
        # Add the digits and operators to the eval_string.
        0.upto(digits.length-2) { |i| eval_string << digits[i] << operators[i] }
    
        # Add teh final digit.
        eval_string << digits.last
    
        # Evaluate the string and save the result in the hash. Create a new array
        # if one doesn't exist at this position.
        (results[eval(eval_string)] ||= []) << eval_string
    end
    
    m = results.max { |a, b| a[1].length <=> b[1].length }
    
    puts "Most evaluated number = #{m[0]} Number of times evaluated = #{m[1].length} values = #{m[1]}"
    
    
  11. Shot said

    My take in ten-odd lines of Ruby: http://gist.github.com/422922

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 628 other followers

%d bloggers like this: