Python 3
This does no worse than 1 more than optimal on any of the test cases, I believe, and does so in 5 seconds.
Basically, I use a single bar approach. I randomly order the input, then insert the weights onto the bar one at a time. Each element is either put in the position that minimizes the excess weight on either side, or the second best position from that perspective, using the former 75% of the time and the latter 25% of the time. Then, I check whether the mobile is balanced at the end, and is better than the best mobile found so far. I store the best one, then halt and print it out after 5 seconds of searching.
Results, in 5 second runs:
py mobile.py <<< '3 8 7 5 9'
Best mobile found, score 15:
|
+-+-+-+-+
| | | | |
8 7 3 5 9
py mobile.py <<< '2 2 1 9'
Best mobile found, score 13:
|
+-++-+-+
| | | |
1 9 2 2
py mobile.py <<< '2 3 3 5 3 9'
Best mobile found, score 18:
|
+-+-+-+-+-+
| | | | | |
2 3 3 5 9 3
py mobile.py <<< '8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 7'
Best mobile found, score 49:
|
+-+--+-+-+-+-+-+++-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | |
7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
\py mobile.py <<< '1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 7 7'
Best mobile found, score 61:
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+
| | | | | | | | | | | | | | | | | | | |
1 7 7 5 4 3 1 9 6 7 8 2 2 9 3 7 6 5 8 4
py mobile.py <<< '3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7'
Best mobile found, score 51:
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | |
4 4 6 7 7 4 5 7 6 6 5 4 6 3 5 5 7
Code:
import random
import time
class Mobile:
def __init__(self):
self.contents = {}
self.lean = 0
def usable(self, loc):
return not any(loc + k in self.contents for k in (-1,0,1))
def choose_point(self, w):
def goodness(loc):
return abs(self.lean + w * loc)
gl = sorted(list(filter(self.usable,range(min(self.contents.keys() or [0]) - 5,max(self.contents.keys() or [0]) + 6))), key=goodness)
return random.choice((gl[0], gl[0], gl[0], gl[1]))
def add(self, w, loc):
self.contents[loc] = w
self.lean += w*loc
def __repr__(self):
width = range(min(self.contents.keys()), max(self.contents.keys()) + 1)
return '\n'.join((''.join(' ' if loc else '|' for loc in width),
''.join('+' if loc in self.contents or loc == 0 else '-' for loc in width),
''.join('|' if loc in self.contents else ' ' for loc in width),
''.join(str(self.contents.get(loc, ' ')) for loc in width)))
def score(self):
return max(self.contents.keys()) - min(self.contents.keys()) + len(self.contents) + 2
def my_score(self):
return max(self.contents.keys()) - min(self.contents.keys()) + 1
best = 1000000
best_mob = None
in_weights = list(map(int,input().split()))
time.clock()
while time.clock() < 5:
mob = Mobile()
for insert in random.sample(in_weights, len(in_weights)):
mob.add(insert, mob.choose_point(insert))
if not mob.lean:
if mob.score() < best:
best = mob.score()
best_mob = mob
print("Best mobile found, score %d:" % best_mob.score())
print(best_mob)
The only one of these solutions which I believe is suboptimal is the longest one, which has this solution, which I found after a 10 minute run:
Best mobile found, score 60:
|
+-+-+-+-+-+-+-+-+-+++-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | | | | |
3 2 9 4 7 8 1 6 9 8 7 1 6 2 4 5 7 3 5 7
total_weight_hung_from_point * distance_of_point_from_pivot
must be the same on both sides of the pivot point. \$\endgroup\$