17
\$\begingroup\$

You have n coins which each weigh either -1 or 1. Each is labelled from 0 to n-1 so you can tell the coins apart. You have one (magic) weighing device as well. At the first turn you can put as many coins as you like on the weighing device which is able to measure both negative and positive weights and it will tell you exactly how much they weigh.

However, there is something really strange about the weighing device. If you put coins x_1, x_2, ..., x_j on the device the first time, then the next time you have to put coins (x_1+1), (x_2+1) , ..., (x_j+1) on the scale with the exception that you of course can't put on a coin numbered higher than n-1. Not only that, for every new weighing you get to choose if you also want to put coin 0 on the scale.

Under this rule, what is the smallest number of weighings that will always tell you exactly which coins weigh 1 and which weigh -1?

Clearly you could just put coin 0 on the device in the first turn and then it would take exactly n weighings to solve the problem.

Languages and libraries

You can use any language or library you like (that wasn't designed for this challenge). However, I would like to be able to test your code if possible so if you can provide clear instructions for how to run it in Ubuntu that would be very much appreciated.

Score

For a given n your score is n divided by the number of weighings you need in the worst case. Higher scores are therefore better. There is no input to this puzzle but your goal is to find an n for which you can get the highest score.

If there is a tie, the first answer wins. In the extremely unlikely situation where someone finds a way to get an infinite score, that person wins immediately.

Task

Your task is simply to write code that gets the highest score. Your code will have to both choose an n cleverly and then also optimize the number of weighings for that n.

Leading entries

  • 4/3 7/5 in Python by Sarge Borsch
  • 26/14 in Java by Peter Taylor
\$\endgroup\$
  • 8
    \$\begingroup\$ I'd love to get my hands on some anti-gravity coins. \$\endgroup\$ – mbomb007 Nov 4 '15 at 15:45
  • 2
    \$\begingroup\$ I have a solution that never uses the machine: Hold each coin and see which ones pull your hand up, and which pull your hand down. \$\endgroup\$ – Fund Monica's Lawsuit Nov 4 '15 at 20:24
  • 1
    \$\begingroup\$ Also, as a side note, it might be better to write "if you weigh coins a through b, then the next time you have to do a+1 through b+1" (maybe with an 'at least' thrown in too, and better formatting) instead of subscripts denoting the coin number. That makes it seem like it's some property or quantity of coin _, instead of the coin itself. \$\endgroup\$ – Fund Monica's Lawsuit Nov 4 '15 at 20:27
  • 1
    \$\begingroup\$ @mbomb007 At each weighing you can choose to weigh coin 0 as well as all the other coins you will be weighing. In other words, you have new choice to make for each weighing you do. \$\endgroup\$ – user9206 Nov 5 '15 at 9:48
  • 3
    \$\begingroup\$ @mbomb007 @QPaysTaxes Regarding the notation x_i: We can have for example a first weighing of (x_1, x_2, x_3) = (3, 2, 7), and then the second weighing can be either (4, 3, 8) or (0, 4, 3, 8). The coin labels need not be consecutive, and the index i in x_i does not refer to the label of the coin. \$\endgroup\$ – Mitch Schwartz Nov 5 '15 at 9:55
3
+100
\$\begingroup\$

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

The solutions of Matrix property X revisited (or the Joy of X) are directly usable as solutions to this problem. E.g. the solution of 31 rows 15 columns:

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 

row N represent which coins you put on the scale for measurement N. Whatever the results of the weighting you get, there is obviously some set of coin values that gives that weight. If there is another combination too (the solution is not unique) consider how they differ. You must replace a set of coins weighting 1 by coins weighting -1. This gives a set of columns that correspond to that flip. There is also set of coins weighting -1 that you replace by 1. That is another set of columns. Because the measurements do not change between the two solutions that means the column sums of the two sets must be the same. But the solutions to Matrix property X revisited (or the Joy of X) are exactly these matrices where such column sets do not exist, so there are no duplicates and each solution is unique.

Each actual set of measurements can be described by some 0/1 matrix. But even if some column sets sum to the same vectors it could be that signs of the candidate solution coin values do not exactly correspond to such a set. So I don't know if matrices such as the one above are optimal. But at least they provide a lower bound. So the possibility that 31 coins can be done in less that 15 measurements is still open.

Notice that this is only true for a non fixed strategy where your decision to put coin 0 on the scales depends on the result of the previous weightings. Otherwise you will have solutions where the signs of the coins correspond with the sets that have the same column sum.

\$\endgroup\$
  • \$\begingroup\$ The current world record :) \$\endgroup\$ – user9206 Nov 5 '16 at 17:23
  • \$\begingroup\$ How fast a computer do you estimate would be needed to get to 2? \$\endgroup\$ – user9206 Nov 9 '16 at 14:01
  • \$\begingroup\$ @Lembik I'm not convinced 2 is possible. I don't know why, but the current results suggest you can only approach 2 arbitrarily close without ever reaching it \$\endgroup\$ – Ton Hospel Nov 9 '16 at 14:55
  • \$\begingroup\$ Did you get a chance to verify the 25 by 50 circulant matrix I pasted which should give 2? 01011011100010111101000001100111110011010100011010 as the first row of a circulant matrix. \$\endgroup\$ – user9206 Nov 9 '16 at 15:03
  • \$\begingroup\$ I don't know how to even check that matrix without writing a dedicated program that will run for a long time \$\endgroup\$ – Ton Hospel Nov 9 '16 at 16:14
