## 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.

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

```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 + 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 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] }

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.length <=> b.length }

puts "Most evaluated number = #{m} Number of times evaluated = #{m.length} values = #{m}"

```
11. Shot said

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