Vous avez des npièces qui pèsent chacune -1 ou 1. Chacune est étiquetée de 0à n-1afin que vous puissiez distinguer les pièces. Vous avez également un appareil de pesée (magique). Au premier tour, vous pouvez mettre autant de pièces que vous le souhaitez sur l'appareil de pesage qui est capable de mesurer les poids négatifs et positifs et il vous dira exactement combien ils pèsent.

Cependant, le dispositif de pesage a quelque chose de vraiment étrange. Si vous mettez des pièces x_1, x_2, ..., x_jsur l'appareil la première fois, la prochaine fois, vous devrez placer des pièces (x_1+1), (x_2+1) , ..., (x_j+1)sur la balance, à l'exception que vous ne pouvez bien sûr pas mettre une pièce numérotée plus haut que n-1. Non seulement cela, pour chaque nouvelle pesée, vous pouvez choisir si vous souhaitez également mettre des pièces 0sur la balance.

Selon cette règle, quel est le plus petit nombre de pesées qui vous dira toujours exactement quelles pièces pèsent 1 et lesquelles pèsent -1?

De toute évidence, vous pourriez simplement mettre de la monnaie 0sur l'appareil au premier tour, puis il faudrait exactement des npesées pour résoudre le problème.

Langues et bibliothèques

Vous pouvez utiliser n'importe quelle langue ou bibliothèque que vous aimez (qui n'a pas été conçue pour ce défi). Cependant, j'aimerais pouvoir tester votre code si possible, donc si vous pouvez fournir des instructions claires sur la façon de l'exécuter dans Ubuntu, ce serait très apprécié.

But

Pour une donnée, nvotre score est ndivisé par le nombre de pesées dont vous avez besoin dans le pire des cas. Des scores plus élevés sont donc meilleurs. Il n'y a aucune entrée dans ce puzzle, mais votre objectif est de trouver celui npour lequel vous pouvez obtenir le meilleur score.

S'il y a égalité, la première réponse l'emporte. Dans la situation extrêmement improbable où quelqu'un trouve un moyen d'obtenir un score infini, cette personne gagne immédiatement.

Tâche

Votre tâche consiste simplement à écrire du code qui obtient le meilleur score. Votre code devra à la fois choisir astucieusement un n puis optimiser également le nombre de pesées pour cela n.

Entrées principales

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

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

Les solutions de la propriété Matrix X revisitées (ou la joie de X) sont directement utilisables comme solutions à ce problème. Par exemple, la solution de 31 lignes 15 colonnes:

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 ligne N représente les pièces que vous mettez sur l'échelle pour la mesure N. Quels que soient les résultats de la pondération que vous obtenez, il existe évidemment un ensemble de valeurs de pièces qui donne ce poids. S'il existe également une autre combinaison (la solution n'est pas unique), considérez en quoi elles diffèrent. Vous devez remplacer un ensemble de pondération des pièces 1par une pondération des pièces -1. Cela donne un ensemble de colonnes qui correspondent à ce flip. Il existe également un ensemble de pondération des pièces -1que vous remplacez 1. C'est un autre ensemble de colonnes. Parce que les mesures ne changent pas entre les deux solutions, cela signifie que les sommes des colonnes des deux ensembles doivent être les mêmes. Mais les solutions à la propriété Matrix X revisitées (ou la joie de X) sont exactement ces matrices où de tels ensembles de colonnes n'existent pas, il n'y a donc pas de doublons et chaque solution est unique.

Chaque ensemble réel de mesures peut être décrit par une 0/1matrice. Mais même si certains ensembles de colonnes totalisent les mêmes vecteurs, il se pourrait que les signes des valeurs des pièces de la solution candidate ne correspondent pas exactement à un tel ensemble. Je ne sais donc pas si des matrices telles que celle ci-dessus sont optimales. Mais au moins, ils fournissent une limite inférieure. Ainsi, la possibilité de faire 31 pièces en moins de 15 mesures est toujours ouverte.

Notez que cela n'est vrai que pour une stratégie non fixe où votre décision de placer des pièces 0sur la balance dépend du résultat des pondérations précédentes. Sinon, vous aurez des solutions où les signes des pièces correspondent aux ensembles qui ont la même somme de colonne.

Python 2, score = 1,0

C'est le score facile, au cas où personne ne trouverait un meilleur score (douteux). npesées pour chacun 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)

J'ai importé antigravitypour que le programme fonctionne avec des poids négatifs.

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

Enregistrer sous LembikWeighingOptimisation.java, compiler sous javac LembikWeighingOptimisation.java, exécuter sous java LembikWeighingOptimisation.

Un grand merci à Mitch Schwartz pour avoir signalé un bogue dans la première version du rejet rapide.

Cela utilise des techniques assez basiques que je ne peux pas justifier rigoureusement. Il force brutalement, mais uniquement pour démarrer des opérations de pesage qui utilisent au plus la moitié des pièces: les séquences qui utilisent plus de la moitié des pièces ne sont pas directement transférables aux pesées complémentaires (car on ne connaît pas le poids total), mais à un niveau ondulé, il devrait y avoir à peu près la même quantité d'informations. Il réitère également les pesées de départ en fonction du nombre de pièces impliquées, en partant du principe qu'il couvre les pesées dispersées (qui, espérons-le, donnent des informations sur l'extrémité supérieure relativement tôt) sans d'abord parcourir un groupe qui commence par un sous-ensemble dense à l'extrémité inférieure.

La MaskRangeclasse est une amélioration massive par rapport à la version précédente en termes d'utilisation de la mémoire, et supprime le GC d'être un goulot d'étranglement.

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

Mise à jour: implémentation de la recherche par force brute dans un ensemble de solveurs "statiques" et obtention d'un nouveau résultat

Je pense qu'il peut être encore amélioré en recherchant des solveurs dynamiques, qui peuvent utiliser les résultats de pondération pour d'autres décisions.

Voici un code Python qui recherche dans tous les solveurs statiques de petites n valeurs (ces solveurs pèsent toujours les mêmes ensembles de pièces, d'où le nom "statique") et détermine leur pire nombre d'étapes en vérifiant simplement que leurs résultats de mesure n'autorisent qu'une seule pièce correspondante fixé dans tous les cas. En outre, il garde la trace du meilleur score trouvé jusqu'à présent et des premiers solveurs de pruneaux qui avaient montré qu'ils étaient nettement pires que ceux qui avaient été trouvés auparavant. Ce fut une optimisation importante, sinon je ne pouvais pas attendre ce résultat avec n= 7. (Mais il est clair qu'il n'est toujours pas très bien optimisé)

N'hésitez pas à poser des questions si vous ne savez pas comment cela fonctionne…

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

Le résultat:

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)

Cette ligne (StaticSolver({0,2}, {0,1,3}, {0,1,2,4}, {1,2,3,5}, {0,2,3,4,6}), 5), score = 7/5 = 1.4découvre le meilleur solveur trouvé. Les chiffres entre {}accolades sont les indices des pièces à mettre sur le dispositif de pondération à chaque étape.