Sie haben nMünzen, von denen jede entweder -1 oder 1 wiegt. Jede ist mit 0bis gekennzeichnet , n-1damit Sie die Münzen voneinander unterscheiden können. Sie haben auch eine (magische) Waage. Bei der ersten Wende können Sie so viele Münzen wie Sie möchten auf die Waage legen, die sowohl negative als auch positive Gewichte messen kann und Ihnen genau sagt, wie viel sie wiegen.

Das Wägegerät hat jedoch etwas wirklich Merkwürdiges. Wenn Sie x_1, x_2, ..., x_jdas erste Mal Münzen auf das Gerät legen , müssen Sie das nächste Mal Münzen (x_1+1), (x_2+1) , ..., (x_j+1)auf die Waage legen, mit der Ausnahme, dass Sie natürlich keine Münze mit einer höheren Nummer als einsetzen können n-1. Darüber hinaus können Sie bei jedem neuen Wiegen auswählen, ob Sie auch eine Münze 0auf die Waage legen möchten .

Was ist nach dieser Regel die kleinste Anzahl von Wägungen, die Ihnen immer genau sagen, welche Münzen 1 wiegen und welche -1 wiegen?

Es ist klar, dass Sie 0in der ersten Runde einfach eine Münze auf das Gerät legen könnten und dann genau das nWägen erforderlich wäre, um das Problem zu lösen.

Sprachen und Bibliotheken

Sie können eine beliebige Sprache oder Bibliothek verwenden (die nicht für diese Herausforderung entwickelt wurde). Ich würde jedoch gerne in der Lage sein, Ihren Code nach Möglichkeit zu testen. Wenn Sie also klare Anweisungen zur Ausführung in Ubuntu geben können, wären Sie sehr dankbar.

Ergebnis

Für eine gegebene wird nIhre Punktzahl ndurch die Anzahl der Wägungen geteilt, die Sie im schlimmsten Fall benötigen. Höhere Werte sind daher besser. Es gibt keine Eingabe für dieses Rätsel, aber Ihr Ziel ist es, eine zu finden, nfür die Sie die höchste Punktzahl erzielen können.

Bei Gleichstand gewinnt die erste Antwort. In der äußerst unwahrscheinlichen Situation, in der jemand einen Weg findet, eine unendliche Punktzahl zu erzielen, gewinnt diese Person sofort.

Aufgabe

Ihre Aufgabe ist es einfach, Code zu schreiben, der die höchste Punktzahl erzielt. Ihr Code muss sowohl ein n geschickt auswählen als auch die Anzahl der Wägungen dafür optimieren n.

Führende Einträge

• 4/3 7/5 in Python von Sarge Borsch
• 26/14 in Java von Peter Taylor

C ++, Score 23/12 25/13 27/14 28/14 = 2 31/15

Die Lösungen der Matrix-Eigenschaft X revisited (oder Joy of X) können direkt als Lösungen für dieses Problem verwendet werden. ZB die Lösung von 31 Zeilen, 15 Spalten:

1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 
1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 
1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 
1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 
1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 
0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 
0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 
1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 
0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 
0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 
0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 
1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 
0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 
0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 
1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 

Zeile N stellt dar, welche Münzen Sie für die Messung N auf die Waage legen. Unabhängig von den Ergebnissen der Gewichtung gibt es offensichtlich eine Reihe von Münzwerten, die dieses Gewicht ergeben. Wenn es auch eine andere Kombination gibt (die Lösung ist nicht eindeutig), überlegen Sie, wie sie sich unterscheiden. Sie müssen einen Satz Münzengewichtungen 1durch Münzengewichtungen ersetzen -1. Dies ergibt eine Reihe von Spalten, die diesem Flip entsprechen. Es gibt auch eine Reihe von Münzen Gewicht -1, die Sie durch ersetzen 1. Das ist ein weiterer Satz von Spalten. Da sich die Messungen zwischen den beiden Lösungen nicht ändern, müssen die Spaltensummen der beiden Sätze gleich sein. Aber die Lösungen für Matrix-Eigenschaft X überarbeitet (oder die Freude an X) die genau in diesen Matrizen werden, in denen solche Spaltenmengen nicht existieren, sodass es keine Duplikate gibt und jede Lösung einzigartig ist.

