Sie erhalten eine Reihe von Gewichten, und Ihre Aufgabe besteht darin, mit diesen Gewichten ein kleines, ausgewogenes Mobiltelefon zu bauen.

Die Eingabe ist eine Liste von Ganzzahlgewichten im Bereich von 1 bis einschließlich 9. Möglicherweise sind Duplikate vorhanden.

Die Ausgabe ist ein ASCII-Bild eines Mobiltelefons, das beim Aufhängen ausgeglichen wird. Vielleicht am besten am Beispiel gezeigt:

Eingang

3 8 9 7 5

mögliche Ausgabe

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

Sie müssen die angegebenen ASCII-Zeichen verwenden. Die horizontalen und vertikalen Segmente können beliebig lang sein. Kein Teil des Mobiltelefons darf (horizontal oder vertikal) einen anderen nicht verbundenen Teil des Mobiltelefons berühren. Alle Gewichte müssen an einem vertikalen Segment von mindestens 1 Länge aufgehängt sein, und es muss ein vertikales Segment vorhanden sein, an dem das gesamte Mobiltelefon aufgehängt ist.

Die Größe eines Mobil ist die Gesamtzahl der +, -und |Zeichen , es zu bauen erforderlich. Geringere Größen sind besser.

Sie können so viele Verbindungen in ein Segment einfügen, wie Sie möchten. Beispielsweise:

Eingang

2 3 3 5 3 9

mögliche Ausgabe

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

Das Gewinnerprogramm ist dasjenige, das den niedrigsten Durchschnitt der Mobilgrößen für einen Testsatz von Eingaben generieren kann. Der eigentliche Test ist sehr geheim, um Hardcodierung zu verhindern, aber es wird ungefähr so ​​aussehen:

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.

Ich betrüge ein wenig Bit:

• Ich baue nur Handys mit einer Horizontalen. Ich habe das Gefühl , (aber ich habe bewiesen , dass es nicht) , dass das optimale Mobil unter den gegebenen Bedingungen tatsächlich immer nicht nur eine horizontalen hat. Edit: Nicht immer wahr; mit 2 2 9 1Nabb hat in den Kommentaren unten ein Gegenbeispiel gefunden:

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

• Ich mache nur dummes Brute-Forcing:

  1. Die angegebenen Gewichte werden zufällig gemischt.
  2. Jeweils zwei Gewichte werden in der besten Position auf das Mobiltelefon gelegt, damit es im Gleichgewicht bleibt.
  3. Wenn das resultierende Mobiltelefon besser ist als das, was wir zuvor hatten, denken Sie daran.
  4. Spülen und wiederholen, bis eine vordefinierte Anzahl von Sekunden verstrichen ist.

Meine Ergebnisse für Ihre Beispieleingaben; Jedes wurde 5 Sekunden lang ausgeführt (ich bin mir bewusst, dass dies für die Kleinen lächerlich ist - es wäre schneller, alle möglichen Permutationen durchzugehen). Da es ein zufälliges Element gibt, können nachfolgende Durchläufe zu besseren oder schlechteren Ergebnissen führen.

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

Der Code (ausführlich, da dies kein Code Golf ist):

import time, random

def gcd(a, b):
    while b > 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 < 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 < 0:
            self.contents = [w] + (abs(listindex) - 1) * [None] + self.contents
            self.pivot += abs(listindex)
        elif listindex >= 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 <= listindex < 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() < 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 < bestScore:
        best = m
        bestScore = s

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

Nun, das ist eine alte Frage, aber ich habe gerade gesehen, dass sie in der oberen Registerkarte "Fragen" angezeigt wird. Hier ist meine (optimale) Lösung:

#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <stdlib.h>

int main(int argc, const char *const *argv) {
    if(argc < 2) {
        fprintf(stderr,
            "Balances weights on a hanging mobile\n\n"
            "Usage: %s <weight1> [<weight2> [...]]\n",
            argv[0]
        );
        return 1;
    }
    int total = argc - 1;
    int values[total];
    int maxval = 0;
    for(int n = 0; n < total; ++ n) {
        char *check = NULL;
        long v = strtol(argv[n+1], &check, 10);
        if(v <= 0 || v > INT_MAX || *check != '\0') {
            fprintf(stderr,
                "Weight #%d (%s) is not an integer within (0 %d]\n",
                n + 1, argv[n+1], INT_MAX
            );
            return 1;
        }
        values[n] = (int) v;
        if(values[n] > maxval) {
            maxval = values[n];
        }
    }
    int maxwidth = (int) log10(maxval) + 1;
    for(int n = 0; n < total; ++ n) {
        int width = (int) log10(values[n]) + 1;
        fprintf(stdout,
            "%*s\n%*d\n",
            (maxwidth + 1) / 2, "|",
            (maxwidth + width) / 2, values[n]
        );
    }
    return 0;
}

Wenn ich mir die Regeln ansehe, bin ich mir ziemlich sicher, dass es nicht betrügt, obwohl es sich so anfühlt. Dadurch werden nur alle angegebenen Zahlen in einer vertikalen Kette ausgegeben, bei einem Gesamtbetrag von 2 * Anzahl_Eingaben (dies ist das Minimum, da jede Zahl unabhängig vom Layout einen Balken darüber haben muss). Hier ist ein Beispiel:

./mobile 3 8 9 7 5

Produziert:

|
3
|
8
|
9
|
7
|
5

Welches ist natürlich in perfekter Balance.

_{Eigentlich wollte ich im Geiste dieser Herausforderung etwas mehr ausprobieren, aber es stellte sich schnell heraus, dass es nur auf diese Struktur optimiert wurde}

Hier ist eine Lösung, die die kleinste einreihige Lösung zwingt. Der Code durchläuft alle Permutationen und berechnet für jede den Massenmittelpunkt. Wenn der Schwerpunkt ganzzahlige Koordinaten hat, haben wir eine Lösung gefunden.

Nachdem alle Permutationen ausprobiert wurden, fügen wir der Mischung in unserem aktuellen Satz von Gewichten ein Segment hinzu (entspricht einem Gewicht von Masse 0) und versuchen es erneut.

Führen Sie Folgendes aus, um das Programm auszuführen python balance.py 1 2 2 4.

#!/usr/bin/env python3
import itertools, sys

# taken from http://stackoverflow.com/a/30558049/436792
def unique_permutations(elements):
    if len(elements) == 1:
        yield (elements[0],)
    else:
        unique_elements = set(elements)
        for first_element in unique_elements:
            remaining_elements = list(elements)
            remaining_elements.remove(first_element)
            for sub_permutation in unique_permutations(remaining_elements):
                yield (first_element,) + sub_permutation

def print_solution(cm, values):
    print(('  ' * cm) + '|')
    print('-'.join(['-' if v == 0 else '+'  for v in values]))
    print(' '.join([' ' if v == 0 else '|'  for v in values]))
    print(' '.join([' ' if v == 0 else str(v) for v in values]))



input = list(map(int, sys.argv[1:]))
mass = sum(input)
while True:
    n = len(input)
    permutations = filter(lambda p: p[0] != 0 and p[n-1] != 0, unique_permutations(input))
    for p in permutations:
        cm = 0
        for i in range(n):
            cm += p[i] * i;
        if (cm % mass == 0):
            print_solution(cm//mass, p)
            sys.exit(0)
    input.append(0)

was diese besten Lösungen hervorbringt:

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


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

                |
+-+-+-+-+-+-+---+-+-+-+-+-+-+-+-+
| | | | | | |   | | | | | | | | |
8 8 8 8 8 8 8   8 8 8 8 8 8 8 8 7


                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | | | | |
1 1 2 2 3 3 4 4 8 8 5 5 6 6 7 7 7 7 9 9


                  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | | | | |
3 4 4 4 4 5 5 5 5 6 7 6 7 7 7 6 6

Python 3

Ich glaube, dies ist in keinem der Testfälle schlechter als 1, und das in 5 Sekunden.

Grundsätzlich benutze ich einen Single-Bar-Ansatz. Ich ordne die Eingabe nach dem Zufallsprinzip und setze dann die Gewichte nacheinander auf die Stange. Jedes Element wird entweder in die Position gebracht, die das Übergewicht auf beiden Seiten minimiert, oder aus dieser Perspektive in die zweitbeste Position, wobei die ersteren 75% der Zeit und die letzteren 25% der Zeit verwendet werden. Dann überprüfe ich, ob das Handy am Ende ausgeglichen ist und besser als das bisher beste Handy ist. Ich speichere die beste, halte an und drucke sie nach 5 Sekunden Suche aus.

Ergebnisse in 5-Sekunden-Läufen:

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)

Die einzige dieser Lösungen, die ich für suboptimal halte, ist die längste mit dieser Lösung, die ich nach 10 Minuten gefunden habe:

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