How to implement an algorithm for the given problem

Question

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

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.

Brute-force doesn't actually seem like a bad approach here. There are only 9! possible orderings of the numbers, which is totally doable. If you start scaling up the number of boxes this becomes more of a problem, though. — templatetypedef
– templatetypedef, Commented Apr 18, 2020 at 18:52
Each problem may have its conditions. For example the third box (the lonely one) can not be 9 otherwise the third row need 3 digits. Another problem (each letter one digit, no repititions),with other conditions is SEND + MORE = MONEY — Ripi2
– Ripi2, Commented Apr 18, 2020 at 19:16

Shivam Jindal · Accepted Answer · 2020-04-18 19:26:16Z

1

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

answered Apr 18, 2020 at 19:26

Shivam Jindal

625 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

9mat · Accepted Answer · 2020-04-18 19:34:58Z

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

Collectives™ on Stack Overflow

How to implement an algorithm for the given problem

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related