Jeder tatsächliche Satz von Messungen kann von einigen beschrieben werden 0/1 Matrix . Aber selbst wenn einige Spaltenmengen dieselben Vektoren ergeben, kann es sein, dass die Vorzeichen der Münzwerte der Kandidatenlösung nicht genau einer solchen Menge entsprechen. Ich weiß also nicht, ob Matrizen wie die oben genannte optimal sind. Aber zumindest bieten sie eine Untergrenze. So ist die Möglichkeit, dass 31 Münzen in weniger als 15 Messungen durchgeführt werden können, noch offen.

Beachten Sie, dass dies nur für eine nicht festgelegte Strategie gilt, bei der Ihre Entscheidung, eine Münze 0auf die Waage zu setzen, vom Ergebnis der vorherigen Gewichtung abhängt. Sonst Sie werden Lösungen, wo die Zeichen der Münzen mit den Sätzen entsprechen, die die gleiche Spaltensumme haben.

Python 2, Punktzahl = 1,0

Dies ist die einfache Punktzahl, falls niemand eine bessere Punktzahl findet (zweifelhaft). nWägungen für jeden n.

import antigravity
import random

def weigh(coins, indices):
    return sum(coins[i] for i in indices)

def main(n):
    coins = [random.choice([-1,1]) for i in range(n)]
    for i in range(len(coins)):
        print weigh(coins, [i]),

main(4)

Ich habe importiert, antigravitydamit das Programm mit negativen Gewichten arbeiten kann.

Score = 26/14 ~ = 1,857

import java.util.*;

public class LembikWeighingOptimisation {

    public static void main(String[] args) {
        float best = 0;
        int opt = 1;
        for (int n = 6; n < 32; n+=2) {
            long start = System.nanoTime();
            System.out.format("%d\t", n);
            opt = optimise(n, n / 2 + 1);
            float score = n / (float)opt;
            System.out.format("%d\t%f", opt, score);
            if (score > best) {
                best = score;
                System.out.print('*');
            }
            System.out.format(" in %d seconds", (System.nanoTime() - start) / 1000000000);
            System.out.println();
        }
    }

    private static int optimise(int numCoins, int minN) {
        MaskRange.N = numCoins;
        Set<MaskRange> coinSets = new HashSet<MaskRange>();
        coinSets.add(new MaskRange(0, 0));

        int allCoins = (1 << numCoins) - 1;

        for (int n = minN; n < numCoins; n++) {
            for (int startCoins = 1; startCoins * 2 <= numCoins; startCoins++) {
                for (int mask = (1 << startCoins) - 1; mask < (1 << numCoins); ) {
                    // Quick-reject: in n turns, do we cover the entire set?
                    int qr = (1 << (n-1)) - 1;
                    for (int j = 0; j < n; j++) qr |= mask << j;
                    if ((qr & allCoins) == allCoins && canDistinguishInNTurns(mask, coinSets, n)) {
                        System.out.print("[" + Integer.toBinaryString(mask) + "] ");
                        return n;
                    }

                    // Gosper's hack to update
                    int c = mask & -mask;
                    int r = mask + c;
                    mask = (((r^mask) >>> 2) / c) | r;
                }
            }
        }

        return numCoins;
    }

    private static boolean canDistinguishInNTurns(int mask, Set<MaskRange> coinsets, int n) {
        if (n < 0) throw new IllegalArgumentException("n");
        int count = 0;
        for (MaskRange mr : coinsets) count += mr.size();
        if (count <= 1) return true;
        if (n == 0) return false;

        // Partition.
        Set<MaskRange>[] p = new Set[Integer.bitCount(mask) + 1];
        for (int i = 0; i < p.length; i++) p[i] = new HashSet<MaskRange>();
        for (MaskRange range : coinsets) range.partition(mask, p);

        for (int d = 0; d < 2; d++) {
            boolean ok = true;
            for (Set<MaskRange> s : p) {
                if (!canDistinguishInNTurns((mask << 1) + d, s, n - 1)) {
                    ok = false;
                    break;
                }
            }

            if (ok) return true;
        }

        return false;
    }

    static class MaskRange {
        public static int N;
        public final int mask, value;

        public MaskRange(int mask, int value) {
            this.mask = mask;
            this.value = value & mask;
            if (this.value != value) throw new IllegalArgumentException();
        }

        public int size() {
            return 1 << (N - Integer.bitCount(mask));
        }

        public void partition(int otherMask, Set<MaskRange>[] p) {
            otherMask &= (1 << N) - 1;

            int baseline = Integer.bitCount(value & otherMask);
            int variables = otherMask & ~mask;
            int union = mask | otherMask;
            partitionInner(value, union, variables, baseline, p);
        }

