Home > Algorithms, Linear programming, Programming, Uncategorized > Linear programming #1 – Project Euler 185

Linear programming #1 – Project Euler 185

I was recently faced with a very nice challenge from Project Euler – Problem 185. The idea is to find a number with a fixed number of digits by making guesses. Each time you are told how many digits you got right. By got right, I mean guessing the right digit on the right position. If you find a digit which is in the number, but on a different position, you don’t know…

There is a test case with 5 digits:

90342 ;2 correct
70794 ;0 correct
39458 ;2 correct
34109 ;1 correct
51545 ;2 correct
12531 ;1 correct

with unique solution 39542 and the difficult case with 16 digits

5616185650518293 ;2 correct
3847439647293047 ;1 correct
5855462940810587 ;3 correct
9742855507068353 ;3 correct
4296849643607543 ;3 correct
3174248439465858 ;1 correct
4513559094146117 ;2 correct
7890971548908067 ;3 correct
8157356344118483 ;1 correct
2615250744386899 ;2 correct
8690095851526254 ;3 correct
6375711915077050 ;1 correct
6913859173121360 ;1 correct
6442889055042768 ;2 correct
2321386104303845 ;0 correct
2326509471271448 ;2 correct
5251583379644322 ;2 correct
1748270476758276 ;3 correct
4895722652190306 ;1 correct
3041631117224635 ;3 correct
1841236454324589 ;3 correct
2659862637316867 ;2 correct

While the small case could be tackled using a pure brute force approach (only 10^5) cases to check, the second case becomes intractable. Looping through all 10^{16} cases would take ages. One could try genetic algorithms or other algorithms based on randomness. Recursive approaches are also possible.

There is however a way to express this problem which makes it solvable right away using a linear programming solver: that is an algorithm which finds valid solutions given some constraints. How do we find these constraints? There are essentially two types of constraints in our case:

  • each of the positions of the result contains one digit from 0 to 9
  • in each of the guesses given above we have a fixed number of correct digits

We can model this in the following way: we define a matrix of size (number of digits from 0 to 9) times (number of digits of the result). At position (i,j) in this matrix we have 1 if the position j of the result contains the digit i-1 and zero otherwise. For example, the matrix corresponding to the result in the case of the 5 digit guess sequence  39542 is

\displaystyle A = \begin{pmatrix}0 &0& 0& 0& 0\\ 0 &0& 0& 0& 0\\ 0 &0& 0& 0& 1\\ 1 &0& 0& 0& 0\\ 0 &0& 0& 1& 0\\ 0 &0& 1& 0& 0\\ 0 &0& 0& 0& 0\\ 0 &0& 0& 0& 0\\ 0 &0& 0& 0& 0\\ 0 &1& 0& 0& 0\\ \end{pmatrix}

Now, we can see clearer how can we impose the desired constraints. The fact that we have only one digit per position in the result is equivalent to the fact that on each column of the above matrix we have only one position equal to 1, or that the sum on the columns of the matrix A is 1. This gives us as many constraints as  digits in the solution. For example, the condition that in column 2 the sum is 1 can be written as

\displaystyle a_{1,2}+a_{2,2}+a_{3,2}+a_{4,2}+a_{5,2}+a_{6,2}+a_{7,2}+a_{8,2}+a_{9,2}+a_{10,2}=1

Now the conditions given by the current guesses are a bit different, but the idea is the same. For example the condition (90342 ;2 correct) can be translated to the following: in the set \{a_{10,1},a_{1,2},a_{4,3},a_{5,4},a_{3,5} \}  there are exactly 2 ones and three zeros. Therefore 

\displaystyle a_{10,1}+a_{1,2}+a_{4,3}+a_{5,4}+a_{3,5}= 2

Of course, this conditions can be found in an automatic way starting from the given guesses. This can be implemented in Matlab or Octave using linprog. If you have Yalmip installed then the setup is more straightforward, as illustrated in previous posts where I showed how to solve a Sudoku puzzle with Matlab or Two more mind games solved using Matlab.

  1. Jonah
    July 26, 2017 at 1:20 am

    Nice post Beni. A couple questions:
    1. What is the big-o complexity of solving a the series of equations?
    2. Can you provide any intuition behind why the brute force search space is so much larger? I can see that we’re “throwing out” the negative information with the brute force approach, as it were, but you wouldn’t guess it would be worth that much. I understand the matrix approach technically, but I can’t quite wrap my head around *why* the seemingly small amount of information we’re given turns out to narrow things down so much.

    • July 26, 2017 at 6:02 pm

      Hello and thank you for your comment.
      1. You ask what is the complexity for solving a series of equations, but what is done here is more: for the big case we have 22×16 unknowns (if I counted right) and only 22+16 equations. Normally this would give infinitely many solutions. The fact that we search solutions with values only equal to 0 or 1 greatly limits the set of solutions, which finally makes the solution unique. Unfortunately, I do not know what is the complexity of the algorithm. I will take a look at the references mentioned in the Matlab documentation.

      2. For the brute force approach, note that you have 16 positions with variable digits. For each position you have 10 possible variants. This gives you 10 ^ 16 possibilities. To imagine the magnitude of the calculation, run an empty for loop and time it. On regular computer you should be able to do a 10^8 loop in under a minute. Now, if 10^8 takes only one second, let’s say, then multiply this with 10^8 to get 10^8 seconds to reach 10^16. Now divide 10^8 seconds by 3600 to get the time in hours and by 24 to get the time in days. You’ll get 1157 days, which is a few years already.

      Hope this helps.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: