code challenge: generate minimal expressions using only digits 1,2,3
Trip Technician
we are trying to express numbers as minimal expressions using only the
digits one two and three, with conventional arithmetic. so for
instance
33 = 2^(3+2)+1 = 3^3+(3*2)
are both minimal, using 4 digits but
33 = ((3+2)*2+1)*3
using 5 is not.
I have tried coding a function to return the minimal representation
for any integer, but haven't cracked it so far. The naive first
attempt is to generate lots of random strings, eval() them and sort by
size and value. this is inelegant and slow.
I have a dim intuition that it could be done with a very clever bit of
recursion, but the exact form so far eludes me.
Paul Rubin
> I have a dim intuition that it could be done with a very clever bit of
> recursion, but the exact form so far eludes me.
This sounds a little like a homework assignment, or maybe a challenge
you are trying to solve for yourself, rather than be given a complete
answer for. Anyway, the basic idea is to enumerate the expression
trees with 1 digit, then 2 digits, then 3 digits, etc, and compute the
value expressed by each tree.
Nigel Rantor
> anyone interested in looking at the following problem.
if you can give me a good reason why this is not homework I'd love to
hear it...I just don't see how this is a real problem.
> we are trying to express numbers as minimal expressions using only the
> digits one two and three, with conventional arithmetic. so for
> instance
>
> 33 = 2^(3+2)+1 = 3^3+(3*2)
>
> are both minimal, using 4 digits but
>
> 33 = ((3+2)*2+1)*3
>
> using 5 is not.
>
> I have tried coding a function to return the minimal representation
> for any integer, but haven't cracked it so far. The naive first
> attempt is to generate lots of random strings, eval() them and sort by
> size and value. this is inelegant and slow.
Wow. Okay, what other ways have you tried so far? Or are you beating
your head against the "search the entire problem space" solution still?
This problem smells a lot like factorisation, so I would think of it in
terms of wanting to reduce the target number using as few operations as
possible.
If you allow exponentiation that's going to be your biggest hitter so
you know that the best you can do using 2 digits is n^n where n is the
largest digit you allow yourself.
Are you going to allow things like n^n^n or not?
n
Trip Technician
Thanks will get onto it. It's just a challenge I set myself so hints
only are cool.
Trip Technician
>
> - Show quoted text -
yes n^n^n would be fine. agree it is connected to factorisation.
building a tree of possible expressions is my next angle.
andrew cooke
this is a neat problem.
here is what i would do: use generators that extend an input. a stream
approach. the initial input would be the numbers themselves.
[('1', 1),('2', 2),('3', 3)]
those are (expression, value) pairs
then an initial attempt at the next function would be to extend that list
with additions:
def additions(pairs):
for (expr1, value1) in pairs:
# first, pass through unchanged
yield (expr1, value1)
# then generate all possible additions
for (expr2, value2) in pairs:
yield ('%s+%s'%(value1, value2), value1 + value2))
this would give you:
[('1', 1),('2', 2),('3', 3), ('1+1', 2), ...]
(you may need to add parentheses to expressions to preserve meaning
correctly)
you could extend that with an extra loop over different operations.
(subtraction, multiplication, etc)
then you could repeat that as often as you want (eating its own tail, in a
sense, i think). an infinite list is ok because these are generators.
then you could filter that to group expressions that give a certain value,
and find the shortest.
andrew
> --
> http://mail.python.org/mailman/listinfo/python-list
>
>
Nigel Rantor
> yes power towers are allowed
right, okay, without coding it here's my thought.
factorise the numbers you have but only allowing primes that exist in
your digit set.
then take that factorisation and turn any repeated runs of digits
multiplied by themselves into power-towers
any remainder can then be created in other ways, starting with a way
other than exponentiation that is able to create the largest number,
i.e. multiplication, then addition...
I've not got time to put it into code right now but it shouldn't be too
hard...
e.g.
digits : 3, 2, 1
n : 10
10 = 2*5 - but we don't have 5...
10 = 3*3 + 1
10 = 3^2+1
3 digits
n : 27
27 = 3*3*3
27 = 3^3
2 digits
n : 33
33 = 3*3*3 + 6
33 = 3*3*3 + 3*2
33 = 3^3+3*2
4 digits
> exponentiation, multiplication, division, addition and subtraction.
> Brackets when necessary but length is sorted on number of digits not
> number of operators plus digits.
>
> I always try my homework myself first. in 38 years of life I've
> learned only to do what i want, if I wanted everyone else to do my work
> for me I'd be a management consultant !
> On Fri, Feb 20, 2009 at 3:52 PM, Luke Dunn <luke...@gmail.com
> <mailto:luke...@gmail.com>> wrote:
>
> I am teaching myself coding. No university or school, so i guess its
> homework if you like. i am interested in algorithms generally, after
> doing some of Project Euler. Of course my own learning process is
> best served by just getting on with it but sometimes you will do
> that while other times you might just choose to ask for help. if no
> one suggests then i will probably shelve it and come back to it
> myself when I'm fresh.
>
> no it's not a real world problem but my grounding is in math so i
> like pure stuff anyway. don't see how that is a problem, as a math
> person i accept the validity of pure research conducted just for
> curiosity and aesthetic satisfaction. it often finds an application
> later anyway
>
> Thanks for your helpful suggestion of trying other methods and i
> will do that in time. my motive was to share an interesting problem
> because a human of moderate math education can sit down with this
> and find minimal solutions easily but the intuition they use is
> quite subtle, hence the idea of converting the human heuristic into
> an algorithm became of interest, and particularly a recursive one. i
> find that the development of a piece of recursion usually comes as
> an 'aha', and since i hadn't had such a moment, i thought i'd turn
> the problem loose on the public. also i found no online reference to
> this problem so it seemed ripe for sharing.
>
> On Fri, Feb 20, 2009 at 3:39 PM, Nigel Rantor <wig...@wiggly.org
> <mailto:wig...@wiggly.org>> wrote:
>
> Trip Technician wrote:
>
> anyone interested in looking at the following problem.
>
>
> if you can give me a good reason why this is not homework I'd
> love to hear it...I just don't see how this is a real problem.
>
>
> we are trying to express numbers as minimal expressions
> using only the
> digits one two and three, with conventional arithmetic. so for
> instance
>
> 33 = 2^(3+2)+1 = 3^3+(3*2)
>
> are both minimal, using 4 digits but
>
> 33 = ((3+2)*2+1)*3
>
> using 5 is not.
>
> I have tried coding a function to return the minimal
> representation
> for any integer, but haven't cracked it so far. The naive first
> attempt is to generate lots of random strings, eval() them
> and sort by
> size and value. this is inelegant and slow.
>
>
Nigel Rantor
>
> yes n^n^n would be fine. agree it is connected to factorisation.
> building a tree of possible expressions is my next angle.
I think building trees of the possible expressions as a couple of other
people have suggested is simply a more structured way of doing what
you're currnetly doing.
Right now you're throwing darts at the problem space, and hoping that
the next one point you hit will be a more optimal solution.
If you enumerate all the expression trees you are just ensuring you
don't miss any solutions.
I think the algorithm/hueristic I just posted should get you to the
answer quicker though...
n
Tim Wintle
> Luke Dunn wrote:
<snip>
That was my initial thought when I read this too - but I'm not certain
that is guaranteed to find a solution (i.e. a solution that's optimal).
I'd welcome a proof that it will though, a few minutes thought hasn't
found a counter-example.
> > anyone interested in looking at the following problem.
> >
> >
> > if you can give me a good reason why this is not homework I'd
> > love to hear it...I just don't see how this is a real problem.
> >
> >
> > we are trying to express numbers as minimal expressions
> > using only the
> > digits one two and three, with conventional arithmetic. so for
> > instance
> >
> > 33 = 2^(3+2)+1 = 3^3+(3*2)
> >
> > are both minimal, using 4 digits but
> >
> > 33 = ((3+2)*2+1)*3
> >
> > using 5 is not.
> >
> > I have tried coding a function to return the minimal
> > representation
> > for any integer, but haven't cracked it so far. The naive first
> > attempt is to generate lots of random strings, eval() them
> > and sort by
> > size and value. this is inelegant and slow.
> >
> >
> > Wow. Okay, what other ways have you tried so far? Or are you
> > beating your head against the "search the entire problem space"
> > solution still?
> >
> > This problem smells a lot like factorisation, so I would think
> > of it in terms of wanting to reduce the target number using as
> > few operations as possible.
> >
> > If you allow exponentiation that's going to be your biggest
> > hitter so you know that the best you can do using 2 digits is
> > n^n where n is the largest digit you allow yourself.
> >
> > Are you going to allow things like n^n^n or not?
> >
> > n
> >
> >
> >
> >
>
andrew cooke
than my streams, but i was interested in the idea, so i wrote an
implementation. hope this is ok - if you don't want to see a worked
solution, read no further...
i have been using generators a lot recently; now that i understand them
better i really like the "laziness" they give. this code is perhaps more
like you would see in haskell than in python...
some results from the code as below:
-725 = (((1)+(1))+((1)+(1)))-(((1)+(2))^((2)*(3))) (length 8)
...
-2 = (1)-(3) (length 2)
-1 = (1)-(2) (length 2)
0 = (1)-(1) (length 2)
1 = 1 (length 1)
2 = 2 (length 1)
3 = 3 (length 1)
4 = (1)+(3) (length 2)
...
972 = (((1)+(1))+((1)+(1)))*(((1)+(2))^((2)+(3))) (length 8)
note that because this is a brute-force search it is limited in the number
of combinations it considers (for a given "take", below), and not at all
"smart" (in preferring pow over other values for example), so the extreme
values are nothing like optimal (the final invocation, commented out, uses
sorting to improve things).
also, complex and float values are generated; i discard those with a
filter, but you can drop that if you are curious.
#!/usr/bin/python3
'''
See
http://groups.google.com/group/comp.lang.python/browse_thread/thread/b387f99deb376392
This is a brute force approach using streams, implemented
with generators.
'''
from operator import add, sub, mul, truediv as div, pow
OPERATORS = [('+', add), ('-', sub), ('*', mul),
('/', div), ('^', pow)]
START = [(str(i), 1, i) for i in [1,2,3]]
def all_operators(stream):
'''
Generate new values by combining the values in 'stream' in
all the different ways possible.
'''
for (exprn, length, value) in stream:
for (symbol, op) in OPERATORS:
for (exprn2, length2, value2) in stream:
try:
yield ('({0}){1}({2})'.format(
exprn, symbol, exprn2),
length + length2,
op(value, value2))
except Exception as e:
# print('Ignoring {}',format(e))
pass
def repeat(generator, preproc=lambda x: x):
'''
Make a generator 'eat its own tail', primed with 'start'.
All output is kept and fed back into the generator as input. Note
that memory use increases steadily.
'''
def repeater(start):
start = preproc(start)
for value in start:
yield value
while True:
finish = []
for value in generator(start):
yield value
finish.append(value)
start = finish
return repeater
def value(elv):
'''
Pick the value from an elv triplet.
'''
(exprn, length, value) = elv
return value
def take(n):
'''
Build a filter that takes the first n values from a stream.
'''
def taker(stream, n=n):
while n > 0:
yield next(stream)
n -= 1
return taker
def mkfilter(predicate):
'''
Curry Python's filter function.
'''
def myfilter(stream):
return filter(lambda elv: predicate(value(elv)), stream)
return myfilter
def compose(*filters):
'''
Compose several filters to give a new filter.
(Is there a better way to write this?)
'''
def composer(iter1, iter2):
def composed(stream):
for value in iter1(iter2(stream)):
yield value
return composed
if len(filters) == 1:
return filters[0]
else:
return composer(filters[0], compose(*filters[1:]))
def summarise(stream):
'''
Group values by value, keeping the shortest expression,
then print everything.
'''
exprns = {}
lengths = {}
for (exprn, length, value) in stream:
if value not in exprns or length < lengths[value]:
exprns[value] = exprn
lengths[value] = length
values = [value for value in exprns if type(value) is int]
for value in sorted(values):
print('{0:>5} = {1:20} (length {2})'.format(
value, exprns[value], lengths[value]))
if __name__ == '__main__':
ints = mkfilter(lambda x: type(x) is int)
small = mkfilter(lambda x: abs(x) < 1000)
# this gets very slow after 20000 values
# summarise(compose(take(20000),
# repeat(compose(ints,
# all_operators)))(START))
# clipping values to below 1000 makes things much faster
# note 200,000 below, 20,000 above!
summarise(compose(take(200000),
repeat(compose(ints, small,
all_operators)))(START))
# get to larger values faster by sorting in the repeat
# sort = lambda x: sorted(x, key=value, reverse=True)
# summarise(compose(take(200000),
# repeat(compose(ints, small,
# all_operators),
# preproc=sort))(START))
> Trip Technician wrote:
>> anyone interested in looking at the following problem.
>> we are trying to express numbers as minimal expressions using only the
digits one two and three, with conventional arithmetic. so for
>> instance
>> 33 = 2^(3+2)+1 = 3^3+(3*2)
>> are both minimal, using 4 digits but
>> 33 = ((3+2)*2+1)*3
>> using 5 is not.
>> I have tried coding a function to return the minimal representation for
any integer, but haven't cracked it so far. The naive first attempt is
to generate lots of random strings, eval() them and sort by size and
value. this is inelegant and slow.
>> I have a dim intuition that it could be done with a very clever bit of
recursion, but the exact form so far eludes me.
>> --
>> http://mail.python.org/mailman/listinfo/python-list
>
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>
>
Dan Goodman
year, you might find that thread gives you some ideas:
http://mail.python.org/pipermail/python-list/2008-January/474071.html
Dan
Jonathan Gardner
Actually, representing 33 has an even shorter answer: '33'
There is actually a really easy solution for this. What you are really
doing is finding the shortest path from point A (the expression '') to
another expression that evaluates to the target number.
From each point, you can take steps that (a) add a digit to the end or
(b) add an operator---but only if it makes sense. Since operators
don't count, those steps don't add anything to the distance, while the
digits do.
What you do is you start walking the map from point A to some
mysterious point that evaluates to the result you want. Actually, you
send out walkers in all directions, and tell only the walkers that
have taken the fewest steps to take another step. Once a walker gets
to an expression with the result, you have your answer since he is the
first walker to get there. When a walker gets to an expression that
has already been visited, you can tell that walker to go home since
his path was no good. When a walker gets to an expression that
evaluates to a value you have already seen, that walker too should go
home since he has just found a longer path to the same result.
So you have a set of walkers, and each walker has the expression they
used to get to where they are and how many steps they took to get
there. You also have a set of values you have seen before and thus
values that if a walker finds you are no longer interested in.
For each iteration, you take each surviving walker and spawn a new
walker that takes a step in each possible direction. Then you check if
any of those walkers found the value you are looking for. If so,
you've found the answer. If they hit a value you've already seen, you
drop that walker from the set.
The only hanging point is parentheses. What you can do here is instead
of building a linear expression, build a tree expression that shows
the operations and the values they operate. It should be trivial to
calculate all the different new trees that are one digit longer than a
previous tree.
Rhodri James
<jgar...@jonathangardner.net> wrote:
[snip]
> For each iteration, you take each surviving walker and spawn a new
> walker that takes a step in each possible direction. Then you check if
> any of those walkers found the value you are looking for. If so,
> you've found the answer. If they hit a value you've already seen, you
> drop that walker from the set.
This relies each value having the same set of next states no matter how
it's reached. Unfortunately that's not true. Consider what happens
when you walk on from (1+3) and (2+2):
One possible step from (1+3) is ((1/3)+3) == 3.33... There's no single
step from (2+2) that can get you to the same place.
> The only hanging point is parentheses. What you can do here is instead
> of building a linear expression, build a tree expression that shows
> the operations and the values they operate. It should be trivial to
> calculate all the different new trees that are one digit longer than a
> previous tree.
Trivial yes, but the number of different new trees is large when you're
dealing with four digits, and ridiculous with 5.
--
Rhodri James *-* Wildebeeste Herder to the Masses
MRAB
import operator
def solve(n):
best_len = n
best_expr = ""
for x in range(1, n - 2):
for y in range(x, n):
for op, name in operator_list:
# Does this pair with this op give the right answer?
if op(x, y) == n:
lx, ex = numbers[x - 1]
ly, ey = numbers[y - 1]
# How many digits in total?
l = lx + ly
# Fewer digits than any previous attempts?
if l < best_len:
# Build the expression.
e = "(%s %s %s)" % (ex, name, ey)
best_len, best_expr = l, e
return best_len, best_expr
operator_list = [(operator.add, "+"), (operator.sub, "-"),
(operator.mul, "*"), (operator.div, "/"), (operator.pow, "^")]
# Tuples contain number of digits used and expression.
numbers = [(1, str(n)) for n in range(1, 4)]
for n in range(4, 34):
numbers.append(solve(n))
for i, (l, e) in enumerate(numbers):
print "%2d = %s" % (i + 1, e)
Dan Goodman
Sadly this doesn't work because you're assuming that the shortest
expression always involves increasing the size of the numbers at every
step. For example, your algorithm for 63 gives:
(3 * (3 * (1 + (2 * 3))))
which involves 4 operations, whereas the simplest is:
2**(2*3)-1
which only involves 3 (but has an intermediate value 2**6=64 above the
target value).
Fixing this is actually pretty hard, because the search space becomes
very large if you allow yourself arbitrarily large numbers. You can't do
any obvious pruning that I can think of, because operations between very
large numbers can end up very small (for example, 13**3-3**7=10 even
though 13**3=2197 and 3**7=2187 are both very large), and the shortest
path to a small number might go through very large numbers (I bet with a
bit more thought than I have put into it, you could come up with some
examples where the intermediate calculations are arbitrarily larger than
the end result). As well as the growth of the search space, the
computations get hairy too, try computing 3**3**3**3 for example (or
better, don't, because it has 3638334640025 digits).
I haven't got a solution that can be guaranteed correct and is feasible
to compute for anything but very small examples - anyone done better?
Dan