# 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(10**4,10**5)
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(i[0],int(i[1]))

print number


How the function works:

1. Generate numbers using mrange()
2. In prob method first I find the index of the each number in problem statement, e.g. 90342
3. That produces [{0: '9'}, {1: '0'}, {2: '3'}, {3: '4'}, {4: '2'}]
4. Using n (n is no. of correct values) I produce combinations of the above dict example as stated in comments
5. For every number I am checking the condition which satisfy the index:value append into temp and at last my new numbers become temp values. This iterates for all values until it arrives at the answer.

note: if n=0. i calculate all the combinations and delete the numbers from temp which satisfy that.

-
These kind of programming problems are designed so that if you have the right time complexity they will be solvable reasonably quickly in any language. As there are 16 digits, there are 10^16 values that can be tried in a brute force manner. I can't readily decipher your algorithm due to poor naming of variables and not being used to python. In any case you should change to another algorithm, which is not in the scope for this stackexchange site in my opinion. –  Emily L. Jun 13 '14 at 11:23

## 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 puzzle by generating all possible solutions first.

-
why i revent xrange as per this brute force the problem statement number is rangeing from 1015 to 1016. so i used that but ur rightbrute force doesnt scale. i am trying other ways.. –  sundar nataraj Сундар Jun 13 '14 at 11:42
@sundarnatarajСундар, range(10**15, 10**16)? –  otus Jun 13 '14 at 13:43

From an algorithm perspective I think the fastest way to solve this problem would be to treat each element as a statistically weighted possibility, add them up and then the ones with the highest chance will be your answer. For the example given:

90342 ;2 correct we have 2/5 correct, so each element has a 40% chance of being correct
70794 ;0 correct here we have 0/5, so each element has a 0% chance of being correct
39458 ;2 correct
34109 ;1 correct
51545 ;2 correct
12531 ;1 correct


if we only look at the digits with the highest chance of being correct we have:

# first element:

9 (.4)
7 (0)
3 (.4)
3 (.2)
5 (.4)
1 (.2)


Thus 3 has a 60% (.4 + .2 = .6) chance of being correct.

# second element:

0 (.4)
0 (0)
9 (.4)
4 (.2)
1 (.4)
2 (.2)


Here we see that 0 occurs twice, but one of the times it has a 0% chance of being correct so we can drop it as a possibility (which is nice because it had a 40% chance in the first guess). This leaves us with 9 and 1 as our two most likely answers.

Repeat this for every element and you will come to the answer that has the highest probability of being correct. Then just test it against all the guesses to see if it matches.

If it doesn't then just move on to your next most statistically viable guess. This method will drastically reduce the time complexity from brute forcing it.

-
Pretty! You can also get away with just counting the occurrence rate of each digit in the guesses. If the digit occurs more often than others it's statistically more likely to be the right answer. This easy approach works better the more digits you have. –  Emily L. Jun 13 '14 at 15:24

