Masz nmonety, z których każda waży -1 lub 1. Każda jest oznaczona od 0do, n-1dzięki czemu możesz rozróżnić monety. Masz także jedno (magiczne) urządzenie do ważenia. Za pierwszym razem możesz włożyć tyle monet, ile chcesz w urządzenie ważące, które jest w stanie zmierzyć zarówno masy ujemne, jak i dodatnie, i dokładnie powie, ile ważą.

Jednak w urządzeniu ważącym jest coś naprawdę dziwnego. Jeśli x_1, x_2, ..., x_jpo raz pierwszy umieścisz monety w urządzeniu, następnym razem będziesz musiał umieścić monety (x_1+1), (x_2+1) , ..., (x_j+1)na skali, z tym wyjątkiem, że oczywiście nie możesz włożyć monet o numerze wyższym niż n-1. Co więcej, przy każdym nowym ważeniu możesz wybrać, czy chcesz umieścić monetę 0na wadze .

Zgodnie z tą zasadą, jaka jest najmniejsza liczba ważeń, które zawsze powiedzą dokładnie, które monety ważą 1, a które -1?

Oczywiście można po prostu położyć monetę 0na urządzeniu w pierwszym zakręcie, a następnie zajmie to dokładne nważenie, aby rozwiązać problem.

Języki i biblioteki

Możesz użyć dowolnego języka lub biblioteki, która Ci się podoba (która nie została zaprojektowana do tego wyzwania). Chciałbym jednak móc przetestować Twój kod, jeśli to możliwe, więc jeśli możesz podać jasne instrukcje dotyczące uruchamiania go w Ubuntu, byłoby to bardzo mile widziane.

Wynik

Dla danego nwyniku twój wynik jest ndzielony przez liczbę ważeń, których potrzebujesz w najgorszym przypadku. Wyższe wyniki są zatem lepsze. Ta układanka nie ma wkładu, ale Twoim celem jest znalezienie takiej, ndla której możesz uzyskać najwyższy wynik.

Jeśli jest remis, pierwsza odpowiedź wygrywa. W niezwykle mało prawdopodobnej sytuacji, gdy ktoś znajdzie sposób na uzyskanie nieskończonej liczby punktów, ta osoba wygrywa natychmiast.

Zadanie

Twoim zadaniem jest po prostu napisanie kodu, który uzyska najwyższy wynik. Twój kod będzie musiał zarówno wybrać n sprytnie, a następnie zoptymalizować liczbę ważeń n.

Wiodące wpisy

• 4/3 7/5 w Pythonie Sarge Borsch
• 26/14 na Jawie autorstwa Petera Taylora

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

Ponownie sprawdzone rozwiązania właściwości Matrix X (lub Radość X) są bezpośrednio użyteczne jako rozwiązania tego problemu. Np. Rozwiązanie 31 rzędów 15 kolumn:

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 

wiersz N reprezentuje monety, które umieściłeś na wadze do pomiaru N. Bez względu na uzyskane wyniki ważenia, oczywiście istnieje pewien zestaw wartości monet, które dają tę wagę. Jeśli istnieje także inna kombinacja (rozwiązanie nie jest unikalne), zastanów się, jak się różnią. Zestaw monet należy zastąpić ważeniem 1monet -1. Daje to zestaw kolumn odpowiadających temu odwróceniu. Istnieje również zestaw wag -1, które zastępujesz 1. To kolejny zestaw kolumn. Ponieważ pomiary nie zmieniają się między dwoma rozwiązaniami, oznacza to, że sumy kolumn dwóch zbiorów muszą być takie same. Ale ponownie sprawdzono rozwiązania właściwości Matrix X (lub Radość X) są dokładnie tymi macierzami, w których takie zestawy kolumn nie istnieją, więc nie ma duplikatów, a każde rozwiązanie jest unikalne.

