CODEWITHSUNDEEP
algorithmcomputer-science
Anirudh
Anirudh

Reputation: 11

How to implement an algorithm for the given problem

I received a random brainteaser and wanted to approach it computationally. The problem is given here:

image

The usage of a brute force algorithm is ineffective, so I thought I could use a greedy algorithm. Can someone help me figure out heuristics for the problem and also a better solutions. Pleas keep it to the basics as I am new to the topic.

Upvotes: 1

Views: 105

Answers (2)

9mat
9mat

Reputation: 1234

Brute force with some bounds for this problem would be very fast (70 milliseconds). In the following code, I used the following bounds:

  • Instead of brute force 9! permutations, we can first try all the permutations for the first 3 digits (in the first two numbers)
  • The next 2 digits (the 3rd number), thus can be calculated since they are the first product. We can eliminate cases where the digits in the first result duplicate some digits in the first 3 digits, or the result has more than 2 digits
  • We then try all the permutations of 2 among the remaining 4 digits to form the 4th number, get the second result (the some of the 3rd and 4th number), and check if any digits are used more than once.

So in the worst case, we only need to try 9*8*7*4*3 = 6048 (9*8*7 from the 3-permutation in step 1, and 4*3 from the 2-permutation in step 3), not even mentioning the fact that many cases are eliminated in the 2nd step.

import itertools


def solve():
    digits = list(range(1,10))

    for a, b, c in itertools.permutations(digits, 3):
        res = (a*10+b)*c # third number

        if res > 100:  # third number uses more than 2 digits
            continue
        d, e = res//10, res%10 
        used = set([a,b,c,d,e])
        if len(used) < 5:  # duplicate digits
            continue
        left = set(digits).difference(used)
        for f, g in itertools.permutations(left, 2):
            res = d*10 + e + f*10 + g # final number
            h, k = res//10, res%10  
            if set([f,g,h,k]) == left:
                print("{}{}*{}={}{}".format(a,b,c,d,e))
                print("{}{}+{}{}={}{}".format(d,e,f,g,h,k))

import time
start = time.time()
solve()
print("Solve in {:.3}s".format(time.time()-start))

The solution is

17*4=68
68+25=93
Solve in 0.073s

Upvotes: 0

Shivam Jindal
Shivam Jindal

Reputation: 62

The usage of Brute-force is ineffective

Why do you think so? The complexity of a brute force is n!, where n is the number of boxes, in this case 9!

It would not take even a second for typical personal computers these days to compute it.

It would be ineffective if the number of boxes to be filled in would be very large something which has n! > 10^8 as 10^8 basic operations can be done by typical computers in a second.

You can do something like this in C++:

vector<int> perm = {1, 2, 3, 4,.., 9};
do {
  // use them to fill sequentially upto element perm[7]
  // and find value

  int compare = perm[7]*10 + perm[8];
  if(compare == value){
    // found solution
  }
} while(next_permutation(perm.begin(), perm.end());

Please follow this link here for more details on next_permutation: Link

Upvotes: 1

Related Questions