Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

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

return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), coinsets)

class Position(object):
self.all_coinsets = all_coinsets
self.coins = coinset

def possible_coinsets(self):

def is_final(self):
possible_coinsets = self.possible_coinsets()
return (len(possible_coinsets) == 1) and possible_coinsets == 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):
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)
except ValueError:  # no successful solvers
continue
score = n / best
best_score = max(score, best_score)
print('{}, score = {}/{} = {}'.format(best, n, best, 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()

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

return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), coinsets)

class Position(object):
self.all_coinsets = all_coinsets
self.coins = coinset

def possible_coinsets(self):

def is_final(self):
possible_coinsets = self.possible_coinsets()
return (len(possible_coinsets) == 1) and possible_coinsets == 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):
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)
except ValueError:  # no successful solvers
continue
score = n / best
best_score = max(score, best_score)
print('{}, score = {}/{} = {}'.format(best, n, best, 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()

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

return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), coinsets)

class Position(object):
self.all_coinsets = all_coinsets
self.coins = coinset

def possible_coinsets(self):

def is_final(self):
possible_coinsets = self.possible_coinsets()
return (len(possible_coinsets) == 1) and possible_coinsets == 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):
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)
except ValueError:  # no successful solvers
continue
score = n / best
best_score = max(score, best_score)
print('{}, score = {}/{} = {}'.format(best, n, best, 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()

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

return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), coinsets)

class Position(object):
self.all_coinsets = all_coinsets
self.coins = coinset

def possible_coinsets(self):

def is_final(self):
possible_coinsets = self.possible_coinsets()
return (len(possible_coinsets) == 1) and possible_coinsets == 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):
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)
except ValueError:  # no successful solvers
continue
score = n / best
best_score = max(score, best_score)
print('{}, score = {}/{} = {}'.format(best, n, best, 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()

4 brute force search of static solvers

## Python 3,score = 4/3 = 1.33… (N = 4) score = 4/3 = 1.33…4 (N = 47)

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

I think it can be further improved by doing a deeper andsearching for dynamic bruteforce search (when the decision of whether to include 0th element will be based on previous measurement results — current solution simply checks with fixed indexes)solvers, but I was too impatient to post an answer :)which can use weighting results for further decisions.

Here is a Python code that makes 3 fixed measurementssearches through all static solvers for small ((1, 2), (0, 2, 3), (1, 3))n, and checks for all possible values (these solvers always weigh the same coin sets, hence "static" name) and determines their worst case number of steps by simply checking that these measurements indeedtheir measurement results allow only one matching coin combinationset 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)

#!/usr/bin/env python3
import itertools

Nfrom =functools 4import partial

all_possible_coinsets
def =get_all_possible_coinsets(n):
return tuple(itertools.product(*itertools.repeat((-1, 1), Nn)))

def weigh(coinscoinset, indexes_to_weigh):
return sum(map(lambdacoinset[x] for x: coins[x],in indexes_to_weigh))

return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), all_possible_coinsetscoinsets)

class Position(object):
self.all_coinsets = all_coinsets
self.coins = coinscoinset

def possible_coinsets(self):

def is_final(self):
possible_coinsets = self.possible_coinsets()
return (len(possible_coinsets) == 1) and possible_coinsets == 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 mainget_all_start_positions(coinsets):
printfor cs in coinsets:
yield Position(allcoinsets, 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):
return self.measurements[index]

