Você tem nmoedas cujo peso é -1 ou 1. Cada uma é rotulada de 0a n-1para que você possa diferenciá-las. Você também tem um dispositivo de pesagem (mágico). No primeiro turno, você pode colocar quantas moedas quiser no dispositivo de pesagem, capaz de medir tanto pesos negativos quanto positivos, e ele informará exatamente quanto pesam.

No entanto, há algo realmente estranho no dispositivo de pesagem. Se você colocar moedas x_1, x_2, ..., x_jno dispositivo pela primeira vez, na próxima vez em que tiver que colocar moedas (x_1+1), (x_2+1) , ..., (x_j+1)na balança, com a exceção de que você obviamente não poderá colocar uma moeda com número maior que n-1. Não é só isso: para cada nova pesagem você escolhe se também deseja colocar moedas 0na balança.

Sob essa regra, qual é o menor número de pesagens que sempre informará exatamente quais moedas pesam 1 e quais pesam -1?

Claramente, você poderia simplesmente colocar moedas 0no dispositivo na primeira curva e depois seriam necessárias npesagens exatas para resolver o problema.

Línguas e bibliotecas

Você pode usar qualquer idioma ou biblioteca que desejar (que não foi projetada para este desafio). No entanto, eu gostaria de poder testar seu código, se possível, para que você possa fornecer instruções claras sobre como executá-lo no Ubuntu que seriam muito apreciadas.

Ponto

Para um dado, nsua pontuação é ndividida pelo número de pesagens necessárias no pior caso. Pontuações mais altas são, portanto, melhores. Não há entrada para esse quebra-cabeça, mas seu objetivo é encontrar um npara o qual você possa obter a maior pontuação.

Se houver um empate, a primeira resposta vence. Na situação extremamente improvável em que alguém encontra uma maneira de obter uma pontuação infinita, essa pessoa vence imediatamente.

Tarefa

Sua tarefa é simplesmente escrever um código que obtenha a maior pontuação. Seu código terá que escolher an inteligente e também otimizar o número de pesagens para isso n.

Entradas principais

• 4/3 7/5 em Python por Sarge Borsch
• 26/14 em Java por Peter Taylor

C ++, pontuação 23/12 25/13 27/14 28/14 = 2 31/15

As soluções da propriedade Matrix X revisitadas (ou a Alegria de X) são diretamente utilizáveis ​​como soluções para esse problema. Por exemplo, a solução de 31 linhas e 15 colunas:

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 

a linha N representa quais moedas você coloca na balança para a medição N. Quaisquer que sejam os resultados da ponderação obtida, obviamente existe um conjunto de valores de moedas que dão esse peso. Se houver outra combinação também (a solução não é única), considere como elas diferem. Você deve substituir um conjunto de ponderação 1de moedas por ponderação de moedas -1. Isso fornece um conjunto de colunas que correspondem a esse flip. Também há um conjunto de moedas -1que você substitui 1. Esse é outro conjunto de colunas. Como as medições não mudam entre as duas soluções, isso significa que a soma das colunas dos dois conjuntos deve ser a mesma. Mas as soluções para a propriedade Matrix X revisitadas (ou a Alegria de X) são exatamente essas matrizes em que esses conjuntos de colunas não existem; portanto, não há duplicatas e cada solução é única.

Cada conjunto real de medições pode ser descrito por alguma 0/1matriz. Porém, mesmo que alguns conjuntos de colunas somam os mesmos vetores, pode ser que os sinais dos valores das moedas da solução candidata não correspondam exatamente a esse conjunto. Portanto, não sei se matrizes como a acima são ótimas. Mas pelo menos eles fornecem um limite inferior. Portanto, a possibilidade de 31 moedas poderem ser feitas em menos de 15 medições ainda está aberta.

Observe que isso só é verdade para uma estratégia não fixa em que sua decisão de colocar moedas 0na balança depende do resultado das ponderações anteriores. Caso contrário, você terá soluções em que os sinais das moedas correspondem aos conjuntos que possuem a mesma soma da coluna.

Python 2, pontuação = 1,0

Essa é a pontuação mais fácil, caso ninguém encontre uma pontuação melhor (duvidosa). npesagens para cada um 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)

Eu importei antigravitypara que o programa possa trabalhar com pesos negativos.

Pontuação = 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);
        }
    }
}

Salvar como LembikWeighingOptimisation.java, compilar como javac LembikWeighingOptimisation.java, executar como java LembikWeighingOptimisation.

Muito obrigado a Mitch Schwartz por apontar um bug na primeira versão do quick-rejeitar.

Isso usa algumas técnicas bastante básicas que não posso justificar rigorosamente. Forças brutas, mas apenas para iniciar operações de pesagem que usam no máximo metade das moedas: seqüências que usam mais da metade das moedas não são diretamente transferíveis para as pesagens complementares (porque não sabemos o peso total), mas em um nível ondulado, deve haver aproximadamente a mesma quantidade de informação. Ele também itera através do início das pesagens na ordem do número de moedas envolvidas, com base nessa maneira que cobre as pesagens dispersas (que esperamos fornecer informações sobre a extremidade superior relativamente cedo) sem primeiro rastejar por um cacho que começa com um subconjunto denso em a extremidade inferior.

A MaskRangeclasse é uma grande melhoria na versão anterior em termos de uso de memória e evita que o GC seja um gargalo.

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, pontuação = 4/3 = 1,33… (N = 4) pontuação = 1,4 (N = 7)

Atualização: implementou a pesquisa de força bruta no conjunto de solucionadores "estáticos" e obteve um novo resultado

Eu acho que pode ser melhorado ainda mais, procurando solucionadores dinâmicos, que podem usar os resultados de ponderação para outras decisões.

Aqui está um código Python que pesquisa todos os solucionadores estáticos em busca de valores pequenos n (esses sempre pesam os mesmos conjuntos de moedas, portanto, o nome "estático") e determina o número de etapas do pior caso, simplesmente verificando se seus resultados de medição permitem apenas uma moeda correspondente definido em todos os casos. Além disso, ele registra a melhor pontuação encontrada até o momento e solucionadores de ameixas precoces, que mostraram que são definitivamente piores do que os encontrados anteriormente. Essa foi uma otimização importante, caso contrário, eu não poderia esperar por esse resultado com n= 7. (Mas claramente ainda não está muito otimizado)

Sinta-se à vontade para fazer perguntas se não estiver claro como isso funciona…

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

A saída:

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)

Esta linha (StaticSolver({0,2}, {0,1,3}, {0,1,2,4}, {1,2,3,5}, {0,2,3,4,6}), 5), score = 7/5 = 1.4descobre o melhor solucionador encontrado. Os números entre {}chaves são os índices de moedas para colocar no dispositivo de ponderação a cada passo.