Anda memiliki nkoin yang masing-masing berbobot -1 atau 1. Masing-masing diberi label dari 0hingga n-1sehingga Anda dapat membedakan koin tersebut. Anda memiliki satu alat penimbang (ajaib) juga. Pada belokan pertama Anda dapat menaruh koin sebanyak yang Anda suka di alat penimbang yang dapat mengukur bobot negatif dan positif dan itu akan memberi tahu Anda berapa beratnya.

Namun, ada sesuatu yang sangat aneh dengan alat penimbang ini. Jika Anda meletakkan koin x_1, x_2, ..., x_jpada perangkat pertama kali, maka pada saat berikutnya Anda harus meletakkan koin (x_1+1), (x_2+1) , ..., (x_j+1)pada skala dengan pengecualian bahwa Anda tentu saja tidak dapat memakai koin yang bernomor lebih tinggi dari n-1. Tidak hanya itu, untuk setiap penimbangan baru Anda bisa memilih jika Anda juga ingin menempatkan koin 0pada skala.

Di bawah aturan ini, berapakah jumlah penimbangan terkecil yang akan selalu memberi tahu Anda dengan tepat koin mana yang berbobot 1 dan yang berbobot -1?

Jelas Anda hanya bisa meletakkan koin 0pada perangkat di belokan pertama dan kemudian akan benar-benar nmenimbang untuk menyelesaikan masalah.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa atau pustaka yang Anda suka (yang tidak dirancang untuk tantangan ini). Namun, saya ingin dapat menguji kode Anda jika memungkinkan jadi jika Anda dapat memberikan instruksi yang jelas tentang cara menjalankannya di Ubuntu yang akan sangat dihargai.

Skor

Untuk yang diberikan nskor Anda ndibagi dengan jumlah penimbangan yang Anda butuhkan dalam kasus terburuk. Skor yang lebih tinggi karenanya lebih baik. Tidak ada input untuk teka-teki ini tetapi tujuan Anda adalah untuk menemukan nyang Anda bisa mendapatkan skor tertinggi.

Jika ada seri, jawaban pertama menang. Dalam situasi yang sangat tidak mungkin di mana seseorang menemukan cara untuk mendapatkan skor tanpa batas, orang itu segera menang.

Tugas

Tugas Anda hanyalah menulis kode yang mendapat skor tertinggi. Kode Anda harus memilih dan cerdas serta mengoptimalkan jumlah penimbangan untuk itu n.

Entri terkemuka

• 4/3 7/5 dalam Python oleh Sarge Borsch
• 26/14 di Jawa oleh Peter Taylor

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

Solusi Matrix properti X yang ditinjau kembali (atau Joy of X) langsung dapat digunakan sebagai solusi untuk masalah ini. Misalnya solusi 31 baris 15 kolom:

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 

baris N menunjukkan koin yang Anda masukkan pada skala untuk pengukuran N. Apa pun hasil pembobotan yang Anda dapatkan, jelas ada beberapa set nilai koin yang memberikan bobot itu. Jika ada kombinasi lain juga (solusinya tidak unik) pertimbangkan perbedaannya. Anda harus mengganti satu set koin yang berbobot 1dengan koin yang berbobot -1. Ini memberikan satu set kolom yang sesuai dengan flip itu. Ada juga serangkaian koin -1yang Anda ganti 1. Itu adalah kumpulan kolom lainnya. Karena pengukuran tidak berubah di antara dua solusi yang berarti jumlah kolom dari dua set harus sama. Tetapi solusi untuk properti Matrix X ditinjau kembali (atau Joy of X) persis matriks ini di mana set kolom seperti itu tidak ada, sehingga tidak ada duplikat dan setiap solusi unik.

Setiap set pengukuran aktual dapat dijelaskan oleh beberapa 0/1matriks. Tetapi bahkan jika beberapa kolom menetapkan penjumlahan ke vektor yang sama, bisa jadi tanda-tanda nilai solusi koin kandidat tidak persis sesuai dengan set tersebut. Jadi saya tidak tahu apakah matriks seperti di atas optimal. Tapi setidaknya mereka memberikan batas bawah. Jadi kemungkinan bahwa 31 koin dapat dilakukan dalam waktu kurang dari 15 pengukuran masih terbuka.

Perhatikan bahwa ini hanya berlaku untuk strategi tidak tetap di mana keputusan Anda untuk meletakkan koin 0pada timbangan tergantung pada hasil dari bobot sebelumnya. Kalau tidak, Anda akan memiliki solusi di mana tanda-tanda koin sesuai dengan set yang memiliki jumlah kolom yang sama.

Python 2, skor = 1.0

Ini adalah skor yang mudah, kalau-kalau tidak ada yang menemukan skor yang lebih baik (ragu-ragu). nberat masing-masing 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)

Saya mengimpor antigravityagar program dapat bekerja dengan bobot negatif.

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

Simpan sebagai LembikWeighingOptimisation.java, kompilasi sebagai javac LembikWeighingOptimisation.java, jalankan sebagai java LembikWeighingOptimisation.

Banyak terima kasih kepada Mitch Schwartz karena menunjukkan bug dalam versi pertama dari penolakan cepat.

Ini menggunakan beberapa teknik yang cukup mendasar yang saya tidak bisa membenarkan dengan ketat. Itu brute-force, tetapi hanya untuk memulai operasi penimbangan yang menggunakan paling banyak setengah dari koin: urutan yang menggunakan lebih dari setengah koin tidak secara langsung dapat ditransfer ke penimbangan komplementer (karena kita tidak tahu berat total), tetapi pada tingkat bergelombang tangan harus ada jumlah informasi yang sama. Hal ini juga beralih melalui penimbangan awal dalam urutan jumlah koin yang terlibat, atas dasar bahwa cara itu mencakup penimbangan yang tersebar (yang diharapkan memberikan informasi tentang ujung atas relatif awal) tanpa terlebih dahulu merangkak melalui sekelompok yang dimulai dengan subset padat di ujung bawah.

The MaskRangekelas perbaikan besar-besaran pada versi sebelumnya dalam hal penggunaan memori, dan menghapus GC dari menjadi hambatan.

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

Pembaruan: menerapkan pencarian brute-force di set "static" solver, dan mendapat hasil baru

Saya pikir itu bisa lebih ditingkatkan dengan mencari pemecah dinamis, yang dapat menggunakan hasil pembobotan untuk keputusan lebih lanjut.

Berikut adalah kode Python yang mencari melalui semua pemecah statis untuk nilai kecil n (pemecah ini selalu menimbang set koin yang sama, maka nama "statis") dan menentukan jumlah kasus terburuk dari langkah-langkah hanya dengan memeriksa bahwa hasil pengukuran mereka hanya memungkinkan satu koin yang cocok. diatur dalam semua kasus. Juga, itu melacak skor terbaik yang ditemukan sejauh ini dan pemecah plum awal yang telah menunjukkan bahwa mereka pasti lebih buruk daripada yang ditemukan sebelumnya. Ini adalah optimasi yang penting, jika tidak saya tidak bisa menunggu hasil ini dengan n= 7. (Tapi itu jelas masih belum dioptimalkan dengan sangat baik)

Jangan ragu untuk bertanya jika tidak jelas cara kerjanya ...

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

Hasil:

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)

Baris ini (StaticSolver({0,2}, {0,1,3}, {0,1,2,4}, {1,2,3,5}, {0,2,3,4,6}), 5), score = 7/5 = 1.4mengungkap pemecah terbaik yang ditemukan. Angka-angka dalam {}kawat gigi adalah indeks koin untuk diletakkan di alat pembobot pada setiap langkah.