Tienes nmonedas que pesan -1 o 1. Cada una está etiquetada de 0an-1 para que pueda distinguir las monedas. También tiene un dispositivo de pesaje (mágico). En el primer turno, puede colocar tantas monedas como desee en el dispositivo de pesaje que puede medir pesos negativos y positivos y le dirá exactamente cuánto pesan.

Sin embargo, hay algo realmente extraño en el dispositivo de pesaje. Si coloca monedas x_1, x_2, ..., x_jen el dispositivo la primera vez, la próxima vez que tenga que colocar monedas (x_1+1), (x_2+1) , ..., (x_j+1)en la báscula, con la excepción de que, por supuesto, no puede colocar una moneda con un número mayor n-1. No solo eso, por cada nuevo pesaje que elijas si también quieres poner monedas 0en la báscula.

Bajo esta regla, ¿cuál es el menor número de pesadas que siempre le dirá exactamente qué monedas pesan 1 y cuáles pesan -1?

Claramente, podría colocar una moneda 0en el dispositivo en el primer turno y luego tomaría nun peso exacto para resolver el problema.

Idiomas y bibliotecas

Puede usar cualquier idioma o biblioteca que desee (que no fue diseñada para este desafío). Sin embargo, me gustaría poder probar su código si es posible, así que si puede proporcionar instrucciones claras sobre cómo ejecutarlo en Ubuntu, sería muy apreciado.

Puntuación

Para un determinado, nsu puntaje se ndivide por la cantidad de pesajes que necesita en el peor de los casos. Las puntuaciones más altas son, por lo tanto, mejores. No hay aportes a este rompecabezas, pero su objetivo es encontrar uno npara el que pueda obtener la puntuación más alta.

Si hay un empate, la primera respuesta gana. En la situación extremadamente improbable en la que alguien encuentra la manera de obtener una puntuación infinita, esa persona gana de inmediato.

Tarea

Su tarea es simplemente escribir código que obtenga la puntuación más alta. Su código tendrá que elegir una n hábilmente y luego también optimizar el número de pesadas para eso n.

Entradas principales

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

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

Las soluciones de la propiedad Matrix X revisitada (o la Alegría de X) se pueden usar directamente como soluciones a este problema. Por ejemplo, la solución de 31 filas 15 columnas:

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 

la fila N representa qué monedas coloca en la báscula para la medición N. Cualquiera que sea el resultado de la ponderación que obtenga, obviamente hay un conjunto de valores de monedas que le dan ese peso. Si también hay otra combinación (la solución no es única) considere cómo difieren. Debe reemplazar un conjunto de ponderación 1de monedas por ponderación de monedas -1. Esto proporciona un conjunto de columnas que corresponden a ese giro. También hay un conjunto de ponderaciones de monedas por las -1que reemplaza 1. Ese es otro conjunto de columnas. Debido a que las mediciones no cambian entre las dos soluciones, eso significa que las sumas de columna de los dos conjuntos deben ser las mismas. Pero las soluciones a la propiedad Matrix X revisited (o la alegría de X) son exactamente estas matrices donde tales conjuntos de columnas no existen, por lo que no hay duplicados y cada solución es única.

Cada conjunto real de mediciones puede ser descrito por alguna 0/1matriz. Pero incluso si algunos conjuntos de columnas suman los mismos vectores, podría ser que los signos de los valores de monedas de la solución candidata no se correspondan exactamente con dicho conjunto. Entonces no sé si las matrices como la anterior son óptimas. Pero al menos proporcionan un límite inferior. Entonces, la posibilidad de que se puedan hacer 31 monedas en menos de 15 mediciones aún está abierta.

Tenga en cuenta que esto solo es cierto para una estrategia no fija donde su decisión de poner monedas 0en la balanza depende del resultado de las ponderaciones anteriores. De lo contrario, tendrá soluciones donde los signos de las monedas se corresponden con los conjuntos que tienen la misma suma de columnas.

Python 2, puntaje = 1.0

Este es el puntaje fácil, en caso de que nadie encuentre un puntaje mejor (dudoso). npesajes para cada uno 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)

Importé antigravitypara que el programa pueda funcionar con pesos negativos.

Puntuación = 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);
        }
    }
}

Guardar como LembikWeighingOptimisation.java, compilar como javac LembikWeighingOptimisation.java, ejecutar como java LembikWeighingOptimisation.

Muchas gracias a Mitch Schwartz por señalar un error en la primera versión del rechazo rápido.

Esto utiliza algunas técnicas bastante básicas que no puedo justificar rigurosamente. Es una fuerza bruta, pero solo para comenzar operaciones de pesaje que usan como máximo la mitad de las monedas: las secuencias que usan más de la mitad de las monedas no son directamente transferibles a los pesajes complementarios (porque no sabemos el peso total), pero en un nivel ondulado a mano debería haber aproximadamente la misma cantidad de información. También itera a través de pesadas iniciales en orden de la cantidad de monedas involucradas, sobre la base de que de esa manera cubre pesadas dispersas (que con suerte brindan información sobre el extremo superior relativamente temprano) sin primero arrastrarse a través de un grupo que comienza con un subconjunto denso en El extremo inferior.

La MaskRangeclase es una mejora masiva en la versión anterior en términos de uso de memoria, y elimina el GC de ser un cuello de botella.

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, puntaje = 4/3 = 1.33… (N = 4) puntaje = 1.4 (N = 7)

Actualización: implementado la búsqueda de fuerza bruta en el conjunto de solucionadores "estáticos", y obtuve un nuevo resultado

Creo que se puede mejorar aún más mediante la búsqueda de solucionadores dinámicos, que pueden utilizar los resultados de ponderación para futuras decisiones.

Aquí hay un código de Python que busca valores pequeños en todos los solucionadores estáticos n(estos solucionadores siempre pesan los mismos conjuntos de monedas, de ahí el nombre "estático") y determina el número de pasos en el peor de los casos simplemente comprobando que sus resultados de medición permiten solo una moneda coincidente establecido en todos los casos. Además, realiza un seguimiento del mejor puntaje encontrado hasta ahora y de los primeros solucionadores de ciruelas pasas que habían demostrado que definitivamente son peores que los que se encontraron antes. Esta fue una optimización importante, de lo contrario no podría esperar este resultado con n= 7. (Pero claramente todavía no está muy bien optimizado)

No dude en hacer preguntas si no está claro cómo 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()

La salida:

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 línea (StaticSolver({0,2}, {0,1,3}, {0,1,2,4}, {1,2,3,5}, {0,2,3,4,6}), 5), score = 7/5 = 1.4descubre el mejor solucionador encontrado. Los números entre {}llaves son los índices de monedas para colocar en el dispositivo de ponderación en cada paso.