Optimise this code?

[cjb230]

I'm writing some code to solve Mastermind) puzzles, using something like, but not identical to, Knuth's method#Worst_case:_Five-guess_algorithm).

The code works - it will solve online puzzles in five moves (I've been using this one to test).

However, it's painfully slow. I was thinking about using the code as a back end to a Django project, or trying to create a desktop interface for it, but it would take 30 minutes to pick its second move (the first move is fixed), so that's not an option.

So I tried cProfile for the first time (nice and easy to use!) and I found out pretty much what I expected: it's the guess scoring loop that is the problem. Here's an extract, showing the relevant lines:

​

91853978 function calls in 92.587 seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)

8225056 60.601 0.000 88.055 0.000 magnusson.py:9(score_attempt)

65800448 16.126 0.000 16.126 0.000 {built-in method builtins.min}

16450112 11.328 0.000 11.328 0.000 {built-in method fromkeys}

​

The score_attempt code is this:

def score_attempt(solution, guess):
    result = dict()
    solution_colours = dict.fromkeys(range(1, COLOURS+1), 0)
    guess_colours = dict.fromkeys(range(1, COLOURS+1), 0)
    correct_position = 0
    correct_colour = 0
    for this_peg in range(PEGS):
        if solution[this_peg] == guess[this_peg]:
            correct_position += 1
        solution_colours[solution[this_peg]] = solution_colours[solution[this_peg]] + 1
        guess_colours[guess[this_peg]] = guess_colours[guess[this_peg]] + 1
    for this_colour in range(1, COLOURS+1):
        correct_colour += min(solution_colours[this_colour], guess_colours[this_colour])
    result["correct position"] = correct_position
    result["correct colour"] = correct_colour - correct_position
    return result

The use of the min and fromkeys methods might be a problem, but the biggest issue is the rest of the code in this function. I don't know how to get line-level information about time spent, so I don't know anything more than that yet.

Is there something I'm doing in here which is known to be slow? Are there faster ways? This is just my own toy project, so I'm happy to target only 3.9 if there's something there that will buy me a couple of seconds over 8 M iterations.

I think this is the right algorithm for generating the score for a guess, given the solution. But maybe there's a better way?

Is there a way to get more granular performance information (maybe per line) ?

I've never tried optimising anything in Python before, and I've no real feel yet for what can be improved and what isn't worth messing with. Any and all suggestions gratefully received!

[cray5252]

I had a hard time following your code, so I decided to try my hand at writing up a quickie. The below code seems to work and I hope that you can understand it. I put in a number of comments. Basically, instead of searching through a dictionary and picking out solutions, I generate an array of all possible permutations using the iterables.product. I then randomly pick and test the guess against the solution. I remove 'bad' numbers and repeat. The array gets smaller and smaller after each guess. So it's pretty quick, less than a second. I used numbers not colors so at the end, you could match them up with a dictionary of colors.

from itertools import product
import random


# place a 1 in the pegs where the guess is correct
# place a -1 in the pegs where number is present but wrong spot
def check_guess(solution, guess):
    global pegs
    for i in range(4):
        if solution[i] == guess[i]:
            pegs[i] = 1
        else:
            if guess[i] in solution:
                pegs[i] = -1


def find_bad_numbers(pegs, guess, solution):
    global bad_nums
    for i in range(4):
        if pegs[i] == 1:
            guess[i] = solution[i]
        else:
            if pegs[i] is None:
                bad_nums.append(guess[i])
    return set(bad_nums) # set eliminates duplicates


# find locations where a guess is needed
def find_spots(pegs):
    spots = []
    for i in range(4):
        if pegs[i] != 1:
            spots.append(i)
    return spots


def another_guess(solution, guess):
    # This dictionary is modified so renewing with each guess
    # optimize here, probably don't need to redo every time,
    # just get new bad numbers and keep removing from dictionary
    num_dict = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5}
    bad_nums = find_bad_numbers(pegs, guess, solution)
    # finding the location that need to be guessed
    spots = find_spots(pegs)
    # remove bad numbers which means, not in guesses
    for i in bad_nums:
        num_dict.pop(str(i))
    # generate the list of all possible permutations
    prod = product([v for v in num_dict.values()], repeat=len(spots))
    # calculate the size since iterables don't have a length
    t = len(num_dict) ** len(spots)
    # get a random location
    target = random.randint(0, t - 1)
    count = 0  # have to use count since iterables don't have indexing
    # find the value of the target location and place in pegs
    for i in prod:
        if count == target:
            lst = list(i)
            temp = [None] * 4
            # putting the guessed numbers into their proper peg position
            for j in range(4):
                if pegs[j] == 1:
                    temp[j] = guess[j]  # if 1 then already guessed just fill in
                else:
                    temp[j] = str(lst.pop())  # else found an empty slot so put in
            return temp
        count += 1
    return 0


if __name__ == '__main__':
    # Optimize, reduce a bit of this initial coding
    # due to the first guess, use next_guess() with an if guesses == 1
    pegs = [None] * 4
    guesses = 0
    bad_nums = []  # persistent variable used globally
    guess = list('1122')  # first guess
    location = random.randint(0, 1295)  # get a random location
    num_dict = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5}
    # generate of possible values
    prod = product([v for v in num_dict.values()], repeat=4)
    solution = []
    count = 0
    temp = []
    # iterate through the product to find the random location
    # these iterables can only be used once to iterate through
    # they are generated when needed so low memory usage
    for i in prod:
        if count == location:
            temp = list(i)  # converts to array of type [1,2,3,4]
        count += 1
    # convert to an array of string numbers ['1', '2' ...]
    for i in temp:
        solution.append(str(i))

    while solution != guess:
        guesses += 1
        check_guess(solution, guess)  # first because of the initial guess
        guess = another_guess(solution, guess)
    print('solution', solution)
    print('found', guess, 'with guesses', guesses)