Każdy rzeczywisty zestaw pomiarów można opisać za pomocą jakiejś 0/1macierzy. Ale nawet jeśli niektóre zestawy kolumn sumują się z tymi samymi wektorami, może się zdarzyć, że znaki wartości monet rozwiązania kandydującego nie odpowiadają dokładnie takiemu zestawowi. Nie wiem więc, czy macierze takie jak powyższa są optymalne. Ale przynajmniej zapewniają dolną granicę. Zatem możliwość wykonania 31 monet w mniej niż 15 pomiarach jest nadal otwarta.

Zauważ, że jest to prawdą tylko w przypadku nieokreślonej strategii, w której decyzja o umieszczeniu monety 0na wadze zależy od wyniku poprzednich ważeń. W przeciwnym razie będziemy mieć rozwiązania, gdzie znaki monet odpowiadają zestawów, które mają taką samą sumę kolumny.

Python 2, wynik = 1,0

To łatwy wynik, na wypadek, gdyby nikt nie znalazł lepszego wyniku (wątpliwe). nważenia dla każdego 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)

Zaimportowałem, antigravityaby program mógł pracować z ujemnymi wagami.

Wynik = 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);
        }
    }
}

Zapisz jako LembikWeighingOptimisation.java, skompiluj jako javac LembikWeighingOptimisation.java, uruchom jako java LembikWeighingOptimisation.

Ogromne podziękowania dla Mitcha Schwartza za wskazanie błędu w pierwszej wersji szybkiego odrzucania.

Wykorzystuje to kilka dość podstawowych technik, których nie mogę dokładnie uzasadnić. To brutalne siły, ale tylko do rozpoczęcia operacji ważenia, które używają co najwyżej połowy monet: sekwencji, które wykorzystują więcej niż połowę monet, nie można bezpośrednio przenieść na uzupełniające ważenia (ponieważ nie znamy masy całkowitej), ale na falistym poziomie powinno być około tyle samo informacji. Powtarza również od początku ważenia w kolejności od liczby zaangażowanych monet, na tej podstawie, że w ten sposób obejmuje ważenia rozproszone (które, mam nadzieję, stosunkowo wcześnie podają informacje o górnej części), bez uprzedniego przeszukiwania wiązki, która zaczyna się gęstym podzbiorem dolny koniec.

MaskRangeKlasa jest ogromny postęp w stosunku do wcześniejszych wersji pod względem zużycia pamięci i usuwa z GC jest wąskim gardłem.

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, wynik = 4/3 = 1,33… (N = 4) wynik = 1,4 (N = 7)

Aktualizacja: zaimplementowano wyszukiwanie siłowe w zestawie „statycznych” solverów i otrzymano nowy wynik

Myślę, że można go jeszcze ulepszyć, szukając dynamicznych solverów, które mogą wykorzystywać wyniki ważenia do dalszych decyzji.

Oto kod Pythona, który przeszukuje wszystkie statyczne solwery w poszukiwaniu małych n wartości (te solwery zawsze ważą te same zestawy monet, stąd nazwa „statyczna”) i określa ich najgorszy przypadek liczby kroków po prostu sprawdzając, czy ich wyniki pomiaru pozwalają tylko na jedną pasującą monetę ustawione we wszystkich przypadkach. Ponadto śledzi najlepszy wynik znaleziony do tej pory i wczesne narzędzia do usuwania śliwek, które wykazały, że są zdecydowanie gorsze niż te, które znaleziono wcześniej. To była ważna optymalizacja, w przeciwnym razie nie mógłbym czekać na ten wynik z n= 7. (Ale najwyraźniej nadal nie jest zbyt dobrze zoptymalizowany)

Zadaj pytanie, jeśli nie jest jasne, jak to działa…

#!/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()

Wyjście:

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)

Ta linia (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 odkrywa najlepszy znaleziony solver. Liczby w {}nawiasach to wskaźniki monet, które należy umieścić na urządzeniu ważącym na każdym kroku.