The general form of the problem as stated is NP-hard, since any 3SAT problem (i.e. http://en.wikipedia.org/wiki/Boolean_satisfiability_problem ) can be easily reduced to a problem of the stated form. Simply use one column per variable, have a line of all "2"'s with a score of zero, and one line for each predicate with a score of 3, using a three ones or zeroes for the variables of interest and twos everywhere else.

Although many problems of the stated form may be solved in reasonable times using a combination of heuristics and backtracking, such approaches are unlikely to be effective on a problem which was designed to be difficult. I'm not familiar enough with Project Euler to know how hard its problems are designed to be, but would not be surprised if a program which could small problem nearly instantaneously might be unable to solve the larger problem in less than a century.

To solve problems of this size, I think it will be necessary to draw more extended inferences by identifying rows whose numbers are related. Toward that end, I would suggest that the data format for your rows include the ability to specify a range of scores, and for each space within a row identify any combination of possible digits. I'd suggest probably using for each space a bit-coded integer. For example, if a column had a value of 18 (2+16--bits 1 and 4 set) that would indicate that that column should add 1 to the score if that digit was a one or a four. To see how this would work, suppose you were given the rows:

111111111111222 1
111111111111333 3


one could from those infer

1111111111111XXX 1
XXXXXXXXXXXXX333 2
XXXXXXXXXXXXX222 0
XXXXXXXXXXXXXqqq 1 [each q would be one of {01456789}]


If another line of the file was 1111111144444444 3

one could infer from that that since at most one of the first 8 digits could be correct, and at most one of the last 3 digits could be correct, at least one of the five digits between had to be a four.

XXXXXXXX44444XXX 1-3


If yet another line was

5555555544444666 2


one would then be able to infer that because at least one of the 4's was correct, at most one of the other numbers could be correct.

55555555XXXXX666 0-1


Allowing code to derive inferences like the above is likely to go a long way toward making these puzzles solvable. The tricky part is knowing when additional inferences are likely to be useful (and should be added to the list of constraints), and when they become redundant (and should be removed from the list of constraints so the code won't waste time with them anymore). Note that development of inferences goes far beyond checking off possibilities as inconsistent with constraints. Since the starting set of potential 16-bit numbers is humongous, building upon constraints is the only way to reduce the problem to manageable size.

-

Instead of recalling the range function for every iteration just call the range function once and save it outside of loop. This would allow you to store the list you are iterating over in memory instead.

this recalculates a list for you len(x)+1 times (redundantly):

temp=[]
for i in range(1,len(x)+1):
temp.extend(list(itertools.combinations(x,i)))


but if you find it once and save it to memory before running the for loop:

range_list = range(1,len(x)+1)
temp=[]
for i in range_list:
temp.extend(list(itertools.combinations(x,i)))


you can shave off some time by not recalculating something you already know.

Second, instead of first creating an empty list and populating with a loop you can use a single list comprehension:

replace this:

temp=[]
for i in range_list:
temp.extend(list(itertools.combinations(x,i)))


with this:

temp = [list(itertools.combinations(x,i)) for i in range_list]


I don't know if this will make a huge change but it should help a little, and it simplifies your code a bit.

-

This is in essence a Constraint Satisfaction Problem (CSP).

You're searching for a number $A=\sum_{i=0}^k a_i\cdot 10^i$ such that for each guess $G_j=\sum_{i=0}^k g_{j,i}\cdot 10^i$ you have a number of correct answers: $C_j=\sum_{i=0}^k\epsilon\left(a_i,g_{j,i}\right)$ where $\epsilon\left(x,y\right) = \left\{\begin{array}{l l} 1 & \quad \text{if x=b}\\0 & \quad \text{other wise}\end{array} \right.$.

Note that $a_i,g_{j,i} \in \mathbb{Z}$, $0 \le a_i,g_{j,i} \le 9 \quad \forall i,j$ for formality's sake.

Also let $\alpha_i=\left\{0,1,2,3,4,5,6,7,8,9\right\}$ initially be the set of values that $a_i$ can take.

Start off by looking at all guesses with zero correct digits: $J_0=\left\{j|C_j=0\right\}$ these tell us right away which numbers each $a_i$ can not be. So remove each $g_{j\in J_0,i}$ from $\alpha_i$ for all values of $i$.

Remove all guesses in $J_0$ from consideration and order the remaining guesses so that $C_{j-1} \le C_j$.

Start with $j=0$ and systematically choose $C_0$ values of $i$ such that $0\le i\le k$ and $g_{0,i}\in \alpha_i$, call this set of values of $i$ for $I_{0}$. Make an hypothesis that $g_{0,i}=a_i\quad \forall i \in I_{0}$.

Next, for all $j>0$, in order, perform the same steps as above and repeat hypothesis. I.e. pick a set of values of $i$, $I_j$ with the added condition that $I_{j}\cap I_{j-1}=\emptyset$ and $\forall\left\{i|i\in I_{j,m}\right\} g_{j,i}\in\alpha_i$. If this hypothesis holds, continue on with the next $j$; If the hypothesis doesn't hold, choose another set of $i$ and form a new previously untried $I_j$ and try again. If after all possible $I_j$ have been tried and no hypothesis holds, back track and try a new value for $I_{j-1}$ until you reach a hypothesis that holds for all $j$.

The above in essence implements a back tracking search for a solution but it will exit early for branches that have no possible solution.

-