def __str__(self, *args, **kwargs):
return 'StaticSolver({})'.format(', '.join(map(checklambda 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(Positionpartial(test_solver, all_possible_coinsetssolver=solver, max_steps=max_steps), start_positions))
yield (solver, max(test_results))
except FailedSolver:
continue

def checkall_measurement_starts(positionn):
Position   for i in range(1, n + 1):
m1 = position  yield from itertools.movecombinations(range(n), i)

def next_measurement(n, measurement, include_zero):
shifted = filter(lambda x: x < n, map(lambda x: x + 1, 2measurement))
if include_zero:
return tuple(itertools.movechain((0,), 2shifted))
else:
return tuple(shifted)

def make_measurement_sequence(n, 3start, 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.moveproduct(*itertools.repeat((True, False), max_steps - 1))
for c in continuations:
yield tuple(make_measurement_sequence(n, 3start, 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 m1map(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)
except ValueError:  # no successful solvers
continue
score = n / best
best_score = max(score, best_score)
print('{}, score = {}/{} = {}'.format(best, n, best, 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.

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

I think it can be further improved by doing a deeper and dynamic bruteforce search (when the decision of whether to include 0th element will be based on previous measurement results — current solution simply checks with fixed indexes), but I was too impatient to post an answer :)

Here is a Python code that makes 3 fixed measurements ((1, 2), (0, 2, 3), (1, 3)), and checks for all possible coin sets that these measurements indeed allow only one coin combination.

#!/usr/bin/env python3
import itertools

N = 4

all_possible_coinsets = tuple(itertools.product(*itertools.repeat((-1, 1), N)))

def weigh(coins, indexes_to_weigh):
return sum(map(lambda x: coins[x], indexes_to_weigh))

return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), all_possible_coinsets)

class Position(object):
self.coins = coins

def possible_coinsets(self):

def is_final(self):
possible_coinsets = self.possible_coinsets()
return (len(possible_coinsets) == 1) and possible_coinsets == self.coins

def move(self, measurement_indexes):
measure_result = (measurement_indexes, weigh(self.coins, measurement_indexes))

def main():
print(all(map(check, map(Position, all_possible_coinsets))))

def check(position: Position):
m1 = position.move((1, 2)).move((0, 2, 3)).move((1, 3))
return m1.is_final()

if __name__ == '__main__':
main()


## 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)

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

return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), coinsets)

class Position(object):
self.all_coinsets = all_coinsets
self.coins = coinset

def possible_coinsets(self):

def is_final(self):
possible_coinsets = self.possible_coinsets()
return (len(possible_coinsets) == 1) and possible_coinsets == 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):
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)
except ValueError:  # no successful solvers
continue
score = n / best
best_score = max(score, best_score)
print('{}, score = {}/{} = {}'.format(best, n, best, 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.

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

I think it can be further improved by doing a deeper and dynamic bruteforce search (when the decision of whether to include 0th element will be based on previous measurement results — current solution simply checks with fixed indexes), but I was too impatient to post an answer :)

Here is a Python code that makes 3 fixed measurements ((1, 2), (0, 2, 3), (1, 3)), and checks for all possible coin sets that these measurements indeed allow only one coin combination.

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

#!/usr/bin/env python3
import itertools

N = 4

all_possible_coinsets = tuple(itertools.product(*itertools.repeat((-1, 1), N)))

def weigh(coins, indexes_to_weigh):
return sum(map(lambda x: coins[x], indexes_to_weigh))

return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), all_possible_coinsets)

class Position(object):
self.coins = coins

def possible_coinsets(self):

def is_final(self):
possible_coinsets = self.possible_coinsets()
return (len(possible_coinsets) == 1) and possible_coinsets == self.coins

def move(self, measurement_indexes):
measure_result = (measurement_indexes, weigh(self.coins, measurement_indexes))

def main():
print(all(map(check, map(Position, all_possible_coinsets))))

def check(position: Position):
m1 = position.move((1, 2)).move((0, 2, 3)).move((1, 3))
return m1.is_final()

if __name__ == '__main__':
main()


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

I think it can be further improved by doing a deeper and dynamic bruteforce search (when the decision of whether to include 0th element will be based on previous measurement results — current solution simply checks with fixed indexes), but I was too impatient to post an answer :)

Here is a Python code that makes 3 fixed measurements ((1, 2), (0, 2, 3), (1, 3)), and checks for all possible coin sets that these measurements indeed allow only one coin combination.

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

import itertools

N = 4

all_possible_coinsets = tuple(itertools.product(*itertools.repeat((-1, 1), N)))

def weigh(coins, indexes_to_weigh):
return sum(map(lambda x: coins[x], indexes_to_weigh))

return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), all_possible_coinsets)

class Position(object):
self.coins = coins

def possible_coinsets(self):

def is_final(self):
possible_coinsets = self.possible_coinsets()
return (len(possible_coinsets) == 1) and possible_coinsets == self.coins

def move(self, measurement_indexes):
measure_result = (measurement_indexes, weigh(self.coins, measurement_indexes))

def main():
print(all(map(check, map(Position, all_possible_coinsets))))

def check(position: Position):
m1 = position.move((1, 2)).move((0, 2, 3)).move((1, 3))
return m1.is_final()

if __name__ == '__main__':
main()


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

I think it can be further improved by doing a deeper and dynamic bruteforce search (when the decision of whether to include 0th element will be based on previous measurement results — current solution simply checks with fixed indexes), but I was too impatient to post an answer :)

Here is a Python code that makes 3 fixed measurements ((1, 2), (0, 2, 3), (1, 3)), and checks for all possible coin sets that these measurements indeed allow only one coin combination.

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

#!/usr/bin/env python3
import itertools

N = 4

all_possible_coinsets = tuple(itertools.product(*itertools.repeat((-1, 1), N)))

def weigh(coins, indexes_to_weigh):
return sum(map(lambda x: coins[x], indexes_to_weigh))

return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), all_possible_coinsets)

class Position(object):
self.coins = coins

def possible_coinsets(self):

def is_final(self):
possible_coinsets = self.possible_coinsets()
return (len(possible_coinsets) == 1) and possible_coinsets == self.coins

def move(self, measurement_indexes):
measure_result = (measurement_indexes, weigh(self.coins, measurement_indexes))

def main():
print(all(map(check, map(Position, all_possible_coinsets))))

def check(position: Position):
m1 = position.move((1, 2)).move((0, 2, 3)).move((1, 3))
return m1.is_final()

if __name__ == '__main__':
main()

2 added 62 characters in body
1