code challenge: generate minimal expressions using only digits 1,2,3

[andrew cooke]

from subsequent posts i think you were looking for something "smarter"
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))



andrew cooke wrote:
>
> 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
>
>
>
> 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
>
>