5
\$\begingroup\$

Python 2, score = 1.0

This is the easy score, in case nobody finds a better score (doubtful). n weighings for each 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)

I imported antigravity so the program can work with negative weights.

\$\endgroup\$
  • \$\begingroup\$ Very helpful. Thank you :) \$\endgroup\$ – user9206 Nov 4 '15 at 19:08
  • \$\begingroup\$ Importing antigravity is basically a no-op, right? \$\endgroup\$ – Sarge Borsch Nov 5 '15 at 14:27
  • \$\begingroup\$ @SargeBorsch For the purpose of this program, it is. But it does actually do something. \$\endgroup\$ – mbomb007 Nov 5 '15 at 17:21
5
\$\begingroup\$

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

Save as LembikWeighingOptimisation.java, compile as javac LembikWeighingOptimisation.java, run as java LembikWeighingOptimisation.

Many thanks to Mitch Schwartz for pointing out a bug in the first version of the quick-reject.

This uses some fairly basic techniques which I can't rigorously justify. It brute-forces, but only for starting weighing operations which use at most half of the coins: sequences which use more than half of the coins aren't directly transferable to the complementary weighings (because we don't know the total weight), but on a hand-wavy level there should be about the same amount of information. It also iterates through starting weighings in order of the number of coins involved, on the basis that that way it covers dispersed weighings (which hopefully give information about the top end relatively early) without first crawling through a bunch which start with a dense subset at the bottom end.

The MaskRange class is a massive improvement on the earlier version in terms of memory usage, and removes GC from being a bottleneck.

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  
\$\endgroup\$
  • \$\begingroup\$ Can you definitely not get 12/7? I am pretty sure that works. Also, how about 19/10? I thought my code gave me that once but I can't reproduce it now. \$\endgroup\$ – user9206 Nov 10 '15 at 15:04
  • \$\begingroup\$ @Lembik, I've listed 12/7, but the best I can do for 19 is 19/11. \$\endgroup\$ – Peter Taylor Nov 10 '15 at 15:13
  • \$\begingroup\$ Oh yes sorry. Is it possible your heuristic throws away some solutions? I am pretty sure 19/10 should work too. \$\endgroup\$ – user9206 Nov 10 '15 at 15:17
  • \$\begingroup\$ It's possible, yes, if the only solution has an initial weighing with more than half of the coins. I'd be mildly surprised, though. \$\endgroup\$ – Peter Taylor Nov 10 '15 at 15:26
  • \$\begingroup\$ Is it worth increasing the half threshold to slightly-more-than-half maybe just to see? \$\endgroup\$ – user9206 Nov 10 '15 at 15:32
2
\$\begingroup\$

Python 3, score = 4/3 = 1.33… (N = 4) score = 1.4 (N = 7)

Update: implemented brute-force search in "static" solvers set, and got a new result

I think it can be further improved by searching for dynamic solvers, which can use weighting results for further decisions.

Here is a Python code that searches through all static solvers for small n values (these solvers always weigh the same coin sets, hence "static" name) and determines their worst case number of steps by simply checking that their measurement results allow only one matching coin set in all cases. Also, it keeps track of best score found so far and early prunes solvers which had shown that they are definitely worse than those which were found before. This was an important optimization, otherwise I could not wait for this result with n = 7. (But it's clearly still not very well optimized)

Feel free to ask questions if it's not clear how it works…

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

The output:

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)

This line (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 uncovers the best solver found. The numbers in {} braces are the indices of coins to put on weighting device at each step.

\$\endgroup\$
  • 4
    \$\begingroup\$ P.S. I wrote this while the electricity source in my home was broken, so I had a laptop on battery power and no Internet connectivity, and I simply had no better things to do than to crack some puzzles. I guess I'd not bother if all was fine :D \$\endgroup\$ – Sarge Borsch Nov 5 '15 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy