У вас есть nмонеты, каждая из которых весит -1 или 1. Каждая помечена от 0до, n-1чтобы вы могли различить монеты. У вас есть одно (волшебное) весовое устройство. На первом повороте вы можете положить столько весов, сколько вам нужно, на весы, которые способны измерять как отрицательные, так и положительные веса, и он точно скажет вам, сколько они весят.

Однако в весовом устройстве есть что-то действительно странное. Если вы кладете монеты x_1, x_2, ..., x_jна устройство в первый раз, то в следующий раз вам нужно будет положить монеты (x_1+1), (x_2+1) , ..., (x_j+1)на шкалу, за исключением того, что вы, конечно, не можете положить монету с номером выше, чем n-1. Мало того, что для каждого нового взвешивания вы можете выбрать, хотите ли вы поставить монету 0на весы.

Согласно этому правилу, какое наименьшее количество взвешиваний всегда будет точно указывать, какие монеты весят 1, а какие - -1?

Очевидно, что вы могли бы просто положить монету 0на устройство в первый ход, а затем потребовались бы именно nвзвешивания для решения проблемы.

Языки и библиотеки

Вы можете использовать любой язык или библиотеку, которая вам нравится (которая не была разработана для этой задачи). Тем не менее, я хотел бы иметь возможность протестировать ваш код, если это возможно, поэтому, если вы можете предоставить четкие инструкции по его запуску в Ubuntu, это было бы очень полезно.

Гол

Для данного результата nваш результат nделится на количество взвешиваний, которое вам нужно в худшем случае. Чем выше баллы, тем лучше. В эту загадку нет входных данных, но ваша цель - найти тот, nза который вы можете получить наивысший балл.

Если есть связь, побеждает первый ответ. В крайне маловероятной ситуации, когда кто-то находит способ получить бесконечное количество очков, он сразу же выигрывает.

задача

Ваша задача - просто написать код, который получает самый высокий балл. Ваш код должен будет как правильно выбрать n, так и затем оптимизировать количество взвешиваний для этого n.

Ведущие записи

• 4/3 7/5 в Python от Sarge Borsch
• 26/14 на Яве Питер Тейлор

C ++, счет 23/12 25/13 27/14 28/14 = 2 31/15

Решения Matrix свойство X повторно (или Радость X) могут непосредственно использоваться в качестве решений этой проблемы. Например, решение из 31 строки 15 столбцов:

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 

строка N представляет, какие монеты вы положили на шкалу для измерения N. Какими бы ни были результаты взвешивания, которые вы получаете, очевидно, есть некоторый набор значений монет, который дает этот вес. Если есть и другая комбинация (решение не уникально), подумайте, чем они отличаются. Вы должны заменить набор взвешивания 1монет на взвешивание монет -1. Это дает набор столбцов, которые соответствуют этому отражению. Существует также набор монет весом, -1который вы заменяете 1. Это еще один набор столбцов. Поскольку измерения не меняются между двумя решениями, это означает, что суммы столбцов двух наборов должны быть одинаковыми. Но решения Matrix свойство X вновь (или Радость X) это именно те матрицы, где такие наборы столбцов не существуют, поэтому нет дубликатов, и каждое решение уникально.

Каждый фактический набор измерений может быть описан некоторой 0/1матрицей. Но даже если некоторые наборы столбцов суммируют одинаковые векторы, возможно, что знаки значений монет-кандидатов решения не точно соответствуют такому набору. Так что я не знаю, являются ли матрицы, подобные приведенной выше, оптимальными. Но, по крайней мере, они обеспечивают нижнюю границу. Таким образом, возможность того, что 31 монета может быть сделана менее чем за 15 измерений, все еще открыта.

Обратите внимание, что это верно только для нефиксированной стратегии, когда ваше решение поставить монету 0на весы зависит от результата предыдущих взвешиваний. В противном случае у вас будут решения, в которых знаки монет соответствуют наборам с одинаковой суммой столбцов.

Python 2, оценка = 1,0

Это простой результат, если никто не находит лучший результат (сомнительно). nвзвешивания для каждого 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)

Я импортировал, antigravityчтобы программа могла работать с отрицательными весами.

Оценка = 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);
        }
    }
}

Сохранить как LembikWeighingOptimisation.java, скомпилировать как javac LembikWeighingOptimisation.java, запустить как java LembikWeighingOptimisation.

Большое спасибо Митчу Шварцу за то, что он указал на ошибку в первой версии быстрого отказа.

Здесь используются довольно простые методы, которые я не могу строго обосновать. Это грубые силы, но только для начала операций взвешивания, в которых используется не более половины монет: последовательности, в которых используется более половины монет, не могут быть напрямую перенесены на дополнительные взвешивания (потому что мы не знаем общий вес), но на уровне волнистости рук должно быть примерно столько же информации. Он также перебирает начальные взвешивания в порядке количества задействованных монет, исходя из того, что таким образом он покрывает рассредоточенные взвешивания (которые, как мы надеемся, дают информацию о верхнем конце относительно рано) без предварительного обхода сгустка, который начинается с плотного подмножества в нижний конец.

Этот MaskRangeкласс является существенным улучшением предыдущей версии с точки зрения использования памяти и устраняет узкие места в 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, оценка = 4/3 = 1,33… (N = 4) оценка = 1,4 (N = 7)

Обновление: реализован поиск методом "грубой силы" в наборе "статических" решателей и получен новый результат

Я думаю, что это может быть улучшено путем поиска динамических решателей, которые могут использовать результаты взвешивания для дальнейших решений.

Вот код Python, который ищет во всех статических решателях небольшие n значения (эти решатели всегда взвешивают одни и те же наборы монет, отсюда и «статическое» имя) и определяет количество шагов в наихудшем случае, просто проверяя, что результаты их измерений допускают только одну совпадающую монету. установить во всех случаях. Кроме того, он отслеживает лучшие результаты, найденные до сих пор, и ранние решатели чернослива, которые показали, что они определенно хуже, чем те, которые были найдены ранее. Это была важная оптимизация, иначе я не мог дождаться этого результата с n= 7. (Но он все еще не очень хорошо оптимизирован)

Не стесняйтесь задавать вопросы, если не ясно, как это работает ...

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

Выход:

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)

Эта линия (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раскрывает лучший найденный решатель. Цифры в {}скобках - это индексы монет, которые нужно надевать на весы на каждом шаге.