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.
8I'd love to get my hands on some anti-gravity coins. – mbomb007 – 2015-11-04T15:45:21.170
@mbomb007 Just fill some balloons with helium :) – None – 2015-11-04T19:08:16.707
2I 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. – Fund Monica's Lawsuit – 2015-11-04T20:24:50.520
1Also, 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. – Fund Monica's Lawsuit – 2015-11-04T20:27:24.967
@QPaysTaxes Your first solution would count as n weighings with a score of 1. – None – 2015-11-04T20:42:10.970
@Lembik Aw, way to kill the fun :( (but yeah, I figured.) – Fund Monica's Lawsuit – 2015-11-04T20:43:57.763
Just to be sure, can you explain for every new weighing you get to choose if you want to put coin 0 on the scale.? Does this mean that if I choose to weigh two at once, I can weigh
(x_0, x_1, x_2), (x_2, x_3), ... (x_0?, x_j-1, x_j)
, aka some of them withx_0
? – mbomb007 – 2015-11-04T21:57:43.677... or if I choose to weigh 2 at a time from
x_3
tox_8
, must they either all or none be weighed withx_0
on the scale? – mbomb007 – 2015-11-04T22:19:38.0631@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. – None – 2015-11-05T09:48:22.780
3@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 indexi
inx_i
does not refer to the label of the coin. – Mitch Schwartz – 2015-11-05T09:55:00.250Does the task define a standard way of testing solutions? – Display Name – 2015-11-05T10:41:30.107
@SargeBorsch It doesn't. I think you can do it in 3^{n/2} time fairly easily. There may be a faster way of course. – None – 2015-11-05T12:23:59.657
I wrote some new code and got 1.4 score (was 1.33…) – Display Name – 2015-11-05T14:17:56.910
btw I think that part of my code could be extracted and used to test any other solutions, but I'm too lazy to do it myself right now. – Display Name – 2015-11-05T15:35:14.820
1@MitchSchwartz Oh. Okay. The OP really needed some examples, because the wording was terribly vague. After looking at your answer, I understand. – mbomb007 – 2015-11-05T17:26:03.650