minizinc

How can I fold an array in MiniZinc?


The way that value of summands of cryptarithms are defined in MiniZinc tutorial look like follows:

constraint           1000 * S + 100 * E + 10 * N + D
                   + 1000 * M + 100 * O + 10 * R + E
       = 10000 * M + 1000 * O + 100 * N + 10 * E + Y;

This is probably OK for one example, but if I want to solve more cryptarithms, and writing sums like this looks rather tedious. Is there a way to compute the sum using a list of variables, say, via something like a fold? In Haskell, I would write this:

ghci> foldl (\x y -> 10 * x + y) 0 [1, 3, 4, 1, 5]
13415

I've looked in the docs and haven't found anything relevant so far


Solution

  • Here is the function I tend to use for connecting digits in an array (a) to a number (n) for a given (and fixed) base (base):

    % n = to_num_base(a, base)
    function var int: to_num_base(array[int] of var int: a, int: base) =
              let { int: len = card(index_set(a));
                    var int: n = sum(i in index_set(a)) (
                       pow(base, len-i) * a[i] 
                     );
             } in n
    ;
    
    % base 10
    function var int: to_num(array[int] of var int: a) = to_num_base(a, 10);
    

    Here's a simple test model (http://hakank.org/minizinc/to_num.mzn ):

    include "globals.mzn"; 
    
    int: m = 10;
    
    var 1..pow(10,m)-1: n;
    array[1..m] of var 0..9: x;
    
    solve satisfy;
    
    constraint
       n = to_num(x) /\
       all_different(x) /\
       x[3] = 4 /\
       n >= 50000 /\
       n mod 2 = 0
    ;
    
    output [
      "x: ", show(x), "\n",
      "n: ", show(n), "\n"
    ];
    

    For this specific problem, there are 22320 solutions. Here are some of them:

    x: [1, 3, 4, 6, 9, 8, 5, 2, 7, 0]
    n: 1346985270
    ----------
    x: [1, 3, 4, 7, 9, 8, 5, 2, 6, 0]
    n: 1347985260
    ----------
    x: [1, 3, 4, 6, 9, 7, 5, 2, 8, 0]
    n: 1346975280
    ----------
    x: [1, 3, 4, 8, 9, 7, 5, 2, 6, 0]
    n: 1348975260
    ----------
    ...
    x: [0, 7, 4, 1, 9, 3, 6, 8, 5, 2]
    n: 741936852
    ----------
    x: [0, 8, 4, 1, 9, 3, 6, 5, 7, 2]
    n: 841936572
    ----------
    x: [0, 8, 4, 1, 9, 5, 6, 3, 7, 2]
    n: 841956372
    ----------
    ...