Python 2 (run faster if run using Pypy)
Believed to almost always guess the correct pairing in 10 rounds or lower
My algorithm is taken from my answer for mastermind as my hobby (see in Ideone). The idea is to find the guess which minimize the number of possibilities left in the worst case. My algorithm below just brute force it, but to save time, it just pick random guess if the number of possibilities left is larger than RANDOM_THRESHOLD. You can play around with this parameter to speed things up or to see better performance.
The algorithm is quite slow, on average 10s for one run if run using Pypy (if using normal CPython interpreter it's around 30s) so I can't test it on the whole permutations. But the performance is quite good, after around 30 tests I haven't seen any instance where it can't find the correct pairing in 10 rounds or lower.
Anyway, if this is used in real life show, it has plenty of time before the next round (one week?) so this algorithm can be used in real life =D
So I think it's safe to assume that on average this will find the correct pairings in 10 guesses or lower.
Try it yourself. I might improve the speed in the next few days (EDIT: it seems difficult to further improve, so I'll just leave the code as is. I tried only doing random pick, but even at size=7, it fails in 3 of the 5040 cases, so I decided to keep the cleverer method). You can run it as:
pypy are_you_the_one.py 10
Or, if you just want to see how it works, input smaller number (so that it runs faster)
To run a full test (warning: it'll take very long for size > 7), put a negative number.
Full test for size=7 (completed in 2m 32s):
...
(6, 5, 4, 1, 3, 2, 0): 5 guesses
(6, 5, 4, 2, 0, 1, 3): 5 guesses
(6, 5, 4, 2, 0, 3, 1): 4 guesses
(6, 5, 4, 2, 1, 0, 3): 5 guesses
(6, 5, 4, 2, 1, 3, 0): 6 guesses
(6, 5, 4, 2, 3, 0, 1): 6 guesses
(6, 5, 4, 2, 3, 1, 0): 6 guesses
(6, 5, 4, 3, 0, 1, 2): 6 guesses
(6, 5, 4, 3, 0, 2, 1): 3 guesses
(6, 5, 4, 3, 1, 0, 2): 7 guesses
(6, 5, 4, 3, 1, 2, 0): 7 guesses
(6, 5, 4, 3, 2, 0, 1): 4 guesses
(6, 5, 4, 3, 2, 1, 0): 7 guesses
Average count: 5.05
Max count : 7
Min count : 1
Num success : 5040
If RANDOM_THRESHOLD and CLEVER_THRESHOLD are both set to a very high value (like 50000), it'll force the algorithm to find the optimal guess that minimizes the number of possibilities in the worst case. This is very slow, but very powerful. For example, running it on size=6 asserts that it can find the correct pairings in maximum 5 rounds.
Although the average is higher compared to using the approximation (which is 4.11 rounds on average), but it always succeeds, even more with one round left to spare. This further strengthen our hypothesis that when size=10, it should almost always find the correct pairings in 10 rounds or less.
The result (completed in 3m 9s):
(5, 4, 2, 1, 0, 3): 5 guesses
(5, 4, 2, 1, 3, 0): 5 guesses
(5, 4, 2, 3, 0, 1): 4 guesses
(5, 4, 2, 3, 1, 0): 4 guesses
(5, 4, 3, 0, 1, 2): 5 guesses
(5, 4, 3, 0, 2, 1): 5 guesses
(5, 4, 3, 1, 0, 2): 5 guesses
(5, 4, 3, 1, 2, 0): 5 guesses
(5, 4, 3, 2, 0, 1): 5 guesses
(5, 4, 3, 2, 1, 0): 5 guesses
Average count: 4.41
Max count : 5
Min count : 1
Num success : 720
The code.
from itertools import permutations, combinations
import random, sys
from collections import Counter
INTERACTIVE = False
ORIG_PERMS = []
RANDOM_THRESHOLD = 100
CLEVER_THRESHOLD = 0
class Unbuffered():
def __init__(self, stream):
self.stream = stream
def write(self, data):
self.stream.write(data)
self.stream.flush()
def __getattr__(self, attr):
self.stream.getattr(attr)
sys.stdout = Unbuffered(sys.stdout)
def init(size):
global ORIG_PERMS
ORIG_PERMS = list(permutations(range(size)))
def evaluate(solution, guess):
if len(guess) == len(solution):
cor = 0
for sol, gss in zip(solution, guess):
if sol == gss:
cor += 1
return cor
else:
return 1 if solution[guess[0]] == guess[1] else 0
def remove_perms(perms, evaluation, guess):
return [perm for perm in perms if evaluate(perm, guess)==evaluation]
def guess_one(possible_perms, guessed_all, count):
if count == 1:
return (0,0)
pairs = Counter()
for perm in possible_perms:
for pair in enumerate(perm):
pairs[pair] += 1
perm_cnt = len(possible_perms)
return sorted(pairs.items(), key=lambda x: (abs(perm_cnt-x[1]) if x[1]<perm_cnt else perm_cnt,x[0]) )[0][0]
def guess_all(possible_perms, guessed_all, count):
size = len(possible_perms[0])
if count == 1:
fact = 1
for i in range(2, size):
fact *= i
if len(possible_perms) == fact:
return tuple(range(size))
else:
return tuple([1,0]+range(2,size))
if len(possible_perms) == 1:
return possible_perms[0]
if count < size and len(possible_perms) > RANDOM_THRESHOLD:
return possible_perms[random.randint(0, len(possible_perms)-1)]
elif count == size or len(possible_perms) > CLEVER_THRESHOLD:
(_, next_guess) = min((max(((len(remove_perms(possible_perms, evaluation, next_guess)), next_guess) for evaluation in range(len(next_guess))), key=lambda x: x[0])
for next_guess in possible_perms if next_guess not in guessed_all), key=lambda x: x[0])
return next_guess
else:
(_, next_guess) = min((max(((len(remove_perms(possible_perms, evaluation, next_guess)), next_guess) for evaluation in range(len(next_guess))), key=lambda x: x[0])
for next_guess in ORIG_PERMS if next_guess not in guessed_all), key=lambda x: x[0])
return next_guess
def main(size=4):
if size < 0:
size = -size
init(size)
counts = []
for solution in ORIG_PERMS:
count = run_one(solution, False)
counts.append(count)
print '%s: %d guesses' % (solution, count)
sum_count = float(sum(counts))
print 'Average count: %.2f' % (sum_count/len(counts))
print 'Max count : %d' % max(counts)
print 'Min count : %d' % min(counts)
print 'Num success : %d' % sum(1 for count in counts if count <= size)
else:
init(size)
solution = ORIG_PERMS[random.randint(0,len(ORIG_PERMS)-1)]
run_one(solution, True)
def run_one(solution, should_print):
if should_print:
print solution
size = len(solution)
cur_guess = None
possible_perms = list(ORIG_PERMS)
count = 0
guessed_one = []
guessed_all = []
while True:
count += 1
# Round A, guess one pair
if should_print:
print 'Round %dA' % count
if should_print:
print 'Num of possibilities: %d' % len(possible_perms)
cur_guess = guess_one(possible_perms, guessed_all, count)
if should_print:
print 'Guess: %s' % str(cur_guess)
if INTERACTIVE:
evaluation = int(raw_input('Number of correct pairs: '))
else:
evaluation = evaluate(solution, cur_guess)
if should_print:
print 'Evaluation: %s' % str(evaluation)
possible_perms = remove_perms(possible_perms, evaluation, cur_guess)
# Round B, guess all pairs
if should_print:
print 'Round %dB' % count
print 'Num of possibilities: %d' % len(possible_perms)
cur_guess = guess_all(possible_perms, guessed_all, count)
if should_print:
print 'Guess: %s' % str(cur_guess)
guessed_all.append(cur_guess)
if INTERACTIVE:
evaluation = int(raw_input('Number of correct pairs: '))
else:
evaluation = evaluate(solution, cur_guess)
if should_print: print 'Evaluation: %s' % str(evaluation)
if evaluation == size:
if should_print:
print 'Found %s in %d guesses' % (str(cur_guess), count)
else:
return count
break
possible_perms = remove_perms(possible_perms, evaluation, cur_guess)
if __name__=='__main__':
size = 4
if len(sys.argv) >= 2:
size = int(sys.argv[1])
if len(sys.argv) >= 3:
INTERACTIVE = bool(int(sys.argv[2]))
main(size)
