Difference between two products nearest to zero: non brute-force solution?

Question

In a science museum in Norway I came across the following mathematical game:

The goal is to place the 10 digits from 0 to 9 such that the difference between the two products is nearest to zero. (The 246 is the current lowest score).

Back home I wrote the following brute-force code:

import time
from itertools import permutations


def form_number(x, y, z, a, b):
    # not explicitly stated, but presume that leading zeroes are not allowed
    if x == 0 or a == 0:
        return 0
    return ((100 * x) + (10 * y) + z) * ((10 * a) + b)

def find_nearest_zero(*args):
    assert len(args) == 10
    return form_number(*args[:5]) - form_number(*args[5:])

if __name__ == '__main__':
    start = time.time()
    count = 0
    for p in permutations(range(10), 10):
        result = find_nearest_zero(*p)
        if result == 0:
            count += 1
            print '{}{}{} * {}{} = {n}'.format(*p[:5], n=form_number(*p[:5]))
            print '{}{}{} * {}{} = {n}'.format(*p[5:], n=form_number(*p[5:]))
            print
    print 'found {} solutions'.format(count)
    print time.time() - start

If we don't allow leading zeroes, then this prints 128 possible solutions in about 12 seconds.

But I'm left wondering, is there an algorithm or a better way to solve this in a non-brute force way?

Answer 1

If you assume there is a solution with difference 0, you can do via prime factors.

If ab - cd = 0, then the prime factors of ab and cd must be the same. You can start the search by going through all 3-digit primes (there are only 143) and see whether they have a multiple that only contains disjunctive digits. If this is the case you have your 2 three-digit numbers and only have to check the 2-digit ones.

If you don't find a solution, continue with the 2-digit primes and look for 2-or-3-digit multiples with disjunct digits. Then you only have to do the permutations for the remaining 2 numbers, which is a lot less.

Answer 2

This one assumes a difference of zero is possible (although it could be adapted to finding the minimum/s by sorting — thank you, m69, for that idea — each group of 120 permutations and using binary search, adding a factor of (log2 120) to the time complexity): hash the multiples for all 10 choose 5 * 5! combinations of three-digit times two-digit numbers, where the key is the sorted five-digit combination. Then if a reciprocal key (one that contains the other five digits) points to an equal multiple, output that match. Altogether 30,240 combinations are checked.

JavaScript code:

function choose(ns,r){
  var res = [];
  
  function _choose(i,_res){
    if (_res.length == r){
      res.push(_res);
      return;
      
    } else if (_res.length + ns.length - i == r){
      _res = _res.concat(ns.slice(i));
      res.push(_res);
      return
    }
    
    var temp = _res.slice();
    temp.push(ns[i]);
    
    _choose(i + 1,temp);
    _choose(i + 1,_res);
  }
  
  _choose(0,[]);
  return res;
}

function missingDigits(str){
  var res = "";

  for (var i=0; i<=9; i++){
    if (str.indexOf(i) === -1){
      res += i;
    }
  }
  
  return res;
}

var digitsHash = {};
    
function permute(digits){
  var stack = [[String(digits[0])]];
  
  for (var i=1; i<5; i++){
    var d = digits[i],
        perms = stack.shift(),
        _perms = [];
    
    for (var j=0; j<perms.length; j++){
      var temp = perms[j];
    
      for (var k=0; k<=perms[0].length; k++){
        if (d == 0 && (k == 0 || k == 3)){
          continue;
        }
        var _temp = temp;
        _temp = temp.split("");
        _temp.splice(k,0,d);
        _temp = _temp.join("")
        _perms.push(_temp);
      }
    }
    
    stack.push(_perms);
  }
  
  var reciprocalKey = missingDigits(stack[0][0]),
      key = stack[0][0].split("");

  key.sort();
  key = key.join("");

  digitsHash[key] = {};
  
  for (var i=0; i<stack[0].length; i++){
    var mult = Number(stack[0][i].substr(0,3)) * Number(stack[0][i].substr(3,2));
    
    digitsHash[key][mult] = stack[0][i];
    
    if (digitsHash[reciprocalKey] && digitsHash[reciprocalKey][mult]){
      console.log(stack[0][i].substr(0,3) + " * " + stack[0][i].substr(3,2)
        + ", " + digitsHash[reciprocalKey][mult].substr(0,3) + " * " 
        +  digitsHash[reciprocalKey][mult].substr(3,2));
    }
  }
}

var fives = choose([1,2,3,4,5,6,7,8,9,0],5);

for (var i=0; i<fives.length; i++){
  permute(fives[i]);
}

Answer 3

12 seconds is too much for my taste. My C++ brute force attack took ~430ms without any heuristics or deep optimizations. Anyway you need to add some heuristics for example:

