Improving efficiency of Project Euler 185 (16-place Mastermind)

This a solution for Project Euler Problem 185. It works fine for the example but slow for the problem statement. How can I improve its speed and efficiency?

```
import itertools
from collections import defaultdict
def mrange(start, stop, step=1):
i = start
while i < stop:
yield i
i += step
#produces the list of numbers
number= mrange(104,105)
newlist=[]
def combination(x,n):
if n==0:
temp=[]
for i in range(1,len(x)+1):
temp.extend(list(itertools.combinations(x,i)))
return temp
return list(itertools.combinations(x,n))

def combineDictTuple(dt):
d = {}
for item in dt:
d.update(item)
return d
def prob(a,n):
temp=[]
if n==0:
temp=number
#modchar is indexing the numbers eg:[{0: '9'}, {1: '0'}, {2: '3'}, {3: '4'}, {4: '2'}]
modchar=[{i: c} for i, c in enumerate(a)]
combos = combination(modchar,n)
newCombos = [combineDictTuple(dt) for dt in combos]
# newCombos gives combination of the indexes
#[{0: '9', 1: '0'}, {0: '9', 2: '3'}, {0: '9', 3: '4'}, {0: '9', 4: '2'}, {1: '0', 2: '3'}, {1: '0', 3: '4'}, {1: '0', 4: '2'}, {2: '3', 3: '4'}, {2: '3', 4: '2'}, {3: '4', 4: '2'}]
for j in number:
for i in newCombos:
index=i.keys()
val=i.values()
# print index,val
if n==0:
if all(str(j)[index[l]]==val[l] for l in range(0,len(val))):
if j in temp:
del temp[temp.index(j)]
break
else:

if all(str(j)[index[l]]==val[l] for l in range(0,len(val))):
temp.append(j)
break
return temp

val='''90342 ;2 correct
70794 ;0 correct
39458 ;2 correct
34109 ;1 correct
51545 ;2 correct
12531 ;1 correct'''
val=val.replace('correct','').replace(';','').split('\n')
for i in val:
i=i.split()
number=prob(

Expressiveness

• What does prob(a,n) mean? How about apply_constraint(guess, n_correct) instead?

• Why do you reinvent xrange() (Python 2) or range() (Python 3)?

• number is a global variable, which makes the code hard to follow.

• number is an iterable of numbers, but your constraints are given as characters, which makes comparisons awkward.

• temp is an uninformative name for a variable. It's especially bad when you return temp — that implies that it's not very temporary at all.

• Parsing the input is better done using a regular expression.

Strategy

Let \$p\$ be the number of positions (16 in the real problem, 5 in the test case).

Let \$g\$ be the number of guesses (22 in the real problem, 6 in the test case).

The outline of prob() is:

for j in number:
    for i in newCombos:
        …
        [… for l in range(len(newCombos.values()))]

number is \$O(10^p)\$ (the number of candidate solutions you initially generate).

newCombos has \$\left(\begin{array}{c}p\\c\end{array}\right) = \dfrac{p!}{c!\ (p - c)!}\$ combinations, each of which has \$c\$ values, where \$c\$ is the number of correct guesses within that constraint.

If we estimate that \$c = 3\$, then the complexity of your solution is \$O(10^p p^3g)\$ in time. The maximum space needed is the number candidates remaining after processing the first constraint, or \$O(\left(\begin{array}{c}p\\c\end{array}\right))\$.

I'm not sure that I analyzed the complexity completely correctly, but in any case those bounds are crazy. Your strategy of enumerating all the possibilities just doesn't scale. It's as if you were trying to solve a sudoku puzzle by generating all possible solutions first.

StackExchange Code Review Q#54138, answer score: 5