טרול המתכנן
New member
טוב, מימשתי את השיטה שלי לקבל את כל האופציות מרשימת תוצאות ב-master-mind. זה היה סיוט קומבינטורי ממדרגה ראשונה, והקוד נוראי בהתאם.
אם מישהו חושב שאפשר לעשות את זה יותר טוב... אני אשמח לשמוע
מבחינת סיבוכיות מקום - כיוון שכל הפונקציות מחזירות איטרטורים, אפשר להסתפק (בערך) במקום הדרוש לבניית סט תוצאות אחד (אם יש רשימת תוצאות ידועה - אפשר לבחור את זאת עם הכי הרבה "בול פגיעות").
from itertools import *
from collections import *
R = 10 # range
Result = namedtuple('Result', 'exact hit') # result of guess
r_set = set(xrange(R))
"""
the 'master-mind' function
"""
def f(guess,target):
s = set(xrange(len(guess)))
exact_indices = [i for i in s if guess == target]
t = [target for i in s if i not in exact_indices]
g = [guess for i in s if i not in exact_indices]
for j in xrange(len(g)):
if g[j] in t:
t[t.index(g[j])] = None
return Result(len(exact_indices),t.count(None))
"""
generate set of all options s.t f(guess,x) = result
"""
def bwoptions(guess,result):
if result.exact == 0: return woptions(guess, result.hit)
if result.hit == 0: return boptions(guess, result.exact)
return pure_bwoptions(guess,result)
def pure_bwoptions(guess,result):
s = set(xrange(len(guess)))
res = [None] * len(guess)
for exact_ind in combinations(s,result.exact):
for i in exact_ind:
res = guess
tmp = [guess for i in s if i not in exact_ind]
for c in woptions(tmp, result.hit):
for x,y in zip(s-set(exact_ind),c):
res[x] = y
yield res
"""
values not 'in guess'
"""
def _complement(guess):
return r_set - set(guess)
"""
helper
"""
def is_match(r,g, guess):
for x,y in zip(r,g):
if guess[x] == guess[y]: return True
return False
"""
(0,*)
only 'hit' results
"""
def woptions(guess, hits):
if hits == 0: return boptions(guess,0)
piter = []
s = set(xrange(len(guess)))
for r_ind in combinations(s,hits):
for p_ind in combinations(s,hits):
for g_ind in permutations(p_ind):
if is_match(r_ind,g_ind,guess): continue
legals = _complement([guess[k] for k in s - set(g_ind)])
res_iter = [legals - set([guess]) for i in s]
for i,j in zip(r_ind,g_ind):
res_iter = [guess[j]]
piter = chain(piter,product(*res_iter))
return piter
"""
(*,0)
only 'exact' results
"""
def boptions(guess, exacts):
s = set(xrange(len(guess)))
piter = (product(*combs) for combs in ([ [guess] if i in c else _complement([guess[j] for j in s - set(c)]) for i in s] for c in combinations(s,exacts)))
return chain(*(p for p in piter))
def read_nums():
return map(int, raw_input().split())
def get_target(N):
return [int(R * random()) for i in xrange(N)]
def get_guess():
print 'enter your guess:'
return read_nums()
def print_res(guess,result):
print guess, '==>', result
def get_options(guess,target):
res = f(guess,target)
print_res(guess,res)
return bwoptions(guess,res)
def print_options(options):
print 'your options:', options
def run_test(N):
target = get_target(N)
guess = get_guess()
options = set([tuple(p) for p in get_options(guess,target)])
while (len(options) > 1):
print 'you have', len(options), 'options...'
guess = get_guess()
if guess == []:
print_options(options)
continue
new_opts = set()
for p in get_options(guess,target):
if tuple(p) in options: new_opts.add(tuple(p))
options = new_opts
print 'yes!'
print 'you found:', options
print 'and the target is:', target
if __name__ == '__main__':
from random import *
run_test(4)