Bitwidth of multiplication result is around the sum of bitwidth of the operands.

So you need to test only the same bit width combinations of the results. for example if a*b are like this:

1xx * 9x dec = 1 xxxx xxxx * 1001 xxxx bin -> 17 bit

so test only c*d combinations that lead to 17 bit results too for example

4xx * 2x dec = 100 xxxx xxxx * 10 xxxx bin -> 17 bit

to make it more clear:

dec  bin bits
 0  0000  0
 1  0001  1
 2  0010  2
 3  0011  2
 4  0100  3
 5  0101  3
 6  0110  3
 7  0111  3
 8  1000  4
 9  1001  4

If highest digit of a,b,c,d is a0,b0,c0,d0 then:

bits(a0)+bits(b0) = bits(c0)+bits(d0)

This will eliminate a lot of iterations. It is similar to subset sum problem. The speed up is from 2177280 iterations to 420480 iterations but also adds some overhead.

Answer 4

There are 126 ways to split 10 digits into 2 sets of 5 without duplicates. For each set of 5 digits, there are 120 ways (permutations) to arrange them into the form ab*cde, or 72 ways if the group contains zero and a leading zero is not allowed. That means a brute-force algorithm would need to check 126 × 120 × 72 = 1,088,640 possibilities.

However, for each pair of sets of 5 digits, if you generate the permutations in the order so that the resulting products are ordered from small to large, you can find the smallest difference of products in 120 + 72 = 192 steps (or fewer depending on how much the ranges overlap) instead of 120 × 72 = 8640. The maximum total becomes 24,192 instead of 1,088,640, which is 45 times less.
(In practice, only 12,574 product differences are calculated, and the first zero-difference result is found after 6679 steps).

You take the permutations with the smallest product for each set, calculate their difference, and store it if it is smaller than the minimum found so far. Then, you replace the permutation whose product is smallest by the next permutation in the list for that set (but stay on the same permutation for the other set) and calculate their difference, and so on, until you reach the end of one of the sets.

In the JavaScript code example below I'm using the product as the index of a sparse array (like a dictionary that can be read in order) to create an ordered list of permutations and their products (because I couldn't immediately find a simple way to generate them in order).

Array.prototype.remove = function() {      // returns first element of sparse array
    for (var key in this) {
        if (!this.hasOwnProperty(key)) return false;
        var value = this[key];
        delete this[key];
        return {prod: key, perm: value};
    }
}
function NorwegianMath() {
    var div = [1,1,1,1,1,0,0,0,0,0];          // which numbers 0-9 go in set 0 or 1
    var result, min = 99999;
    while (div[0]) {                    // keep zero in group 1 to avoid duplicates
        var set = [[],[0]];
        for (var i = 1; i < 10; i++) set[div[i]].push(i);   // distribute over sets
        var dict = [[],[]];
        for (var i = 0; i < 2; i++) {
            permute(set[i], dict[i]);         // generate permutations for each set
        }
        var x = dict[0].remove(), y = dict[1].remove();      // start with smallest
        while (x && y) {
            var diff = Math.abs(x.prod - y.prod);
            if (diff < min) {
                result = {x: x.perm, y: y.perm, d: diff};      // store new minimum
                /* if (diff == 0) return result */      // possible early exit here
                min = diff;
            }
            if (x.prod < y.prod) x = dict[0].remove();
            else y = dict[1].remove();    // replace smallest premutation with next
        }
        revLexi(div);                     // get next distribution into 2 sets of 5
    }
    return result;

    function permute(s, dict) {// there are better permutation algorithms out there
        for (var a = 0; a < 5; a++) {
            if (s[a] == 0) continue;
            for (var b = 0; b < 5; b++) {
                if (a == b) continue;
                for (var c = 0; c < 5; c++) {
                    if (a == c || b == c || s[c] == 0) continue;
                    for (var d = 0; d < 5; d++) {
                        if (a == d || b == d || c == d) continue;
                        for (var e = 0; e < 5; e++) {
                            if (a == e || b == e || c == e || d == e) continue;
                            var p = (s[a]*10 + s[b]) * (s[c]*100 + s[d]*10 + s[e]);
                            dict[p] = "" + s[a] + s[b] + "*" + s[c] + s[d] + s[e];
                        }
                    }
                }
            }
        }
    }
    function revLexi(seq) {       // next binary sequence (reverse lexicographical)
        var max = true, pos = seq.length, set = 1;
        while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false;
        if (pos < 0) return false;
        seq[pos] = 0;
        while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0;
        return true;
    }
}
var result = NorwegianMath();
document.write("|" + result.x + " - " + result.y + "| = " + result.d);