[melbourne-pug] Friday Afternoon Python

martin schweitzer schweitzer.ubiquitous at gmail.com
Fri Aug 21 07:26:59 CEST 2009

Shlomi Fish posted a 'problem' to a Perl list of which I am a member.  I
thought "Why should Perl people have all the fun - and since it is Friday
afternoon decided to attack it using Python.  My answer is probably not the
most elegant - and I am sure some members can come up with better
solutions.  So, if there are any Pythonistas looking for an interesting
problem after Friday lunch, I will post the problem below (and my solution
below that).

(if there is any interest in this problem, I will try to think up an
original problem for next Friday)


Problem from Shlomi Fish:

We are given two positive integers $L and $R we need to find Plusified
expressions of both for which Eval($E_L) == Eval($E_R). So what is a
expression? It is an expression where we can choose whether to add a single
"+" between any consecutive digit. So for example the number 123 has the
following plusified expression:

* 123
* 12+3
* 1+23
* 1+2+3

So if we are given 123 and 96 we can form the following plusified equation:

* 12+3 == 9+6

Your mission is to write a Perl program (or an equivalent program in any
programming language) that will find all solutions to the plusified equation
of two numbers given as input. To normalise the output we'll rule that:

1. The equations should be given one at each line.

2. They will be sorted so consecutive digits will take precedence over

3. A "+" has no surrounding spaces.

4. The = sign does have a preceding and following space.

As an example:

$ ./plusified-equation 12341234 1010
1+23+41+2+34 = 101+0
1+2+3+4+1+2+3+4 = 10+10

--- End of Problem ---

Below this section there be spoilers....

Spoiler coming up...

Spoiler real close now...


def get_bin(n, width = 0):
    Given a number n, return the binary representatio
    of that number left padded with 0s to the length
    result = ''
    while (n):
        result = ('0','1')[n % 2] + result
        n = n / 2
    while len(result) < width:
        result = '0' + result
    return result

def get_partitions(string):
    Given a string s, treat each digit as the element
    of a set (a list, really), and return all the
    ways that set can be 'partitioned'.
    l = len(string) - 1
    partitions = [get_bin(n, l) for n in range(2 ** l)]
    return partitions

def insert_pluses(string):
    Return all combinations of string and pluses
    eg. with string = 123 will return
    ['123', '1+23', '12+3', '1+2+3']
    partitions = get_partitions(string)
    results = []
    for partition in partitions:
        result = ''

        i = 0
        l = len(string)
        for i in range(l - 1):
            result = result + string[i] + ('', '+')[int(partition[i])]
            #if partition[i] == '1':
            #    result = result + '+'
        result = result + string[l - 1]
    return results

# create a dictionary from lhs..
lhs = {}
for x in insert_pluses('12341234'):
    lhs.setdefault(eval(x), []).append(x)

rhs = {}
for x in insert_pluses('1010'):
    rhs.setdefault(eval(x), []).append(x)

for key in lhs.keys():
    if key in rhs:
        for v in lhs[key]:
            for u in rhs[key]:
                print v + ' = ' + u
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/melbourne-pug/attachments/20090821/1137e85d/attachment.htm>

More information about the melbourne-pug mailing list