Build a small and balanced mobile You are given a bunch of weights, and your task is to build a small balanced mobile using those weights.

The input is a list of integer weights in the range 1 through 9, inclusive.  There may be duplicates.

The output is an ascii picture of a mobile that, when hung, would balance.  Perhaps best shown by example:

input

3 8 9 7 5


possible output

         |
   +-----+---------+
   |               |
+--+-+        +----+------+
|    |        |           |
8   ++--+     7           5
    |   |
    9   3


You must use the ascii characters as shown.  The horizontal and vertical segments may be of any length.  No part of the mobile may touch (horizontally or vertically) another unconnected part of the mobile.  All weights must be hung from a vertical segment of length at least 1, and there must be a vertical segment from which the whole mobile is hung.

The size of a mobile is the total number of +,-,and | characters required to build it.  Lower sizes are better.

You may put as many connections on a segment as you would like.  For example:

input

2 3 3 5 3 9


possible output

           |
   +---+---+-----------+
   |   |               |
+--+-+ 5               9
|  | |
2  | 3
   |
  +++
  | |
  3 3


The winning program is the one that can generate the lowest average of mobile sizes for a test set of inputs.  The real test is super-secret to prevent hard-coding, but it will be something like this:

8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 7
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 7 7
3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7
Python 2.

I'm cheating a little bit:


I only construct mobiles with one horizontal. I have a feeling (but I haven't proven it) that the optimal mobile under the given conditions actually always does only have one horizontal. Edit: Not always true; with 2 2 9 1 Nabb has found a counter-example in the comments below:

Size 18:                Size 16:
   |                        |
+-++--+-----+            +--++-+
| |   |     |            |   | |
2 9   2     1           -+-  9 1
                        | |
                        2 2

I just do stupid brute-forcing:


The given weights are shuffled randomly.
Two weights at a time are placed on the mobile in the best positions such that it stays balanced.
If the resulting mobile is better than any that we had before, remember it.
Rinse and repeat, until a pre-defined number of seconds is up.



My results for your sample inputs; each was run for 5 seconds (I'm aware that this is ridiculous for the small ones &ndash; just going through all possible permutations would be faster). Note that since there's a random element, subsequent runs may find better or worse results.

3 8 9 7 5
Tested 107887 mobiles, smallest size 20:
        |
+-+-----+-+--+
| |     | |  |
5 3     7 9  8

2 3 3 5 3 9
Tested 57915 mobiles, smallest size 23:
      |
+--+-++--+-+---+
|  | |   | |   |
3  5 9   3 3   2

8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 7
Tested 11992 mobiles, smallest size 50:
                |
+-+-+-+--+-+-+-+++-+-+--+-+-+-+-+
| | | |  | | | | | | |  | | | | |
8 8 8 8  8 8 8 8 8 8 8  7 8 8 8 8

1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 7 7
Tested 11119 mobiles, smallest size 62:
                    |
+-+-+-+-+-+--+-+-+-+++-+-+-+--+-+-+-+-+-+
| | | | | |  | | | | | | | |  | | | | | |
2 7 5 6 6 8  3 2 3 7 9 7 8 1  1 7 9 5 4 4

3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7
Tested 16301 mobiles, smallest size 51:
                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | |
4 6 5 7 7 4 6 5 3 5 6 4 7 6 7 5 4


The code (verbose, as this isn't code golf):



import time, random

def gcd(a, b):
    while b &gt; 0:
        a, b = b, a % b
    return a

class Mobile(object):
    def __init__(self):
        self.contents = [None];
        self.pivot = 0;

    def addWeights(self, w1, w2):
        g = gcd(w1, w2)
        m1 = w2 / g
        m2 = w1 / g
        mul = 0
        p1 = -1
        while True:
            if p1 &lt; 0:
                mul += 1
                p1 = mul * m1
                p2 = -mul * m2
            else:
                p1 *= -1
                p2 *= -1
            if self.free(p1) and self.free(p2):
                self.add(w1, p1)
                self.add(w2, p2)
                return

    def add(self, w, pos):
        listindex = self.pivot - pos 
        if listindex &lt; 0:
            self.contents = [w] + (abs(listindex) - 1) * [None] + self.contents
            self.pivot += abs(listindex)
        elif listindex &gt;= len(self.contents):
            self.contents += (listindex - len(self.contents)) * [None] + [w]
        else:
            self.contents[listindex] = w

    def at(self, pos):
        listindex = self.pivot - pos
        if 0 &lt;= listindex &lt; len(self.contents):
            return self.contents[listindex]
        return None

    def free(self, pos):
        return all(self.at(pos + d) is None for d in (-1, 0, 1))

    def score(self):
        return 1 + 2 * len(self.contents) - self.contents.count(None)

    def draw(self):
        print self.pivot * " " + "|"
        print "".join("+" if c is not None or i == self.pivot else "-" for i, c in enumerate(self.contents))
        print "".join("|" if c is not None else " " for c in self.contents)
        print "".join(str(c) if c is not None else " " for c in self.contents)

    def assertBalance(self):
        assert sum((i - self.pivot) * (c or 0) for i, c in enumerate(self.contents)) == 0


weights = map(int, raw_input().split())

best = None
count = 0

# change the 5 to the number of seconds that are acceptable
until = time.time() + 5

while time.time() &lt; until:
    count += 1
    m = Mobile()

    # create a random permutation of the weights
    perm = list(weights)
    random.shuffle(perm)

    if len(perm) % 2:
        # uneven number of weights -- place one in the middle
        m.add(perm.pop(), 0)

    while perm:
        m.addWeights(perm.pop(), perm.pop())

    m.assertBalance() # just to prove the algorithm is correct :)
    s = m.score()
    if best is None or s &lt; bestScore:
        best = m
        bestScore = s

print "Tested %d mobiles, smallest size %d:" % (count, best.score())
best.draw()