        private static void partitionInner(int v, int m, int var, int baseline, Set<MaskRange>[] p) {
            if (var == 0) {
                p[baseline].add(new MaskRange(m, v));
            }
            else {
                int lowest = var & (1 + ~var);
                partitionInner(v,          m, var & ~lowest, baseline, p);
                partitionInner(v | lowest, m, var & ~lowest, baseline + 1, p);
            }
        }

        @Override
        public String toString() {
            return String.format("(x & %x = %x)", mask, value);
        }
    }
}

Speichern als LembikWeighingOptimisation.java, Kompilieren als javac LembikWeighingOptimisation.java, Ausführen als java LembikWeighingOptimisation.

Vielen Dank an Mitch Schwartz für den Hinweis auf einen Fehler in der ersten Version des Quick Reject.

Dies verwendet einige ziemlich grundlegende Techniken, die ich nicht konsequent rechtfertigen kann. Brute-Forces, aber nur zum Starten von Wiegevorgängen, bei denen höchstens die Hälfte der Münzen verwendet wird: Sequenzen, bei denen mehr als die Hälfte der Münzen verwendet wird, können nicht direkt auf die Zusatzwägungen übertragen werden (da das Gesamtgewicht nicht bekannt ist). Auf einer handgewellten Ebene sollte es jedoch ungefähr die gleiche Menge an Informationen geben. Es iteriert auch durch das Starten der Wägungen in der Reihenfolge der Anzahl der beteiligten Münzen, auf der Grundlage, dass es verteilte Wägungen abdeckt (die hoffentlich relativ früh Informationen über das obere Ende liefern), ohne zuerst durch einen Haufen zu kriechen, der mit einer dichten Teilmenge bei beginnt das untere Ende.

Die MaskRangeKlasse ist eine massive Verbesserung gegenüber der früheren Version in Bezug auf die Speichernutzung und beseitigt den Engpass bei GC.

20      [11101001010] 11        1.818182* in 5364 seconds
22      [110110101000] 12       1.833333* in 33116 seconds
24      [1000011001001] 13      1.846154* in 12181 seconds                                                                                                            
26      [100101001100000] 14    1.857143* in 73890 seconds  

Python 3, Punktzahl = 4/3 = 1,33… (N = 4) Punktzahl = 1,4 (N = 7)

Update: Brute-Force-Suche in "statischen" Lösungssätzen implementiert und neues Ergebnis erzielt

Ich denke, es kann weiter verbessert werden, indem nach dynamischen Lösern gesucht wird, die Gewichtungsergebnisse für weitere Entscheidungen verwenden können.

Hier ist ein Python-Code, der alle statischen Löser nach kleinen n Werten durchsucht (diese Löser wiegen immer die gleichen Münzsätze, daher der "statische" Name) und die Anzahl der Schritte im ungünstigsten Fall ermittelt, indem er einfach überprüft, ob die Messergebnisse nur eine übereinstimmende Münze zulassen in allen fällen eingestellt. Außerdem werden die bisher besten Ergebnisse und die frühen Pflaumenlöser protokolliert, die gezeigt haben, dass sie definitiv schlechter sind als diejenigen, die zuvor gefunden wurden. Dies war eine wichtige Optimierung, ansonsten konnte ich mit n= 7 nicht auf dieses Ergebnis warten . (Aber es ist eindeutig immer noch nicht sehr gut optimiert)

Sie können gerne Fragen stellen, wenn nicht klar ist, wie es funktioniert.

#!/usr/bin/env python3
import itertools
from functools import partial


def get_all_possible_coinsets(n):
    return tuple(itertools.product(*itertools.repeat((-1, 1), n)))


def weigh(coinset, indexes_to_weigh):
    return sum(coinset[x] for x in indexes_to_weigh)


# made_measurements: [(indexes, weight)]
def filter_by_measurements(coinsets, made_measurements):
    return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), coinsets)


class Position(object):
    def __init__(self, all_coinsets, coinset, made_measurements=()):
        self.all_coinsets = all_coinsets
        self.made_measurements = made_measurements
        self.coins = coinset

    def possible_coinsets(self):
        return tuple(filter_by_measurements(self.all_coinsets, self.made_measurements))

    def is_final(self):
        possible_coinsets = self.possible_coinsets()
        return (len(possible_coinsets) == 1) and possible_coinsets[0] == self.coins

    def move(self, measurement_indexes):
        measure_result = (measurement_indexes, weigh(self.coins, measurement_indexes))
        return Position(self.all_coinsets, self.coins, self.made_measurements + (measure_result,))


