Python 2 (uruchom szybciej, jeśli uruchamiasz za pomocą Pypy)
Uważa się, że prawie zawsze odgadnie się prawidłowe parowanie w 10 rundach lub niżej
Mój algorytm wzięty jest z mojej odpowiedzi dla mistrza jako hobby (patrz Ideone ). Chodzi o to, aby znaleźć przypuszczenie, które zminimalizuje liczbę możliwości pozostawionych w najgorszym przypadku. Mój algorytm poniżej brutalnie go zmusza, ale aby zaoszczędzić czas, po prostu losowo zgaduję, czy liczba pozostałych możliwości jest większa niż RANDOM_THRESHOLD. Możesz pobawić się tym parametrem, aby przyspieszyć lub zobaczyć lepszą wydajność.
Algorytm działa dość wolno, średnio 10 sekund na jeden cykl, jeśli jest uruchamiany przy użyciu Pypy (jeśli używa się normalnego interpretera CPython, to około 30 sekund), więc nie mogę go przetestować na całej permutacji. Ale wydajność jest całkiem dobra, po około 30 testach nie widziałem żadnego przypadku, w którym nie można znaleźć prawidłowej pary w 10 rundach lub niżej.
W każdym razie, jeśli używa się tego w prawdziwym życiu, ma dużo czasu przed następną rundą (tydzień?), Więc ten algorytm można wykorzystać w prawdziwym życiu = D
Myślę więc, że można bezpiecznie założyć, że średnio znajdzie to prawidłowe pary w 10 domysłach lub mniej.
Spróbuj sam. Mogę poprawić prędkość w ciągu najbliższych kilku dni (EDYCJA: wydaje się, że dalsza poprawa wydaje się trudna, więc po prostu zostawiam kod bez size=7zmian . Próbowałem tylko wybierać losowo, ale nawet przy nie udaje się to w 3 z 5040 przypadków , więc postanowiłem zachować lepszą metodę). Możesz uruchomić go jako:
pypy are_you_the_one.py 10
Lub, jeśli chcesz tylko zobaczyć, jak to działa, wprowadź mniejszą liczbę (aby działała szybciej)
Aby uruchomić pełny test (ostrzeżenie: zajmie to dużo czasu dla size> 7), wpisz liczbę ujemną.
Pełny test size=7(ukończony w 2m 32s):
...
(6, 5, 4, 1, 3, 2, 0): 5 domysłów
(6, 5, 4, 2, 0, 1, 3): 5 domysłów
(6, 5, 4, 2, 0, 3, 1): 4 domysły
(6, 5, 4, 2, 1, 0, 3): 5 domysłów
(6, 5, 4, 2, 1, 3, 0): 6 domysłów
(6, 5, 4, 2, 3, 0, 1): 6 domysłów
(6, 5, 4, 2, 3, 1, 0): 6 domysłów
(6, 5, 4, 3, 0, 1, 2): 6 domysłów
(6, 5, 4, 3, 0, 2, 1): 3 domysły
(6, 5, 4, 3, 1, 0, 2): 7 domysłów
(6, 5, 4, 3, 1, 2, 0): 7 domysłów
(6, 5, 4, 3, 2, 0, 1): 4 domysły
(6, 5, 4, 3, 2, 1, 0): 7 domysłów
Średnia liczba: 5,05
Maksymalna liczba: 7
Min. Liczba: 1
Num sukces: 5040
Jeśli RANDOM_THRESHOLDi CLEVER_THRESHOLDto zarówno zestaw do bardzo dużej wartości (np 50000), to będzie zmusić algorytm, aby znaleźć optymalne przypuszczenie, że minimalizuje liczbę możliwości w najgorszym wypadku. To jest bardzo wolne, ale bardzo potężne. Na przykład uruchomienie go na size=6upewnia się, że może znaleźć prawidłowe pary w maksymalnie 5 rundach.
Chociaż średnia jest wyższa w porównaniu do zastosowania przybliżenia (czyli średnio 4,11 rund), ale zawsze się udaje, tym bardziej, że jedna runda jest wolna. To dodatkowo wzmacnia naszą hipotezę, że kiedy size=10prawie zawsze powinno znaleźć prawidłowe pary w 10 rundach lub mniej.
Wynik (ukończony w 3m 9s):
(5, 4, 2, 1, 0, 3): 5 domysłów
(5, 4, 2, 1, 3, 0): 5 domysłów
(5, 4, 2, 3, 0, 1): 4 domysły
(5, 4, 2, 3, 1, 0): 4 domysły
(5, 4, 3, 0, 1, 2): 5 domysłów
(5, 4, 3, 0, 2, 1): 5 domysłów
(5, 4, 3, 1, 0, 2): 5 domysłów
(5, 4, 3, 1, 2, 0): 5 domysłów
(5, 4, 3, 2, 0, 1): 5 domysłów
(5, 4, 3, 2, 1, 0): 5 domysłów
Średnia liczba: 4,41
Maksymalna liczba: 5
Min. Liczba: 1
Num sukces: 720
Kod.
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)