code challenge: generate minimal expressions using only digits 1,2,3
MRAB
google at mrabarnett.plus.com
Fri Feb 27 01:11:43 CET 2009
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)
More information about the Python-list
mailing list