def get_all_start_positions(coinsets):
    for cs in coinsets:
        yield Position(coinsets, cs)


def average(xs):
    return sum(xs) / len(xs)


class StaticSolver(object):
    def __init__(self, measurements):
        self.measurements = measurements

    def choose_move(self, position: Position):
        index = len(position.made_measurements)
        return self.measurements[index]

    def __str__(self, *args, **kwargs):
        return 'StaticSolver({})'.format(', '.join(map(lambda x: '{' + ','.join(map(str, x)) + '}', self.measurements)))

    def __repr__(self):
        return str(self)


class FailedSolver(Exception):
    pass


def test_solvers(solvers, start_positions, max_steps):
    for solver in solvers:
        try:
            test_results = tuple(map(partial(test_solver, solver=solver, max_steps=max_steps), start_positions))
            yield (solver, max(test_results))
        except FailedSolver:
            continue


def all_measurement_starts(n):
    for i in range(1, n + 1):
        yield from itertools.combinations(range(n), i)


def next_measurement(n, measurement, include_zero):
    shifted = filter(lambda x: x < n, map(lambda x: x + 1, measurement))
    if include_zero:
        return tuple(itertools.chain((0,), shifted))
    else:
        return tuple(shifted)


def make_measurement_sequence(n, start, zero_decisions):
    yield start
    m = start
    for zero_decision in zero_decisions:
        m = next_measurement(n, m, zero_decision)
        yield m


def measurement_sequences_from_start(n, start, max_steps):
    continuations = itertools.product(*itertools.repeat((True, False), max_steps - 1))
    for c in continuations:
        yield tuple(make_measurement_sequence(n, start, c))


def all_measurement_sequences(n, max_steps):
    starts = all_measurement_starts(n)
    for start in starts:
        yield from measurement_sequences_from_start(n, start, max_steps)


def all_static_solvers(n, max_steps):
    return map(StaticSolver, all_measurement_sequences(n, max_steps))


def main():
    best_score = 1.0
    for n in range(1, 11):
        print('Searching with N = {}:'.format(n))
        coinsets = get_all_possible_coinsets(n)
        start_positions = tuple(get_all_start_positions(coinsets))


        # we are not interested in solvers with worst case number of steps bigger than this
        max_steps = int(n / best_score)

        solvers = all_static_solvers(n, max_steps)
        succeeded_solvers = test_solvers(solvers, start_positions, max_steps)

        try:
            best = min(succeeded_solvers, key=lambda x: x[1])
        except ValueError:  # no successful solvers
            continue
        score = n / best[1]
        best_score = max(score, best_score)
        print('{}, score = {}/{} = {}'.format(best, n, best[1], score))
    print('That\'s all!')


def test_solver(start_position: Position, solver, max_steps):
    p = start_position
    steps = 0
    try:
        while not p.is_final():
            steps += 1
            if steps > max_steps:
                raise FailedSolver
            p = p.move(solver.choose_move(p))
        return steps
    except IndexError:  # solution was not found after given steps — this solver failed to beat score 1
        raise FailedSolver


if __name__ == '__main__':
    main()

Die Ausgabe:

Searching with N = 1:
(StaticSolver({0}), 1), score = 1/1 = 1.0
Searching with N = 2:
(StaticSolver({0}, {0,1}), 2), score = 2/2 = 1.0
Searching with N = 3:
(StaticSolver({0}, {0,1}, {0,1,2}), 3), score = 3/3 = 1.0
Searching with N = 4:
(StaticSolver({0,1}, {1,2}, {0,2,3}, {0,1,3}), 3), score = 4/3 = 1.3333333333333333
Searching with N = 5:
Searching with N = 6:
Searching with N = 7:
(StaticSolver({0,2}, {0,1,3}, {0,1,2,4}, {1,2,3,5}, {0,2,3,4,6}), 5), score = 7/5 = 1.4
Searching with N = 8:
Searching with N = 9:
(I gave up waiting at this moment)

Diese Zeile (StaticSolver({0,2}, {0,1,3}, {0,1,2,4}, {1,2,3,5}, {0,2,3,4,6}), 5), score = 7/5 = 1.4deckt den besten gefundenen Löser auf. Die Zahlen in {}Klammern sind die Indizes der Münzen, die bei jedem Schritt an der Wägevorrichtung angebracht werden müssen.