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.
Here's my solution (I haven't bothered with making it efficient, BTW):
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)
--
http://mail.python.org/mailman/listinfo/python-list
