Python大师

Question

我正在尝试用python-donaldknuth的算法在不超过5步的时间内实现代码破译。我已经检查了我的代码好几次了，它似乎遵循了如下算法：http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm

不过，我知道有些秘密需要7步甚至8步才能完成，比如[5,4,4,5]。在

代码如下：

# returns how many bulls and cows
def HowManyBc(guess,secret):
    invalid=max(guess)+1
    bulls=0
    cows=0
    r=0
    while r<4:
        if guess[r]==secret[r]:
            bulls=bulls+1
            secret[r]=invalid
            guess[r]=invalid
        r=r+1
    r=0
    while r<4:
        p=0
        while p<4:
            if guess[r]==secret[p] and guess[r]!=invalid:
                cows=cows+1
                secret[p]=invalid
                break
            p=p+1
        r=r+1          
    return [bulls,cows]

# sends every BC to its index in HMList
def Adjustment(BC1):
    if BC1==[0,0]:
        return 0
    elif BC1==[0,1]:
        return 1
    elif BC1==[0,2]:
        return 2
    elif BC1==[0,3]:
        return 3
    elif BC1==[0,4]:
        return 4
    elif BC1==[1,0]:
        return 5
    elif BC1==[1,1]:
        return 6
    elif BC1==[1,2]:
        return 7
    elif BC1==[1,3]:
        return 8
    elif BC1==[2,0]:
        return 9
    elif BC1==[2,1]:
        return 10
    elif BC1==[2,2]:
        return 11
    elif BC1==[3,0]:
        return 12
    elif BC1==[4,0]:
        return 13  
# returns positive's list minimum without including zeros    
def MinimumNozeros(List1):
    minimum=max(List1)+1
    for item in List1:
        if item!=0 and item<minimum:
            minimum=item
    return minimum

TempList=[[5, 4, 4, 5]]

for secret in TempList:
    guess=[0,0,1,1]
    BC=HowManyBc(guess[:],secret[:])
    counter=1
    optionList=[]
    allList=[]
    for i0 in range(0,6):
        for i1 in range(0,6):
            for i2 in range(0,6):
                for i3 in range(0,6):
                    optionList.append([i0,i1,i2,i3])
                    allList.append([i0,i1,i2,i3])
    while BC!=[4,0]:
        dummyList=[]
        for i0 in range(0,6):
            for i1 in range(0,6):
                for i2 in range(0,6):
                    for i3 in range(0,6):
                        opSecret=[i0,i1,i2,i3]
                        if HowManyBc(guess[:],opSecret[:])==BC:
                            dummyList.append(opSecret)
        List1=[item for item in optionList if item in dummyList]
        optionList=List1[:]
        nextGuess1=[]
        item1Max=0
        L1=optionList[:]
        L2=allList[:]
        for item1 in L1:
            ListBC=[]
            for item2 in L2:
                ListBC.append(HowManyBc(item1[:],item2[:]))
            HMList=[0]*14 # how many times every possible BC appeared
            for BC1 in ListBC:
                index=Adjustment(BC1)
                HMList[index]=HMList[index]+1
            m=MinimumNozeros(HMList[:])
            if m>item1Max:
                item1Max=m
                nextGuess1=item1[:]
        guess=nextGuess1[:]
        BC=HowManyBc(guess[:],secret[:])
        counter=counter+1

有人能帮忙吗？在

谢谢，迈克

Answer 1

Knuth的算法是：

1. 创建一组剩余的可能性（此时有1296个）。第一个猜测是aabb。在
2. 如果答案是彩色和白色的，去掉所有不给相同分数的可能性。在
3. 对于每个可能的猜测（不一定是在S中），计算每个可能的彩色/白色分数将从S中排除多少可能性。猜测的分数是这些值中最小的。用最高分数（minimax）猜猜。在
4. 回到第2步，直到正确为止。在

你的算法是：

1. 创建一组剩余的可能性（此时有1296个）。第一个猜测是aabb。在
2. 如果答案是彩色和白色的，去掉所有不给相同分数的可能性。在
3. 对于每个可能的猜测（必须在S中）计算从所有选项的集合中，对于每个可能的彩色/白色分数，将保留多少可能性。猜测的分数是这些值中最小的。用最高分数（minimax）猜猜。在
4. 回到第2步，直到正确为止。在

可以通过将循环更改为：

for secret in TempList:
    guess=[0,0,1,1]
    BC=HowManyBc(guess[:],secret[:])
    counter=1
    optionList=[]
    allList=[]
    for i0 in range(0,6):
        for i1 in range(0,6):
            for i2 in range(0,6):
                for i3 in range(0,6):
                    optionList.append([i0,i1,i2,i3])
                    allList.append([i0,i1,i2,i3])
    #while BC!=[4,0]:
    while len(optionList)>1:
        dummyList=[]
        for i0 in range(0,6):
            for i1 in range(0,6):
                for i2 in range(0,6):
                    for i3 in range(0,6):
                        opSecret=[i0,i1,i2,i3]
                        if HowManyBc(guess[:],opSecret[:])==BC:
                            dummyList.append(opSecret)
        List1=[item for item in optionList if item in dummyList]
        optionList=List1[:]
        nextGuess1=[]
        item1Max=0
        #L1=optionList[:]
        #L2=allList[:]
        L2=optionList[:]
        L1=allList[:]
        for item1 in L1: 
            ListBC=[]
            for item2 in L2: 
                ListBC.append(HowManyBc(item1[:],item2[:]))
            HMList=[0]*14 
            for BC1 in ListBC:
                index=Adjustment(BC1)
                HMList[index]=HMList[index]+1  
            #m=MinimumNozeros(HMList[:])
            m=len(L1)-max(HMList[:]) 
            if m>item1Max:
                item1Max=m
                nextGuess1=item1[:]
        guess=nextGuess1[:]
        BC=HowManyBc(guess[:],secret[:])
        counter=counter+1
print optionList